# Tag Info

### 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 ...
• 6,159
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 ...

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

• 10.3k
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$, ...
Accepted

• 44.7k
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 ...
• 1,989
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,639
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,216

### 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,074
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 ...
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,461 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 ... • 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,461 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) ... • 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\...
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$ ...