So learning to count is just the beginning of appreciating what is finite and what is infinite: all understanding is impossible without the ability to construct functions. “Functions are the sole thing that makes thinking possible.” This may be exaggerated, but when it comes to set theory, it’s true.
My lecture is getting more exciting these days…
We learned about the definitions of finiteness and infinity. The definitions are:
A set S is called finite if it is empty or if there exists a natural number n as well as a bijective function (i.e. a one-to-one correspondence) from {1, 2, …, n} to S. If a set is not finite, then we call it infinite.
Basically, the definitions say nothing more than :”A set is finite if its elements can be counted, otherwise it is infinite…” Because, when we think of what we do when we count, we find that we are simply matching the first few natural numbers to the objects in a collection! The last of those natural numbers that we use is the number of objects.
But then, we proved some “basic theorems” like
1. (Pigeonhole Principle) The number of objects in a finite set is unique. (i.e. if two people count the number of words in an essay and somehow get different results, then at least one of them must be wrong.)
2. There is really an infinite set, and specifically, the set of natural numbers is infinite.
3. A finite set can never contain an infinite set as a subset, that is, if a set contains an infinite set as a subest, then the set itself must be infinite as well. (i.e. Infinity is bigger than all finiteness.)
4. If set A is a proper subset of a finite set B (i.e. all elements in A are in B, but there is an element in B that is not in A), then the number of elements in A must be strictly smaller than the number of elements in B. (i.e. The whole is bigger than the part.)
The statements all seem to be self-evident, but nooo! Since we don’t define finiteness and infinity in our usual intuitive way, but rather based on the existence of bijective functions, the proofs of all these statements are not trivial at all! Bascially, to prove any of them, one has to first construct a function, show it is well-defined, totally defined, and bijective, and then consider whatever is said in the theorems. Constructing functions is never a piece of cake in mathematics!
For example, how to prove that the set of natural numbers N is infinite?
PROOF:
Well, the function f defined on N by f(n):=n+1 is a bijective function from N to N\{1}.
The latter is a proper subset of N.
Now if N is finite, then according to the last statement above, N\{1} is also finite and has less number of elements than N.
But the fact that there is a bijective function from N to N\{1} suggests that they have the same number of elements.
A contradiction! So N is infinite!
We have used Statement 4 above. To prove Statement 4, we need to construct a more complicated function and I have virtually written 2 pages simply for an idea of that proof. I believe, however, that the above proof is enough to give the reader an idea of what “constructing a function” means.
The proof can be generalized to the following statement:
If a set can be mapped by a bijective function to a proper subset of itself, then it is infinite.
This can be shown easily using Statement 4.
Now, what a good mathematician should do is to ask if the reverse statement is true…
If a set is infinite, can it always be mapped bijectively to a proper subset of itself?
This sounds hard to answer at first, but what a good mathematician does is starting to think about how to cook up such a bijective function.
It turns out that if an infinite set contains a subset that “looks like the set of natural numbers“, then such a bijective function from the infinite set to a proper subset of itself is very easy to find.
For example, the set of all real numbers R contains the set of natural numbers, so we can define the function f on R to be
- f(x):=x, if x is not a natural number;
- f(x):=x+1, if x is a natural number.
f can be shown to be a bijective function from R to R\{1}.
As another example, the set P of all real numbers in the interval (0,1) does not contain N as a subset, but the set T:={1/2, 1/3, 1/4, …} can be “counted” by N, i.e. there is a bijective function from N to T. Therefore, we can define the function g on P to be
- g(x):=x, if x is not an element in T;
- g(x):=1/(x+1), if x is an elment in T.
g can be shown to be a bijective function from P to P\{1/2}.
I believe that the reader can generalize these examples to show that
Let S be an infinite set. If there exists a subset of S that is equivalent to the set of natural numbers, then S is equivalent to a proper subset of itself.
Here two sets are equivalent means there exists a bijective function from one to another.
Now it’s only left to show that any infinite set S has a subset that is equivalent to N. This can be proven easily using the Axiom of Choice.
We simply choose any element a in S and assign 1 to it.
Then we choose any element b in S\{a} and assign 2 to it. S\{a} is nonempty because otherwise S would be finite.
Then we choose any element c in S\{a,b} and assign 3 to it. Again S\{a,b} is nonempty because otherweise S would be finite.
The argument can go on and on (i.e. we can use induction) and we are able to construct a bijective function from N to {a, b, c, …} which is a subset of S.
But in order to choose those a, b, c, we do need Axiom of Choice!!
Therefore,
If the Axiom of Choice is accepted, then any infinite set is equivalent to a proper subset of itself.
But does the latter part imply the Axiom of Choice?? I am still stuck on this question. I hope my lecturer, Prof Chin, will enlighten me on this 😀