What formal mathematical terms are used to talk about different scales of infinity?

Question

(Sorry, it's a dummy question but I don't have enough math vocabulary!)

Example: the set of all odd integers is infinite in size, but still it's "smaller" than the set of all integers, yes? When one has relationships between infinite sets like that, what is this called by mathemeticians?

This is going into a children's story, so if you can dumb it down for me then I can dumb it down for the children. Hopefully.

Answer 1

The most formal way of saying what you had in mind is that the limit as $n$ tends to infinity of the proportion of the first positive integers that are odd is $\frac12$. As that's probably too formal for your purposes, you might say half of positive integers (or whatever name you give them in your story) are odd in the long run. However, the name for this concept, natural density, should be accessible with an appropriate introduction.

Answer 2

If you're trying to explain this to children, maybe try to explain that two sets have the same size, if you can line up the elements of the sets in correspondence. Do a few examples with finite sets (you can line up your 3 fingers with 3 pencils on the table etc). Now start writing a list of all the integers $$ \dots, -2,-1,0,1,2,3,\dots $$ and then all the even integers $$ \dots, -4,-2,0,2,4,6,\dots $$ But this second list can be written like $$ \dots, 2(-2),2(-1),2(0),2(1),2(2),2(3),\dots $$ Now there is an obvious "line" you can draw connecting each even integer with exactly one integer. Therefore, these two sets have the same size. If you'd like to introduce them to some real terminology, such a correspondence is called a "bijection". This is how we define the size of a set

Answer 3

There is no single notion of "size" of an infinite set appropriate to all context. Here are a couple relevant terms:

Cardinality is a very important notion, and the default notion of size when we talk about the "size" of an infinite set. Cardinality is determined by maps between sets: roughly, $A$ is smaller than $B$ if there is an injection from $A$ to $B$ but no injection from $B$ to $A$, and two sets have the same cardinality iff there is a bijection between them. This is a very coarse notion, however: the set of odd numbers, the set of integers, and the set of rational numbers all have the same cardinality (although the set of reals is different).

If we want to draw finer distinctions, we can either talk about proper subsets: $A$ is a proper subset of $B$ if $A\subseteq B$ and $A\not=B$. So for example the set of odd numbers is a proper subset of the set of integers. This is by far the simplest notion to consider, and - when the sets involved are finite - plays well with cardinality.

However, this is in many contexts to fine: do we really want to say that the set of integers is strictly bigger in "size" than the set of all integers except $17$? In some sense, once we "zoom out" a bit these two sets look more-or-less the same in a way in which the odds and the integers don't. Thinking along these lines leads to the notion of asymptotic density, which is incredibly important in many areas of mathematics but is also much more limited (it only makes sense in contexts where we already have some way to take ratios and limits).

Answer 4

Cardinality is the word you are looking for. If a set is finite and has $n$ elements, then we say its cardinality is $n$. If a set is infinite, then we describe cardinality in terms of other sets.

Two sets $A$ and $B$ have the same cardinality if there is a bijection between them. Rather than defining bijection in terms of functions, it is easy to just use words.

Suppose we have two stacks of poker chips. If the second stack is taller than the first, then it must contain more chips. At the same time, we might have no idea how many chips are in either stack; we just know which stack contains more. Similarly, if the stacks are the exact same height, then they contain the same number of chips, even though we still don't know what this number is.

In this analogy, each stack is a set, and each poker chip is an element of the set. If the two stacks have the same height, then the two sets are in bijection with one another.

Now you can imagine how this generalizes to sets with infinitely many elements. We say that two sets $A$ and $B$ are in bijection if there is some way to systematically pair up each element of $A$ with an element of $B$. This means that every element $a$ in $A$ has exactly one partner $b$ in $B$. No two elements in $A$ can have the same partner in $B$, and every element of $B$ must have some partner in $A$.

In other words, two sets are in bijection if you can get from one to the other by just relabeling the elements.

---

In the math world, here are the basic types of cardinality to know.

1. A set $S$ is finite if it is in bijection with $\{1,2,3,\ldots, n\}$ for some positive integer $n$. In this case we say $S$ has cardinality $n$.
2. A set is infinite if it is not finite.
3. We say that $S$ is countable if it is in bijection with the natural numbers $\Bbb N=\{1,2,3,\ldots\}$. Depending on who you ask, we also call finite sets countable, or rather use the word "countable" to mean "at most countable."
4. If a set is not countable, then it is called uncountable. The standard example of an uncountable set is the set of all real numbers $\Bbb R$.

Perhaps shockingly, it turns out that the cardinality of the integers $\Bbb Z$ is the same as $\Bbb N$, and also the same as that of the rationals $\Bbb Q$. To pair up $\Bbb N$ and $\Bbb Z$, we can do something like

\begin{matrix} \Bbb N: & 1 & 2 & 3 & 4 & 5 & 6 & \cdots\\ & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \cdots\\ \Bbb Z:& 0 & 1 & -1 & 2 & -2 & 3 & \cdots \end{matrix}

