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
75 questions
4
votes
0
answers
129
views
Ziegler spectrum of group rings
I am interested in the Ziegler spectrum of $\mathcal{A}=\mathrm{Mod}\text{-}kG$, the category of $kG$-modules, for $G$ a finite group and $k$ a field of characteristic $p$ dividing the order of the ...
- 1,017
2
votes
0
answers
69
views
Necessity of the closedness assumption in the definition of (definable) Whitney stratification
In, the paper Geometric categories and o-minimal structures by Van Den Dries and Miller, the definition of a Whitney stratification of a function is given for a function $f: A \rightarrow \mathbb{R}^n$...
- 125
1
vote
1
answer
243
views
Natural functions outside $\sf PA$?
Can theories stronger than $\sf PA$ manage to define functions from the naturals to the naturals, that $\sf PA$ cannot? If so, what are examples of those functions?
- 13.5k
9
votes
1
answer
412
views
Complexity of definable global choice functions
It is well-known that $L$ has a $\Sigma_{1}$-definable global choice function; it is also known that there are other transitive class models of ZFC with this property.
I wonder about the complexity ...
- 93
2
votes
1
answer
267
views
Definability in pure-second order logic
Are the universe and the empty set the only definable sets without parameters in the language of pure second-order logic? TIA
5
votes
0
answers
275
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 ...
7
votes
1
answer
450
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 ...
- 1,984
20
votes
2
answers
2k
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
196
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_\...
- 13.5k
4
votes
1
answer
360
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{...
- 13.5k
3
votes
1
answer
343
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:
$$\...
- 13.5k
1
vote
1
answer
260
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 (...
- 13.5k
3
votes
2
answers
348
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 $\...
- 13.5k
14
votes
1
answer
852
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:
$...
- 13.5k
0
votes
1
answer
191
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 ...
- 13.5k