Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does there exist a first-order set-theoretic formula $\phi(x)$ using only bounded quantifiers such that, in ZF without assuming the Axiom of Foundation/Regularity, $\phi(x)$ is true if & only if $x$ is (the von Neumann construction of) a natural number? The only predicates for defining the naturals that I can find are variations on $\phi(x) := \forall I(\emptyset\in I \land (\forall y\in I)(y\cup\{y\}\in I) \to x\in I)$ (which isn't bounded) and $\phi(x) := x=\emptyset \lor ((\exists k\in x)(k\cup\{k\}=x) \land (\forall y\in x)(y=\emptyset \lor (\exists k\in x)(k\cup\{k\}=y)))$ (which needs not be satisfied by only the naturals in non-well-founded theories; e.g., the Quine atom satisfies this predicate).

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

I don't think this is possible, for the following reason:

The characteristic property of a formula with bounded quantification $\phi(x)$ is that the truth of $\phi(x)$ for some $x$ in a model $M$ depends only on how the membership relation behaves on the transitive closure of $x$, not on what is in the rest of the model.

Therefore, if we can find two models $M$ and $N$ of $\text{ZF}-\text{Reg}$ with elements $x\in M$ and $y\in N$ such that $x$ is a natural in $M$ but $y$ is not one in $N$, yet the transitive closures of $x$ in $M$ and $y$ in $N$ are isomorphic, then there cannot exist a bounded-quantifier formula that defines the naturals.

Here's a slightly convoluted way to do that (assuming, of course, that ZF is consistent):

Let $N$ be a model of $\text{ZF}-\text{Reg}$ with Aczel's anti-foundation axiom.

Inside $N$, carry out the usual compactness argument that there is a model $M$ of ZF which contains a non-standard integer $x$.

Still working inside $N$, look at the membership structure of the transitive closure of $x$. Because of the anti-foundation axiom, $N$ contains some $y$ whose transitive closure is exactly isomorphic to $x$. But $y$ cannot be a natural in $N$, because $(M,x)$ was explicitly constructed such that $x$ would be a non-standard natural when seen from $N$.

Now, even though $(M,x)$ was constructed inside $N$, we can easily lift it out of $N$ to become a model that lives in our universe side-by-side with $N$. It is still a model of $\text{ZF}-\text{Reg}$ (because everything is first-order, so the conditions for being a model inside $N$ guarantee that the lifted model is a model at our metalevel too), and similarly the isomorphism between $\bar x$ and $\bar y$ that exists in $N$ induces an isomorphism at the metalevel. This completes the proof.

share|improve this answer
add comment

The method below fails because we need at least one unbounded quantifier in order to obtain the power set of $x$, however I am keeping this answer here so that others attempting to solve this problem will have a starting point.

To define $\omega$ we either need to find a way to express its minimality as an inductive set, or its minimality as an infinite ordinal; or we need to find a way to define a finite ordinal and write $\omega$ as the set of finite ordinals.

  • $x$ is transitive, that is every element of an element of $x$ is also an element of $x$.
  • $x$ is linearly ordered by $\in$, that is given two distinct elements of $x$, one is the element of the other.
  • $x$ is inductive, that is the set with no elements is in $x$, and for every $k$, element of $x$, there is another element of $x$ which is equal to $k\cup\{k\}$.
  • $x$ is well-founded, that is for every element of $\mathcal P(x)$ which is non-empty there is a $\in$-minimal member.
  • $x$ contains only finite sets, that is every $k$, element of $x$, has the property that every collection of subsets of $k$ is either empty or contains a $\subseteq$-maximal element.

Note that I use the power set twice, once for well-foundedness and one for finiteness. I also use Tarski's definition of finite (Dedekind's definition would also be applicable and would require quantification over elements of $\mathcal P(x\times x)$, so we use power sets again as well as products).

It should be remarked that finite-ness and well-foundedness are both second-order properties, i.e. there are models of ZF in which there are uncountably many [internally] finite sets. Spooky but true. It seems a bit unlikely to find a way to define them without appealing to unbounded quantifiers, or at least bounding the quantifiers at the power set or so.

share|improve this answer
    
Wouldn't "$x$ is transitive and well-ordered by $\in$" and "$x$ is Dedekind-finite" be enough? –  Hagen von Eitzen Dec 20 '12 at 10:10
    
@Hagen: What about $\omega+1$? :-) –  Asaf Karagila Dec 20 '12 at 10:11
    
I meant to formalize "$x\in\omega$ directly, not $x=\omega$, therefore I used "$x$ Dedekind-finite". –  Hagen von Eitzen Dec 20 '12 at 10:17
    
@Hagen: Oops! I didn't see... I just woke up and my BAC is still not low enough. :-) Either way, that would define a finite ordinal, but not the collection of all finite ordinals. –  Asaf Karagila Dec 20 '12 at 10:20
    
@Asaf Karagila. How do you write "$x$ is well-ordered by $\in$" as a bounded formula over ZF-Foundation? –  Ali Kare Dec 20 '12 at 11:21
show 5 more comments

This is too long to write in comments so let me note here that if we can express "$x$ is an ordinal" as a bounded formula $\mbox{ord}(x)$ over ZF-Foundation then we can also express "$x$ is a natural number". First define (as in Jech, 3rd ed, p. 164) "$x$ is a limit ordinal" as

$$ \lim(x) \mbox{ iff } \mbox{ord}(x) \wedge (\forall u\in x) (\exists v\in x) u\in v.$$

Now

$$x \mbox{ is a natural number iff } \mbox{ord}(x) \wedge (\neg \lim(x) \vee x=0) \wedge (\forall u\in x) (u=0 \vee \neg\lim(u) ).$$

So if it is the case that "$x$ is a natural number" is not equivalent to a bounded formula over ZF-Foundation then neither is "$x$ is an ordinal". Since the usual definition of "$x$ is an ordinal" employs "$x$ is well-founded", it also follows that "$x$ is well-founded" is not equivalent to a bounded formula over ZF-Foundation.

$$ \mbox{ }$$

Note: If the axiom of foundation holds, then it is easy to define "$x$ is an ordinal" as a bounded formula over ZF. There are different ways to do it: $$\mbox{ord}(x) \:\: \mbox{ iff } \:\: x \mbox{ is a transitive set } \wedge x \mbox{ is totally ordered by } \in.$$ Or $$\mbox{ord}(x) \:\: \mbox{ iff } \:\: x \mbox{ is a transitive set } \wedge \: \in \! \mbox{ satisfies trichotomy on }x.$$ Or $$\mbox{ord}(x) \:\: \mbox{ iff } \:\: x \mbox{ is a transitive set } \wedge (\forall u \in x)(u \mbox{ is a transitive set}).$$

The above equivalences are in Kunen 2011, p.34, p.38, p.39.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.