Transfinite Cardinals

This is a very brief and elementary introduction to Cantor's Theory of Transfinite Cardinals. We are at the footsteps of this magnificent theory, trying to learn to count infinte1, infinite2, and so on. Even at this early stage it takes a lot of preparation. Most of which has to do with the Set Theory. So we begin in the first section by learning the bare essentials of Set Theory that we are in absolute need. Bear in mind that what you learn in this section and the exercises you do here become invaluable tools in the second section when we learn to count beyond the finite. Most of the exercises in the second section will be a breeze if you had finished the ones on the first.

Set Preliminaries

You are no doubt familiar with the concept of sets, their elements or members, the empty set, subsets of sets, and the operations of union and intersection on sets. In this section you are going to learn a little bit more about sets and set notation. You may see topics that you are already familiar with, from other branches of mathematics such as Analysis, but pay particular attention to the Set Theoretic way of approaching these topics and handling them. Quite often you will see an old concept defined in a fancy new way! But this is just the eccentric way Set Theory deals with things. One striking thing you will notice is that in Set Theory almost everything is a set! It is almost as if meeting someone who is rather self centered and eccentric, but very interesting and fun to be with.

Set Equality

Two sets are said to be equal if and only if they have exactly the same elements (no more, no less). In particular, we never say two sets are equal just because they have the same number of elements.

Exercise 1: Write a formal definition of set equality using the set theoretic notation. (i.e., A, a, B, b, Î , { } together with logical expressions like and, or, and Þ ).

Proper Subset versus Subset

A is said to be a proper subset of B if A is a subset of B but A ¹ B. A proper subset A of set B cannot be equal to the set B. A proper subset A is definitely smaller than the "bigger set" B. There is a possibility for confusion here, because different authors use different notations. We will stick to the following one. Subset is indicated by Í . Which means a subset may or may not be equal to the "mother" set. A proper subset is indicated by Ì . So, A Ì B Û A Í B and A ¹ B. For instance,

{ odd integers } Ì { integers } whereas { students who are bored } Í { students in a lecture }.

Disjoint Sets

When the intersection of two sets is empty we say the sets are disjoint.

Partition

When we divide a set into subsets that are mutually disjoint and their total union is equal to the original set, we call it a Partition. Just like everything else in set theory, a partition too is a set. For instance, if A È B È C = S and A Ç B = B Ç C = C Ç A = F , then { A, B, C } is a partition of S.

Compliment of a set on another

The compliment of A on B is all B that is not A. Sometimes it is also called the set difference. It is indicated by B \ A or B - A. While the phrase "compliment of B on A" is the most precise one, the phrase set difference makes more intuitive sense. For this reason, when we apply this concept, it is often helpful to think in terms of the difference or subtraction. That is, think of B - A but write B \ A.

Exercise 2: Suppose A, B, C are sets such that C = A \ B. Write A È B in terms of A and C.

Power Set

The set of all subsets of a given set A is called the Power Set of A and is denoted by P(A). As you will see later, Power Sets play a very important roll at a crucial juncture in the development of the Theory of the Transfinite Cardinals. The last phrase is just a posh way of saying the Theory of the Sizes of Infinite Sets. As you will learn later, there are many infinite sets with the same "size". If you add many of these sets together, even 'infinitely' many of them, or more precisely, if you take the union of these sets, contrary to what you may have expected, the "size" may not increase! However, you will learn later that, given a set, one sure way of going to a set of larger size would be to take the power set of a given set.

Exercise 3: Suppose set A has 7 elements. Prove P(A) will have 2⁷ elements ( You should know of at least two different methods of doing this, both using high school combinatorics. Also, do not forget that the Empty set is a subset of any set ).

It should be apparent to you now, that if we let |A| stand for the number of elements in set A, then the number of elements in the set P(A) is given by |P(A)| = 2 ^|A|. This is where the word power in the term power-set comes from.

Cartesian Product A ´ B

The Cartesian product A ´ B is the set of all the ordered pairs ( a, b) where a is any element in A and b is any element in B. Note that the word ordered is used to indicate that the elements of A take the first place in the pair. This word does not mean that we have to take the elements of either set in any particular order with respect to the elements of the other set. Each element of A gets paired with each element of B, and vice versa. For instance, if A = { a, b } and B = { 0, 1, 2 }, then A ´ B = { (a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2) }. A formal definition of A ´ B would be as follows.

A ´ B = { (a,b) | a Î A, bÎ B}

The coordinate pair (x, y) we are so familiar with, is another example of ordered pairs, where x comes from the set X ( of Reals ) and y comes from the set Y ( of Reals ). The set of all such pairings is denoted by X ´ Y and said to be the Cartesian product of X and Y. The reason for this notation will become clear after you do the following exercise.

Exercise 4: Suppose set A has 5 elements and set B has 7 elements. How many elements will be there on the set A ´ B?

Exercise 5: Write a few members of the set N ´ {3} to make sure you understand this notation.

It should be clear to you after exercise 4, that if we denote the number of elements in set A by |A| and the number of elements in set B by |B|, then there are |A| ´ |B| elements in the set of ordered pairs. This is exactly the motivation behind the notation |A| ´ |B|.

Relations

Among the members of the Cartesian product A ´ B, there may be some that share a common relation. That is, all the (a, b)'s where a and b have a special relation. This subset of A ´ B is called a Relation from the set A to set B. Chances are that you have been already introduced to Relations in a different context, through a slightly different approach. What you just saw here is an example of the fancy way things are defined in Set Theory! ( And there are plenty of them !!). A relation can be one-one, one- many, many-one, or many-many. More over not all elements of set A need to have this Relation with any elements of set B. This means the Domain of the Relation does not have to be A. Typically, the Domain is a subset of A.

Exercise 6: Think of the people in a huge Christmas Party. Let A be the set of adults, and C be the set of children. ( You can define who is an adult and who s a child according to your own philosophy! ) Now define the Relation R from set A to set C as "is a parent of". Is R one-one, one-many, or many-many? Is R onto? Is the domain of R equal to A ?

As you have noticed, there is a lot of freedom in Relations! When we begin to restrict this freedom enjoyed by Relations, we will be talking about Functions. But that will have to wait for a while.

Set A and set B does not have to different. It is quite possible to have a relation from Set A to set A itself. When this happens, we call it a Relation on set A. Sometimes it is helpful to look at this situation from the perspective of the elements of this set. We could say that some elements of a set might be related to each other in some way. Consider the set of all people P, in an Office Christmas Party, and a Relation B, defined by "has the same boss as". We say B is a Relation on set P. There is a special type of Relations on sets that is quite important, and we will look at it next.

