The definability tag has no wiki summary.

**0**

votes

**1**answer

103 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

182 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

137 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

216 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

418 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

718 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

199 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

229 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

**3**answers

172 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

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