14
$\begingroup$

I have been studying Cantor's theorem, and I follow entirely that the set of natural numbers $\mathbb{N}$ is countable, as is the set of odd numbers (let's call it $\mathbb{O}$).

I understand his proof that there is a correspondence between the two sets and feel like I could accept that they therefore have the same cardinality based on that ... but ... hold on ...

We know that $\mathbb{O}$ is a subset of $\mathbb{N}$ right? $\mathbb{N}$ certainly contains all of the odd numbers.

We also know that $\mathbb{N}$ contains numbers that are not odd.

So if $\mathbb{N}$ contains all of $\mathbb{O}$ and some other stuff as well then surely it would be totally justified to argue that $\mathbb{N}$ is larger than $\mathbb{O}$?

$\endgroup$
10
  • 8
    $\begingroup$ In the ordinary sense, yes. In the sense of set theory, no. $\endgroup$
    – Bernard
    May 27, 2017 at 23:18
  • 9
    $\begingroup$ Infinite sets behave differently than finite sets. Consider the map $f : \mathbb{N} \to \mathbb{O}$ where $\mathbb{O}$ is the set of all odd numbers. This can be written as a bijection $f(n)=2n-1$ and they have the same cardinality ($|\mathbb{N}| = |\mathbb{O}|$) $\endgroup$
    – Dando18
    May 27, 2017 at 23:24
  • 2
    $\begingroup$ Also a question to think about: if two sets are infinite, than how is one larger than the other? What constitutes their size? This is why we look at the density and countability of sets. $\endgroup$
    – Dando18
    May 27, 2017 at 23:26
  • 1
    $\begingroup$ Take the integers and the even integers (since they are a group and subgroup whereas the odds are not). If you defined "larger" to mean index bigger than 1, then $\Bbb{Z}$ would be larger, $[\Bbb{Z}:\Bbb{2Z}]=2$, but in terms of cardinality both sets are the same size. They can be put in 1-1 correspondence with each other. $\endgroup$
    – sharding4
    May 27, 2017 at 23:29
  • $\begingroup$ puzzling.stackexchange.com/q/44752/31311 $\endgroup$
    – Count Iblis
    May 28, 2017 at 0:28

10 Answers 10

Reset to default
41
$\begingroup$

It depends on your definition of "larger". Once you make that precise, you'll answer your own question.

