# Questions tagged [definability]

The definability tag has no usage guidance.

24
questions

**1**

vote

**1**answer

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

**9**

votes

**1**answer

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

**8**

votes

**1**answer

234 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, ...

**5**

votes

**0**answers

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

**4**

votes

**0**answers

39 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**

vote

**1**answer

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

**6**

votes

**1**answer

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

**8**

votes

**1**answer

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

**30**

votes

**2**answers

1k views

### Define $\mathbb{N}$ in the ring $\mathbb{Z}$ without Lagrange's theorem

It is well-known that the set of nonnegative integers $\mathbb{N}$ is definable in the ring of integers $\mathbb{Z}$. Indeed, by Lagrange's four squares theorem we have $\mathbb{N} = \{n \in \mathbb{Z}...

**8**

votes

**0**answers

328 views

### Cohen's model yet again

It has been discussed already whether a countable OD set necessarily contains an OD element. See e.g.
A question about ordinal definable real numbers
.
A negative answer was obtained in Archive for ...

**3**

votes

**2**answers

190 views

### What are the minimal requirements for the definable hyperreal field plus transfer?

It is interesting that to prove the transfer principle for the definable hyperreal field, one requires no more choice than for proving, for instance, the countable additivity of the Lebesgue measure. ...

**15**

votes

**2**answers

842 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?

**8**

votes

**1**answer

344 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

585 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

227 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 (...

**6**

votes

**1**answer

252 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

158 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

276 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 \mathcal{L}-Form~~\...

**10**

votes

**2**answers

564 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 : \phi(...

**20**

votes

**1**answer

872 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

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

**8**

votes

**1**answer

285 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 U\...

**9**

votes

**3**answers

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

**3**

votes

**3**answers

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