Equivalence Relations

Any relation on a set that has the three properties listed below is called an equivalence relation. We need some notation to state these properties. Let S be any set and a, b, and c are three elements from this set. We will write a ~ b to indicate that a and b have this relation.

1. Reflexivity: a ~ a.

2. Symmetry: a ~ b implies b ~ a.

3. Transitivity: a ~ b and b ~ c implies a ~ c.

Let's think of some sets and some Relations on them. For instance, consider the set of students on your class, and the Relation, "has the same eye color as". It is easy to see this relation satisfies all three conditions above, and hence, is an Equivalence Relation. Consider the Relation, "got the same mark as or higher mark than" ( in the last test ). This relation is not Symmetric, and therefore is not an equivalent relation.

Also notice that the equivalent relation "has the same eye color as" can be used to partition the set of students into people with the same eye color. This is a characteristic of Equivalent Relations. An Equivalent Relation on a set divides the members of that set into a partition. ###### In the example above, there will be mutually disjoint subsets of people with brown color eyes, blue color eyes, and so on. If Allan and Beth both have blue eyes, we say they both belong to the "modulo class blue" and write

Allan ~ Beth ( modulo blue ),

Where, ~ stands for the relation, "has the same color as".

This should remind you of an equivalence relation in Number Theory, that you are already familiar with, the Congruence relation defined on the set of integers. You know very well that

a º a ( mod m ),

a º b ( mod m ) implies b º a ( mod m ), and

a º b ( mod m ) and b º c ( mod m ) implies a º c ( mod m ).

The congruence relation " º ( mod m )" divides the set of integers into a partition called the "residue class modulo m". For instance, if m = 5, we have 5 mutually disjoint subsets of the integers, the integers in each subset leaving a different remainder when divided by 5.

Exercise 7: Name two different equivalent relations that can be defined on the set of students on your class or University.

Exercise 8: Is the relation "greater than or equal to" on the set of real numbers an equivalent relation?

Exercise 9: How about the relation " is a friend of " defined on the set of all people? ( Let's exclude all those people who hate themselves, and those weirdoes who think someone is there friend while that someone thinks I don't even know that guy! )

We will soon come across another example of an equivalence relation, called the Equinumerousity of sets. Two sets are said to be Equinumerous if they have the "same size". For finite sets, this means they have the same number of elements. What this means for infinite sets is a major part of what we are setting out to learn.

Functions

A Relation f from set X to set Y that satisfies the following two conditions is called a Function from X to Y.

1. Domain of f = X

2. For each x Î X, there is only one y Î Y such that (x, y) Î f.

Note that the second condition merely means that f has to be one-one or many-one. In other words, one-many is not allowed. Also note the fancy expression (x, y) Î f. This should make sense in light of the fact that f itself is a set. Remember our Set Theoretic definition of a Relation as a subset of the Cartesian product set X ´ Y. Also note that the first condition guarantees a y for each and every x.

A function from set X to set Y is written f: X ® Y.

x ® f(x)

Set X is called the Domain, and set Y is called the Co-domain. As mentioned earlier, by definition of a Function, for every x there is an f(x). This condition, that for every x, f must point to a single y clearly is sometimes referred to by the phrase "well defined". So by definition, a function must be well defined and "exhaust" the set X. However, f does not necessarily need to exhaust the set Y. If f does exhaust Y, that is, if for every y in Y there is some x in X such that y = f(x), then we say f is onto.

Note also, that f cannot take any x outside of Y. In other words, for every x in X, f(x) must be in Y.

The collection of all places in Y where f could possibly take an x is called the Range of f. This subset of Y, which is the set of all y such that y = f(x) for some x, is called the Range of f and written Range(f). That is, Range(f) = { y | y = f(x), xÎ X }. If it happens that Range(f) = Y ( that is, Range = Co-domain ) then we say f in onto.

You are probably very familiar with the concept of one-one functions. Let's talk about it a bit anyway. We already know that the definition of functions guaranties that for every x there is only one y. If in addition, for every y there is only one x then we say f is one-one. With a little bit of thought you can translate this sentence into its analytical counterpart:- f is one-one iff "f(x₁) = f(x₂) implies x₁ = x₂".

In Set Theory functions that are one-one are called Injections. Functions that are onto are called Surjections. Functions that are both one-one and onto are called Bijections. Sometimes, a Bijection is called a one-one correspondence.

If f is one to one, then for every y there is only one x. This means that if we reverse the passage we took from x to y through f, the reverse relation will indeed be a (new) function from Y to X. This new function from Y to X is called the inverse of f and is written f ^-1. Thus, f ^-1 exists only if f is one to one. Also, f ^-1(y) = x, provided f(x) = y.

Exercise 10: Suppose R₀ = { x: x Î R, 0 £ x < 1 } and f(x) = x / ( 1- x ). Show f: R₀ ® R⁺ is well defined, one - one, and onto.

Exercise 11: Name a bijection f such that f: R ® R⁺

Exercise 12: Suppose f and g are one to one. Prove the composition f ° g is one to one.

Exercise 13: Suppose the inverses of f and g exist. Prove ( f ° g ) ^-1 = g ^-1 ° f ^-1

Exercise 14: Given two bijections f and g from A to B and C to D respectively, find a bijection from S to T, where S = B È D and T = A È C.

Exercise 15: Given one-one correspondences f: A ® B, and g: C ® D, find a one-one correspondence from A ´ C to B ´ D.

Set of all Functions from set A to set B :- B^A

Earlier, you saw a brief account of why Power sets are important in the Theory Of Transfinite Cardinals. Another set that is important for the same reason is the Set of All Functions from a given set A to a given set B. It would be easy if we start with finite sets. For instance, let A = { a, b, c } and B = { 0, 1 }. Now let's define some functions from set A to set B. Bear in mind that we are not imposing any conditions on the functions. They could be one-one or many-one. ( One-many is not a function ). They could be onto or not.

a b c

¯ ¯ ¯

0 0 0 - - - - - - f₁

0 0 1 - - - - - - f₂

0 1 0 - - - - - - f₃

0 1 1 - - - - - - f₄

1 0 0 - - - - - - f₅

1 0 1 - - - - - - f₆

1 1 0 - - - - - - f₇

1 1 1 - - - - - - f₈