Note that to be countable is the same as being able to list out the elements in a sequence. The above pairing can instead be written $0,1,-1,2,-2,3,-3,\ldots$, and this is understood to mean "pair up $n$ in $\Bbb N$ with the $n$-th element of the list." Then we can list out the rational numbers with some creativity: every rational number is a fraction $p/q$, where $p$ and $q$ are both integers. Just focusing on positive rationals for the sake of simplicity, we can make the following table:

\begin{matrix} 0 & 1 & 2 & 3 & 4 & 5 & \cdots\\ 1 & 1 & \frac12 & \frac13 & \frac14 & \frac15 & \cdots\\ 2 & 2 & \frac22 & \frac23 & \frac24 & \frac25 & \cdots\\ 3 & 3 & \frac32 & \frac33 & \frac34 & \frac35 & \cdots\\ 4 & 4 & \frac42 & \frac43 & \frac44 & \frac45 & \cdots\\ 5 & 5 & \frac52 & \frac53 & \frac54 & \frac55 & \cdots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{matrix}

That is, the entries are the number of the row divided by the number of the column. Clearly every positive rational number is listed here, and we can snake along diagonals to write them out in a single sequence: the first diagonal is $0$; the second is $1, 1$; the third is $2, 1, 2$; the fourth is $3, 2, \frac12, 3$, etc. Then the sequence

$$0, 1, 1, 2, 1, 2, 3, 2, \frac12, 3,\ldots$$

contains every positive rational number, probably with a bunch of duplicates. Now we can delete all the duplicates to see that the positive rational numbers are in fact countable, and the same argument shows the same for the set of all rational numbers.

Another classic argument is to show that $\Bbb R$ is not countable, i.e., cannot be listed out in this way. The argument goes as follows: suppose we had such a list of all real numbers $r_1,r_2,r_3,\ldots$. Then construct a new number $x$ such that the $n$-th decimal place of $x$ is different from the $n$-th decimal place of $r_n$. To be concrete, if the $n$-th decimal place of $r_n$ is $1$, pick the corresponding entry of $x$ to be $0$, and if the $n$-th decimal place of $r_n$ is anything else, set the corresponding entry of $x$ to be $1$.

If the sequence $r_1,r_2,r_3,\ldots$ begins with

\begin{align} 3.&\fbox{1}4603432\ldots\\ 9243.&8\fbox{2}9621\ldots\\ -56.&59\fbox{1}943\ldots\\ 93.&901\fbox{7}583\ldots \end{align}

then $x$ begins $0.0101\ldots$. Now the resulting $x$ is a fixed number, which is fully defined and definitely exists, even though we cannot write it out without infinitely many steps. Since $x$ is a real number, it must be contained in our list, so $x=r_n$ for some $n$. But this is impossible because $x$ and $r_n$ are not equal in the $n$-th decimal place.

Answer 5

The key idea, and one that you might be able to explain to children, is that to check if two sets have the same number of elements, you don't need to count: you can compare them side by side, pairing each element of the first set with an element of the second set. For instance, to say that $A=\{a,b,c\}$ and $X=\{x,y,z\}$ have the same number of elements you don't have to known to count to three: you pair, for instance, $$\tag1 a\to x,\ \ \ b\to y,\ \ \ c\to z. $$ No counting, and you have check that both sets have the same number of elements (cardinality is the lingo). The assignments in $(1)$ form a bijection between the two sets. A bijection is a function (an assignment, like in $(1)$) that is injective (no two elements of $A$ go to the same element of $X$) and surjective (all elements of $X$ appear as the result of mapping some element of $A$). When these two things happen you have a bijection.

Now the genius observation is that we can apply the above to infinite sets. For instance consider $\mathbb N$, the natural numbers, and $2\mathbb N$, the even natural numbers. Then you can map $f(n)=2n$: $$ 1\to 2,\ \ \ 2\to 4,\ \ \ 3\to 6,\ \ \ \ldots $$ and you get a bijection. So $\mathbb N$ and $2\mathbb N$ have the same cardinality. If you consider now the integers $\mathbb Z$, you can map $$ 0\to 1,\ \ \ 1\to 3,\ \ \ 2\to 5,\ \ \ \cdots \ \ \ n\to 2n+1\ \ \ \cdots $$ and $$ -1\to 2,\ \ \ -2\to 4,\ \ \ -3\to 6,\ \ \ \cdots -n\to 2n,\ \ \ \cdots $$ and you get a bijection between $\mathbb Z$ and $\mathbb N$. The sets for which there exists a bijection with $\mathbb N$ are said to be countable. As a less obvious example, $\mathbb Q$ (the rational numbers) is countable. But (and this was Cantor's great breakthrough), the set of real numbers $\mathbb R$ is not countable. One can prove that there is no possible bijection with $\mathbb N$. Another example of an uncountable set is the set of (infinite) sequences of $0$ and $1$.

The most common terms to express that two sets $A$ and $B$ have a bijection between them, is that they have the same cardinality. Slightly less common but well understood is to say that $A$ and $B$ are equinumerous. Less common synonyms are equipotent and equipollent.

When there is an injection from $A$ to $B$, but no surjection (for instance, $\mathbb N$ into $\mathbb R$), one says that the cardinality of $A$ is less than the cardinality of $B$, $|A|<|B|$. I'm not aware of other terminology. Of course one can have the reverse relation ("$\mathbb R$ has greater cardinality than $\mathbb N$").