# Telling the Story of Infinity

## Cardinality: 1-1 Correspondence

• Cardinality is used for comparing two data sets. If they have the same sizes, we say these two data sets have the same cardinality.
• The 1-1 Correspondence theorem is to compare two data sets one by one. If all elements in one data set match the other data sets, we say they have the same cardinality, if not, they don’t.
• For example, data sets A [1, 2, 3, 4, 5] and B [6, 7, 8, 9 ,10]. In those two data sets, we can make 1 corresponds 6, 2 corresponds 3, and so on. So, we can conclude that A and B have the same cardinality.
• The 1-1 Correspondence theorem is a stable relationship between two data sets. If we conclude that, the data sets A and B have the same cardinality, that means we can find a stable relationship, that given an element in A, to find its corresponding one in B, which is not random but constant, and don’t miss one out.

## Cardinality of the Integers

• This section we compare the natural numbers and the integers to see if they have the same cardinality.
• First, we list some of the natural numbers and the integers to see the difference.
• The natural numbers: [0, 1, 2, 3, …, n-2, n-1, n]
• The integers: [-n, -n+1, -n+2, …, -3, -2, -1, 0, 1, 2, 3, …, n-2, n-1, n]
• The only difference between them is, the integers have lots of negative numbers. So to simplify the question, let’s use the subset of the integers: [-3, -2, -1, 0, 1, 2, 3, …, n-2, n-1, n]. How to make one-to-one correspondence between the subset of the integers and the natural numbers ? Quite simple, right? -3 -> 0, -2 -> 1, -1 -> 0, …, but we can apply this method to the integers, it will cause one infinity append to another infinity.
• Let’s rewrite the integers’ format to this [0, 1, -1, 2, -2, 3, -3, …, n-2, -n+2, n-1, -n+1, n, -n]. We can see the data all flow to the right. Then compare to the natural numbers will be like: 0 -> 0, 1 -> 1, 2 -> -1, 3 -> 2, 4 -> -2, … . So we proved the natural numbers and the integers
do have the same cardinality. And the key to this question is to let them flow to one side.

## Cardinality of the Rationals

• Now, we compare the rational numbers and the natural numbers. Wikipedia says a rational number is any number that can be expressed as the quotient or fraction p/q of two integers.
• The numbers are too complex to us. So, to start with a small group will be a good strategy. Like the last question, we can start with all the positive numbers. But they are still too many to find a solution. So keep narrow down the range. what about the numbers between 0 and 1? They are 0, 1, 1/2, 1/3, 2/3, 1/4, 3/4, …, 1/n, 2/n, …, (n-1)/n. Seems like, we already arrange them as one-to-one to natural numbers.
• Next step is to expand the range to all the positive numbers. We already got all the [0, 1] numbers, and we know that f(x) = 1/x, when x -> 0, f(x) -> infinity. So what if we flip all the numbers in the range [0, 1], will it be all the numbers greater than 1? Let’s make some tests. Say 123/345, doesn’t it exist in our list of [0, 1]? Since n -> infinity, so 123/345 and 345/123 should all be on our list. For now we covered all the positive numbers, and our list is [0, 1, 1/2, 2, 1/3, 3, 2/3, 3/2, 1/4, 4, 3/4, 4/3, …, 1/n, n, 2/n, n/2, …, (n-1)/n, n/(n-1)].
• What about all negative numbers? Use the strategy in the last question, just insert them behind every positive number. Then the list will be: [0, 1, -1, 1/2, -1/2, 2, -2, 1/3, -1/3, 3, -3, 2/3, -2/3, 3/2, -3/2, 1/4, …].

## Dodgeball

• For a specific size N (N is a natural number) to fill in O or X, all the possibilities of combinations should be 2^N. For example, N = 6, as in the video, the possibilities of combinations are 2^6 = 64, and the player one can only fill in 6 rows. So the player two has 64 - 6 = 58 possibilities to win this game.
• Since the player two can only fill in one symbol once the player one finished a row. So the player two just need to focus on the current symbol to make it different from one of the symbols in the last row which the player one just filled in. In the end, the player two will get a row which different with all of the rows the player one filled in.

## Infinite Dodgeball

• Like the statement, I wrote in the last question, the possibilities are 2^N. So to this question, I just need to prove 2^N > N. If you plot f(x) = 2^x, and f(x) = x, you will see that they never intersect with each other. So 2^N will always bigger than N. As N goes infinite, the possibilities of the player two wins will be higher.
• Still, we just need to follow the strategy that the player two only focus on the single row and fill in the different one. Even N goes infinite, the player two will always have a different one with all the rows the player one filled in.