14
$\begingroup$

We will call the set of all positive even numbers E and the set of all positive integers N.

At first glance, it seems obvious that E is smaller than N, because for E is basically N with half of its terms taken out. The size of E is the size of N divided by two.

You could see this as, for every item in E, two items in N could be matched (the item x and x-1). This implies that N is twice as large as E

On second glance though, it seems less obvious. Each item in N could be mapped with one item in E (the item x*2).

Which is larger, then? Or are they both equal in size? Why?

(My background in Set theory is quite extremely scant)

$\endgroup$
3
  • 1
    $\begingroup$ For every item in N, two items in E could be matched (4n and 4n-2), so by your logic, E is also twice as large as N. $\endgroup$ Aug 2, 2010 at 23:18
  • 4
    $\begingroup$ It might be a good exercise to try and define what exactly one means by one infinite set being larger than another set. $\endgroup$
    – Aryabhata
    Oct 1, 2010 at 17:14
  • 1
    $\begingroup$ Galileo raised more or less the same question. $\endgroup$
    – bof
    May 6, 2014 at 3:33

9 Answers 9

43
$\begingroup$

Mathematics is the art of clever forgetting. The first mathematical breakthrough, numbers, came about when people realized that if you just forgot about whether it was 5 cows + 3 cows, or 5 rocks + 3 rocks or whatever you always got 8. Numbers are what you get when you look at collections of objects and forget what kind of object they are.

When you say "as sets" you mean you're forgetting a lot of information, in particular you don't care about what the names of the elements in that set are or what properties those elements have. As sets the positive numbers and the positive even numbers are "the same" (that is are in bijection) because you can take 1,2,3,... and just rename 1 to 2, and 2 to 4, and n to 2n, and you've just renamed all the elements and got the even numbers!

However, if you want to remember more about these sets, for example that they're not arbitrary sets they're both subsets of the natural numbers, then they become distinguishable. Depending on how you want to measure "size of a subset of the natural numbers" they might be different sizes. For example, a common way to measure "size of a subset of the natural numbers" is by its "density." That is you look at the first N numbers and calculate what fraction of them are in your set, and then take the limit as N goes to infinity (warning for sufficiently complicated sets this limit might not exist). So for your two examples, one has density 1 and the other has density 1/2, which is one way to make precise the intuition that the former is bigger as a subset of the natural numbers (though not as a set) than the latter.

$\endgroup$
5
  • $\begingroup$ Thanks for addressing the distinction between the two sets :) I think this answer is the most complete. $\endgroup$
    – Justin L.
    Jul 22, 2010 at 0:23
  • $\begingroup$ Unless you have proved that Mathematics is the art of clever forgetting, or else nobody should believe it and use it to solve math questions . $\endgroup$
    – iMath
    Sep 23, 2016 at 12:54
  • 3
    $\begingroup$ The usual term for "clever forgetting" is, of course, abstraction. $\endgroup$
    – celtschk
    Sep 26, 2016 at 18:53
  • $\begingroup$ @iMath What he said is basically the process called "abstraction" which is indeed very useful in modern mathematics. $\endgroup$
    – BigbearZzz
    Sep 26, 2016 at 18:53
  • 2
    $\begingroup$ Actually, the subset relation is a partial order, and in that order the set of positive integers is also strictly larger than the set of positive even integers. Of course in the subset order, the set of positive odd integers is neither larger nor smaller than the set of positive even integers. $\endgroup$
    – celtschk
    Sep 26, 2016 at 19:11
8
$\begingroup$

The word 'size' doesn't have a intuitive meaning for set of infinite items.

Mathematicians defined cardinality by one-to-one correspondence(bijection), and it's generally what it means by 'size'.

If there exist a bijection between A and B, then the two sets have the same cardinality. You have shown the existence of a bijection, therefore E and N have the same cardinality.

You might mean the 'density' of N is twice as large as E. density of A(a subset of natural number) is limit of |{a<=n|a\in A}|/n as n goes to infinity.

$\endgroup$
6
$\begingroup$

They are both the same size, the size being 'countable infinity' or 'aleph-null'. The reasoning behind it is exactly that which you have already identified - you can assign each item in E to a single value in N. This is true for the Natural numbers, the Integers, the Rationals but not the Reals (see the Diagonal Slash argument for details on this result).

