26
votes
Accepted
Is multiplication implicitly definable from successor?
Contrary to my initial expectation, the answer is Yes.
This answer is based on the idea of Clemens Grabmayer, which makes the observation that addition $+$ is definable from multiplication $\cdot$ and ...
- 236k
25
votes
Non-definability of graph 3-colorability in first-order logic
Here is one way to do it.
2-colorability case. First let's warm up with the 2-colorability case. Notice that odd-length cycles are not 2-colorable, since the colors have to alternate as you go around ...
- 236k
21
votes
Accepted
Is the set of primes implicitly definable from successor?
The set of primes is not implicitly definable in $(\mathbb{N},S)$. This is immediately implied by following:
Theorem. A unary predicate $P$ on $\mathbb{N}$ is implicitly definable in $(\mathbb{N},S)$ ...
- 5,821
18
votes
Is the theory of a partial order bi-interpretable with the theory of a pre-order?
They are not one dimensional bi-interpretable. The pre-order on $\{a,b,c,d\}$ given by $a\equiv b$ and $c\equiv d$ (and $a, b$ not related to $c, d$) is homogeneous in the sense that for any ...
- 2,467
15
votes
Definability of Gödel's pairing function on ordinals
For your first question, it's not hard to show with a back-and-forth argument that for any uncountable cardinal $\kappa$, the structure $\left<\kappa; \in\right>$ has $\left<\omega^\omega; \...
- 12.4k
15
votes
Definability of the ring of integer in algebraic extensions of $\mathbb Q$
If $K$ is a finite extension of $\mathbb{Q}$, then, yes, $\mathbb{Z}$ is definable in $\langle K, +, \times, 0, 1 \rangle$. See R. Rumely, Undecidability and definability for the theory of global ...
- 2,971
15
votes
Accepted
Can $L$ be defined without parameters?
Yes, the parameter-free version of $L$ gives rise to the same constructible universe $L$. You will still get all of $L$ this way, but it will come more slowly.
The reason is that at stage $\alpha+1$, ...
- 236k
12
votes
Accepted
Is $\mathbb{Z}$ universally definable in any number fields other than $\mathbb{Q}$?
Koenigsmann's result was generlized by Jennifer Park to number fields, giving a universal definition of the ring of integers $\mathcal{O}_K$ in $K$. Then there is a series of results proving that $\...
- 2,051
12
votes
Accepted
Is every set being cardinal definable consistent with ZF + negation of Choice?
This is consistent. Kanovei constructed a model $M$ with an infinite Dedekind finite set of reals which is lightface projectively definable. By descending to $L(R),$ we can further assume it satisfies ...
- 4,316
12
votes
Is factorial definable using a $\Delta_0$ formula?
I didn't look at the above references, and I took this as an exercise for myself.
Here is a way to express "$x! = y$" as a $\Delta_0$ formula with two free variables $x$ and $y$.
The idea is to ...
- 1,174
11
votes
Accepted
Are no infinite subsets of the set of all propositional atoms definable in this structure, even with parameters?
It's a nice question. This Boolean algebra, known as the Lindenbaum algebra, is a countable atomless Boolean algebra — it is atomless because we can always take the conjunction of any formula with a ...
- 236k
11
votes
Definability of Gödel's pairing function on ordinals
For $\langle\kappa,{\in}\rangle$, James Hanson has already answered the question as stated. However, let me mention a generalization: it’s not just Gödel’s pairing function that’s not definable in $\...
- 47.1k
11
votes
Accepted
Complexity of definable global choice functions
There is no such phenomenom for $n\geq 2$.
The reason is that if a model of ZFC has a definable choice function, of any complexity, then it actually has one of complexity $\Delta_2$. This is because ...
- 236k
10
votes
Accepted
What is the lowest complexity definition of $\mathbb{Z}$ in an infinite extension of $\mathbb{Q}$
There is an existential definition of $\mathbb{Z}$ in the rational function field $\mathbb{R}(t)$ by a beautiful result of Denef using elliptic curves (Proposition 2 of The diophantine problem for ...
- 2,051
10
votes
Accepted
Why include $0$ and $1$ in the signature of Presburger arithmetic?
It is the same in Peano arithmetic, where the standard language is $\{+,\cdot,0,1,<\}$ for the standard model $\langle\mathbb{N},+,\cdot,0,1,<\rangle$, even though $0$, $1$, and $<$ are ...
- 236k
9
votes
Accepted
Is there a complete characterization of ordered fields without definable proper subfields?
This is an interesting question. We know some things about this, but we do not have a characterization of fields with this property. As Wojowu says above the restriction to countable fields doesn't ...
- 1,689
8
votes
Accepted
Are the definable hyper-reals, using quantifiers only over the standard reals and natural numbers, the same as the algebraic numbers?
$\newcommand{\st}{\textrm{st}}\newcommand{\bR}{{\bf R}}\newcommand{\bN}{{\bf N}}$
I think the limit of any definable convergent sequence $(a_n)$ (including $e$) is definable by the formula
$$\varphi(x)...
- 1,338
8
votes
Accepted
Can we have ZF + Definability + True Foundation + True Finiteness? Can it be Categorical?
The models of your theory are exactly the pointwise-definable (with respect to $\mathcal{L}_{\omega,\omega}$ as usual) well-founded models of $\mathsf{ZF}$; incidentally, your true finiteness axiom is ...
- 21.1k
7
votes
Is there a simple instance of intransitivity for implicit definability?
Here is an example with a relatively simple and elementary proof.
Lets say that a set $A$ of natural numbers is universal if for any natural $n$ and a set $a\subseteq n$ there exists $m$ such that $\...
- 5,821
7
votes
Accepted
Is ordinal definability in terms of stages of cumulative size hierarchy equivalent to the usual one?
The answer is yes, in a very general way.
What I claim, first, is that the Lévy-Montague reflection theorem holds in ZF for any definable continuous cumulative hierarchical representation of the set-...
- 236k
7
votes
Accepted
Are all constructible from below sets parameter free definable?
There are two issues with your question.
First, your statement "in other words" is not correct, since there are theories whose models have the property that whenever a statement holds of ...
- 236k
7
votes
Accepted
Natural functions outside $\sf PA$?
Sure, but this is really a fact about structures rather than theories. For example, $\mathsf{ZFC}$ can define the function sending $n$ to the least natural number not definable in the language of ...
- 21.1k
6
votes
Accepted
Is every set being cardinal definable consistent with ZF?
Yes, assuming ZF is consistent it is, because it follows from ZFC + V=HOD. This is because the ordertype of the class of (ordinal-)cardinals is just that of the ordinals. That is, if $X$ is definable ...
- 9,902
6
votes
Accepted
Definability of ordinals in various signatures
I do not have enough reputation to add a comment. The following paper may be useful for you. It contains results extending the work of Tarski, Mostowski, and Doner, as well as some very nice ...
- 126
6
votes
Is there a simple instance of intransitivity for implicit definability?
Indeed, the set of primes is not implicitly definable over $(\mathbb{N},S)$. I gave a proof of this in an answer to the question of Geoffrey Irving. See https://mathoverflow.net/a/426382/36385 .
- 5,821
6
votes
Accepted
Terminology for ordinals whose constructible level is the least one satisfying some formula
Let me say first that your concept is similar in spirit to the notion of sententially categorical cardinal appearing in my joint paper
J. D. Hamkins and R. Solberg, Categorical large cardinals and ...
- 236k
6
votes
Accepted
Is every countable model of ZFC a subset of some parameter free definable pointwise-definable model of ZFC?
The answer is in the positive. Since by the completeness theorem the existence of a countable model of ZFC is equivalent to Con(ZFC), the argument below works with the assumption that ZFC + Con(ZFC) ...
- 17.7k
6
votes
Accepted
Can we state $\sf V=HOD$ using a single ordinal parameter(other than the formula code)?
Yes, because there is a definable ordinal pairing function.
Specifically, if you want to get the set $\{y\in V_\theta\mid V_\theta\models\varphi(y,\alpha)\}$, then let $\beta=\langle\theta,\alpha\...
- 236k
Only top scored, non community-wiki answers of a minimum length are eligible