In Wolfgang Wechler's Universal Algebra for Computer Scientists, he says that natural numbers can be represented as finite sets:

$0$ stands for $\emptyset$, $1$ for {$\emptyset$}, $2$ for {$\emptyset$,{$\emptyset$}}, $3$ for {$\emptyset$,{$\emptyset$,{$\emptyset$}}} and so on.

Then he says that a more readable way is that $0 = \emptyset$ and $ n = \{0,1,\dots\,n-1\}$ for $n \ge 1$.

But to me this seems different: in my opinion $3$ would be coded as $ \{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\} $.

Isn't this a mistake in the book? If it is, which construction is the "right" one?

  • 6
    $\begingroup$ I think the book has a typo. Your opinion is correct. $\endgroup$ – tomcuchta Jul 22 '11 at 19:00
  • 2
    $\begingroup$ I suggest you send an e-mail to either the original author or the publisher. Sometimes they maintain a list of errata on their websites, sometimes in their next printing your name will be acknowledged for pointing out the error, and sometimes you even get some money and bragging rights out of it. $\endgroup$ – Willie Wong Jul 22 '11 at 19:16

The book has a typo in its description of $3$, and you are correct.

To expand a bit.

Given a set $a$, we define $s(a)$, the successor of $a$, to be the set $s(a) = a\cup \{a\}$.

A set $X$ is said to be inductive if and only if:

  1. $\emptyset \in X$; and
  2. If $a\in X$, then $s(a)\in X$.

The Axiom of Infinity in ZF Set Theory states that there exists at least one inductive set. Given an inductive set $X$, we define $$\mathbb{N}_X = \bigcap\{ S\subseteq X\mid S\text{ is inductive.}\}.$$

One can then prove that if $X$ and $Y$ are inductive sets, then $\mathbb{N}_X=\mathbb{N}_Y$; we define "the natural numbers", $\mathbb{N}$, to be this (now shown to be well-defined) set.

So what is $\mathbb{N}$? It contains $\emptyset$; we call it $0$. It contains $s(0) = s(\emptyset) = \emptyset\cup\{\emptyset\} = \{\emptyset\}$, which we call $1$.

It contains $s(1)$, which we call $2$. What is $2$? $$2 = s(1) = s(\{\emptyset\}) = \{\emptyset\} \cup \{\{\emptyset\}\} = \{\emptyset,\{\emptyset\}\}.$$ Then we have $s(2)$, called (unsurprisingly), "$3$"; and we have: $$3 = s(2) = s(\{\emptyset,\{\emptyset\}\}) = \{\emptyset,\{\emptyset\}\}\cup\Bigl\{\{\emptyset,\{\emptyset\}\}\Bigr\} = \Bigl\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\Bigr\} = \{0,1,2\}.$$

And so on. The set contains exactly $\emptyset$ and its successors, and it corresponds to the naive idea of the "natural numbers:". The fact that it is the "smallest inductive set" implies that induction holds: if $S\subseteq \mathbb{N}$ is such that $0\in S$ and, whenever $n\in S$ we have $s(n)\in S$ (that is, $S$ is inductive), then $S=\mathbb{N}$.

  • $\begingroup$ Thank you, now it makes sense to me. I would like to upvote your answer, but it says that I do not have enough reputation to do so. $\endgroup$ – Matej Jul 22 '11 at 19:18
  • 3
    $\begingroup$ Incidentally, a small side note on why we define the successor of a set $a$ the way we do: by the Axiom of Regularity, $a$ can't contain $\{a\}$ as a member, so $s(a) = a\cup\{a\}$ is guaranteed to be a different set than $a$ is and in fact to satsify $a\subsetneq s(a)$, and it's essentially the simplest definition that offers this guarantee. $\endgroup$ – Steven Stadnicki Jul 22 '11 at 19:23
  • $\begingroup$ @Steven: Don't you mean, $a$ can't contain $a$ as a member? (Equivalently, $a$ cannot contain $\{ a \}$ as a subset.) $\endgroup$ – Zhen Lin Jul 23 '11 at 7:12
  • $\begingroup$ Ahh yes, of course; mea culpa. $\endgroup$ – Steven Stadnicki Jul 23 '11 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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