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?

  • 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
    Ahh yes, of course; mea culpa.2011-07-23