$\endgroup$
7
  • 2
    $\begingroup$ Interesting, so I understand that as: neither is larger than the other in the standard sense - because both are endless. We are therefore inventing this method of correspondence to define size for this particular purpose. Is that right? $\endgroup$
    – Sam Redway
    May 27, 2017 at 23:29
  • 18
    $\begingroup$ @SamRedway: Close but not quite. It's your idea of "the standard sense" that needs to be fixed. If you have ten sheep in a field and ten rocks in a bag then you can make a 1-1 correspondence between rocks and sheep. So "the normal sense" of comparing the size of two things is exactly the same whether the two things are infinite or finite; if there is a 1-1 correspondence, then by definition they are the same size. The fact that taking something away from a finite set takes it out of 1-1 correspondence with another finite set is a curious fact about finite sets! $\endgroup$
    – Eric Lippert
    May 28, 2017 at 0:56
  • 2
    $\begingroup$ @EricLippert: I disagree. I think in "the standard sense" ten sheep in the field are far larger than ten rocks in a bag (unless it's a really huge bag). Furthermore, even if you say that the two have the same number of elements, we don't usually mean that we can pair them directly. What we do is we count the elements and say that they have the same number if we count up to the same number. This definition does not easily generalise to infinite sets (or at all, in absence of choice; otherwise, you need transfinite recursion), hence the need for the "bijective" definition of equinumerosity. $\endgroup$
    – tomasz
    May 28, 2017 at 14:07
  • 9
    $\begingroup$ @tomasz: What is this thing you call "counting"? If I'd never heard of it, you'd probably explain it by eventually saying that there is a 1-1 correspondance between the numbers 1, 2, 3... and the elements of the set being counted. Your method and my method are the same, except that you've introduced an entirely irrelevant and unnecessary concept that has to be taught. Innumerate shepherds could use my technique to determine if they'd lost a sheep before the invention of counting with numbers. $\endgroup$
    – Eric Lippert
    May 28, 2017 at 14:19
  • 2
    $\begingroup$ @EricLippert: I'm not arguing about hypotheticals, I'm just saying that's how counting is done (even in absence of a precise notion of a number), and that's how most people understand it. It's right there in the name: we are talking about the number of elements. $\endgroup$
    – tomasz
    May 28, 2017 at 14:41
36
$\begingroup$

Imagine that you didn't know that $\mathbb O$ is a subset of $\mathbb N$, or that they have any elements in common. Imagine that you couldn't even inspect the properties of the elements of $\mathbb O$ and $\mathbb N$. Imagine that you didn't even recognize those elements as numbers. To paint a picture, imagine that someone takes a copy of $\mathbb O$ and a copy of $\mathbb N$ and encloses all of their elements in whimsically colored hardwood boxes.

Now, all you know is that $\mathbb N=\{a,b,c,d,\ldots\}$ and $\mathbb O=\{A,B,C,D,\ldots\}$, where $a$ denotes the teal-striped rosewood box, etc. Maybe $a$ contains the number $0$. Maybe $B$ contains the number $3$. But you have no way of knowing that.

Under these restrictions, how will you compare the sizes of $\mathbb O$ and $\mathbb N$? Can you come up with any justification that one is larger than the other?

$\endgroup$
4
  • 7
    $\begingroup$ (There are infinitely many letters in the alphabet, of course!) $\endgroup$
    – Akiva Weinberger
    May 28, 2017 at 15:43
  • $\begingroup$ Recommended you use dots or other simple objects. $\endgroup$
    – Simply Beautiful Art
    May 29, 2017 at 1:23
  • $\begingroup$ It seems to me that if you couldn't inspect the properties of the elements of the sets you wish to compare, then it would be difficult to compare the sets at all. But this only seems difficult because we use properties of the natural and odd numbers in order to set up a correspondence between their elements. In general however, we do not need to know the properties of elements of sets in order to compare those sets. Instead we must know about a certain property by which their elements were generated. However, this property may just be equivalent to giving the cardinal number of the set. $\endgroup$
    – Saud Molaib
    May 30, 2017 at 23:20
  • $\begingroup$ So, if we just had two sets of different colored boxes which seemed to go on forever would we be able to set up a correspondence between the two sets without having any information about the properties of the elements? $\endgroup$
    – Saud Molaib
    May 30, 2017 at 23:25
22
$\begingroup$

For the following lists,

$$1,2,3,...$$

$$1,3,5,...$$

erase the labels, and replace them by dots:

$$\small{\bullet,\;\bullet,\;\bullet,\;...}$$

$$\small{\bullet,\;\bullet,\;\bullet,\;...}$$

Now which list has more elements?

The key idea is that for comparing the "sizes" of two sets, labels shouldn't matter. What matters for determining equal size is one-to-one correspondence.

$\endgroup$
0
9
$\begingroup$

"Larger" means different things depending on the circumstance.

One common notion of larger and smaller comes from partially ordered sets. A partially ordered set is a set $X$, together with a special relation on $X$, commonly denoted by the symbol '$<$'. If $x, y \in X$, the symbol $x < y$ is read as "$x$ is less than $y$," or "$y$ is bigger than $x$." The relation is required to satisfy the following conditions:

1 . If $x, y, z$ are in $X$, with $x < y$ and $y < z$, then $x < z$.

2 . Let "$x \leq y$" mean that $x < y$ or $x = y$. Then if $x \leq y$ and $y \leq x$, then $x = y$.

Note that we are NOT saying that any two elements of $X$ can necessarily be compared. A partially ordered set with this property is called totally ordered.

Thus a partially ordered set gives a notion of elements being bigger or smaller than others. Here are some examples:

1 . Let $X$ be the set of all subsets of some given set $S$. For $A, B \in X$, set $A \leq B$ if and only if $A \subseteq B$.

It is in this sense that the set of odd numbers is smaller than the set of natural numbers.

2 . Let $X$ be the same set as in (1), but this time, set $A \leq B$ if and only if $A \supseteq B$.

So here, the notion of bigger doesn't conform to the usual notion.

3 . Let $X = \mathbb{R}$, and for $x, y \in X$, set $x < y$ to be the usual thing.

This is a total ordering.

4 . Let $X = \mathbb{R}$, but this time set $x < y$ if and only if $|x| < |y|$.

This is actually not a partially ordered set, since $-5$ and $5$ are "less than or equal to each other," yet they are not equal. It does arguably give a good notion of size though: we think of $-10$ as being bigger than $5$ in this sense.

Another common notion of size in mathematics, specifically the size of sets, is cardinality. This is the thing you first mentioned: one say that the cardinality of a set $X$ is less than or equal to that of a set $Y$ if there exists an injective map of $X$ into $Y$.

If the cardinality of $X$ is less than or equal to that of $Y$, and vice versa, then one can show (under some reasonable assumptions) that there exists a bijective map $X \rightarrow Y$. One says in this case that $X$ and $Y$ have the same cardinality. It is in this sense that the set of natural numbers and the set of odd numbers have the same size.

Moreover, one can show that for any sets $X$ and $Y$, one of their cardinalities is less than or equal to that of the other. So we can sort of say that cardinality is a total ordering, but we don't say this to avoid logical inconsistencies. A partial ordering is defined on the elements of a given set, and we don't consider all sets to be members of a given set.

$\endgroup$
6
$\begingroup$

Ponder this. If you have an infinite set, does adding or subtracting a single element make it larger or smaller?

How can it. The set still remains infinite. Measuring the size of the set can no longer be done by counting. Neither set has fewer elements than the other. So we can't say one is smaller than the other.

All right. Now suppose you are talking and say "$A\subset B $ so $A $ is smaller than $B $ ...." and some snot - nosed 5 year old says "Why?" and you say "well, it's smaller because it has fewer elements"

And the brat says "Why?" and you say "Every element in A is in B but there are elements in B that aren't in A so B has more elements than A".

And the kid says "Why?" and you say "If $B $ has $b $ elements and $x $ are the elements in $B $ that aren't in $A $ then $A $ has $b-x $ and $b-x<b $".

And the kid says "Why?" and you say "listen, punk, you start off with $b$ and every time you remove one you make it smaller so you get a smaller set, then a smaller, then a smaller".

And the kid opens his mouth and you expect another "Why?" but instead the pest says "What if the set is infinite?".

And you say "Well, when you remove elements from an infinite set then you get.... oh."

So. No, Being a proper subset and the other set having elements you don't have does NOT mean the subset is smaller or has fewer elelements.

.... but there is a chapter 2 coming...

$\endgroup$
5
$\begingroup$

Consider the correspondence

$n \to 4n-1$

I.e.,

$1\to 3$

$2\to 7$

Etc.

Now it looks like there only enough natural numbers to cover a proper subset of the odds. So does that mean there are more odd natural numbers than natural numbers?

$\endgroup$
4
$\begingroup$

So if $\mathbb{N}$ contains all of $\mathbb{O}$ and some other stuff as well then surely it would be totally justified to argue that $\mathbb{N}$ is larger than $\mathbb{O}$ ?

It surely is! As you point out yourself, we have $\mathbb{O}\subsetneq\mathbb{N}$ and that is exactly in which sense $\mathbb{O}$ is smaller than $\mathbb{N}$. On the other hand, you also correctly noted that there is a bijective mapping between $\mathbb{N}$ and $\mathbb{O}$ so in that sense, it is not the case that $\mathbb{N}$ is "larger" than $\mathbb{O}$. However, this is no contradiction as we apply two different notions of one set being "larger" than another set. What is probably irritating you is the fact that in the finite case these two notions are kind of "consistent" in the sense that:

if $A\subsetneq B$ then $|A|<|B|$

which does not hold in the general case.

$\endgroup$
4
$\begingroup$

This all depends on how you define 'smaller', and how you want to use it. Yes, if $A$ is a strict subset of $B$, then we can reasonably call $A$ 'smaller' than $B$, even if we deal with infinite sets. However, one big drawback of using the strict subset relation to define 'smaller' is that you wouldn't be able to compare the sizes of sets of different elements. For example, $A = \{ a \}$ is now no longer smaller than $B = \{ b,c \}$ .... which is clearly an undesired result.

So, instead of using the subset relation, most of the time mathematicians use Cantor's notion of cardinality to do set-size comparisons. And yes, while this has some unintuitive results (such as there being 'just as many' odd numbers as natural numbers), this notion does allow us to compare 'sizes' of sets with different elements, and it does obey the following properties that one would like such a set-size comparison notion to have, for example:

  • Every set is the same size as itself
  • If $A$ is smaller or equal in size than $B$, and $B$ is smaller or equal than $A$, then $A$ and $B$ are the same size
  • If $A$ is smaller or equal than $B$, and $B$ is smaller or equal than $C$, then $A$ is smaller or equal than $C$
  • For any two sets, $A$ is smaller or equal than $B$, or $B$ is smaller or equal than $A$

Notice that the subset relation has the first three properties as well, but it doesn't have the last property, and so using the notion of cardinality can give us important results that we cannot get using the subset relation.

Of course, this does not mean that you can't use the subset relation, or that using the subset relation can't give you useful results, or that it would be wrong to think of 'smaller than' in terms of the subset relation. For example, given that the set of odd numbers is a strict subset of all natural numbers tells you that here are natural numbers that are not odd, and that is a useful result.

As another example: There are only countably many Turing-machines, but uncountably many functions from natural numbers to natural numbers. So in that case, we use their difference in cardinality to conclude that there are functions from natural numbers to natural numbers that are not Turing-computable. However, suppose that there were only countably many of such functions. Then cardinality would not have helped us prove this result. But if we could have proven that the set of all Turing-computable functions is a strict subset of all such functions, then we would have gotten our result after all.

This example of uncomputable functions shows another important point, and that is that these different notions of 'smaller than' and 'just as many' are often 'vehicles', or a means to an end. And, as such, while we can quibble over whether there really are more natural numbers than odd numbers, for our eventual results this may not matter at all.

Indeed, nothing forces you to use the notion of cardinality when doing set-size comparisons, and indeed we are not forced to say that there are just as many odd numbers as natural numbers. But what you do need to do is to spell out exactly wat you mean when you make claims involving 'smaller' or 'just as many', especially when it comes to infinite sets.

$\endgroup$
2
$\begingroup$

A set is called "Dedekind infinite" if and only if it can be put into one-to-one correspondence with a proper subset of itself.

Example: N = {1, 2, 3, ...} = set of natural numbers is in 1-1 correspondence with O = {odds}, using f(n) = 2n-1, as already noted.

One can prove that a set is Dedekind infinite if and only if it is infinite (in usual sense). It is for infinite sets that we have the seeming paradox noted so far about subsets.

The answer is that we don't use terms like "larger" based on the idea of the subset relation. It is simply not done because it is not useful and it is even confusing insofar as it overlooks this seeming paradox.

N and O have the same cardinality, owing to the bijection f(n) = 2n-1. The fact that O is a proper subset of N is initially confusing, but we never speak of N being "larger than" O.

BONUS: This reminds me of a puzzle. You have infinitely many rooms numbered 1, 2, 3, ... ad infinitum, each filled with a rock. Each room has exactly one rock, and there are no other rooms. I come to you and bring one more rock. How can I arrange to have each and every rock (mine plus originals) in a room, but with no two rocks in one room?

VARIATION: Same as before, but I bring my own infinity of rocks, numbered 1, 2, 3, ... and want to combine with existing infinity so as to have each rock in a room, with no two rocks sharing a room. How?

Have fun!

(Dr. Michael W. Ecker is a retired Penn State U. associate professor of mathematics. He also was editor-publisher of Recreational & Educational Computing in addition to holding other positions.)

$\endgroup$
0
$\begingroup$

What I find curious...

If you say O and N are the same size, how comes that would you remove all numbers found in O from N, there would be an infinite amount of numbers left in N. For me that would be an indicator that the size of N is in fact larger.

Kinda like that, you would always find a correlation for O in N but this is not true for N in O -> qed. N is larger? :-)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .