A proper subset of a set $S$ is equinumerous to $S$. Is this a contradiction? [duplicate]

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)

Solution 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.

Solution 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.