Note each row of zeros and ones represents a different function because as long as a single element of A ( that is, a, b, or c ) goes to a different place, even if all the rest goes to the same old places we still have a new function. Note also, that the first and the last rows represent constant functions, but who cares; they are functions too. Are you convinced that all possible functions are there? How many onto functions do you see? Are there any one-one functions?

There are 8 different functions. It happens that 8 = 2³, and there are 2 elements in set B, and 3 elements in set A. If we denote the number of elements in set A by |A| and the number of elements in set B by |B|, then the number of elements in the set of all functions from A to B seems to be |B| ^|A|. For this reason the set of all functions from set A to B is denoted by B^A. Note that it is not A^B.

We can make sense of the formula |B| ^|A| in the following manner. Each member of set A has to go somewhere in B. Each member of A has a choice of two possible destinations, either 0, or 1. Each different destination represents a different function. There are three members of A, each with a choice of 2 different destinations, and the choice made by a particular member of A is independent of the choices made by the other members. Hence we have 2.2.2 = 2³ choices, or functions.

A Taste of Things to come: A definition of Reals and a proof of |R| = 2^|N|

So far, in our elementary approach to sets we have developed some impressive results, such as 2 ^|A|, |A| ´ |B|, and |B| ^|A| concerning the number of elements in various sets. We have to keep in our minds, that we only proved these results for finite sets. At the moment we have no clue about the number of elements in an infinite set. Does it even make sense to talk about the number of elements in an infinite set, other than to say it has an infinite number of elements? Of course we know some infinite sets have more elements than others. For instance, the set of integers and the set of even numbers are both infinite sets, but we know there are more elements in the set of integers than in the set of even numbers. We also know that there are still more elements in the set of real numbers. Are these enough reasons to suspect that there may be more than one infinite? I don't think so. Is this enough to motivate at least an investigation of the sizes of infinite sets? I still don't think so.

Almost a hundred years ago, the motivation came to Georg Cantor, from an entirely different perspective, while investigating a topic from an entirely different area of mathematics, rather applied in nature, that of the Fourier Series. (Today, the main application of Fourier Series is in Electrical Engineering!) He was "forced against his will, by the shear flow of logic….", to consider the possibility of different infinite sizes. ( The story of exactly how Cantor was forced against his will, is a fascinating one. What is more, the mathematics involved is quite within the reach of a second year university student. It is a long story though, and consequently has to wait for another day!) It is in order to study the infinite, that Cantor developed the Theory of Sets. So, whatever we studied so far about the finite sets must have passed through the mind of Canter in a flash, before he went on to infinite sets. But we, on the other hand, are already so tired!

But before we retire, let's take a peek at the beautiful world of infinite sets Cantor created. The following discussion will give you a taste of the impressive things you will be able to accomplish. The result you are about to derive is usually proven at the end of the study of Transfinite Cardinals, yet you are going to do it "in a way" right after the introduction! Recall a few paragraphs before we asked the question if the infinite in the set of reals is any different from the infinite in the set of integers. We will derive a result that shows the relationship between these two infinities. You can go to sleep with the sense of accomplishment you feel after deriving this result.

Before we worry about the size of the set of real numbers, we have to think about how are we defining the reals. We can define integers easily, and we can define rationals as ordered pairs of integers. The problem is with irrationals. But we know between any two rationals, no matter how close, there is an irrational. This tells us that perhaps we can define an irrational by the rationals to the left of it and the rationals to the right of it. Imagine the real line and a single irrational sitting somewhere on it. To the left of it, we have an infinite set of rationals and to the right of it we have another infinite set of rationals. If you take the infinite set of rationales to the left, for example, we may not know what is the last or the biggest rational in that set, but what we do know is that it is a subset of the set of rationals. We can define an irrational in terms of these two infinite subsets of rationals, one to the left and one to the right. What is more, we can totally forget about one of them, say the one to the right, and talk about the infinite subset of rationals to the left of the irrational we want to define.

What we have come to realize is, that associated with each irrational is a subset of rationals. Now from the opposite angle, we also have that corresponding to each subset of rationals, there is a unique irrational. ( Do not think this irrational number is in the subset of rationales we are talking about. ) A bit of reflection tells us that what we just said about an irrational number is also true about every rational number. This is because, between any two rationals, there is always another rational. This means that we can define the entire reals in the same way as we defined the irrationals. Corresponding to every subset of rationals there is a unique real number, and corresponding to every real number is a subset of rationals. In other words, a real number is uniquely determined by a subset of the set of rational numbers to the left of it.

That leads us to the amazing conclusion that the "number" of reals, (or size of the set of reals,) must be the same as the "number" of subsets of the set of rationals, (or the size of the power set of the set of rationals). If we can extend the formula for the power set of a finite set we proved earlier, we have,

|R| = |P(Q)| = 2 ^|Q|. Now, you have probably heard of the result |Q| = |N|. Thus we have the famous result |R| = 2 ^|N|.

You have probably realized by now that the ease with which we derived this result has a lot to do with the fabulous way we defined the real numbers. This way of defining reals is due to the famous mathematician Dedekind who is a contemporary and friend of Cantor. Dedekind defined a real number using the two sets of rationals on either side of it. For this reason, his method is often referred to as the "Dedekind's cut".

Another way of defining the real numbers that you must know is to think of them as the limit of a converging infinite sequence of rationals. For example, if you remember Taylor Series, the irrational number e can be defined as the limit of the partial sums of the infinite series:- e = 1 + 1 + 1/ 2! + 1/ 3! + 1/ 4! + . . . As a more telling example, the irrational Ö 2 can be defined as the limit of the sequence defined recursively by A₁ = 2, and A _{n +1} = A _n - ( A_n² - 2 ) / ( 2A_n ). Notice every number of this sequence is rational. Assuming this sequence converges ( which can be proven using the bounded above, non-decreasing properties ), you must be able to show easily that the limit is indeed Ö 2.

Counting beyond the finite

Suppose we want to compare the sizes of two infinite sets. Counting the elements of each set is not going to work, as we will never finish counting! Therefore we must find another way. Let's go back to finite sets for a moment. Consider the sets A = {a, b, c, d} and B = { p, q, r, s}. We say they are of the same size and usually justify this by saying they both have 4 elements. Suppose we justify this in a different way. Suppose we say there is a one-one and onto function f from A to B, and hence they are of the same size. One way of defining such a function is as follows.

f: A ® B

a ® p

b ® q

c ® r

d ® s

