Tag: one-to-one correspondence

One to One Correspondence and Hilbert’s Grand Hotel

College Mathematics, Set Theory

In the Understanding Hilbert’s Grand Hotel, we have discussed the brilliant schemes of a hotel manager in accommodating finite and infinite number of guests in a hotel with infinite number of rooms, where each room was occupied by one guest. In other words, the hotel was fully occupied. In this post, I will explain the mathematics behind these schemes. To be able to understand the explanation, it his highly recommended that you read first the post in the link above.

Finite Number Of Guests

In the Grand Hotel problem, during the first night, a guest arrived. The hotel was full, so there was no room available. However, to accommodate the new guest, the manager requested the guest in Room 1 to move to Room 2, the guest in Room 2 to move to Room 3, the guest in Room 3 to move to room 4 and so on. This means that each guest had to move to the room whose number is 1 higher than the the current room number. This leaves the Room 1 vacant.

Now, how is this possible? » Read more

Leave a comment , ,

Counting the Real Numbers

Calculus and Analysis, College Mathematics, Set Theory

If we are in a room full of ballroom dancers where each male dancer has a female dancer partner, and no one is left without a partner, we can say that there are as many male as female dancers in the room even without counting. In mathematics, we say that there is a one-to-one correspondence between the set of male dancers and the set of female dancers.

Pairing Infinite Sets

In the A Glimpse at Infinite Sets, we have learned that if we can pair two sets in one-to-one correspondence, we can say that the two sets have the same number of elements. The number of elements of a set is its cardinality. Therefore, the cardinality of the binary numbers {1,0} is 2 and the cardinality of the set of the vowel letters in the English alphabet {a, e, i, o, u} is 5.

The pairing of sets can be extended to compare sets with infinite number of elements or infinite sets.  In Figure 1, it is clear that it is possible to pair the set of integers with the set of counting numbers in one-to-one correspondence (can you see why?).  Infinite sets whose elements can be paired with the set of counting numbers in one-to-one correspondence is said to be countably infinite.

Figure 1

As a consequence of the analogy above, we can conclude the cardinality of counting numbers is equal to the cardinality of integers (Can you see why?). » Read more

Leave a comment , , , , , , , , , , ,