3
$\begingroup$

This question already has an answer here:

I was in the shower today and I just thought of this so I'm asking it. I'm sure this has been thought of before.

Let's say we have two sets, the set of all even numbers and the set of all natural numbers. They are both infinite, right?

But let's say we cut off the set at any number $n$. So for example if $n = 4$ then the even set would be ${2,4}$ and the natural set would be ${1,2,3,4}$.

So the set of natural numbers is bigger when they both reach 4, since they both increase in the same direction in a linear fashion that doesn't seem to be an unreasonable comparison to me. So if we take $n = \infty$ , then why are both sets the same size? In other words, is it possible that one infinity is greater than another?

I'm sure this is not the case, but can someone please explain? Thanks

$\endgroup$

marked as duplicate by Newb, Pedro Tamaroff, Eric Naslund, Logan M, Grigory M Dec 21 '13 at 6:58

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Before I answer, there are a lot more real numbers than you describe there. Real numbers include every rational number $p/q$ as well as every number in between them - ones that can't be written as a fraction. What you mean to say for your second set is 'the set of all natural numbers'. $\endgroup$ – user98602 Dec 21 '13 at 4:38
  • $\begingroup$ yes, true you're right, thanks $\endgroup$ – Sam Creamer Dec 21 '13 at 4:38
  • 2
    $\begingroup$ The procedure you are using to compare these two sets that lie one inside another is studying the density. For finite sets, if one set is inside another, and they have the same number of elements the density of the set inside is going to be one (equally dense). But for infinite sets, as you pointed out, that doesn't have to be the same. So, the even numbers are in a ratio 1:2 inside the natural numbers in terms of density. This observation tells you that cardinality and density are different notions, the latter depending on how you place a set of number inside another. $\endgroup$ – OR. Dec 21 '13 at 4:52
  • $\begingroup$ See mike's answer about natural densities; note also that there is a big difference between natural numbers and real numbers. $\endgroup$ – goblin Dec 21 '13 at 4:52
  • 3
    $\begingroup$ @Newb, they clearly aren't duplicates. Did you even read the question? $\endgroup$ – goblin Dec 21 '13 at 4:53
5
$\begingroup$

It is certainly possible that one infinity is greater than another. With sets, we generally talk about size in terms of bijections: two sets are the same size if they can be put in bijection with each other (A bijection is a map from one set to the other such that everything is the second set is mapped to exactly once). The two sets you describe have a bijection: we send every even number to half of itself. So in set-theoretic terms, they have the same size. However, there are sets that are strictly larger: what are known as the real numbers CANNOT be put in bijection with the natural numbers. This was proven by Cantor with his diagonalization argument.

The concept you're looking for is known as the natural density. This is a way to count just how much smaller than the natural numbers a given subset is: if, roughly, it has one number for every $a$ natural numbers, then it has natural density $\frac 1a$. Your set is a particularly nice example: it has natural density $\frac 12$ because it has exactly one number for every two natural numbers! At the same time, there are many important sets that have natural density $0$ (in other words, there are far fewer of them than natural numbers in total): the square numbers, for insance, or the prime numbers.

$\endgroup$
  • $\begingroup$ Thanks for the clear explanation. So if two infinite sets have different natural densities, then in a sense one of the infinities is "greater" than the other? Is that a accurate? EDIT: Sorry I guess what I just wrote is wrong, if they have a bijection even if they have different natural densities then they're equal in size? $\endgroup$ – Sam Creamer Dec 21 '13 at 4:51
  • 4
    $\begingroup$ I think that's probably not the right way to think about it - they really are just the same size - but more that one is 'less dense' than another (hence the name density) - that they're more spread out. The squares are eventually infinitely spread out between each square, and primes have pretty big average gaps. While these sets have the same 'size' in the sense of bijections, some are more spread out than the others. $\endgroup$ – user98602 Dec 21 '13 at 4:55
  • 4
    $\begingroup$ Cardinality and density are measuring different things. Roughly speaking, cardinality is measuring how big a set is in unequivocal terms without reference to any other set, while density is measuring how big a specific subset is in relation to the set it's contained in. $\endgroup$ – D Wiggles Dec 21 '13 at 5:06
2
$\begingroup$

I think you're confused about what a real number is. There are infinitely many real numbers less than $4$, including $\frac{1}{2}$, $\pi$, $\sqrt{2}$, etc. Instead of the set of real numbers, you seem to be talking about the set of natural numbers.

But putting that aside, you seem to be talking about the concept of Asymptotic Density for subsets of the natural numbers.

$\endgroup$
  • $\begingroup$ sorry, I'll change the set in my question to natural numbers set $\endgroup$ – Sam Creamer Dec 21 '13 at 4:39
1
$\begingroup$

The short answer is yes, it is possible that one infinity is greater than another. You need to clearly define what this means. In the usual definition, Cantor's diagonal argument shows there are more reals than integers. The long answer is that the subject is (almost) all of set theory.

$\endgroup$
0
$\begingroup$

Yes, you've touched on something that is indeed true and interesting. Some infinities are larger than others, and this is a well-discussed topic on M.SE.

See, for example: different kinds of infinities
are all infinities equal?
You may also find this article on Aleph Numbers informative. Good Luck! I'm voting to close this question as it is fundamentally a duplicate.

$\endgroup$

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