The definability tag has no wiki summary.
11
votes
1answer
260 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?
7
votes
1answer
217 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?
...
6
votes
1answer
403 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 ...
0
votes
1answer
136 views
Definability of arithmetic functions and relations
Motivation: Many "weak" arithmetic functions and/or relations ("relations" for short) are equivalent with relations explicitly definable by relations which were recursively defined by them beforehand ...
5
votes
1answer
200 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 ...
3
votes
1answer
139 views
Outer Definability of a Class
Definition: Let $C$ be a class of sets and $\mathcal{L}$ a first order relational language. We say $C$ is "outer definable" by $\mathcal{L}$ if there is a first order theory $T$ and for each $n_{R}$ - ...
2
votes
1answer
220 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 ...
10
votes
2answers
436 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 : ...
19
votes
1answer
741 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 ...
14
votes
1answer
209 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 ...
7
votes
1answer
237 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 ...
8
votes
3answers
188 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 ...
2
votes
3answers
358 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 ...