We say the existence of such a bijection or one-one correspondence f , tells us that the sets are of the same size. This method has the advantage of being workable also with infinite sets. This is exactly what Cantor came up with to compare the sizes of infinite sets. We will say two sets have the same size if there is a bijection from one to the other. We will rigorize the concept of "same size" and define a Relation called "Equinumerousity". Then, as a first step towards our study of the Transfinite Cardinals, we will define "Cardinal Equality" using Equinumerousity.

Equinumerousity Relation and Cardinal Equality

Two sets A and B (finite or infinite) are Equinumerous if and only if there is a Bijection between them. Remember a bijection is a one-one function that exhausts both sets. We will use » to indicate this relation.

A » B iff $ a bijection f such that f: A ® B

Other words that were at times used to describe the same relation between sets are, "Equipotence", and "Equivalence". While the word Equivalence is completely outdated, the word Equipotence is still used by some authors to mean Equinumerousity.

Cardinality of a set is a property that has to do with the size of the set or how "numerous" the set is. Roughly speaking, we can think of cardinality as a "number" that represents the size of a set. For finite sets the cardinality of the set is equal to the number of elements in the set, which means it is just an integer. The most general definition of the terms Cardinality of a Set, and Cardinal Numbers, that includes infinite sets, is something that we won't be able to produce at this stage of our study. However we will begin to use the word Cardinality in a limited sense right away. Particularly, we will define what we mean by Cardinal Equality, straight away. Soon, we will also define Cardinal Inequalities.

Two sets have the same Cardinality if and only if they are Equinumerous with each other. We will use the notation |A| to mean the Cardinality of set A.

|A| = |B| if and only if A » B

For instance, consider the set of Natural numbers N = {0, 1, 2, 3, . . . } and the set of non-negative Even numbers E = {0, 2, 4, 6, . . . }.

There is a bijection f given by

f: N ® E

f(n) ® 2n

Therefore E » N or |E| = |N|.

Exercise 16: Argue carefully and analytically why the function f above is indeed onto.

Exercise 17: Find a bijection g(n) between the set of natural numbers N and the set of integers Z and conclude Z » N.

Equinumerousity is an Equivalence Relation

Obviously, the first property of equivalence, Reflexivity, is satisfied by » , because any set is Equinumerous with itself. If you want to rigorously prove this, consider the identity function f(x) = x from set A to set A.

Let's prove the relation satisfies the second property, Symmetry. That is, A » B Þ B » A.

A » B implies there is an one-one and onto function f from A to B. Since f is one-one, the inverse function f ^-1 exists, and since f is a function, the Range of f ^-1 is A, or in other words, f ^-1 is onto. Since f is onto, the domain of f ^-1 is B. Therefore we have a one-one and onto function g = f ^-1 from B to A. Hence, B » A.

Proving that "Equinumerous" satisfies the third property, Transitivity, is left as the next exercise.

Exercise 18: Prove if A » B and B » C, then A » C.

A Very Useful Property

Note that from the Transitive property of the Equinumerousity proven above, we have a very useful property of Cardinal Equality.

If |A| = |B| and |B| = |C|, then |A| = | C|

In the many exercises and problems you are going to do in the future involving Cardinality, you will be using this property frequently, often without even pausing to think about it. But keep in mind that the reason you don't think about it is that you are probably mistaking Cardinal Equality for ordinary number equality. In other words, you are making a big blunder, but are saved because Cardinals seems to be obeying the normal rules of arithmetic! So, it is a good practice to stop and state that you are in fact using this property of cardinal equality before you continue with your solutions, as it shows to the instructor, that you have a deeper understanding of what is going on. Also, as you will see soon, cardinals do not obey all the rules of arithmetic!

Further Useful Properties of »

1. If A » B and C » D, then A ´ C » B ´ D.

2. If A » B, C » D, and A Ç C = B Ç D = f , then A È C » B È D.

3. If A » B and C is any set, then A^C » B^C.

Keep in mind that these properties can be translated to corresponding properties of Cardinal Equality, which we will be using in the future.

Exercise 19: Prove the above properties of Equinumerousity.

( Hint: some exercises from the section on functions may be helpful for Ex18 and Ex19 )

Cardinal Non-Equality

If we can find a bijection between two sets we say they are Equinumerous or they are equal in Cardinality. If we cannot do this then we want to say they are not Equinumerous or unequal in Cardinality. But how do we know we cannot find a bijection? When do we stop trying? This shows we have to slightly refine our intuitive idea of Cardinal Non-equality. We can say two sets are Not Equinumerous when we can prove there cannot be any bijection between them. This clearly puts away any ambiguity. But how do we prove there cannot be any bijection? Well, we assume there is one, and arrive at a contradiction!

As an example, let's prove part of a very important result. The full result, known as Cantor's Theorem, says that the cardinality of the power set P(X), of a set X, is strictly greater than the cardinality of the set X. That is, |P(X)| > |X|. Recall that we said that power set is a sure way of "increasing the size". Well, here we go, we at the brink of proving it. At the moment though, we will only prove they are unequal.

Proof: |P(X)| ¹ |X|

Suppose |P(X)| = |X|. Then there is a bijection f from X to P(X). Clearly, f maps the members of X onto subsets of X. For example, if X = {a, b, c, . . . } then f can either map a ® {a, b}, or a ® {b, c}, etc., etc. As you can see an element of X can either get mapped into a subset containing itself or not containing itself. Let A be the set of all elements of X that does not get mapped into a subset containing itself. That is, A = { x | xÎ X, x Ï f(x) }.

Now, since A is a subset of X and f is onto, there must be an aÎ X such that f(a) = A (think about this for a moment). Further, this element a is either a member of set A or it is not. We will now prove both these possibilities lead to contradictions.

Suppose aÎ A. Then by definition of set A, aÏ f(a). But earlier we showed f(a) = A. Therefore aÏ A. We started with aÎ A and end up in aÏ A. So, we have a contradiction.

Suppose a Ï A. Since A = f(a), we have aÏ f(a). That is, aÎ X and aÏ f(a). By definition of set A, aÎ A. We started with aÏ A and end up in aÎ A. Again we have a contradiction.

Therefore f cannot be onto. So, there is no bijection f from X to P(X). Therefore |P(X)| ¹ |X|.

Denumerabilty and Countability

A set that is Equinumerous with the set of Natural numbers is said to be Denumerable. A set that is either finite or Denumerable is said to be Countable. An infinite set that is Countable is said to be Countably Infinite. For instance, consider the sets A = { a, b, p, q, 3, 4 }, Z = { . . . -3, -2, -1, 0, 1, 2, 3, . . . }, D = { 4n + 1: nÎ N }. A is countable because it is finite. Z and D are countable because they are denumerable. Sometimes we will also say Z and D are countably infinite. Furthermore, |A| = 6, and |Z| = |D| = |N|.

