Tag: set elements

Because a recent post about the German mathematician Georg Cantor (1845-1918) generated a great deal of interest, I decided to do two more posts about Cantor’s contributions to mathematics. Of course, I find Cantor’s mathematics fascinating, and apparently many readers found the content of that post intellectually stimulating as well. You might think that Cantor’s work amounts to a bunch of clever and interesting mathematical mind games, but this is not the case. His work helped lay the foundation upon which much of modern mathematical analysis rests. If you have not read my first Cantor post, Infinity Does Not Necessarily Equal Infinity, I strongly suggest that you read it before continuing. The concepts presented in this post heavily depend on an understanding of the concepts presented in that post.

The purpose of this post is to show how Cantor proved that there are infinitely many levels of infinity or there are infinitely many different infinite cardinal numbers! The purpose of the next Cantor post will be to give readers a general description of the Cantor ternary set which is counter-intuitive, preposterous, absurd, and astonishing. I will not delve deeply into formal abstract mathematics, because my understanding of Cantor’s work only scratches the surface of his deep mathematics.

To get started, I will do a quick review of some basic definitions and concepts in set theory.

• A set can be any collection of objects such as numbers, character symbols, cars, people, cats, etc.
• Set A is a subset of set B if and only if every element of set A is an element of set B.
• Let A equal any subset of B. A is a proper subset of B if and only if there is an element in B that is not in A.
• The null or empty set is a set that contains no elements. The symbols { } or Ø denote the empty set.
• Sets {0}, {Ø}, and {{ }} are not the empty set because each of the three sets contains an element.
• The null set is both a subset and proper subset of every set.
• Set A equals set B if and only if the sets are subsets of each other.
• In set theory and Boolean algebra, the word “or” means “one or the other and possibly both.” In contrast, when a parent uses the word “or” with a child, the parent means “one or the other, but not both.”
• In set theory and Boolean algebra, the word “and” means “both are in the set” or “both are true.”
• The union of sets A and B, denoted by A ∪ B, is the set of elements that are in A or B.
• The intersection of sets A and B, denoted by A ∩ B, is the set of elements that are in A and B.

I can now explain the proof Cantor’s theorem which states that the cardinal number of P(A) is strictly greater than the cardinal number of A where A is any finite or infinite set. Cantor’s theorem can be used to show that there are infinitely many different infinite cardinal numbers. Recall from my first Cantor post that the cardinal number of a set equals the number of elements the set contains. Therefore the cardinal number of a google of water molecules equals 10¹⁰⁰, and the cardinal number of a MLB active roster equals 25.  Also recall from my first Cantor post that the symbol for the cardinal number of the counting numbers is ℵ₀, the symbol for the cardinal number of the real numbers is ℵ₁, and ℵ₀ < ℵ₁.

For finite sets, Cantor’s theorem is obvious. If the cardinal number of finite set A equals n, then the cardinal number of P(A) equals 2ⁿ. For infinite sets Cantor’s theorem might seem obvious, but it’s much more difficult to prove. To make Cantor’s proof more comprehensible for infinite sets, I will first give a proof that shows that the cardinal number of P(C) is strictly greater than the cardinal number of C where C equals the set of counting numbers. Like many deep abstract mathematical proofs, Cantor’s proof uses the sophisticated technique of proof by contradiction. For set C, his proof goes something like this:

• Assume that there is a one-to-one function f with domain C and range P(C) that matches the counting numbers in C with all of the elements of P(C). The text box below shows one of the infinitely many possible ways that we could create a matching rule for f. The order in which domain and range elements are listed makes no difference. The important point is that there exists a one-to-one function f such that the domain of f equals set C and the range of the function, all function values, equals the set P(C).

• Construct a special subset M of the counting numbers as follows: (See the text box above.) Let set M equal all counting numbers n such that n is not contained in f(n). M is not the empty set because counting number j, such that f(j) = {   }, must be an element of M by definition.

• Set M raises a contradiction as follows: There must be a unique counting number k such that f(k) = M. Either k is contained in M or k is not contained in M. If k is contained in M, then by the definition of set M, k is not an element of M. If k is not contained in M, they by the definition of set M, k is an element of M. Therefore the function f can’t exist. Hence there is no counting number k that matches with M, and the cardinal number of set P(C) is greater than the cardinal number of set C. (The contradiction is somewhat like damned if you do and damned if you don’t.)

Now let’s see how we can prove that the cardinal number of the set of real numbers is strictly less than the cardinal number of the power set of real numbers. We need only to modify the last proof a little bit to give us our proof. The following algorithm describes how to create the modified proof:

• Let R equal the set of real numbers and the variable x equal any real number or element of R.

• Assume that there is a one-to-one function f with domain R and range P(R) that matches the real numbers in R with all of the elements of P(R).

• Construct a special subset M of the real numbers as follows:
  1. Let set M equal all real numbers x such that x is not contained in f(x).
  2. M is not the empty set because real number y, such that f(y) = {   }, must be an element of M by definition.

• Set M raises a contradiction as follows:
  1. There must be a unique real number k such that f(k) = M. Either k is an element of M or k is not an element of M.
  2. If k is an element of M, then by definition of set M, k is not an element of M.
  3. If k is not an element of M, they by definition of set M, k is an element of M.
  4. Therefore function f can’t exist. Hence there is no real number k that matches with M, and the cardinal number of set P(R) is greater than the cardinal number of set R.

1. How will I ever apply set theory and cardinal numbers in my daily life? A: Probably never.
2. Do many engineers and scientists use set theory and cardinal numbers? A: Very few.
3. Name a math class that uses set theory? A: Venn diagrams to model probabilities of events in statistics.
4. Who uses set theory on a regular basis? A: People who design computer logic circuits use Boolean algebra.
5.  Is the study of set theory and cardinal numbers really just a mind game played by crackpot mathematicians? A: No – Cantor’s work helped create the foundation upon which much of modern mathematics rests.
6. Should very bright and curious high school math students be exposed to some of Cantor’s ideas? A: Yes.