# Cardinality of sets

## 8. Show that a countably infinite number of guests arriving at Hilbert’s fully occupied Grand Hotel can be given rooms without evicting any current guest

“HILBERT’S GRAND HOTEL: We now describe a paradox that shows that something impossible with finite sets may be possible with infinite sets. The famous mathematician David Hilbert invented the notion of the Grand Hotel, which has a countably infinite number of rooms, each occupied by a guest. When a new guest arrives at a hotel […]

## 6. Suppose that Hilbert’s Grand Hotel is fully occupied, but the hotel closes all the even numbered rooms for maintenance. Show that all guests can remain in the hotel

“HILBERT’S GRAND HOTEL: We now describe a paradox that shows that something impossible with finite sets may be possible with infinite sets. The famous mathematician David Hilbert invented the notion of the Grand Hotel, which has a countably infinite number of rooms, each occupied by a guest. When a new guest arrives at a hotel

## 4. Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set.

Relevant definitions: “A set that is either finite or has the same cardinality as the set of positive integers is called countable. A set that is not countable is called uncountable. When an infinite set S is countable, we denote the cardinality of S by א0 (where א is aleph, the first letter of the

## ∗9. Suppose that a countably infinite number of buses, each containing a countably infinite number of guests, arrive at Hilbert’s fully occupied Grand Hotel. Show that all the arriving guests can be accommodated without evicting any current guest

Relevant definitions: “A set that is either finite or has the same cardinality as the set of positive integers is called countable. A set that is not countable is called uncountable. When an infinite set S is countable, we denote the cardinality of S by א0 (where א is aleph, the first letter of the

## 7. Suppose that Hilbert’s Grand Hotel is fully occupied on the day the hotel expands to a second building which also contains a countably infinite number of rooms. Show that the current guests can be spread out to fill every room of the two buildings of the hotel

Relevant definitions: “A set that is either finite or has the same cardinality as the set of positive integers is called countable. A set that is not countable is called uncountable. When an infinite set S is countable, we denote the cardinality of S by א0 (where א is aleph, the first letter of the

## 3. Determine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set

As we always do, let’s first start with the relevant definitions we need to solve this exercise. “A set that is either finite or has the same cardinality as the set of positive integers is called countable. A set that is not countable is called uncountable. When an infinite set S is countable, we denote

## Give an example of two uncountable sets A and B such that A−B is

Let’s refresh the definitions we will need to solve this exercise. Definition: “Let A and B be sets. The difference of A and B, denoted by A − B, is the set containing those elements that are in A but not in B. The difference of A and B is also called the complement of

## Show that if A and B are sets and A⊂B then |A|≤|B|

Let’s start with the definitions. Definition: “Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is a finite set and that n is the cardinality of S. The cardinality of S is denoted by |S|.” Definition: “If there is a

## Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set

As usual, let’s review the definitions before starting to solve the exercise. Definition: “The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write |A| = |B|.” Definition: “A set that is either finite

## Show that a finite group of guests arriving at Hilbert’s fully occupied Grand Hotel can be given rooms without evicting any current guest.

In this case, we first must revisit the paradox of Hilbert’s Hotel. “HILBERT’S GRAND HOTEL: We now describe a paradox that shows that something impossible with finite sets may be possible with infinite sets. The famous mathematician David Hilbert invented the notion of the Grand Hotel, which has a countably infinite number of rooms, each