Which of these sets is bigger?

Question

I am a fourth year computer science student and I am taking second year level maths because they are very useful for computer stuff.

At the end of the linear algebra lecture the Prof left us with a question to think about.

Which of theses two sets is "bigger" (contains more elements?).

The set of positive integers from $0$ to $\infty$ OR the set of reals inclusive $0$ to $1$?

My intuition tells me they are the same size (infinity).

I suck at math but its so useful for computer vision (my field) and I am trying to get a better understanding of pure maths.

Thanks!

Answer 1

The key question here is what do we mean by "size". How do you count an infinite set? Aren't they both infinite?

When we count a finite number of things, one way of thinking about it is that we designate each thing with a counting number - so to count the number of people in a room, I designate each person a consecutive number and the number of people in the room is the largest number. There are $n$ people in a room if we can map the people in the room with the set $\{1,2,\ldots,n\}$.

Mathematically, we can extend this concept. Two sets have the same "size" or cardinality if there is a bijection - i.e. a "complete" one-to-one mapping between the two sets.

For example, there is a bijection between the set of integers $\mathbb Z$ and the set of even integers $2\mathbb Z$ given by $$\mathbb Z \to 2\mathbb Z\\n\mapsto 2n$$so we can say that these two sets have the same cardinality, even though $2\mathbb Z \subset \mathbb Z$.

However, not all infinite sets have the same cardinality, and it turns out that there is no way of creating a bijective map between $[0,1]$ and $\mathbb N$ - the positive integers. One way of proving this is called Cantor's diagonal argument: suppose we could assign each decimal number a unique positive integer. That means that we could write down a complete ordered list of decimals:

1) $0.a_1a_2a_3\ldots$
2) $0.b_1b_2b_3\ldots$
3) $0.c_1c_2c_3\ldots$
$\vdots$

But I can write down a decimal that differs from each of these: $0.(a_1 + 1)(b_2+1)(c_3 + 1)\ldots$ (where I'll take $9+1=0$ - i.e. addition modulo 10)

Then I've written down a number that wasn't on my list as it's different to every number on the list in at least one place... but that can't be true if my list contained every decimal... so my list can't have contained every decimal.

Answer 2

You can "put" all integers $x$ from $0$ to $\infty$ into the reals in $[0,1]$ by assigning $x$ to $1/x$. You eventually see later, that the other way round it is completely impossible.

Answer 3

Map the integers $n$ to $1/n$ (except $0$), they all fit into $[0, 1]$, but still have all irrational numbers in that range...

Answer 4

The set of positive integers is denoted $\mathbb{N}$. The set of reals between 0 to 1 is denoted $(0,1)$ (exlusive) or $[0,1]$ (inclusive). This is a very basic (but not trivial) problem in infinte set theory and you can find its solution in every book on this subject. The final answer is: $$ | \mathbb{N} | < |(0,1)| = | [0,1] | $$ and it is proven by Cantor's diagonal argument.

Google for Cantor's Diagonal or read in Wikipedia: https://en.wikipedia.org/wiki/Cantor_diagonalization