4
$\begingroup$

(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.

$\endgroup$
13
  • 9
    $\begingroup$ The set of all odd integers has exactly the same size as the set of all integers. $\endgroup$ Mar 14 '20 at 19:23
  • 1
    $\begingroup$ It's called an inclusion order. If you don't mind some lingo, we say that the category of all sets (denoted as $\textbf{Set}$) is a category with structure, and one of those structures is a partial order (given two sets, one can be a subset of the other, or v.v., or neither). $\endgroup$ Mar 14 '20 at 19:23
  • 2
    $\begingroup$ While strictly speaking, the number of odd integers is the same as the number of integers, we can differentiate them by noting that the odd integers are a proper subset of the integers. So, if we denote the set of odd number by $O$, we can write $O\subsetneq\mathbb Z$, or $O <\mathbb Z$. $\endgroup$ Mar 14 '20 at 19:24
  • 2
    $\begingroup$ For sets, the size(or "cardinality") order is described by existence of a injective functions. So the set of all integers is the same cardinality of all odd integers. see this $\endgroup$
    – ℋolo
    Mar 14 '20 at 19:25
  • 7
    $\begingroup$ @DonThousand there is absolutely no need to introduce categories here... It can only confuse $\endgroup$
    – ℋolo
    Mar 14 '20 at 19:25
1
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Right, you can think about sets of the form $\{1,\ldots,n\}$ for increasing $n$. That might be the right approach for OP. $\endgroup$ Mar 14 '20 at 19:35
  • $\begingroup$ So it's OK to talk about the ratio between the size of sets as n increases, yes? There's an aging professor in the story explaining things to the children, and he starts with terms they won't understand, then backs up with something that the reader can grasp. I've gotten some new terms and some understanding of those from others, but the ratio-between-growth-of-sets is something that makes intuitive sense as an explanation. $\endgroup$
    – Stabledog
    Mar 15 '20 at 15:21
  • 1
    $\begingroup$ @Stabledog It has a surprisingly unscary technical term. $\endgroup$
    – J.G.
    Mar 15 '20 at 15:27
  • $\begingroup$ @J.G.: Bingo! "natural density". That's the term and concept that ties this all together I think. So now I think I have enough pieces to proceed, thanks! $\endgroup$
    – Stabledog
    Mar 15 '20 at 15:32
  • 1
    $\begingroup$ @Stabledog Done. $\endgroup$
    – J.G.
    Mar 15 '20 at 15:59
8
$\begingroup$

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).

$\endgroup$
6
  • 1
    $\begingroup$ It might be worth it to provide some intuition on why bijections show cardinality equivalence (the pairing analogy), since OP is new to the topic. $\endgroup$ Mar 14 '20 at 19:33
  • 2
    $\begingroup$ Maybe I'm misunderstanding you, but -- "proper subsets" isn't really a "finer distinction" than cardinality; if it were, then "A has a lesser cardinality than B" would imply "A is a proper subset of B", which it obviously doesn't. And even if you combined cardinality with proper subsets to create a finer distinction than cardinality, that combined notion wouldn't say anything about (say) $\mathbb{N}$ vs. $\mathbb{Z} \setminus \{10\}$. $\endgroup$
    – ruakh
    Mar 15 '20 at 4:17
  • 2
    $\begingroup$ @Stabledog No, because they have the same cardinality, since you can pair them up. If you could tie every sheep to every sheep such that one sheep is tied to each tree, you'd agree that the number of sheep is the same as the number of trees, regardless of how many there are. The same argument applies here. $\endgroup$ Mar 15 '20 at 16:07
  • 2
    $\begingroup$ An injection from $A$ to $B$ means that $|A|\leq|B|$. Assuming AC, we can totally order cardinalities. $\endgroup$ Mar 15 '20 at 16:25
  • 1
    $\begingroup$ @Stabledog No, they have the same cardinality: there's a bijection between them (consider $f(x)=2x+1$). This is what I mean when I say that cardinality is "coarse:" sets which "obviously" differ in size may still have the same cardinality. $\endgroup$ Mar 15 '20 at 16:38
5
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ I like "line up the sets with lines" as a way to communicate, that's helpful. As for formal vocabulary, the story isn't really trying to teach math but it wants to not piss off mathematicians with bad claims :) $\endgroup$
    – Stabledog
    Mar 15 '20 at 15:14
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, Eliot, that's helpful. $\endgroup$
    – Stabledog
    Mar 15 '20 at 15:18
1
$\begingroup$

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$").

$\endgroup$
3
  • $\begingroup$ Thanks, that adds some clarity. But I still don't get how to say what I need to say. If there's a bijection between N and 2*N, then they have the same cardinality? So how does one say "but still, the former is 'bigger' than the latter because they grow at different rates as N increases?" $\endgroup$
    – Stabledog
    Mar 15 '20 at 15:30
  • 1
    $\begingroup$ I added two paragraphs at the end. There is not much variety, because usually one would only talk about this in a mathematical context, and so it is easier to just write $|A|=|B|$, $|A|<|B|$, or $|A|>|B|$. $\endgroup$ Mar 15 '20 at 15:44
  • 1
    $\begingroup$ @MartinArgerami Usually, we use $\leq$ for cardinality, since there's a more natural parallel for it than $<$. $\endgroup$ Mar 15 '20 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.