35
votes

### Define $\mathbb{N}$ in the ring $\mathbb{Z}$ without Lagrange's theorem

Raphael Robinson, in a paper entitled Arithmetical Definitions in the Ring of Integers, gives a definition of $\mathbb{N}$ in $\mathbb{Z}$ using only two existential quantifiers. He does not use ...

25
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 ...

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 ...

23
votes

Accepted

### Define $\mathbb{N}$ in the ring $\mathbb{Z}$ without Lagrange's theorem

Here is an outline of a possible approach. We will show in a simple way that every natural number is a ratio of two sums of four squares, so that formula $\exists a_1,\dots,a_8:(a_1^2+a_2^2+a_3^2+a_4^...

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)$ ...

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 ...

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 ...

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; \...

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$, ...

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 $\...

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 ...

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 ...

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 $\...

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 ...

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 ...

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)...

8
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 ...

8
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 ...

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 $\...

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-...

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 ...

7
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 ...

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 ...

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 .

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 ...

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) ...

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\...

6
votes

Accepted

### Does V=HOD prove all kinds of consistent universal hereditary definability?

The answer is no. Indeed, one can rarely move from consistency to truth in this way.
For a counterexample, let $Q(v)$ be the property "CH holds and $v$ is an ordinal."
If CH holds, then $Q$ ...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

definability × 71lo.logic × 61

set-theory × 41

model-theory × 30

axiom-of-choice × 5

ordinal-numbers × 5

large-cardinals × 4

fields × 4

constructibility × 4

theories-of-arithmetic × 4

infinitary-logic × 4

nt.number-theory × 3

foundations × 3

axioms × 3

computability-theory × 2

order-theory × 2

nonstandard-analysis × 2

reference-request × 1

gr.group-theory × 1

ac.commutative-algebra × 1

graph-theory × 1

ra.rings-and-algebras × 1

soft-question × 1

algebraic-number-theory × 1

arithmetic-geometry × 1