# Is this a valid construction of the natural numbers under ZF?

First, define an equivalence relation, $\sim$, such that two sets, $A$ and $B$ are equivalent, $A\sim B$ if and only if there exists a bijection between them. Then define $$0=[\emptyset]_\sim$$ Where I have used $[]_\sim$ to denote the equivalence class. Then, to define the successor function, $$S([n]_\sim)=[n\cup \{n\}]_\sim$$ Then, $$\exists!\mathbb{N}(0\in\mathbb{N} \wedge(n\in \mathbb{N}\rightarrow S(n)\in \mathbb{N}))$$ And of course the set $\mathbb{N}$ is the natural numbers. Now that I've written this out, I feel like the axiom of infinity would have to be replaced with the last line. But my question is, is this a valid construction under the ZF system or does it require different axioms? I also fear that I may have violated Russell's paradox...

## 2 Answers

There are a couple of problems with your construction. The first is that for each nonempty set $x$, the equivalence class $[x]_{\sim}$ really is a class — a proper class: it's too big to be a set. A class is a set precisely when it's a member of a set. Thus, no $\sim$ equivalence class (except your $0$) can be a member of any set, and in particular there is no set of these equivalence classes.

In practice, there are ways around this. "Scott's trick" provides a way to separate out a set-sized collection from a class. To explain it, we need the notion of rank. The rank of a set $x$ is the least ordinal $\alpha$ such that $x\in V_{\alpha}$, where the $V_{\alpha}$ form the cumulative hierarchy, a proper class of sets whose union is the universe. The axioms of ZFC guarantee that this is well defined. Now, given a class $C$, possibly proper, the collection of all $x\in C$ of minimal rank $\alpha_0$ is a set, because it's a member of $\mathcal{P}(V_{\alpha_0})$.

Using the notion of rank, you can see why the $\sim$ equivalences classes are too big: each contains members of arbitrarily high rank. For any set $x$, $\{x\} \sim \{\emptyset \}$. If $[\{\emptyset \}]_{\sim}$ were a set, then by the Axiom of Replacement the set of all ranks of its members would be a set too; but that latter collection is unbounded in the class of all ordinals, and its transitive closure is equal to the class of all ordinals.

Once you address the first problem, there's another: there is no unique set $N$ such that $$0\in N \text{ and } \forall n\,(n\in N\to S(n)\in N).\tag{Ind_N}$$ However, you can fix this too. Define $\Bbb N'$ as the smallest set (in the sense of set inclusion) satisfying $Ind_N$ — equivalently, the intersection of all $N$ satisfying $Ind_N$. In order for this set to exist (not be an empty intersection and therefore equal to the whole universe) you need an Axiom of Infinity to guarantee that there's at least one set satisfying $Ind_N$.

• Let $V_\alpha$ be a "stage" in the cumulative hierarchy and $\alpha$ be the rank of a set. If we were to restrict the set that the equivalence relation applies to to the set of all $x$ such that $x\in V_\alpha$ where $\alpha$ is a successor ordinal, would the equivalence classes still be too big to be sets? – Praise Existence Aug 9 '16 at 20:49
• No, they're "just right" now, they're sets: you've defined them so they're small enough. In fact you answered your own question: by restricting the equivalence classes to collection to some $V_{\alpha}$, you produce a set. Every $V_{\alpha}$ is a set, so by ZF's Comprehension axiom, definable subcollections of it are sets too. – BrianO Aug 10 '16 at 3:37

This set could easily be "too big". Your axioms state that it must contain all of the natural numbers, but it does not state that it must only contain then. Consider the equivalence class of the set of real numbers. It is certainly not in bijection with any finite set, so it is distinct from any natural numbers under the given equivalence relation, yet there is nothing saying that it cannot be in your version of $\mathbb{N}$.