Why the principle of counting does not match with our common sense

Question

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)

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

Because sets of numbers can be infinitely divisible. See this Reddit comment.

I think his intuition comes from the fact that the world is discrete in practice. You have 2x more atoms in [0, 2cm] than in [0, 1cm]. If you are not looking at something made of atoms, let's say you have 2x more Planck lengths in [0, 2cm] than in [0, 1cm]. See what I mean?

OP's intuition can be correct for physical things in our world, but mathematics go beyond that, with rational numbers being infinitely divisible. As soon as there is a limit to how much you can divide things, even if it's one million digits after the decimal point, OP's intuition is valid.