4
$\begingroup$

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)

  • 1
    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.2012-11-21

3 Answers 3

2

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.

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.

  • 0
    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.2012-11-21
0

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.

  • 0
    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".2015-04-06