Topics Mathematics

Question Hi, I've been reading about transfinite cardinal numbers and was wondering if you could answer this question. Supposedly the set of integers has the same cardinality as the set of even integers (both are countably infinite) since there exists a bijection between the two sets. But at the same time, doesn't there also exist a function between the set of even integers and the set of integers that is injective while NOT bijective (g(x) = x), since the image of f does not compose all of the integers (only the even ones)? To clarify, let f and g be functions from the set of EVEN integers to the set of ALL integers. Let f(x) = 1/2 x, and g(x) = x. Both are injective functions, but f is onto while g is not. So f is a bijection, while g is merely 1-to-1. Why, then, can I not say that the set of even integers and the set of all integers do NOT have the same cardinality since there exists some 1-1 function that is not onto? It seems like I should be able to draw this intuitive conclusion since g is 1-1, so for every element in the first set there exists a corresponding element in the second, but since g is not onto there are more elements in the second than in the first? Thanks!

Accepted:
August 17, 2009

Comments

The background issue here is: what's the best way of extending our talk of one set's being "larger" than another from the familiar case of finite sets to the infinite case?

Now, in the finite case, we can say that [L] the set A is larger than the set B if and only if there is a 1-1 mapping between B and some proper subset of A (i.e. there is an injection from B into A, which isn't onto). But equally, in the finite case, we can say that [C] the set A is larger than the set B if and only if there is a 1-1 mapping between B and some proper subset of A, but no 1-1 mapping between B and the whole of A.

In finite cases, [L] and [C] come to just the same: but in infinite cases they peel apart. [L] says the set of naturals is larger than the set of evens; [C] denies that. So isn't [L] the more intuitive principle to adopt?

No! For take the case where A and B are both the very same set, the natural numbers. There is a 1-1 mapping from the natural numbers into the natural numbers which isn't onto: take the mapping S: m --> m + 1. This correlates each number with its successor; and of course zero isn't in the image of the natural numbers under this mapping. So if we adopted that suggestion [L] about what it is for one set to be larger than another, we'd have to say that the set of natural numbers is larger than itself. That is an unwelcome implication to say the least! We've lost a key basic property of the larger than relation that makes it a strict order relation, namely its asymmetry.

Now you might think that we have a straight choice here: do we adopt [L] with its radically counterintuitive implications (e.g. the set of naturals is larger than itself), or [C] with its counterintuitive implications (the set of naturals is no larger than the set of evens)? But the situations aren't symmetric. For [C] preserves at least something of the idea of comparisons of size by keeping larger than an order relation: we get a workable concept of cardinal order. By contrast, [L] destroys too much of the idea of order-by-size to be any use.

Which is why [C] is the definition to adopt.