The definability tag has no usage guidance.

**12**

votes

**1**answer

403 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

**1**answer

242 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?
...

**7**

votes

**1**answer

419 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

**1**answer

149 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

**1**answer

206 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

**1**answer

141 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

**1**answer

223 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

**2**answers

449 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

**1**answer

760 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

**1**answer

212 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

**1**answer

245 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 ...

**9**

votes

**3**answers

203 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

**3**answers

377 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 ...