Infinite Sets

Typically objects that are of interest to us (like numbers, strings, etc.) are studied collectively as a group. This brings us to the notion of a set. Intuitively, a set is a well-determined collection of distinct objects. The objects in a set are called elements or members of the set. The word well-determined in the definition refers to a specific property which makes it possible to identify whether a given object belongs to the set under consideration or not. An object is a member of a set if it is one of the objects in the set.

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?

Russell's Paradox

While the intuitive definition of sets expresses our idea of sets, it has a problem. For any precisely-specified property, we may think that there is the set of all and only the objects that have that property. As examples, consider the set of all primes, the set of odd numbers, etc.

Given any property of things, there exists the set of all things having the property.

Call a set ordinary if it is not a member of itself. For example, the set of all points on a given line is not itself a point and so it is an ordinary set.

Every set is either ordinary or not ordinary.
All sets that we come across are ordinary and it is questionable whether there are any sets that are not ordinary. What about the set of all sets? This set contains itself and is thus not ordinary.

Let $\mathcal{O}$ be the collection of all ordinary sets. Is $\mathcal{O}$ ordinary or not? If $\mathcal{O}$ is ordinary then $\mathcal{O}$ contains $\mathcal{O}$ (since $\mathcal{O}$ is the set of all ordinary sets) leading to the conclusion that $\mathcal{O}$ is not ordinary. On the other hand, if $\mathcal{O}$ is not ordinary then $\mathcal{O}$ contains $\mathcal{O}$ (by the definition of ordinary sets) leading to the conclusion that $\mathcal{O}$ is ordinary.

Therefore, if $\mathcal{O}$ is ordinary then $\mathcal{O}$ is not ordinary which in turn implies that $\mathcal{O}$ is ordinary and so on. This logically inconsistent result obtained even while properly applying accepted ways of reasoning is called as Russell's paradox. This leads us to conclude that $\mathcal{O}$ cannot exist.

There is another paradox called Cantor's paradox that shows that the set of all sets cannot exist. These paradoxes imply that the definition of set is unsatisfactory and we need to be precise while defining any mathematical primitive. How can one correctly define a set?

References

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