There are some important theorems about Countable Sets that we need to learn. But we will wait for a while and look at them after we arm ourselves with a powerful technical theorem that is named after Schroder and Bernstein. In the mean time we will take a brief look at some of Cantor's surprises regarding the countability of certain number sets.

Cantor's Proof That the Rationals are Countable.

You have probably heard about how cantor arranged the positive Rationals on a two dimensional array, so each rational appears at least once in the array. He then deleted the repeated appearance of each number and produced an enumerated list of all positive Rationals. Since the numbers in any enumerated list can be placed in one-one correspondence with the set of natural numbers, he concluded that the set of positive Rationals is denumerable or countable. As one can list a negative rational right next to its positive counterpart, it is easy to see why the set of all Rationals can be enumerated and hence countable. Two-dimensional arrays can be used to prove other results about cardinality as well.

Exercise 20: Use a two-dimensional array to prove N ´ N is countable.

Exercise 21: Suppose A and B are countable. Prove A ´ B is countable. State clearly any properties of Equinumerousity or Cardinal Equality used. ( don't work hard! ).

Cantor's Proof that the Reals are Uncountable

You have probably also heard of the Diagonal Method Cantor used on the decimal representations of real numbers to show by contradiction that the set of real numbers is not countable. You should also know that this technique Cantor invented, called the Method of Diagonal has a broader scope and is also used in other areas of advanced mathematics in proving some important results.

Suppose we used this method of diagonals to prove the set real numbers in the semi-open interval [0, 1), described by the set R₀ = {x: xÎ R, 0 £ x < 1} is uncountable.

In the exercises after the section on Functions, we already encountered the function f(x) = 1/(1 - x) from R₀ to R⁺ that is one-one and onto. Hence |R₀| = |R⁺|. Therefore R⁺ is not countable.

If you had done the next exercise in the same section you would have probably thought of the function g(x) = e^x from R to R⁺. It is one-one and onto. Hence |R| = |R⁺|. So, R is uncountable. This way of arriving at R may be lengthy but we learned a lot along the way. Notably, by the transitive property of the Cardinal Equality, we have |R₀| =|R⁺| = |R|. In other words, in a sense, there are as many real numbers between zero and one as there are anywhere!

Exercise 22: Consider the real open interval (-1, 1). Find a bijection from (-1, 1) to R and conclude |(-1, 1)| = |R|.

You probably realized there is nothing special about the intervals [0, 1) or (-1, 1). In fact the cardinality of the set of real numbers between any two unequal real numbers is equal to |R|. You can prove it in the next exercise.

Exercise 23: Use a linear function to prove | [0, 1) | = | [a, b) |, where a < b and a, b Î R.

Exercise 24: Guess a simple linear function to prove | [0, 1) | = | (0, 1] |.

So, |R| ¹ |N|. We also know that N Ì R. Does that mean |R| > |N| ? It is time we started thinking about Cardinal Inequalities.

Less than or Equinumerous and the Weak Cardinal Inequality

Set A is Less than or Equinumerous with set B if and only if there is a one-one function from A to B. We will also say Cardinality of A is less than or equal to the Cardinality of B if and only if A is less than or Equinumerous with B. Note that the word weak is used to indicate that it is not a strict inequality. ( i.e., not <, but £ ). Put concisely,

A B or |A| £ |B| if and only if $ a one-one f such that f: A ® B

Also note that |C| ³ |D| means exactly |D| £ |C|.

Now consider the following scenario. Suppose A and B are two sets and there is a one-one and onto function from set A to a subset of B, called B₀. Obviously, this same function can be thought of as a one-one (but possibly not onto) function from set A to set B. This means that if A is Equinumerous with a subset of B, then A is less than or Equinumerous with B. Now think of the converse of this statement and prove it to yourself that this is true too. Thus A is less than or Equinumerous with B if and only if A is Equinumerous with a subset of B. Sometimes this statement is used as a definition of Less than or Equinumerous and our definition earlier is derived as a consequence.

A B or |A| £ |B| if and only if $ a bijection f such that f: A ® B₀ and B₀ Í B

As an example, let's prove |N| £ |N ´ N|. All we have to do is to come with a one-one function from N to N ´ N. How about x ® (x, 5) ? There is nothing special about the number 5, any constant natural number would do. Clearly it is one to one, and it is a function. Hence |N| £ |N ´ N|.

Note that the one-one function from N to N ´ N we came up with above is not onto. But if we consider the same function from set N to the set |N ´ {5}| instead, then it is one-one and onto. Also, |N ´ {5}| Ì |N ´ N|. Therefore by the other definition of Less than or Equinumerous, we arrive at the same result, that |N| £ |N ´ N|.

The usefulness of the Less than or Equinumerous, or the Weak Cardinal Inequality will become apparent after we learn that technical theorem we talked about earlier. In the mean time however, while we are at it, let's define the Strict Cardinal Inequality.

Less Numerous and the Strict Cardinal Inequality

A B or |A| < |B| if and only if |A| £ |B| and |A| ¹ |B|

Also note that |C| > |D| means exactly that |D| < |C|.

Given two sets A and B, we already know how to show |A| £ |B|. We also know how to show by contradiction |A| ¹ |B|. As an example let's finish the proof of Cantor's Theorem.

Proof: |X| £ |P(X)|.

We already proved the difficult part, that is, |X| ¹ |P(X)|, right after our definition of Cardinal Non-equality. It only remains to prove |X| £ |P(X)|. To accomplish this we only have to find a one-one function from X to P(X). And x ® {x} is a perfectly good one-one function from X to P(X). It takes a member of X to the single element subset of X containing itself. Thus, we have |X| £ |P(X)|.

We already had |X| ¹ |P(X)|. Hence by definition, |X| < |P(X)|.

|P(X)| = |2^X|

So, as promised earlier, going from a set to its power set is a sure-fire way of arriving at an increased cardinality. But how big is P(X) compared to X? We already know that for finite sets, |P(X)| = 2^|X|. Before we generalize this result to infinite sets, we have to translate the number 2 in this formula into the cardinality of a set. Any set of finite cardinality would do as long as its cardinality is 2. So, {a, b}, {5, 7}, {0, 1} all would do. But the set {0, 1) has a special name in set theory. It is denoted by 2. So we will use the set 2 = {0, 1}. We will prove |P(X)| = |2^X|.

Proof: ##########

Exercise 25: Prove |R| > |N|.

Schroder - Bernstein Theorem

There are situations where we suspect, or know for sure, that there are bijections between two sets A and B, but coming up with one would not be that easy, and would involve a lot of grinding work. Often in these situations, we can easily come up with two different one-one functions one from A to B and one from B to A. And the grinding technical work might involve creating the bijection starting from these two one-one functions that go in opposite directions. If there is a theorem that guarantees the existence of such a bijection, given the existence of the two one-one functions, then our lives would be easy. All we have to do is state the two one-one functions and say according to the theorem there will be a bijection and hence the two sets are Equinumerous. You will be happy know that indeed such a theorem exists and says exactly what we wanted it to say.

If there is a one-one function from A to B and another one-one function from B to A then there is a one-one and onto function from A to B.

And it is known as the Schroder - Bernstein Theorem, after the mathematicians who first proved it independently of each other. At least that is what a lot of people think. Actually, Bernstein actually proved it. Schroder's proof had an error in it. Cantor conjectured it but could not prove it. Before Schroder's error can be corrected, Dedekind produced an entirely different correct proof. So perhaps Dedekind's name should be attached to the theorem as well.

If we remember the definitions of Cardinal Inequality and Cardinal Equality, this statement can be translated to:

If |A| £ |B| and |B| £ |A|, then |A| = |B|.

And it is in this form the theorem is often stated. Obviously, the proof of this theorem depends on constructing a one-one and onto function from the two one-one functions that go in the opposite directions. At first, it might look simple intuitively, but that is not the case. Let's postpone the proof until the end of this section and concentrate on the results we can derive using the theorem.

In an exercise earlier you were asked to find a bijection from the open interval (-1, 1) to R. There are many. The easy one would be tan(kx), where I leave it to you to figure out what k should be. Suppose instead, you are interested in the closed interval [-1, 1], and looking for a bijection to R. This would be very difficult. On the other hand it is pretty easy to come up with two one-one functions ( that are not onto) in either direction. f(x) = x is a perfectly good one-one function from [-1, 1] to R. In the other direction, g(x) = arctan(kx) is a one-one function from R to [-1, 1]. Again you should figure out k. Thus, we have |[-1, 1]| £ |R| and |R| £ |[-1, 1]|. By Schroder - Bernstein theorem we have |[-1, 1]| = |R|.

Let's now use the theorem to derive some important results. Some of them, we may have proven using other methods earlier, but pay attention nonetheless, as the techniques you learn will become useful later. Also, the following two results are of paramount importance from a problem solving point of view. Soon will come across many problems, that we will solve by falling back on these two results.

|N ´ N| = |N|

You are probably aware of at least two methods of proving this. One is by drawing a continuous line on the coordinate plane staring from the origin and moving to (1, 0), then to (1, 1), then to (0,1), and so on. The other is to use a two dimensional array. Let's now prove it using yet another method, that which uses Schroder-Bernstein Theorem and the Fundamental Theorem of Arithmetic.

Consider the one-one functions f: N ® N ´ N g: N ´ N ® N

n ® (n, 3) (n, m) ® 2ⁿ.3^m

Note that g is one-one because of the Unique Factorization Theorem ( or FTA ). Thus |N| £ |N ´ N| and |N ´ N| £ |N|, and by Schroder-Bernstein, |N ´ N| = |N|.

|R ´ R| = |R|

What a surprise! There are as many points on the plane as there are on a line. This was one of the most dramatic of the results Cantor came up with that really annoyed his contemporaries. The concept of Dimension from Geometry has failed to make its presence known in Cardinality! Not only this, but |R ´ R ´ R| = |R| as well !

Again, you have no doubt heard of the way Cantor proved this by proving |(0, 1) ´ (0, 1)| = |(0, 1)|. He mapped (a, b) to c where, c is the number whose decimal representation alternates the digits of the representations of a and b. If you thought that this would be a one-one and onto function, and therefore we are done, you are wrong. Actually, because of a problem with recurring 9's, this function is only one-one. It is not onto! Cantor originally thought this is a one-one and onto function, and mailed his proof to Dedekind. Dedekind spotted the error! ( Hey, that's what friends are for! ).

