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
67
questions
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?
- 309
1
vote
0
answers
143
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_\...
- 7,891
3
votes
1
answer
206
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{...
- 7,891
3
votes
1
answer
201
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:
$$\...
- 7,891
1
vote
1
answer
158
views
Can we state $\sf V=HOD$ using a single ordinal parameter(other than the formula code)?
$\sf V=HOD$ is stated as:
$\forall X \, \exists \theta \, \exists \alpha < \theta \, \exists \varphi : X=\{y \in V_\theta\mid V_\theta\models\varphi(y,\alpha)\}$
This use two ordinal parameters (...
- 7,891
3
votes
2
answers
241
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 $\...
- 7,891
12
votes
1
answer
528
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:
$...
- 7,891
0
votes
1
answer
134
views
How do these two principles of Foundation written in $\mathcal L_{\omega_1,\omega}$ compare?
This comes in continuation to posting titled "Can Foundation be captured for some $\mathcal L_{\omega_1, \omega}$ theories?".
Here, an attempt at a stronger notion of Foundation, yet ...
- 7,891
1
vote
1
answer
115
views
Can we have ZF + Definability + True Foundation + True Finiteness? Can it be Categorical?
Lets extend $\mathcal L_{\omega_1, \omega_1}$ with axioms of equality and of:
$\sf ZF + Definability+Ture$-$\sf Foundation+True$-$\sf Finiteness $
Where $\sf ZF$ is written, as usual, in $\mathcal L_{...
- 7,891
2
votes
1
answer
126
views
Does adding definability axiom expressed in infinitary language to ZF, let all models be pointwise definable?
This posting is generally related to a prior posting titled "Are all constructible from below sets parameter free definable?"
If we work in infinitary language $\mathcal L_{\omega_1, \omega}$...
- 7,891
3
votes
1
answer
467
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 ...
- 7,891
5
votes
2
answers
355
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 \...
- 491
-2
votes
1
answer
187
views
Does cardinal definable choice imply AC?
Recall the definition of cardinal definable sets, to re-iterate:
$Define: X \text { is cardinal definable} \iff \\\exists \text { cardinal } \kappa \, \exists \text { cardinals } \lambda_1,.., \...
- 7,891
2
votes
1
answer
151
views
Which fragment of ZF does the class of all hereditarily predicatively definable sets capture?
$\begin{align}x \text { is predicatively} &\text{ definable } \iff \exists x_1,..,x_n \exists \varphi:\\ & \rho(x_1) < \rho(x) ,.., \rho(x_n) < \rho(x) \ \land \\&\forall y \, (y \...
- 7,891
4
votes
1
answer
210
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 < ...
- 7,891
3
votes
1
answer
150
views
If a theory speaks of sets that cannot be forced to be parameter free definable, then does this entail a large cardinal property?
If we say that an effectively generated first order theory $\sf T$ extends $\sf ZF$, such that every countable model of $\sf T$ doesn't have a class forcing extension that is pointwise definable. ...
- 7,891
1
vote
1
answer
137
views
Is there a model of each of the following kinds of theories in the first transitive model of ZFC?
The question of whether the minimal transitive model $M$ of $\sf ZFC$ have a model of each consistent extension $\sf T$ of $\sf ZF$, is answered to the negative, basically because $M$ is countable and ...
- 7,891
1
vote
1
answer
81
views
Are externally pointwise definable models of ZFC subject to the same limitations of the internally pointwise definable ones?
By pointwise definable models, it's meant that every element of those models is definable after a formula in a parameter free manner, but that defining formula is in the language of that model, i.e., ...
- 7,891
7
votes
1
answer
436
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$ ...
- 2,023
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?
- 7,891
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) ...
- 216k
12
votes
3
answers
825
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)$, ...
- 216k
21
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 ...
- 1,558
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)...
- 216k
1
vote
0
answers
90
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 ...
- 7,891
6
votes
0
answers
235
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 ...
- 7,891
11
votes
1
answer
469
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 \\\...
- 7,891
1
vote
1
answer
192
views
Is every set being cardinal definable consistent with ZF?
$Define: X \text { is cardinal definable} \iff \\\exists \text { cardinal } \kappa \, \exists \text { cardinals } \lambda_1,.., \lambda_n <^\rho \kappa \ \exists \phi : \\ X=\{ y \in V_{\rho(\...
- 7,891
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^\...
- 309
0
votes
1
answer
117
views
An infinite Leibnizian structure in a finite language with precisely $n$ definable elements
This question was inspired by Joel David Hamkins's excellent question on Leibnizian structures with no definable elements. Let $n$ be a positive integer. Is there an infinite structure in a finite ...
- 2,023
10
votes
1
answer
372
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 ...
- 753
10
votes
0
answers
208
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 ...
- 1,969
2
votes
0
answers
306
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 ...
- 7,891
14
votes
2
answers
595
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 ...
- 2,281
4
votes
1
answer
276
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,471
8
votes
1
answer
243
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$-...
- 4,471
10
votes
1
answer
374
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 ...
- 4,471
10
votes
0
answers
306
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 ...
- 5,742
4
votes
0
answers
476
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 ...
- 2,023
5
votes
1
answer
362
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 ...
- 4,471
6
votes
1
answer
335
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 ...
- 479
9
votes
0
answers
317
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 ...
1
vote
1
answer
257
views
Does choice always hold in a model of ZF with point-wise parameter-free definable sets?
If one add to ZF the rule that all sets are parameter free definable. Would that prove the axiom of choice?
More specifically. IF we add the following omega rule to inference rules of the language of ...
- 7,891
10
votes
2
answers
447
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 ...
- 101
8
votes
1
answer
718
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, ...
- 1,499
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.
...
- 1,132
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 ...
- 1,469
1
vote
1
answer
213
views
In NBG (ZFC + classes) if $P$ nonempty predicate of classes must $P$ have definable solution?
Let $A, B, C..X, Y$ range over potentially proper classes in NBG set theory (or adding class quantification to ZFC in obvious way) and $x,y,z$ range over sets.
Since I don't know the proper symbols ...
- 2,419
6
votes
1
answer
430
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 ...
- 764
8
votes
1
answer
512
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 ...
- 216k