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

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
Arno Fehm's user avatar
  • 1,989
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 ...
Dmytro Taranovsky's user avatar
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 ...
Guy Crouchback's user avatar
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 ...
Vladimir Kanovei's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Alexey Slizkov's user avatar
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. ...
tomasz's user avatar
  • 1,214
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 ...
user107952's user avatar
  • 2,063
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 ...
Ma Joad's user avatar
  • 1,611
2 votes
0 answers
127 views

Quantifierisation of maps

I will rewrite my question using Matt F. suggestion. Consider the logical structure $L = (\mathbb{R}, +, *, 1, 0, =)$ and a function $f:\mathbb{R}\to\mathbb{R}$. Consider the map $Q:2^\mathbb{R}→2^\...
A.Skutin's user avatar
  • 319
2 votes
0 answers
311 views

Can we have $\sf V=HTD$? How it relates to $\sf V=HOD$?

In my search for some type-set motivated line of thought that might prove axiom of choice, I was thinking of a concept that looks like $\sf V=HOD$, but in terms of types instead of ordinals, that is ...
Zuhair Al-Johar's user avatar
1 vote
0 answers
154 views

Can ordinal definability be defined using no more than one ordinal parameter?

This answer shows that one can indeed define ordinal definable this way: $\begin{align} \textbf{Define: } & \operatorname {OD} (X) \iff \\& \exists \theta \, \exists \varphi: X= \{y \in V_\...
Zuhair Al-Johar's user avatar
1 vote
0 answers
51 views

Can we define the notion of ordinal\cardinal definable set in Z + Ranks?

Working in Zermelo + Ranks, can we define the notions "ordinal definable" set, "cardinal definable" set? Or does it beg Replacement\Reflection to be defined?
Zuhair Al-Johar's user avatar
1 vote
0 answers
92 views

Is definability in $V$ in $\sf Ack+MK$ expressible in its language?

Recall Ackermann set theory. If we extend Ackermann's set theory by adding all axioms of $\sf MK$ to it. We shall denote the universe of all elements by $W$, while $V$ is the primitive constant symbol ...
Zuhair Al-Johar's user avatar