So, what we have so far is, only |R ´ R| £ |R|. But it is damn easy to show |R| £ |R ´ R|. Consider the function x ® ( x, 0 ), for instance, which is clearly one-one. Hence by Schroder-Bernstein Theorem, we have |R ´ R| = |R|.

You will agree that we are only a stone through away from proving that |R ´ R ´ R| = |R|, or using induction, proving |Rⁿ| =|R|, where nÎ N.

Some Properties of

In our rush to take a peak at the all-important Schroder-Bernstein Theorem, we have over looked some very important properties of the Weak Cardinal Inequality. As these properties are very useful for our study of infinite sets, we will take a look at them now. Before we proceed however, it pays to go back and check the two alternative definitions of Less than or Equinumerous or the Weak Cardinal Inequality. While you are at it why don't you also try to recall the definition of the Strict Cardinal Inequality.

Proof: Straight forward. We know that |A| = |A|. This means that if A is a subset of B, then A is Equinumerous with a subset of B. Consequently, from the definition of Less than or Equinumerous, we have |A| £ |B|.

One very important thing to remember is that A Ì B does not imply |A| < |B|. The fact that A is actually not just a subset but a proper subset is of no use to us; it does not strengthen the cardinal inequality. Even if we had A Ì B, all we can say is merely that |A| £ |B|.

Exercise 26: Produce two counter examples to disprove: A Ì B implies |A| < |B|.

Next we ask which of the properties of an equivalence relation are satisfied by Less than or Equinumerous. Clearly, |A| £ |A|, because we can use the identity mapping as a one-one function from A to itself. Let's skip the second property, and go to the third one, the Transitivity.

Proof: Left as an exercise. Hint: think composition.

As an illustration of the use of the first property of Less than or Equinumerous, let us look at yet another proof that the rationals are countable.

Another Proof that the Rationals are Countable.

Since N Ì Q, we have |N| £ |Q|. Now let's prove |Q| £ |N|. Consider the function from Q to N, that takes q = a / b, to 2^a.3^b, where (a, b) = 1. This function is one-one because of the Fundamental Theorem of Arithmetic. So we have |N| £ |Q| and |Q| £ |N|, and by Schroder-Bernstein, we conclude |Q| = |N|.

We now list three more properties that mix the Weak Cardinal Inequality with Cardinal Equality and Strict Cardinal Inequality.

Exercise 27: Prove the properties above.

