4 ms·
Bijection is a simple idea. But it’s an important tool because it helps keep us out of the counterintuitive weeds when working with infinite sets
by malandrew 12y ago
Bijection is a simple idea. But it’s an important tool because it helps keep us
out of the counterintuitive weeds when working with infinite sets. For instance,
we can now figure this out: are there more positive integers {1, 2, 3, ...} or
even integers {2, 4, 6, ...}? The naive answer would be that there must be more
positive integers, because the set of positive integers includes both the even
and odd integers.
But this is wrong. Using bijection, we see that we can put the positive integers
and even integers into a one-to-one correspondence like so:
1, 2, 3, 4, ...
2, 4, 6, 8, ...
Couldn't you also reason that there are more even integers than positive integers if you start with the notion that you start with a number and start counting in the direction(s) of the defined set:
X--->
1, 2, 3, 4, ...
..., -4, -2, 0, 2, 4, 6, 8, ...
<--X-->
The set of all integers progresses along two vectors with each "count" and only positive increases along a single vector with each count.
- roywiggins 12y agoAs long as the bijection exists at all, the sets have the same cardinality. To prove two sets don't have the same cardinality, the most direct way is to prove that such a bijection is impossible. Anyway, the bijection from counting numbers to the set of all natural numbers is easy: 1, 2, 3, 4, 5, ... 0, 1, -1, 2, -2, ...
- te_platt 12y agoThe idea is that if there is any bijection at all between the two sets then they are the same "size". So you can make all kinds of relations between two sets that are not bijections but once you find one you have satisfied the definition of same size in this sense. Note that it is a way of defining size that corresponds to what we mean with finite sets and then extends that definition in a consistent way. So yes you could define a "malandrew size" however you like and see what kind of insights you get.
- pavas 12y agoYou have an infinite number of both since the counting never ends. In your example, if you've counted n positive integers, you've counted 2n even integers associated with those (by going both ways). But if you continue counting, eventually you will count 2n positive integers (at which point you'll have counted 4n even integers). For any number of even integers that you count, you can just keep counting the positive integers and you'll eventually reach that number. Here's another way to think about it: are there more positive integers than there are positive integers? (Any "correct" approach should say no, or at least not yes.) Using your approach, however, here is a proof that there are more positive integers than there are positive integers. Lets rearrange the positive integers in this manner: X---> 1, 2, 3, 4, ... ..., 7, 5, 3, 1, 2, 4, 6, 8, ... <--X-->
- malandrew 12y agoSo an odd counting vector and and even counting vector, both in the positive direction would be equivalent to the approach I suggested. That makes sense. Thanks for the clarification.