Questions tagged [definability]
definability by formulas in first-order logic, e.g. as explained at https://en.wikipedia.org/wiki/Definable_set, or as in J. Robinson's first-order definition of the integers in the field of rationals
70
questions
44
votes
2
answers
4k
views
Is multiplication implicitly definable from successor?
A relation $R$ is implicitly definable in a structure $M$ if there is a formula $\varphi(\dot R)$ in the first-order language of $M$ expanded to include relation $R$, such that $M\models\varphi(\dot R)...
33
votes
0
answers
2k
views
Defining $\mathbb{Z}$ in $\mathbb{Q}$
It was proved by Poonen that $\mathbb{Z}$ is definable in the structure $(\mathbb{Q}, +, \cdot, 0, 1)$ using $\forall \exists$ formula. Koenigsmann has shown that $\mathbb{Z}$ is in fact definable by ...
30
votes
2
answers
1k
views
Define $\mathbb{N}$ in the ring $\mathbb{Z}$ without Lagrange's theorem
It is well-known that the set of nonnegative integers $\mathbb{N}$ is definable in the ring of integers $\mathbb{Z}$. Indeed, by Lagrange's four squares theorem we have $\mathbb{N} = \{n \in \mathbb{Z}...
22
votes
1
answer
1k
views
Is the set of primes implicitly definable from successor?
An earlier question by Joel David Hamkins asked whether multiplication is implicitly definable in the structure $(\mathbb{N},S)$ of the naturals with successor. Here $R$ is implicitly definable if ...
21
votes
1
answer
1k
views
Is there a subset of the natural number plane, which doesn't know which of its slices are arithmetic?
$\newcommand{\N}{\mathbb{N}}$My question, more precisely, is:
Question. Is there a set $B\subset \N\times\N$, such that the set of indices where it is arithmetically definable, that is, $\{ n\in\N \...
20
votes
2
answers
1k
views
Non-definability of graph 3-colorability in first-order logic
What is a proof that graph 3-colorability is not definable in first order logic? Where did it first appear?
19
votes
1
answer
1k
views
Is the theory of a partial order bi-interpretable with the theory of a pre-order?
A partial order relation $\leq$ on a set $A$ is a binary relation that is reflexive, transitive, and antisymmetric.
A preorder relation $\unlhd$ (also sometimes known as a quasi order or pseudo order) ...
16
votes
2
answers
1k
views
Is factorial definable using a $\Delta_0$ formula?
The factorial function is primitive recursive, and therefore definable by a $\Sigma_1$ formula.
Is it also definable by a $\Delta_0$ formula (i.e. bounded quantifiers)?
If not, why?
14
votes
2
answers
624
views
Definability of Gödel's pairing function on ordinals
Given an infinite cardinal $\kappa$, Gödel's function is a well-known bijection $p:\kappa^2\to\kappa$.
Is $p$ definable in the structure $\langle\kappa;\in\rangle$?
Is $p$ definable in a bigger 2nd ...
14
votes
1
answer
287
views
Existence property for ordered fields
A theory $T$ has the existence property (EP) if the following holds:
Let $\phi(x)$ be a formula with one free variable (and no parameters) such that $T \vdash (\exists x) \phi(x)$. Then there is ...
13
votes
1
answer
592
views
Can $L$ be defined without parameters?
If we omit parameters in the definition of $L$ would the result still be $L$?
That is, we define a successor stage $L_{\alpha+1}$ in the constructible universe $L$, without including parameters; as:
$...
12
votes
3
answers
848
views
Is there a simple instance of intransitivity for implicit definability?
This question continues the theme of some recent questions on implicit definability.
A relation $R$ is implicitly definable in a first-order structure $M$ if there is a property $\varphi(\dot R)$, ...
12
votes
2
answers
699
views
Ways to define "definability"
The notion of a definable set is not expressible in the language of set theory: there is no formula $\delta(x)$ that is equivalent with there being a formula $\phi(y)$ such that $x = \lbrace y : \phi(...
11
votes
1
answer
498
views
Is every set being cardinal definable consistent with ZF + negation of Choice?
Recall the definition of cardinal definable, where every set being cardinal definable is proved consistent relative to ZF + V=HOD. To re-iterate it:
$Define: X \text { is cardinal definable} \iff \\\...
10
votes
2
answers
468
views
Definability of the ring of integer in algebraic extensions of $\mathbb Q$
J. Robinson has proved that exists a formula $\psi(x)$ in the language of rings which,applied to the rational numbers, defines the the ring integers (making the theory of $\mathbb{Q}$ undecidable, due ...
10
votes
1
answer
391
views
Is $\mathbb{Z}$ universally definable in any number fields other than $\mathbb{Q}$?
In 2009, Jochen Koenigsmann showed that $\mathbb{Z}$ is universally definable in the field $\mathbb{Q}$. My question is, are there any other number fields in which $\mathbb{Z}$ is universally ...
10
votes
1
answer
448
views
Definable constructions in o-minimal geometry
Recently I've been working with o-minimal expansions of $(\mathbb{R},\times,+)$, and I want to work "internally" to the language of o-minimal sets instead of working with "definable ...
10
votes
0
answers
211
views
Are the nonnegative rationals diophantine with only two quantifiers?
Definition: A subset $D\subseteq \mathbb{Q}$ is diophantine if it is the projection of the zero set of a polynomial, i.e. there exists a polynomial $f\in\mathbb{Q}[X,Y_1,\dots,Y_n]$ for some $n$ such ...
10
votes
0
answers
316
views
Definability up to isomorphism versus definability of an isomorphic copy
Question: Is it provable in ZFC that every structure that is ordinal definable up to isomorphism has an ordinal definable isomorphic copy? If not, what are some counterexamples? All structures are ...
9
votes
3
answers
385
views
What ordinals are definable relations in Peano Arithmetic?
I am not asking which order types PA proves are well ordered. That would be all up to $\epsilon_0$. Rather I mean, assuming a stronger ambient theory such as Zermelo set theory, which ordinals have ...
9
votes
0
answers
320
views
Is there a definable model of PA whose domain is a proper class and whose complete theory is not definable?
Assume ZFC. Is there a formula of $\mathcal{L}_\in$ (without parameters) defining a model $\mathcal{M}$ of PA whose domain is a proper class but the complete theory of that model is not definable by ...
8
votes
1
answer
246
views
What is the lowest complexity definition of $\mathbb{Z}$ in an infinite extension of $\mathbb{Q}$
In 2009, Jochen Koenigsmann showed that $\mathbb{Z}$ is universally definable in the field $\mathbb{Q}$. And in 2012, Jennifer Park proved a result which implies that $\mathbb{Z}$ is $\exists\forall$-...
8
votes
1
answer
390
views
Are there known ways to posit definable global choice in ZF without positing V=L?
I need a global choice function defined by a formula in (a fragment of) ZF. There is no harm in assuming V=L for my purposes. But I wonder if there are any familiar alternative ways to get this?
...
8
votes
1
answer
521
views
Are the definable hyper-reals, using quantifiers only over the standard reals and natural numbers, the same as the algebraic numbers?
This question arose today at Yevgeny Gordon's talk, "Will nonstandard analysis be
the analysis of the future?" at the CUNY Logic
Workshop. Here is my way of asking it.
Consider the ordered real field ...
8
votes
1
answer
723
views
Non-normal numbers definable without parameters in the langauge of differential rings with composition
Background: It is currently unknown whether $e$ is normal. A natural way to approach this question is to find a class to which $e$ belongs, and prove all members of that class are normal. For example, ...
8
votes
1
answer
350
views
Iterating definability
An odd -- probably basic -- question about model theory:
For $\mathcal{M}$ a structure in a (first-order) signature $\Sigma$, let $\mathcal{M}'$ be the structure in signature $\Sigma\sqcup\lbrace U\...
8
votes
0
answers
349
views
Cohen's model yet again
It has been discussed already whether a countable OD set necessarily contains an OD element. See e.g.
A question about ordinal definable real numbers
.
A negative answer was obtained in Archive for ...
7
votes
1
answer
444
views
Are no infinite subsets of the set of all propositional atoms definable in this structure, even with parameters?
I asked this on Math Stack Exchange, but apparently no one paid attention to it. So, I am asking it again, filling in the background necessary to understand it.
Consider a countably infinite set $P$ ...
6
votes
2
answers
468
views
Reconstructing a model from its definable sets
Let $\mathcal{M}$ be an infinite model of a first-order language, and for each $n$, let $\mathcal{B}_n$ be the algebra of definable sets of $n$-tuples from $|\mathcal{M}|$.
Given $\{\mathcal{B}_n\mid ...
6
votes
1
answer
727
views
Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?
This question arises from an issue arising in user38200's recent question concerning models of set theory in which every definable set has a definable element. In my answer to that question, with ...
6
votes
1
answer
358
views
Definability of ordinals in various signatures
Recently, I've been studying what the definable subsets of the countable ordinals "look like" from the perspective of bare-bones first order logic (not set theory) equipped with various ways ...
6
votes
1
answer
455
views
Problem with definability in the constructible hierarchy
This is a rather technical question. I cannot find my mistake in a proof of the (obviously wrong) following sentence: Every countable ordinal is $\Sigma_2$-definable in $J_{\omega_1 + 1}$ by a formula ...
6
votes
1
answer
286
views
Ordinal definable sets of reals in the Solovay
To be precise, let $\Omega$ be an inaccessible cardinal in $L$ and let N be the Solovay model defined by the Levy-collapse in this case. Then $\Omega$ is $\aleph_1$ in $N$.
How many different OD (=...
6
votes
0
answers
249
views
Can HCD accommodate all known large cardinal axioms?
HOD has been found to be useful in that it is an inner model that can accommodate essentially all known large cardinals.
However, there is a definable well ordering over HOD, so it cannot satisfy ...
5
votes
1
answer
399
views
Is there a complete characterization of ordered fields without definable proper subfields?
$\mathbb{Q}$ has no proper subfields. As a result, all ordered fields elementarily equivalent to $\mathbb{Q}$ have no proper subfields which are first-order definable without parameters. And by the ...
5
votes
1
answer
245
views
Why include $0$ and $1$ in the signature of Presburger arithmetic?
I recently became interested in some problems concerning decidability of extensions of Presburger arithmetic. However, being a number-theorist rather than a logician, I am confused by some notational ...
5
votes
2
answers
367
views
Terminology for ordinals whose constructible level is the least one satisfying some formula
An ordinal $\alpha$ is "meta-definable" by some formula $\varphi$ without free variables if:
$$
\begin{cases}
L_\alpha \models\varphi \\
\forall\beta < \alpha \, L_\beta \not\models \...
5
votes
0
answers
143
views
Higher-order equivalence of ordinals
I wonder which ordinals are second-order equivalent, and similarly for other logical equivalences. Let the signature be fixed and include only <. For concreteness, let us first ask for the first ...
5
votes
0
answers
140
views
Self-additive posets
We say that a partially ordered set $(P,<)$ is self-additive if the two natural embeddings of $P$ in $P\oplus P$ (the linear sum of $P$ and itself) are elementary.
We have the following.
...
4
votes
3
answers
1k
views
Methods for proving non FO definability
I'm having difficulties to prove that the subset of even numbers is not first-order definable in $(\mathbb{N},<)$. Any hint is welcomed!
More generally, what are usual techniques in order to prove ...
4
votes
1
answer
232
views
Is ordinal definability in terms of stages of cumulative size hierarchy equivalent to the usual one?
Working in $\sf ZF$
Define: $W_0 = \emptyset \\ W_{\alpha+1} = H_{\leq |W_\alpha|} =\{x \mid \forall y: y \in \operatorname {trcl} (\{x\}) \ |y| \leq |W_\alpha| \} \\ W_\lambda= \bigcup W_{\alpha < ...
4
votes
1
answer
280
views
What is the lowest complexity definition of $\mathbb{Z}$ in an infinite algebraic extension of $\mathbb{Q}$?
In 2009, Jochen Koenigsmann showed that $\mathbb{Z}$ is universally definable in the field $\mathbb{Q}$. And in 2012, Jennifer Park proved a result which implies that $\mathbb{Z}$ is $\exists\forall$-...
4
votes
0
answers
523
views
A question regarding the "math tea" argument
Joel David Hamkins published a paper where he analyzes the "math tea" argument, namely, the argument that some real numbers are undefinable. He constructed a countable model of set theory ...
4
votes
0
answers
48
views
Closed and bounded intervals of definably complete ordered groups
True or false?
All closed and bounded intervals of definably complete
ordered groups are definably compact.
Let $G$ be an ordered abelian group. Then, a definable subset $D ⊆ G$ is said to be ...
3
votes
2
answers
258
views
Is every countable model of ZFC a subset of some parameter free definable pointwise-definable model of ZFC?
Is it consistent with $\sf ZFC + \text{ countable models of } ZFC \text { exist}$, that every countable model of $\sf ZFC$ is a subset of some parameter free definable pointwise-definable model of $\...
3
votes
1
answer
494
views
Are all constructible from below sets parameter free definable?
Lets take the intersection of the theory of $L_{\omega_1^{CK}}$ and $\sf ZF + [V=L]$, this is equivalent to the theory of constructability from below + limit stages.
Can this theory prove the ...
3
votes
1
answer
243
views
Is ZF + Def a conservative extension of ZFC+HOD? If not, what are counter-examples?
$\sf ZF + Def$ is the theory that extends $\mathcal L(=,\in)_{\omega_1,\omega}$ with axioms of $\sf ZF$ (written in $\mathcal L(=,\in)_{\omega, \omega}$) and the axiom of definability:-
$\textbf{...
3
votes
1
answer
225
views
Does V=HOD prove all kinds of consistent universal hereditary definability?
Is the following a theorem of $\sf ZF+[V=HOD]$?
If $Q$ is a property definable in a parameter free manner, then: $$\operatorname {Con}(\sf ZF + [V=HQD]) \implies V=HQD$$
where $\sf V=HQD$ means:
$$\...
3
votes
2
answers
235
views
What are the minimal requirements for the definable hyperreal field plus transfer?
It is interesting that to prove the transfer principle for the definable hyperreal field, one requires no more choice than for proving, for instance, the countable additivity of the Lebesgue measure. ...
3
votes
1
answer
299
views
$(\kappa,\lambda)$ - Minimal Models & Stronger Version of Rowbottom's Theorem
Definition 1: Let $M$ be a $\mathcal{L}$ - structure and $A\subseteq Dom(M)$. Define:
$Def_{A}(M):=\{X\subseteq Dom(M)~|~\exists n\in \omega~~\exists \varphi (x,y_1,...,y_n)\in \mathcal{L}-Form~~\...