Exercise 28: Prove or disprove |A| < |B| and |B| < |C| implies |A| < |C|.

Exercise 29: Prove if |A| Í |B| Í |C| Í |D| and |A| = |D|, then |B| = |C|.

All these properties will be put to good use in the next section.

Infinite Sets

The main purpose of this section is to learn that the smallest infinite set has the same Cardinality as N. We will give a natural and intuitive definition of an infinite set, and talk about a few theorems which are very intuitive as well. We will finish the section with a not so obvious, but imaginative, alternative definition of an infinite set that is due to Dedekind.

A natural way to define an infinite set would be to first define a finite set and then say any set that is not finite is infinite. We can define a finite set following our intuition.

Finite Set

Any set A that is Equinumerous with a set of the form n = {0, 1, 2, . . ., n -1 }, where nÎ N, is said to be finite.

Infinite Set

Any set that is not finite is said to be infinite. This means that in order to prove a given set is infinite, we assume it is finite and derive a contradiction.

Proof: Assume N is finite and use the pigeon hole principle to arrive at a contradiction.

The following theorem essentially says that the smallest infinite set has the same cardinality as N.

Proof:

Part 1: If |A| ³ |N|, then A is infinite.

Suppose A is finite. Then |A| = |n|, for some n. Together with the given |A| ³ |N|, this implies |n| ³ |N|. This contradicts the fact that N is infinite.

Part 2: If A is infinite, then |A| ³ |N|.

The proof of this part involves a lengthy construction that uses the Axiom of Choice.

Corollary: Every infinite set has a countable subset.

Proof: Easily follows from Part 2 of the last theorem. If A is infinite then |N| £ |A|. Using the definition of cardinal £ , there is a subset A₀ of A such that |N| =|A₀|.

The next theorem is a rather obvious fact about finite sets.

Proof:

Part 1: If A is finite, then |A| < |N|.

From definition, A is finite implies |A| = |n|, for some n. Since N is infinite, |n| < |N|.

Now |A| = |n| and |n| < |N| implies that |A| < |N|.

Part 2: If |A| < |N|, then A is finite.

Suppose A is infinite. Then |N| £ |A|. Together with |A| < |N|, this means |N| < |N|, which is

absurd.

As an illustration of the type of problems you must be able to handle by now, consider the following.

Example: Prove if A Í N, then either A is finite or |A| = |N|.

Note A Í N implies |A| £ |N|. Now if A is not finite, then it is infinite, and that means |A| ³ |N|. By the Schroder-Bernstein Theorem we have |A| = |N|.

Proof : Part I: |A| = |B| and B Ì A Þ A is infinite.

Suppose A is finite. This means a finite set is Equinumerous with a proper subset (of itself).

Think about why this is absurd.

Part II: A is infinite Þ There is a B Ì A such that |A| = |B|.

Since A is infinite, it has a countable subset C = { c₀, c₁, c₂, . . . }. Let S = A - C. Consider the

function f from A to A, defined the following way. f(x) = x if xÎ S, f(x) = c_n+1 if x = c_n .

Convince yourself, f is one-one, and Range(f) = A - {c₀ }. Thus |A| = |A - {c₀}|.

Dedekind came up with the formation above and he used this as the very definition an infinite set.

Countably Infinite Sets

Recall that if |A| = |N|, then A is said to be countably infinite, and, a set that is either finite or countably infinite is said to be countable. There are a number of theorems dealing with countably infinite sets that happens to be true for finite sets as well. For this reason it is customary to state these theorems with the word countable instead of countably infinite, although their primary usefulness lies in the infinite cases. This custom also lengthens the proofs, as we have to consider the finite case first and give a separate proof before we moving on to the proof for the infinite case. You should also know that it is very common in set theory to say countable and only mean countably infinite. This kind of sloppiness is prevalent in mathematics in certain areas when we understand the meaning in the context. Some mathematicians even have a fond name for this. It is called PLS after Principle of Licensed Sloppiness. In our proofs of the theorems we will consider only the infinite cases, for two reasons. First and very importantly, the proofs for the finite cases are rather easy and you can figure it out on your own if you wanted to. Secondly, we can always use PLS as our excuse, and claim we only meant the infinite cases anyway.

As was the case throughout our study of Cardinality, you may be unhappy with the lack of rigor in some of the proofs or techniques you will see here. However, these proofs or techniques still should be appreciated for their imagination and more importantly for their value as intuitive aids. Later when we face challenging problems, our first step will always be intuition.

Proof: Left as an exercise. First prove the simple cases of adding or removing a single element. Then you can use mathematical induction.

Union of Countable Sets

Think of the sets of odd and even integers, O and E. We know they are both countable and their union is countable too. This special case is certainly not sufficient to prove that the union of two countable sets is countable. But perhaps we can use this fact together with something that we established earlier. Recall the property that if |A| = |C| and |B| =|D| and A Ç B = C Ç D = Æ , then |A È B| = |C È D|.

Suppose A and B are mutually disjoint countable sets. So, |A| = |O| and |B| = |E|. By the above property, |A È B| = |O È E| = |N|. Therefore A È B is countable.

What if A Ç B ¹ Æ ? Let B \ A = C. Then we have A È B = A È C and A Ç C = Æ . Also C is either finite or countable. If C is finite ( and A is countable ) , then by the last theorem of the last section, A È C is countable. If both are countable and disjoint we proved the union is countable in the last paragraph.

There are other methods of proving this result that are equally important to know. We now state this result as a theorem and list the various proofs. We will only consider the case where the sets are disjoint.

Theorem: The Union Of Two Countable Sets is Countable.

Proof 1: See above.

Proof 2: Suppose A and B are two disjoint countable sets. Since they are countable the elements of each set can be lined up as follows using subscripts that take positive integer values.

A = { a₁, a₂, a₃, . . . } B = { b₁, b₂, b₃, . . . }

We can line up the elements of A È B in the following way and therefore A È B is countable.

A È B = {a₁, b₁, a₂, b₂, a₃, b₃, . . . }

Proof 3: Since A and B are countable there are bijections f and g such that f: A ® N and g: B ® N. Consider the function h from A È B to N defined the following way. h(x) = 2f(x), if xÎ A but 2g(x) + 1, if xÎ B. Remember f(x) and g(x) will be natural numbers and 2f(x) will be even and 2g(x) + 1 will be odd for all x. Also A and B are disjoint. Therefore h(x) is will be well defined and onto. Since f is one-one, 2f will be one-one; since g is one-one, 2g + 1 will be one-one. Thus h is a bijection.

