Math 301 - Introduction To Analysis - Schedule

Please Login to access more options.

How do we determine if two sets have the same number of elements? If both sets are finite, the answer is simple as you can count the number of elements. However, what if both sets have infinitely many elements? The sets $\mathbb{Z}$ and $\mathbb{N}$ both have infinitely many elements. How do we compare the size of these sets?

We could say there more than two times as many integers as there are natural numbers. This is because we can see an injection $f:\mathbb{N}\to\mathbb{Z}$ defined by $f(n)=n$, and this injection misses all the negative integers and zero.

To help us build some intuition, let's examine a classical fun way to look at this issue. It involves a rather strange hotel that has infinitely many rooms.

Problem: The Hilbert Hotel

Sally owns a rather strange hotel. This hotel has infinitely many rooms which are numbered 1, 2, 3, 4, .... Business has been good, and Sally manages to fill the entire hotel. Frank, Sally's brother, shows up at the main lobby and asks to get a room. The front clerk says, "Sorry, we're full." Luckily Sally overhears this comment and interrupts by saying, "Frank, I think we can find a room for you. We may have to ask some people to switch around rooms, but we can fit you in." Sally comes to you and asks you to find a room for Frank.

Prepare new room assignments for every single occupant in Sally’s hotel so that after each occupant has moved to their new room, there will be an empty room available for Frank. In other words, if someone is currently in room $k$, which room do you want them to move to, and in which room will you put Frank. You’re allowed to move as many people in the hotel as you want, but you can’t make anyone share rooms.
If George, who is Sally's cousin, had shown up at the same time as Frank, how could you have prepared the room assignments to make space for two empty rooms?
If $n$ people show up to Sally's full hotel, how can you make room for $n$ extra people?

Definition: Cardinality

Suppose $A$ and $B$ are two sets. The cardinality of $A$ is written $|A|$.

We say that the cardinality of $A$ is finite if $A$ has finitely many elements. Otherwise, we say that the cardinality of $A$ is infinite.
If $A$ has finitely many elements, say $n$ elements, then we write $|A|=n$.
If there is an injection $f:A\to B$, then we write $|A|\leq |B|$.
If there is a surjection $g:A\to B$, then we write $|A|\geq |B|$.
If there is a bijection $h:A\to B$, then we write $|A|=|B|$. Two sets have equal cardinalities if and only if there is a bijection between the two sets.

Problem: Several Countably Infinite Sets

What does the Hilbert Hotel Problem tell us about the cardinality of $\mathbb{N}$ and $\mathbb{N}\cup \{0\}$? What about the cardinality of $\mathbb{N}$ and $\mathbb{N}\cup \{0,-1,-2,-3,-4\}$? Which has a greater cardinality, or are they the same? Why?

Definition: Countably Infinite, Countable, Uncountable

Let $A$ be a set.

We say that $A$ is countably infinite if $|A|=|\mathbb{N}|$.
We say that $A$ is countable if either $A$ is a finite set or $A$ is countably infinite.
We say that $A$ is uncountable if $A$ is not countable.

What happens when you start combining sets whose cardinality is infinite? Some might call the results below strange, while others might call them beautiful.

Problem: Finite Products of Countable Sets

Business has been really good for Sally, so her brother Frank decides to open another hotel across town, next to the river. Both Sally and Frank manage to fill their hotels completely every night (really good business). However, a week of excessive rain causes the river to flood, and Frank has to find lodging for all of his hotel guests (quite a feat). Frank calls Sally (whose hotel is full) and he tells her about the problem. Sally immediately says, ``Oh, I've got room for all your guests. Bring them over.'' Since you were the one who figured out how to make room for Frank, George, and $m$ friends, Sally figures you can find a way to fit in an extra infinite number of guests. She asks you to prepare the room assignments for all of Franks guests. Not wanting to disappoint her, you accept the challenge.

Prepare new room assignments for every single occupant of both hotels. If someone is currently in room $k$ in your hotel, which room should they move to? If someone was in room $j$ of Frank's hotel, which room will you give them in your hotel? You can't make anyone share rooms. Sally would also like you to make sure the hotel is still full when you're done (if there are vacancies, it might look bad, we have to keep up appearances).
George, remember Sally's cousin, decides to open a hotel as well (he puts it next to a lake). A month later, severe flooding causes both Frank and George to vacate their hotel. All three of Sally, Frank, and George have completely full hotels, but Sally tells the boys to bring all their guests over and she'll fit them all into the hotel. She then tells you to make room assignments.

Problem: Countable Products of Countable Sets

One night, Sally decides to take her hotel plan and sell the concept to potential investors. The idea is quite popular, and she fills each room in her hotel with someone who wants to build a hotel just like hers. For sake of ease, we'll name the new entrepreneurs $p_1, p_2, p_3, \ldots.$ Every entrepreneur goes out and opens a new hotel (businessman $p_k$ opens hotel $H_k$) that is just like Sally's. After a few months, every single hotel $H_k$ is filled to capacity. The business men $p_k$ decide to have a party in recognition of Sally, and as part of the party they decide that everyone should bring all their occupants to Sally's hotel on the same night (so there will be an infinite number of hotels, each bringing infinitely many guests). Sally decides to clear her hotel of all guests for the day, so her hotel is empty to start with. She asks you to prepare room assignments for all the inhabitants of all the hotels. Sally insists that you can do this.

Your job is clear. When each guest arrives, they tell you which hotel $H_k$ they came from, and then they tell you which room number $j$ they were occupying at hotel $H_k$. How will you make the room assignments so that you can fill every single room in Sally's hotel with exactly one occupant? Which room will you assign guest $(j,k)$ to ($j$ was their old room assignment in hotel $H_k$)?

Problem: An uncountable set

One day, an alien space ship lands next to Sally's hotel. They had heard about her hotel and its amazing feats from an intergalactic newspaper. The alien ship is quite full, and Sally is having a hard time remembering names. She discovers that you can name all the aliens if you name them $a_x$ for each $x\in \mathbb{R}$. The aliens want to all stay in Sally's hotel, so Sally asks you to prepare room assignments for them all. You tell her it can't be done. She insists that it can be done, but you are firm in your convictions and tell her that it can't be done (you're not discriminating against aliens, rather you are just stating a fact). Sally doesn't believe you, so she prepares the room assignments herself. She brings you a list that says which alien should be in room 1, which alien to put in room two, etc. Before she takes it to the ship, she ask you to look over the list to make sure she hasn't missed anyone.

Your job is clear. Show Sally why her room assignment plan is missing an alien. In other words, give her a counterexample that proves here list is incomplete.

When you complete this problem, you'll show that the cardinality of the real numbers is larger than the cardinality of the natural numbers. This proves that $\mathbb{R}$ is an uncountable set. There are different sizes of infinity.

For more problems, see AllProblems