Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

November 1, 2024

Axiomatic Set Theory 7: Number Systems

Posted by Tom Leinster

Previously: Part 6.

As the course continues, the axioms fade into the background. They rarely get mentioned these days. Much more often, the facts we’re leaning on are theorems that were deduced from theorems that were deduced — at several removes — from the axioms. And the course feels like it’s mostly converging with any other set theory course, just with the special feature that everything remains resolutely isomorphism-invariant.

This week we constructed \mathbb{N}, \mathbb{Z}, \mathbb{Q} and \mathbb{R}. This was the first time in the course that we used the natural numbers axiom, and that axiom did get cited explicitly (in the first few pages, anyway). We had to use the universal property of \mathbb{N} to define sums, products and powers in \mathbb{N}, and to prove the principle of induction.

I think my highlight of the week was a decategorification argument used to prove the classic laws of natural number arithmetic. Read on…

The decategorification argument goes like this. We’d already seen various theorems about sets that are strongly redolent of ordinary arithmetic, like

X×(Y+Z)(X×Y)+(X×Z) X \times (Y + Z) \cong (X \times Y) + (X \times Z)

and

X Y×Z(X Y) Z. X^{Y \times Z} \cong (X^Y)^Z.

Now, in this chapter we gave recursive definitions of addition, multiplication and exponentiation in \mathbb{N}, using the universal property of \mathbb{N}. (How else? The universal property is the only tool at our disposal.) Of course, we then wanted to prove that they satisfy equations like

x(y+z)=xy+xz x(y + z) = xy + xz

and

(x y) z=x yz. (x^y)^z = x^{yz}.

We could have done it by induction. But there’s no need! Instead, we argued as follows.

First define, for each nn \in \mathbb{N}, the set

n={i:i<n}={0,,n1}. \mathbf{n} = \{ i \in \mathbb{N} : i \lt n \} = \{0, \ldots, n - 1\}.

Then show that the passage nnn \mapsto \mathbf{n} respects addition, multiplication and exponentiation. For example, if we write p=m+np = m + n then p\mathbf{p} is the coproduct of m\mathbf{m} and n\mathbf{n}. This makes expressions like m+n\mathbf{m} + \mathbf{n} unambiguous: it doesn’t matter whether you add in \mathbb{N} then turn the result into a set, or turn each of mm and nn into sets and then take the coproduct. Finally, show that

mnm=n. \mathbf{m} \cong \mathbf{n} \iff m = n.

This done, we can deduce the standard algebraic laws in \mathbb{N} from general isomorphisms for sets. For instance, the fact that

m×(n+p)(m×n)+(m×p) \mathbf{m} \times (\mathbf{n} + \mathbf{p}) \cong (\mathbf{m} \times \mathbf{n}) + (\mathbf{m} \times \mathbf{p})

immediately implies that

m(n+p)=mn+mp, m(n + p) = m n + m p,

for all m,n,pm, n, p \in \mathbb{N}.

The same technique also works for inequalities, like mnm+pn+pm \leq n \implies m + p \leq n + p.

The only thing it doesn’t work for is cancellation, because that’s specifically a phenomenon for finite sets: it is true for natural numbers that m+p=n+pm=nm + p = n + p \implies m = n, but it’s not true for general sets (only finite sets) that X+ZY+ZXYX + Z \cong Y + Z \implies X \cong Y.

The decategorification method of proving the identities for natural numbers doesn’t save a vast amount of work. The inductions aren’t particularly onerous. But since we’d want to prove anyway that sums, products and powers of natural numbers corresponds to coproducts, products and exponentials of sets, it’s an opportunity to get something for free.

Posted at November 1, 2024 3:08 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3575

1 Comment & 0 Trackbacks

Re: Axiomatic Set Theory 7: Number Systems

This week we constructed ℕ, ℤ, ℚ and ℝ.

It must feel great! How many people can say that when someone asks what they’ve been up to lately?

Posted by: John Baez on November 1, 2024 7:32 PM | Permalink | Reply to this

Post a New Comment