Suppose now we have three countable sets. You must be able to think of at least four different ways of proving their union is countable. Of course the one that looks completely different from any of the above will be the shortest!

Proof: 1. We can line up elements the way we did in proof 2 above. Or,

2. If you think of proof 3 above as something to do with mod 2, now you can use mod n. Or,

3. If you completely lack imagination, you can always use Mathematical Induction!

How far can we stretch this result? The answer is we can go as far as a countably many! But this time we have to look elsewhere for a proof.

Proof 1: Consider the following way of listing N.

1 2 6 7 . .

3 5 8 . . .

4 9 . . . .

10 . . . . .

. . . . . .

. . . . . .

Each row has countably many integers. And there are countably many rows. The elements of each given set can be put to one-one correspondences with the integers of each row. Thus we have established a one-one correspondence between the elements of the union set and the set N.

Proof 2: Consider the straight lines of the form y = an integer in the coordinate plane. That is, lines like y = 1 , y = 2 etc., etc.. Each of these lines has a countable number of points with integer coordinates. For example, y = 1 has …(-1, 1), (0, 1), (1,1)… Each countable set can be put on a single line, such that each element goes to a point on the line with integer coordinates. There are a countable number of such lines. This way we have a bijection from the elements of the union set to the points of N´ N. But we know N´ N is countable. Hence the union is countable.

Proof 3: We rigorize the proof above or the connection between our union set and N ´ N.

There are countable number of sets, which we enumerate S₁, S₂, S₃, . . .S_i, . .

Each set S_i has a countable number of elements that we enumerate a_i1, a_i2, a_i3, . . .a_ij, . . .

We consider the function f from È _{iÎ N} S_i to N´ N that sends a_ij to (i, j).

Clearly f is a bijection, and hence | È _{iÎ N} S_i | = |N´ N| = |N|.

Exercise 28: Prove the union of a countable number of 5 element sets is countable.

Exercise 29: Prove the union of a countable number of finite sets is countable.

Exercise 30: Prove that the roots of all quadratic equations is countable.

Exercise 31: Prove that the set of algebraic numbers is countable.

Exercise 32: Prove that the set of Transcendental numbers is uncountable.

Characteristic Functions and the Proof: |P(X)| = |2^X|

Consider any set X and the specific set 2 = {0, 1}. There is a special class of functions from set X to the set 2, that are very useful. Suppose A is a subset of X. Then by the characteristic function of A on X, we mean the following function.

1, if x Î A

c _A : X ® 2 c _A(x) = {

0, if x Ï A

Characteristic function of A on X is a function from set X to the set 2; it is not a function from A to X or from X to A. This function takes an element of X and tells us if it belongs to the subset A of X or not, using the binary notation.

For a different subset B of X, we will have a deferent characteristic function c _B : X ® 2, and c _B(x) will be 1 or 0 according to whether x belongs or not to subset B.

For each subset of X we can define a characteristic function. This shows there is a one-one function g from the Power set of X to the set of functions from X to 2. Recall our notation of T ^S for the set of functions from set S to set T. Under this notation, the set of functions from set X to the set 2 would be written as 2^X. Thus we have the one-one function g.

g : P(X) ® 2^X

A ® c _A

Now convince your self that this function g is actually onto 2^X. In other words you have to justify the claim that every function in 2^X, that is, every function from X to 2, is in fact a characteristic function of X. This means g is a bijection and we have the following result.

| P(X) | = | 2^X|

It is important to note that all we have shown here is that the cardinality of the power set of X is the same as the cardinality of the set of functions from set X to set 2. In other words,

|P(X)| = |2^X|, where 2^X = { functions f | f : X ® {0, 1} }

Note that the cardinal sign is completely outside of 2^X; we did not write 2 ^|X|, or 2 ^|X|. Later on however, we will define cardinal addition, multiplication, and eventually exponentiation. At that point we will define cardinal exponentiation |A| ^|B| as equal to |A ^B| . Because of this, sometimes, even at this stage, we will write |2^X| as |2| ^|X|, or since |2| = 2, as 2 ^|X|. So finally we have the often seen result

| P(X) | = 2^|X|

Sets of Functions

Consider the sets A = { a, b, c } and B = { 1, 2, 3, 4 }, and the Cartesian product set

A ´ B = { (a, 1), (a, 2), . . . (b, 1), (b, 2), . . . (c, 1), (c, 2), . . . }. We know that a function from set A to set B will have some of the ordered pairs in the set A ´ B. In other words any function from A to B is essentially a subset of A ´ B. Now consider the following subsets of A ´ B.

f = { (a, 1), (b, 2), (c, 3) }
g = { (a, 1), (b, 1), (c, 2) }

h = { (a, 2), (b, 4), (c, 1) }

y = { (a, 1), (a, 2), (b, 2), (c, 3) }

t = { (a, 1), (b, 2) }

We know f, g, and h are functions from A to B. f and h are one-one, whereas g is many-one. y is not a function because it is one-many, and t is not a function from A to B because it leaves out the element c of set A. Thus only certain subsets of A B define a function from A to B. Also note that two different subsets that do define functions define two different functions.

Exercise: What is Range(f) ? Range(g) ? Define yet another function from A to B that is not listed above. Suppose someone said although t is not a function from A to B, it is a function from A₀ to B, where A₀ = … Is she correct? Fill in the blanks.

We now know that functions from set A to set B are certain subsets of A ´ B, that meet special requirements. The set of all the functions from A to B will include all such special subsets of A ´ B. On the other hand, the power set of A ´ B consists of all the subsets of A ´ B, without any discrimination. Therefore the sets of functions from A to B is actually a subset of the power set of A ´ B. Thus we have the following results.

As an example, let's consider the set of all functions from N to N. |F| £ | P(N ´ N) | = | P(N) | = 2^|N| = |R| = c. Thus |F| £ c.

So we have an upper bound on the cardinality of the set functions. Let's try to get some lower bounds. As an example, once again let's consider the set of functions from N to N. Think of the characteristic functions on N. Since 2 = {0, 1} is a subset of N, characteristic functions c : N ® 2 are part of the set of functions from N to N. In other words the set of characteristic functions on N is actually a subset of the functions from N to N.

|C| £ |F|

We know the cardinality of the set of characteristic functions on N is 2^|N|. So |C| = 2^|N| = c. Thus we have |F| ³ c.

Combining the results from the last two paragraphs and using Schroder- Bernstein Theorem, we get |F| = c.

Exercise: Using the method outlined above find the cardinalities of the sets of functions from R to R, and R to N.