**Infinity: The Story So
Far**

(Revised: 2018-04-11)

**Introduction**

Here we turn Hilbert's Hotel on its head. Instead of frantically shuffling infinitely many guests for one room to the next in Hilbert's mythical infinite hotel, we start with a leisurely walk through an ordinary and quite finite village.

**A Walk Through a Finite Village **

Starting at any house in this finite village, you set out to visit some or all of the houses there. You keep walking non-stop until you return to your starting point, visiting no house more than once.

Intuitively, it seems obvious that you could not avoid returning to your starting point under these conditions. You could, of course, return to your starting point without first going to every other house in the village. If you kept going, however, you would eventually run out of different places to go, and you would

have toreturn to your starting point. Going anywhere else at that point would be going there more than once. (As you might imagine, in aninfinitevillage, it might be possible to keep walking from house to house, never stopping and never returning to your starting point.)How can we describe such paths mathematically? We can begin by letting

Sbe the set of houses in the village. Each path that you can take through the village can be specified by:1. Your starting pointing at house

x_{0}2. A relation

fon S that specifies the order in which you will visit the houses inS.For every house in

Son your path, you will go next to exactly one house inS.Therefore,fis a function onS.

Figure 1: Relationfis a function onS.You cannot go to the same house more than once, i.e. function

fis injective.

Figure 2: Functionfis injective.

Figure 3: Example of a walk starting and finishing at housex_{0}. Housex_{n}

is the last house visited before returning to housex_{0}.How do we specify that you must return to your starting point

x_{0}? Simply by requiring that there must exist a housexin the village such that_{n}f(x_{n}) =x_{0}. (See figure 3, dashed line.)Thus, we can define set

Sto be finite if and only if for allx_{0}andf, ifx_{0 }e_{ }Sandfis an injective function mappingSto itself, then there must existxe_{n}Ssuch that f(x) =_{n}x_{0}.In DC Proof format:

ALL(s):[Set(s) => [FiniteA(s)

<=> ALL(x0):ALL(f):[x0 e s

& ALL(a):[a e s => f(a) e s]

& ALL(a):ALL(b):[a e s & b e s => [f(a)=f(b) => a=b]]

=> EXIST(xn):[xn e s & f(xn)=x0]]]]

**An Equivalent Definition of Finite (Dedekind)**

First introduced by Richard Dedekind, here is an equivalent and somewhat easier definition to work with:

ALL(s):[Set(s) => [Finite(s)

<=> ALL(f):[ALL(a):[a e s => f(a) e s]

& ALL(a):ALL(b):[a e s & b e s => [f(a)=f(b) => a=b]]

=> ALL(a):[a e s => EXIST(xn):[xn e s & f(xn)=a]]] Formal Proof (55 lines)

In words, a set *S* is *finite* if and only if for all
functions *f* mapping *S* to itself, if *f* is injective
(1-to-1) , then *f* is surjective (onto).

**The Infinite as the Negation of the Finite**

In walking through an *infinite* village, there would be no guarantee,
as above, that you would ever return to your starting point. Not surprisingly
then, a set is infinite if and only it is *not* finite. Thus, we define *Infinite* as
follows:

ALL(s):[Set(s) => [Infinite(s)

<=> EXIST(f):[ALL(a):[a e s => f(a) e s]

& [Injection(f,s,s)

& ~Surjection(f,s,s)]]]]

where

Infinte(x) means x is infinite

Injection(f,x,y) means f is an injection (1-to-1) mapping set x to set y

Surjection(f,x,y) means f is an surjection (onto) mapping set x to set y

In words, a set *S* is *infinite* if and only if there
exists a function *f* mapping *S* to itself that is injective
(1-to-1) and not surjective (*not* onto).

**An Equivalent, Numerically-based Definition of Infinite**

Suppose we are given the set *N*, 0 e *N*
and a successor function *next* that satisfy the Peano axioms. Then we can
then develop the following equivalent definition of
infinite:

ALL(s):[Set(s) => [Infinite(s)

<=> EXIST(f):[ALL(a):[a e n => f(a) e s]

& ALL(a):ALL(b):[a e n & b e n => [f(a)=f(b) => a=b]]]]] Formal Proof (515 lines)

Or equivalently:

ALL(s):[Set(s) => [Infinite(s)

<=> EXIST(f):[ALL(a):[a e n => f(a) e s]

& Injection(f,n,s)]]]

In words, a set *S* is *infinite* if and only if there
exists an injective function (1-to-1) mapping *N* into *S*.

**Countable Sets**

A set *S* is said
to *countable* if and
only there exists an injective function mapping *S* into *N*. (Note similarities to previous definition.)

ALL(s):[Countable(s)

<=> EXIST(f):[ALL(b):[b e s => f(b) e n]

& Injection(f,s,n)]]

A countable set

Smay be finite or infinite. IfSis countable and infinite, there exists a bijection mappingStoN(see Cantor-Bernstein-Schroeder Theorem).It is trivial to show that the set of natural numbers

Nmust itself be countable.

Cantor's TheoremLet

Pbe the power set ofS. (Smay be finite or infinite.) Then there exists no surjective function mappingSontoP.ALL(s):ALL(p):[Set(s)

& Set(p)

& ALL(c):[c e p <=> Set(c) & ALL(d):[d e c => d e s]]

=> ALL(f):[ALL(a):[a e s => f(a) e p] => ~Surjection(f,s,p]]] Formal Proof (53 lines)Thus, we can never cover the entire power set

Pwith images ofSunderanyfunction mappingStoP. This suggests that the power set of a setSis always somehowlargerthanSitself, even ifSis infinite. This, in turn, suggests that some infinities are larger than others.It is easy to prove that the set of natural numbers

Nand its power set are both, by definition, infinite. Cantor's Theorem suggests that the power set ofN, in particular is somehow larger thanNitself.

The power set ofNis uncountableLet

PNbe the power set of the set of natural numbersN:ALL(a):[a e pn <=> Set(a) & ALL(b):[b e a => b e n]]

Then

PNis not countable:~Countable(pn) Formal Proof (25 lines)