-- Added explanation from comment --

The first reasoning is invalid because the cardinality of infinite sets doesn't follow 'normal' multiplication rules. If you multiply a set with cardinality of aleph-0 by 2, you still have aleph-0. The same is true if you divide it, add to it, subtract from it by any finite amount.

$\endgroup$
6
  • $\begingroup$ But what about the first reasoning? Is it invalid? Why? $\endgroup$
    – Justin L.
    Jul 21, 2010 at 22:21
  • 6
    $\begingroup$ because infinity is not a number; 2*"infinity" = "infinity" = "infinity + 1" = "infinity squared" ... they all have the same cardinality if the infinities are all of cardinality aleph-0. $\endgroup$
    – Jason S
    Jul 21, 2010 at 22:23
  • $\begingroup$ Thanks @Jason, I've updated my answer to include that point :) $\endgroup$
    – workmad3
    Jul 21, 2010 at 22:36
  • 1
    $\begingroup$ @Jason: But $2^{\aleph_0} > \aleph_0$ so not all operations behave this way with infinite cardinals. $\endgroup$ Jul 21, 2010 at 23:10
  • $\begingroup$ @Francois: I've heard that one... what does that correspond to? the mapping between an infinite set S and its subsets? $\endgroup$
    – Jason S
    Jul 22, 2010 at 1:28
2
$\begingroup$

Almost all of this misses the idea that you can't do traditional arithmetic with infinity that way that most of us think of it. 10/2 = 5, five is half of 10, no problem. If Judy has five apples and Joe has 10 apples, then it is proper to say "Judy has half as many apples as Joe." But to say "there are half as many even positive integers as there are positive intergers" is to infer something about infinity/2, or half of infinity, which is not entirely kosher.

$\endgroup$
1
  • $\begingroup$ (I've reverted a superfluous comment that only accomplished to remove the answer from its personality.) $\endgroup$ May 6, 2014 at 3:28
1
$\begingroup$

Each item in N could be mapped with one item in E (the item x*2).

Yes. Both sets have cardinality aleph-0.

$\endgroup$
4
  • $\begingroup$ Does this not imply that N is twice as large as E? $\endgroup$
    – Justin L.
    Jul 21, 2010 at 22:22
  • $\begingroup$ Jason S is correct. $\endgroup$
    – user126
    Jul 21, 2010 at 22:24
  • $\begingroup$ No, this does not imply that N is twice as large as E. The sets are in a one-to-one correspondence. Each 2*x in your set E has a unique "pullback" to N. $\endgroup$ Jul 21, 2010 at 22:25
  • $\begingroup$ I misquoted the wrong part of the original post first, sorry about that. $\endgroup$
    – Jason S
    Jul 22, 2010 at 1:29
1
$\begingroup$

Your example is an example of a countable sets: http://en.wikipedia.org/wiki/Countable_set

As others have explained, if you find a bijection between these two sets then they are of the same cardinality or have the same number of elements.(I hope that statement is true :)) But in this case you have found one with N which is what makes it a countable set. f(x)=2x would be an example of a bijection between N and 2N. Since for every x in the set of natural numbers there is a corresponding number in the set of 2N (only one) then you can say that they have the same cardinality.

A cooler example would be the interval of the real numbers (0, 1) and R itself, those are not countable but their cardinality is the same.

Other notes, if you are wondering what aleph is: http://en.wikipedia.org/wiki/Aleph_number

$\endgroup$
1
$\begingroup$

You can also get it the other way around -- N is (kind of) a subset of E.

Map each integer n into 4n. Then there's a bijection (1-1, onto function) between N and (let's call it) N4, the set of all integers divisible by 4, so N and N4 are, in your intuition, of the same "size". But N4 is a proper subset of E ! Of course, you could just as well have mapped N directly to E with bijection f(n) = 2n.

Anyway, that shows you how slippery it is to apply concepts of finite size to infinite sets, and why bijection is the way to go.

$\endgroup$
1
  • $\begingroup$ I think your understanding of bijection is not correct here, Bijection means one-to-one and a surjection (i.e., "onto"). $\endgroup$
    – iMath
    Sep 9, 2015 at 7:07
1
$\begingroup$

In some sense, both perspectives are correct. There is the notion of density and the notion of a one-to-one correspondence.

