Principle of counting says that

"the number of odd integers, which is the same as the number of even integers, is also the same as the number of integers overall."

This does not match with my common sense (I am not a mathematician, but a CS student).

Can some people here could help me to reach a mathematicians level of thinking for this problem. I have searched net a lot (Wikipedia also)

  • 4
    $\begingroup$ You probably have never counted them all yet. :) $\endgroup$ – Hagen von Eitzen Nov 21 '12 at 15:54
  • 1
    $\begingroup$ In the inifinite case, it is no longer true that if $A$ is a proper subset of $B$, then the "size of $A$" is strictly less than the "size of $B$." That intuition is true in finite sets, but would prove useless when dealing with infinite sets. $\endgroup$ – Thomas Andrews Nov 21 '12 at 16:04
  • $\begingroup$ Note, most mathematicians don't say "the number of odd integers" because that is confusing the word "number." Rather, we talk about the "cardinality of the set of odd integers." $\endgroup$ – Thomas Andrews Nov 21 '12 at 16:06
  • 1
    $\begingroup$ The thing is, even if you think you do, you have very little common sense regarding «counting infinite sets». You, like most people, are just extrapolating your life-long experience with manipulating finite sets, and there is no reason —if you think about it— to expect things to work the same. $\endgroup$ – Mariano Suárez-Álvarez Nov 21 '12 at 16:28
  • 1
    $\begingroup$ To add on Thomas' last comment, the idea behind cardinality is to discard internal structure, because there are plenty of very large sets which don't have any internal structure which makes "intuitive sense" for us. $\endgroup$ – Asaf Karagila Nov 21 '12 at 17:21

The basic idea is very simple: Two sets are said to have the same number of elements if they can be put in a one-to-one correspondence with each other.

So here is a one-to-one correspondence between the positive odd numbers and the positive even numbers: (1,2), (3,4), (5,6), … So any odd number $2i-1$ is matched to a corresponding even number $2i$.

To match all positive numbers with all positive even numbers, match instead $i$ with $2i$, resulting in (1,2), (2,4), (3,6), (4,8), …

See also: Hilbert's paradox of the Grand Hotel for a more entertaining way to see this.

  • $\begingroup$ While I find the Grand Hotel paradox to be very educational and relevant, it's not directly related to the question. The question asks, in a nutshell, "how come the paradox is not a mathematical contradiction?" $\endgroup$ – Asaf Karagila Nov 21 '12 at 16:04
  • $\begingroup$ @AsafKaragila: Ah, but the question, as you summarize it, cannot have a mathematical answer, in the sense that you cannot prove the consistency of mathematics. Instead, what is called for is to develop a better intuition, once it becomes clear that your old intuitions don't work. Which happens all the time in mathematics (not to mention physics). And one way to do it is to first have your faced rubbed in the failure of old intuitions. $\endgroup$ – Harald Hanche-Olsen Nov 21 '12 at 16:13
  • $\begingroup$ Yes. I agree, and I said that in my answer. Naive intuition does not go very far in mathematics, but it provides a good start for "how to model things" in the sense of what properties we expect a certain mathematical notion to have. $\endgroup$ – Asaf Karagila Nov 21 '12 at 16:14

Well, counting is really just judging how big a set is. It is a question about cardinality, then.

Your intuition is based on finite sets. Infinite sets are different. However mathematics is not built on naive intuition, when it does it often run into paradoxes and problems (e.g. Russell's paradox and naive set theory).

Therefore we need to find good properties which generalize what we want to hold. So we have to think "when do two sets have the same size?" well, for finite sets we know that if two sets have the same number of elements then they have the same size. But we also know the following:

  1. If $A\subseteq B$ then $A$ cannot exceed the size of $B$.
  2. Equinumerosity is an equivalence relation.
  3. If there is a bijection between $A$ and $B$ then they must have the same cardinality. It is impossible that $\{0,1\}$ and $\{5,6\}$ would have different sizes.

It turns out that to say that $A$ and $B$ have the same cardinality (or same number of element, although the word number is definitely confusing at first) if and only if there exists a bijection between $A$ and $B$. Furthermore, we can order the cardinals by injections, namely $|A|\leq|B|$ if and only if there is an injection from $A$ into $B$.

So it turns out that for infinite sets you get a few "naively paradoxical" results. Like having a set which is in bijection with a proper subset. However infinite sets often have "room for change" and allow us to move things around like that.

One could model the size of sets differently, but the properties which are written above will not necessarily be preserved. For example if we require that a proper subset always have a smaller cardinality, then this is no longer invariant under bijections.

Some reading material related to this:

  1. Comparing the sizes of countable infinite sets
  2. Cardinality != Density?
  3. Is there a way to define the "size" of an infinite set that takes into account "intuitive" differences between sets?
  4. Why do the rationals, integers and naturals all have the same cardinality?

The third one is particularly relevant.


I too once thought like you, but in CS counting is your friend.

When counting sets, we can determine if two sets have the same size or cardinality. For example countable infinite sets can always be put into correspondence with the natural numbers $\mathbb{N}$. These countably infinite sets are recursively enumerable languages, they can be iterated indefinitely.

So lets call the set of even numbers $\mathbb{E}$ and the set of odd numbers $\mathbb{O}$

Now, starting from the beginning, in increasing order, pair the smallest even number with the smallest natural number, next, pair the next smallest number with the next smallest natural number, so on and so forth. It looks something like this:

$\mathbb{N} = \{0, 1, 2, 3, 4, ...\}$

$\mathbb{E} = \{2, 4, 6, 8, 10, ...\}$

We see for every number in $\mathbb{N}$ there is a number in $\mathbb{E}$, that is, every number in $\mathbb{E}$ can be mapped to a unique number in $\mathbb{N}$ and vice versa.

This kind of mapping is known as a computable map or a bijection Such functions are one-to-one and onto, every element from each set is paired with a unique element of the other set.

The same argument can be applied to show than $|\mathbb{O}| = |\mathbb{N}|$.

Now, you may ask why is this important to CS, well, every language (set) that can be mapped to $\mathbb{N}$ can be recognized by a computer machine, and languages that do not map to $\mathbb{N}$ cannot even be recognized by a computer, therefore, we study this.

  • $\begingroup$ I didnt get the lats part.Why mapped set can be recognized by a computer machine? $\endgroup$ – user5507 Nov 21 '12 at 16:26
  • $\begingroup$ Using with computable functions is not a great idea for developing an initial intuition about infinite sets. It means that every infinite set has an uncountable subset. How about that. $\endgroup$ – Asaf Karagila Nov 21 '12 at 16:30
  • $\begingroup$ This answer strikes me as pretty confused – it conflates "countably infinite" with "recursively enumerable", where those two concepts are quite different, and likewise "computable map" is basically nothing to do with "bijection". $\endgroup$ – Ben Millwood Apr 6 '15 at 23:52

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.