1. Are there more even than odd numbers ?
2. Are there more even numbers than integers ?
3. Are there more rational numbers than negative integers ?

The basic idea when trying to count infinitely large (or otherwise difficult to count) sets can roughly be described as follows:

• Suppose you are standing in an empty classroom, with a lot of students waiting to get in. How could you know whether there are enough chairs for everyone? You can not count the students, because they walk around too much. So, you simply let in the students, one by one, and take a seat. If all the seats are taken, and no students are left standing, then there was the same number of students as chairs.

Definition 2.1.1: Cardinality
	Let A and B be two sets. We say that A and B have the same cardinality if there is a bijection f from A to B. We write card(A) = card(B). If there exists a function f from A to B that is injective (i.e. one-to-one) we say that card(A) card(B). If there exists a function f from A to B that is surjective (i.e. onto) we say that card(A) card(B).

Examples 2.1.2:

We can now answer questions similar to the ones posed at the beginning: Let E be the set of all even integers, O be the set of odd integers. Then card(E) = card(O). What is the bijection ? Let E be the set of even integers, Z be the set of all integers. Again, card(E) = card(Z). Can you find the bijection ? Let N be the set of natural numbers, Z be the set of all integers. Which set, if any, has the bigger cardinality ?

Definition 2.1.3: Countable and Uncountable

If a set A has the same cardinality as N (the natural numbers), then we say that A is countable. In other words, a set is countable if there is a bijection from that set to N. An alternate way to define countable is: if there is a way to enumerate the elements of a set, then the set has the same cardinality as N and is called countable. A set that is infinite and not countable is called uncountable.

• If a set A is countable, there is a bijection f from N to A. Therefore, the elements f(1), f(2), f(3), ... are all in A. But we can easily enumerate them, by putting them in the following order: f(1) is the first element in A, f(2) is the second element in A, f(3) is the third one, and so on...
• If a set A can be enumerated, then there is a first element, a second element, a third element, and so on. Then the function that assigns to each element of A its position in the enumeration process is a bijection between A and N and thus A is countable by definition.

Note that there is a difference between finite and countable, but we will often use the word countable to actually mean countable or finite (even though it is not proper). However, here is a nice result that distinguishes the finite from the infinite sets:

Theorem 2.1.4: Dedekind Theorem
	A set S is infinite if and only if there exists a proper subset A of S which has the same cardinality as S. Proof

Examples 2.1.5:
	Use Dedekind's Theorem to show that the set of integers Z and the interval of real numbers between 0 and 2, [0, 2], are both infinite (which is of course not surprising).

Proposition 2.1.6: Combining Countable Sets
	Every subset of a countable set is again countable (or finite). The set of all ordered pairs of positive integers is countable. The countable union of countable sets is countable The finite cross product of countable sets is countable. Proof

Think about these propositions carefully. It seems to be contrary to ones beliefs. To see some rather striking examples for the above propositions, consider the following:

Examples 2.1.7:

The set of all rational numbers is countable. The collection of all polynomials with integer coefficients is countable. To prove this, follow these steps: Show that all polynomials of a fixed degree n (with integer coefficients) are countable by using the above result on finite cross products. Show that all polynomials (with integer coefficients) are countable by writing that set as a countable union of countable sets.

A nice example that illustrates how difficult and counter-intuitive the concept of infinity can be is provided by the story of Hilbert's Hotel. This particular version of Hilbert's Hotel has been created by Jillian Gaglione, a former Seton Hall student and avid Yankee (a New York baseball team) fan - with apologies to any Red Sox (a Boston baseball team) fan.

Example 2.1.8: Hilbert's Hotel

Imagine two hotels in Boston, Massachusetts; the Holiday Inn, which has three hundred rooms and Hilbert’s Hotel, which contains a countable infinite number of rooms. The New York Yankees are leaving town after defeating the Red Sox, again! However, their tour bus breaks down and they are forced to get off the bus and stay overnight in Boston. The Yankees, excluding their pitching coach, decide to walk to the Holiday Inn only to find that all three hundred rooms are already occupied. At the same time the pitching coach decides to walk over to Hilbert’s Hotel because he heard it was a nicer hotel. When the pitching coach arrives at Hilbert’s Hotel, he discovers that all of the rooms are taken as well. However, the manager of the hotel, a Mr. Hilbert, is an extremely big Yankee fan and says, after some thought, that he could accommodate one more person. If all of the rooms are occupied, how is the manager of Hilbert’s Hotel going to find a room for the pitching coach? After the pitching coach settles into his room, he calls his two best friends, the right fielder and the shortstop, to tell them to come over to Hilbert’s Hotel for a room. When they arrive at Hilbert’s Hotel the manager informs them that all the rooms are still occupied, but, once again, he can find accommodations for two more people. If all of the rooms are still occupied, how can the manager of Hilbert’s Hotel find room for two more players? The Yankees soon find out that Hilbert’s Hotel was accommodating some members of their team and the manager of the hotel finds himself trying to find rooms for the rest of the members. There were fifty-eight people that need to find a room and still none of the guests have checked out of their rooms. The manager of the hotel says not to worry because he could find rooms for the remaining members. If every room is occupied, how can the manager find enough rooms for the entire team? Throughout the night, rumors spread that the Yankees are staying in Hilbert’s Hotel. Many fans from the surrounding area travel to Hilbert’s Hotel to book a room. When Hilbert looks outside his hotel, he sees a never-ending line of people that wish to stay for the night. But Hilbert wonders how he could find rooms for a countable infinite number of guests ... then he looks outside the hotel again and reassurs the people waiting in line that everyone will soon have a room for the night. How could the manager of the hotel accommodate a countable infinite number of guests?