8
$\begingroup$

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
    I think the book has a typo. Your opinion is correct.2011-07-22
  • 2
    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](http://en.wikipedia.org/wiki/Knuth_reward_check).2011-07-22

1 Answers 1

13

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}$.

  • 0
    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.2011-07-22
  • 3
    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.2011-07-22
  • 0
    @Steven: Don't you mean, $a$ can't contain $a$ as a member? (Equivalently, $a$ cannot contain $\{ a \}$ as a subset.)2011-07-23
  • 0
    Ahh yes, of course; mea culpa.2011-07-23