Infinite Sets

In universe Marvel, there are planets that can communicate with each other and following facts are known.

  1. Each planet has sent a message to at least one other planet.

  2. No planet has received messages from more than one planet.

  3. There is one planet that has not received any message.

How many planets are there in universe Marvel?

No natural number can be the answer to this question!

Finite & Infinite Sets

A set $X$ is finite if there is a number $n \in \mathbb{N}$ and an injection from $X$ to $\{0,1,\ldots,n-1\}$. A set $X$ is infinite if it is not finite. The cardinality of a finite set $X$ is the smallest natural number $n$ such that an injection from $X$ to $\{0,1,\ldots,n-1\}$ exists. 
-   The set of all positive integers is an infinite set

-   The set of all positive even integers is an infinite set

-   The set of all prime numbers is an infinite set
Observe that the empty set $\emptyset$ is a finite set with cardinality 0. $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$ and $\mathbb{R}$ are all infinite sets. The cardinality of a finite set is the number of elements in it. Extending this definition of cardinality to infinite sets is tricky as we would never be done counting the elements of an infinite set. We need a definition that applies to both finite and infinite sets. Before defining the cardinality (or size) $|X|$ of a set $X$, we define how to compare the cardinalities of two sets.

Cardinality

  • A set $X$ has cardinality at most that of a set $Y$ (denoted as $|X| \leq |Y|$) if there is an injection from $X$ to $Y$.
  • Two sets $X$ and $Y$ are of the same cardinality (denoted as $|X| = |Y|$) if $|X| \leq |Y|$ and $|Y| \leq |X|$.
  • A set $X$ has cardinality less than that of $Y$ (denoted as $|X| < |Y|$) if $|X| \leq |Y|$ but $|Y| \not\leq |X|$.
When we say that two sets $X$ and $Y$ are of the same size, we mean that $X$ can be put into a 1-1 correspondence with $Y$. The set $X$ can be put into a 1-1 correspondence with the set $Y$ if it is possible to match each element of $X$ with one and only one element of $Y$ in such a way that no element of $Y$ is left out and no two distinct elements of $X$ are matched with the same element of $Y$. One may wonder why we did not define two sets to be of the same cardinality if and only if there is a bijection between them. It turns out that this definition is equivalent to the one based on injections. Now we are ready to pose an interesting question: Are all infinite sets of the same size?

Cardinality Games

Imagine that you and I are immortal. I write down a positive integer $n$ on a piece of paper and fold it up and tell you that every day you have one guess as to what $n$ is. If you guess correctly you get a prize. Is there a strategy that will enable you to be sure that you will get the prize sooner or later?
Guess in the order 1, 2, 3, 4, 5, ...
Next, I write down a positive integer or a negative integer $n$ on a piece of paper and fold it up and tell you that every day you have one guess as to what the number $n$ is. If you guess correctly you get a prize. Is there a strategy that will enable you to be sure of winning the prize sooner or later?
Guess in the order 1, -1, 2, -2, 3, -3, ...
Next, I write down a fraction $a/b$, where $a$ and $b$ are positive integers. Again you have one and only one guess each day as to what fraction I wrote. What strategy would enable you to be sure of sooner or later naming the fraction I wrote?
Guess in the order 1/1, 1/2, 2/1, 2/2, 1/3, 3/1, 2/3, 3/1, 3/3,...
This time I write down some finite set of positive integers. You are not told how many integers are in the set, nor what is the highest number in the set. Is there a strategy that will ensure that you get the prize sooner or later?
Hint: For a natural number n, how many finite sets have the maximum element as n?

An Intriguing Game

A certain mathematician has a book called Book of Sets with the pages numbered consecutively from 1. The Book of Sets has infinitely many pages, but these pages are in a 1-1 correspondence with the set of positive integers. On each page is written a description of a set of positive integers. A set which is listed on a page in the Book of Sets is called a listed set. Call a number $n$ an extraordinary number if $n$ belongs to the set listed on page $n$ and call $n$ an ordinary number if $n$ does not belong to the set listed on page $n$. Can the set of ordinary numbers be listed in the Book of Sets? 
What about the set of extraordinary numbers?

References

  1. The Gödelian Puzzle Book by Raymond M. Smullyan.
  2. https://www.ias.edu/ideas/2016/pires-hilbert-hotel