Difference between revisions of "Cardinality"

Revision as of 03:00, August 22, 2010

Cardinality is a measure of the size of a set. For finite sets, its cardinality is simply the number of elements in it.

For example, there are 7 days in the week (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday), so the cardinality of the set of days of the week is 7. Similarly, there are 26 letters in the alphabet, so the set of letters of the alphabet has cardinality 26. As another example, the set of suits for playing cards is 4 (there are four suits, hearts, diamonds, clubs and spades).

One interesting property of finite sets is that when two sets have the same cardinality, they can be put into a one-to-one correspondence (known as a bijection). For example, there are 4 suits in a deck of cards, and four main compass directions (North, South, East and West). Thus, the cardinality of the set of suits in a deck of cards, and that of the set of compass directions, are both four, so the two sets have the same cardinality.

We can place them in one-to-one correspondence as follows: Hearts <-> North, Diamonds <-> South, Clubs <-> East, Spades <-> West. Each suit corresponds to exactly one compass direction, and vice versa.

Similarly, we can put the set of days of the week, and the Seven Deadly Sins in one-to-one correspondence: Monday <-> Pride, Tuesday <-> Envy, Wednesday <-> Gluttony, Thursday <-> Lust, Friday <-> Anger, Saturday <-> Avarice, Sunday <-> Sloth.

Also, if two finite sets have different cardinalities, they cannot be placed in a one-to-one correspondence. If we tried to place the 4 suits, and the 7 days of the week in such a correspondence, we could start with Hearts <-> Monday, Diamonds <-> Tuesday, Clubs <-> Wednesday, Spades <-> Thursday. Then we would have to start repeating suits, which is not allowed for a one-to-one correspondence.

This suggests another definition for cardinality, that two sets have the same cardinality if there is a one-to-one correspondence between them. This is the definition we will use for infinite sets, where the concept of the number of elements of a set is not as clear.

Infinite sets

Infinite sets are sets that go on for ever. For example, the set of natural numbers (1,2,3...) is infinite, as no matter how far we go, there will always be more numbers. An important type of infinite set is the countable set. A set is countable, if it can be written as a list. For example, the set of natural numbers itself is countable. This is where countable sets get their name from, as the natural numbers are sometimes called counting numbers, as they are the numbers we use to count with.

One alternative definition of a set being countable, is that it has the same cardinality as the natural numbers. This is equivalent to saying that there is a one-to-one correspondence between the set, and the set of natural numbers.

One example of a countable set is the set of even numbers. These can be written as a list: 2, 4, 6, 8, 10, 12, 14, 16... Alternatively, they can be put into a one-to-one correspondence with the set of natural numbers: 1 <-> 2, 2 <-> 4, 3 <-> 6, 4 <-> 8, 5 <-> 10,....

Similarly, the multiples of 3 (3, 6, 9, 12, 15...), 4 (4, 8, 12, 16, 20, 24, 28... and so on, each form a countable set, as each can be written as a list.

One unusual property of infinite sets is that a "smaller" set can have the same cardinality as a "larger" one. For example here we see that the set of even numbers has the same cardinality as the set of natural numbers, and thus it is in a sense the same size, even though the set of even numbers misses out a lot of numbers from the set of natural numbers.

Infinite sets are assigned different cardinalities using the hebrew symbol (aleph), for example the natural numbers have cardinality .