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 ...
Sidney Raffer's user avatar
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 ...
Joel David Hamkins's user avatar
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 ...
Joel David Hamkins's user avatar
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^...
Wojowu's user avatar
  • 27.4k
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)$ ...
Fedor Pakhomov's user avatar
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 ...
Rodrigo Freire's user avatar
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 ...
Thomas Scanlon's user avatar
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; \...
James Hanson's user avatar
  • 10.3k
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$, ...
Joel David Hamkins's user avatar
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 $\...
Arno Fehm's user avatar
  • 1,989
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 ...
Elliot Glazer's user avatar
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 ...
Joel David Hamkins's user avatar
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 $\...
Emil Jeřábek's user avatar
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 ...
Arno Fehm's user avatar
  • 1,989
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 ...
Erik Walsberg's user avatar
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)...
tomasz's user avatar
  • 1,216
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 ...
Gabriel Nivasch's user avatar
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 ...
Joel David Hamkins's user avatar
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 $\...
Fedor Pakhomov's user avatar
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-...
Joel David Hamkins's user avatar
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 ...
Joel David Hamkins's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Buchi Fan's user avatar
  • 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 .
Fedor Pakhomov's user avatar
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 ...
Joel David Hamkins's user avatar
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) ...
Ali Enayat's user avatar
  • 17.1k
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\...
Joel David Hamkins's user avatar
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$ ...
Joel David Hamkins's user avatar

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