Difference between revisions of "Walther375Spring2014 Cardinals versus ordinals: size and counting" - Rhea

Revision as of 09:30, 27 April 2014

How does one measure the size of a set, and is there a way of saying one set is bigger than another, even when they are both infinite? What "numbers" do measure size of infinite sets?

Size of A Set

Cardinal Numbers: In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set.

Ordinal Numbers: In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditary transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals.

From the definition of ordinal comparison, it follows that the ordinal numbers are a well ordered set. In order of increasing size, the ordinal numbers are 0, 1, 2, ..., omega, omega+1, omega+2, ..., omega+omega, omega+omega+1, .... The notation of ordinal numbers can be a bit counterintuitive, e.g., even though 1+omega=omega, omega+1>omega. The cardinal number of the set of countable ordinal numbers is denoted aleph_1 (aleph-1).

This is the standard representation of ordinals. In this representation,

Every set can be well ordered, so every set has the cardinality of a unique cardinal number. The cardinality of a set S, denoted |S|, is the number of elements in S. If the set has an infinite number of elements, then its cardinality is ∞.

Example: |{1, 7, 3}| = 3

Example: |N| = ∞

Two sets A and B have the same cardinality if there is a bijection f:A->B.

Example: The sets A={red, violet, green, yellow} and B={1, 2, 3, 4} have the same cardinality, since there is a bijection from A to B (find one).

A set A is finite (with cardinality n∈N) if there is a bijection from the set {0, 1, ..., n-1} to A, for some natural number n. A set A is infinite if it is not finite.

A set A is infinite if there exists an injection f:A->A such that f(A) is a proper subset of A. A set is finite if it is not infinite.

One Set is Bigger than One Another even if they are both infinite!

Normally, people believe that it is easy to recognize the size of finite set rather than infinite set because we can count the number of elements in finite sizes. For instance, if a class holds 40 people and only 35 people attend the class, thus, we know that the number of seats is larger than the number of people since 40 is greater than 35.

However, you will surprise to know that it is no different if we want to compare the size of infinite sets too! Using the same example above, we can still know that the number of seats is larger than the number of people even if we don’t know the number (how many) of them! How? We can ask everyone to sit down and if there are number of seats left over, so we can conclude that there are more seats than people. This technique is used by Georg Cantor, a great Mathematician to compare the size of sets.

To explain this mathematically, let assume that X and Y are sets. Each element of X is matched with one and only one element of Y. This process is called as a one-to-one correspondence between sets X and Y. If we can construct the one-to-one correspondence between them, then we can say X and Y have the same size (X and Y have the same cardinality).
However, IF every trial to construct the one-to-one correspondence leaves X with elements that are not matched with elements of Y,
THEN we can say that X is larger than Y. (The cardinality of X is larger than the cardinality of Y)

Example

Back to MA375 Spring 2014