Cardinal Numbers

You can read the LaTeX document online (for the latest updated chapters) from the link: https://pdf.gaomj.cn/?file=get.php?f=set-theory

Cardinal Numbers

Contents
Contents
 1.  Temporary Assumptions
 2.  Sets With the Same Size
 3.  Continued on Page Two

1. Temporary Assumptions In this chapter we shall study the size of a set, which is a natural number. However from the axiomatic point of view, the concept of natural numbers has not yet been defined. It is postponed to later chapters.

For now we temporatily assume some basic propositions that will be used before their formal discussion. We have actually familiar with them.

Natural Numbers

1. The numbers 0,1,2,\dots are called natural numbers.
   
2. There is a set \mathbb N of all natural numbers.
   
3. A statement involving n that holds for all n\in\mathbb N, can be proved by induction. Also, an object involving n can be defined recursively.
   
4. The natural numbers are equipped with two operations: addition and multiplication, which have the usual properties.

Ordering Relations

There is a binary relation on \mathbb N, denoted by <.

1. For any two natural numbers n,m, among the following three statements one and only one of them holds: n<m, n=m, m<n.
   
2. The < relation is transitive: (n<m)\wedge (m<p)\Rightarrow n<p.

An immediate consequence is that there is no x such that x<x. And for distinct x,y, either x<y or y<x.

The notation \mathbb N _ {< n} denotes the set of all natural numbers less than n:
\[ \mathbb N _ {< n}=\{m\in\mathbb N\mid m<n\}. \]

Others

We will also use the basic properties of the set of rational numbers \mathbb Q and the set of real numbers \mathbb R.

With additional axioms, for any set S we can define |S| such that:

1. For any two sets A,B, |A|=|B| if and only if there is a bijection from A onto B.
   
2. If for a set A there is a natural number n such that there is a bijective from A onto \mathbb N _ {<n}, then |A|=n.

We will first try to explore the possibility of proposing a definition that satisfies the second property, without using additional axioms.

2. Sets With the Same Size How can we compare the size of two sets? For finite sets it is easy since we can compare by counting the number of elements. What about infinite sets? In this case \mathbb N is no longer a good model to measure the size.

Solution 1: It seems natural to say A is larger than B if A\subsetneq B, but they are non-comparable when there is no inclusion relation. This is a very limited approach.

Solution 2: How about B is larger than A if and only if there exists a bijection from A onto a proper subset of B? This is better to some extent. Consider the following three sequences:
\begin{align*}
&2,4,6,8,\dots\\
&1,2,3,4,\dots\\
&4,8,12,16,\dots
\end{align*}

If we compare the size of sets A,B with elements of the first two sequences, then the second is larger since it properly contains the first. However there is a bijection from the second onto the third, which is properly contained in the first. We have to conclude that A is larger than B while B is also larger than A.

Solution 3: It turns out that we can do better if we adopt the following definition:

The set \{1,2,3,\dots\} is equinumerous to the set \{2,4,6,\dots\}. The set \mathbb N of natural numbers and the set E of even numbers have a bijection between them: n\mapsto 2n. This is an amazing property impossible for finite sets.

Consider two more examples.

1. The set \mathbb N is equinumerous to the set \mathbb N\times\mathbb N. This is easy to see.
   
2. The set (0,1) is equinumerous to the set \mathbb R, because the function x\mapsto\tan (x-\frac12)\pi is a bijection from (0,1) onto \mathbb R.

Since all sets cannot form a set, the sets that are equinumerous to each other cannot be related by a relation. But they do have all the properties that an equivalence relation has.

We can give a precise definition of finite sets. Recall that \mathbb N _ {<n} denotes the set of all natural numbers less than n.

By definition \mathbb N _ {<n} is finite for any natural number n.

Cardinal Numbers of Finite Sets

If we want to define |A|=n when A\sim \mathbb N _ {<n}, we have to check such a natural number n is unique. An important property of \mathbb N _ {<n} is needed.

To prove the theorem, we take an arbitrary injective function f:\mathbb N _ {<n}\to\mathbb N _ {<n} and show f is also surjective. This means any such an injection f cannot have a range that is a proper subset of \mathbb N _ {<n}.

We use induction on n. The base case is obvious so we now assume the theorem holds for n. We shall prove the theorem holds for n+1. Suppose f:\mathbb N _ {<{n+1}}\to\mathbb N _ {<{n+1}} is an injective function. Consider the image of \mathbb N _ {<n} under f. If this image is just \mathbb N _ {<n}, then we have f(n)=n and therefore f maps \mathbb N _ {<n+1} onto \mathbb N _ {<n}\cup\{n\}=\mathbb N _ {<n+1}. The theorem holds for n+1 in this case. If there is a number m<n such that f(m)=n, we interchange the value of f(m) and f(n). Define g(m)=f(n)<n, g(n)=f(m)=n and g=f on \mathbb N _ {<{n+1}}\setminus\{m,n\}. This case is reduced to the first case. Thus the theorem holds for n+1 in either case.

The first corollary is not difficult to show. A finite set can be mapped bijectively onto \mathbb N _ {<n} by a function g. For any injective function f from this finite set into itself, we can consider the "transition function" g\circ f\circ g^{-1} and apply the theorem.

Later we will see the "if" part of this corollary also holds.

For the second corollary, suppose A\sim \mathbb N _ {<n} and A\sim\mathbb N _ {<m}. We have \mathbb N _ {<n}\sim\mathbb N _ {<m}. If n\neq m then either n<m or m<n. Without loss of generality suppose m<n, indicating \mathbb N _ {<m}\subsetneq\mathbb N _ {<n}. By the theorem this is impossible, so n=m.□
.

The theorem justifies the definition of cardinal number for a finite set:

We defer the generalization of cardinal numbers of infinite sets to the next chapter. Before that it is regarded as a primitive notion such that |A|=|B| if and only if A\sim B, as we assumed in the beginning of this chapter.

3. Continued on Page Two