First let us talk about the one-to-one correspondence. Given two sets $A$ and $B$, a function $f:A\rightarrow B$ is a one-to-one correspondence if $f$ satisfies the property that for every $b\in B$ there is a unique $a\in A$ such that $f(a)=b$.

As a concrete example given the sets $A=\{1,2,3\}$ and $B=\{a,b,c\}$ the function $f:A\rightarrow B$ where $f(1)=a$, $f(2)=b$, and $f(3)=c$ is a one-to-one correspondence.

An example of a function that is not a one-to-one correspondence would be something like $g:A\rightarrow B$ where $g(1)=a$, $g(2)=a$ and $g(3)=b$. This is not a one-to-one correspondence since there is no element of $A$ which maps to $c$ and we also have that the element mapping to $a$ is not unique (as both $1$ and $2$ map to $a$), so this function double fails in being a one-to-one correspondence.

Now we define two sets to have the same cardinality (size) if there is a one-to-one correspondence between them. That is given two sets $A$ and $B$ there is a function $f:A\rightarrow B$ that is a one-to-one correspondence. Thus, in our above example we have that $\vert \{1,2,3\}\vert=\{a,b,c\}$ since we had our one-to-one correspondence $f$.

There is a one-to-one correspondence between the even and whole numbers, we see this as follows. If we let $\mathbb{N}=\{1,2,3,...\}$ be the set of whole numbers, and we let $E=\{2,4,6,...\}$ be the set of even numbers, then we can construct the function $f:\mathbb{N}\rightarrow E$ by $f(n)=2n$, and this will give the one-to-one correspondence. We can check that it satisfies the two required properties, namely, we have that every even number $x\in E$ is of the form $x=2n$ (this is by definition of being even), and we need that given such an $x\in E$ if we write it as $2n$ where $n\in\mathbb{N}$, then this $n$ is unique. You can see this as if $n$ is not unique, then there is some $n'\neq n$ that is there say we could write $2n=2n'$, and rearranging this would imply that $2(n-n')=0$, so $n-n'=0$ and $n=n'$ which is a contradiction. Thus, we must have that the expression is unique, and we have our function is a one-to-one correspondence.

In this view, we have that $\vert \mathbb{N}\vert=\vert E\vert$.

Now to your point where it seems that there should be half as many even numbers as whole numbers. For this to be precise, we shall introduce the notion of density. The way I like to think about density is in terms of probability. That is if I asked for a random whole number what is the probability that it is even? Well, there are infinitely many options to choose from, so we can't just divide infinity by infinity. But what we can do instead is use calculus and take a limit, so let us define $[n]=\{1,2,3,...,n\}$. Then given some set $A\subset \mathbb{N}$, we define the density of $A$ as $$ \lim_{n\rightarrow\infty}\frac{\vert A\cap[n]\vert}{n} $$ If you think of this in terms of probability, it is asking the conditional probability question of given that the number I choose is less than of equal to $n$ what is the probability the number chosen is from the set $A$, and then we take the limit as $n$ goes to infinity to deal with the notion that $\mathbb{N}$ is infinite.

Thus, if we consider the density of $E$ inside $\mathbb{N}$, we will have that the probability sequence will be $$0,\frac{1}{2},\frac{1}{3},\frac{1}{2},\frac{2}{5},\frac{1}{2},\frac{3}{7},\frac{1}{2},\frac{4}{9},... $$ thus, we can see that $$ \lim_{n\rightarrow\infty}\frac{\vert E\cap[n]\vert}{n}=\frac{1}{2} $$ so we get that the density of the even numbers is $\frac{1}{2}$.

To conclude, there is a one-to-one correspondence between the whole numbers and even numbers; however, the density of the even numbers inside the set of whole numbers is $\frac{1}{2}$.

$\endgroup$
0
$\begingroup$

The density argument above is not quite to the point, since it involves not only a set but an ordering.

In fact, if you play with orderings, you can get even stranger results, such as the integers and rationals can both be ordered as a continuum (according to the ordering, between any two members in the set there is another member) and a non-continuum (there are two members with no other member in between). Or worse, between any two members is at most a finite set of other members (non-continuum) or an infinite set of other members (continuum). That's kind of an extreme form of density.

$\endgroup$
0

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.