## The bijection problem the natural numbers and the even numbers

• 13.9k
My math is at high school level so bear with me.

One definition of an infinite set I know of is that an infinite set is in bijection with a proper subset of itself.

Bijection, as I understand it, means that we can pair one item in a set with exactly one item in another. For example take two sets {a, e, i, o, u} and (3, 9, 2, 7} The bijection would be a3, e9, i2, u7

Now let's take two infinite sets:

1) Natural numbers N = {1, 2, 3,...}
2) Even numbers E = {0, 2, 4,...}

E is a proper subset of N and according to the definition of infinite sets E is in bijection with N. For any element y in N there's exactly one element in E that's (2y - 2) I.e. 1 in N is paired with 0 in E, 2 in N is paired with 2, 3 in N is paired with 4 in E, so and so forth.

In terms of cardinality or largeness or magnitude N = E. They are both infinite and in an equivalent way.

However, let's do something different. We take the same sets N and E. We know that N has the even numbers. So we pair the members of E with the even numbers in N. We can do that perfectly and with each member of E in bijection with the even number members of N. What now of the odd numbers in N? They have no matching counterpart in E.

Doesn't this mean N > E?

What's wrong with my argument?

Thanks
• 2
Two sets are said to have the same cardinality if there exists a bijection between them. Your second function is not a bijection.
• 176
In terms of cardinality or largeness or magnitude N = E.

That's not how we say it. Rather, we say the cardinality of N equals the cardinality of E.

card(N) = card(E)

we pair the members of E with the even numbers in N.

The even numbers in N are just the members of E. So your pairing is just pairing the members of
E with the members of E.

What now of the odd numbers in N? They have no matching counterpart in E.

Doesn't this mean N > E?

No.

N > E

means

Both hold: (1) there is a pairing from E to a proper subset of N and (2) there is no pairing between N and E.

But there is a pairing between N and E, so it is not the case that N > E. The fact that there is a pairing from E to a proper subset of N (e.g. the pairing misses the odd numbers in N) does not contradict that still there is a pairing between N and E.

/

I recommend this terminology ('<->' means 'if and only if'):

f is an injection from S into T <-> (f is a one-to-one function & the domain of f is S & the range of S is a subset of T) [note: here the range of f might not be a proper subset of T since it is allowed that the range of f is T]

f is a surjection from S onto T <-> (f is a function & the domain of f is S & the range of S is T) [note: here f might not be a one-to-one function]

f is a bijection from S to T <-> (f is an injection from S into T & f is a surjection from S onto T)

S is equinumerous with T <-> there is a bijection from S to T

S is dominated by T <-> there is an injection from S into T

S is strictly dominated by T (i.e., S < T) <-> (there is an injection from S into T & there is no bijection from S to T)
• 176
My math is at high school level so bear with me.

If you like I can recommend a few textbooks in first order predicate logic and then set theory that would provide you with a self-course in this subject. Then you would not be prone to confusions about the subject.
• 13.9k

My argument is like Cantor's diagonal argument regarding the absence of bijection between the real numbers and the natural numbers

N = {1, 2, 3, 4, 5, 6, 7, 8, 9,...}

E = {0, 2, 4, 6, 8, 10, 12, 14, 16,...}

Now pair the even numbers in N to the members of E

(2,0), (4,2), (6,4), (n,n-2),... There's a bijection but it leaves the odd numbers in N without a matching pair. In other words card(N) > card(E)
• 176
No, your argument is nothing like Cantor's argument.

Cantor proved that there does not exist a surjection from the one set onto the other, peforce that there is no bijection between them. (No surjection from N onto R, perforce no bijection between them).

Your argument just points out that one particular function is not a bijection from the one set onto the other (it's not a bijection from E onto N) The fact that one particular function is not a bijection from the one set onto the other does not prove that no other function that is a bijection from one set onto the other. And indeed we prove that there is a bijection from the one set onto the other.

Cantor proved that there is no surjection from N onto R.

But we also know that there is a bijection between N and E.

It is a clear logical fallacy to infer that because some particular function is not a bijection between N and E that therefore there is no function that is bijection between N and E.

I offered to recommend some starting books on this subject so that you can inform yourself to avoid the fallacies and confusions to which you are prone.
• 41
The statement " there are as many even integers as integers",
is typically demonstrated using a 'one to one' correspondence as shown.
N: 1 2 3 4 5 6 ...
E: 2 4 6 8 10 12 ...
1. Random sampling of integers results in an average of 50% even E, 50% odd D.
Statistics can be verified in the real world, and is useful in applications of probability.
2. In the above example, removing E from N leaves D, removing E from E leaves nothing, so where is the logic? An odd feature of this example is the appearance of the same integers in both sets.
The 'bijection' for example 1 defines y=2x, as a mapping from N to E. The results are not about the size of sets, but the definition used for mapping.

Representing the first 'one to one' correspondence above in a rectangular form, partitioned into subsets:
1 2 4 8...
3 6 12 24...
5 10 20 40...
...
The odd integers, all listed in column 1, are paired with the column of even integers to the right.
The remaining even integers in each column are paired with the column to the right.
The pairing is independent of direction.
The odd are paired 1 to 1 with an even.
The first subset of even (col 2) is paired with odd (col 1) and even (col 3).
The remaining even are paired with two columns.
Not all pairings are 1 to 1, and each integer appears only once.
A true example of a 1-1 correspondence, "there are as many even integers as odd integers "
D: 1 3 5 7 9 11 ...
E: 2 4 6 8 10 12 ...
A set without limit (infinite) is not measurable, since boundaries enable measurement.
I have a straight stick with one end. Can anyone tell me its length?
• 8.5k
I have a straight stick with one end. Can anyone tell me its length?

And that's the point. On your stick would there be more inch markers or foot markers or mile markers? On a stick with two ends, obvious answer. But how do you answer on a stick that just keeps going? You match the first of each with each other and then the second of each with each other, and then the third, and so forth. When do you get to a point, given that up to that point that everything matches, where the quantity of one differs from the quantity of another? Ans.: at the other end of the stick. And if there is no other end of the tick, then you don't.

Your objection presupposes a finite stick, or finite sets. But neither of those are the case in hand.
• 7.2k
My argument is like Cantor's diagonal argument regarding the absence of bijection between the real numbers and the natural numbers

So we pair the members of E with the even numbers in N. We can do that perfectly and with each member of E in bijection with the even number members of N. What now of the odd numbers in N?
Do understand what you are making with a bijection: every member of E has a pair in N and vice versa. That is a bijection, one to one correspondence. You are now somehow assuming it wouldn't be a bijection, but either a surjection or an injection.

The idea is most easily understood like this:

Natural number N: 1, 2, 3, 4, 5,...

Then multiply EVERY natural number by two.

:1x2, 2x2, 3x2, 4x2, 5x2,....

Then you get even numbers.
E:2, 4, 6,8, 10,...

And you can do with let's say by 10 000.

Hence there is a bijection between
N: 1,2,3,4,5...

and the infinite series
:10 000, 20 000, 30 000, 40 000, 50 000,...

even if there is 9 999 numbers "in between".
• 159
My math is at high school level so bear with me.

What's wrong with my argument?

Others have pointed it out. I second their criticisms. This is, however, a fascinating subject, and I also second the notion that you should pick up a book on it. There is room for philosophical criticism of the assumptions involved, but I don't see even room for invalidating relatively trivial results. If one learns the game, then such results are trivially true within the game. Whether this or that game is better in various sense is another question.
• 159
1. Random sampling of integers results in an average of 50% even E, 50% odd D.
Statistics can be verified in the real world, and is useful in applications of probability.
2. In the above example, removing E from N leaves D, removing E from E leaves nothing, so where is the logic? An odd feature of this example is the appearance of the same integers in both sets.
The 'bijection' for example 1 defines y=2x, as a mapping from N to E. The results are not about the size of sets, but the definition used for mapping.

No. Sorry. The equivalence is defined as the mathematical existence of a bijection. Mathematicians are well aware that they are different sets. And 'statistics can be verified in the real world' is anything but an obvious truth --assuming that it has a definite meaning in the first place.

While some mathematicians have little interest in philosophy and may ignore fascinating questions, they aren't slouches when it comes to actual math. Pure math is about as squeaky clean as it gets. The game has rules. What the game means when held against the 'real world' is a non-mathematical question. And the rules were established so that math wouldn't be a sloppy philosophical conversation.

A set without limit (infinite) is not measurable, since boundaries enable measurement.

https://en.wikipedia.org/wiki/Measure_(mathematics)

In mathematical analysis, a measure on a set is a systematic way to assign a number to each suitable subset of that set, intuitively interpreted as its size. In this sense, a measure is a generalization of the concepts of length, area, and volume. A particularly important example is the Lebesgue measure on a Euclidean space, which assigns the conventional length, area, and volume of Euclidean geometry to suitable subsets of the n-dimensional Euclidean space Rn. For instance, the Lebesgue measure of the interval [0, 1] in the real numbers is its length in the everyday sense of the word, specifically, 1. — Wiki

The measure of Q is 0. But Q has no boundary on its left or right (on the real line.) It also has infinitely many elements.
• 7.2k
There is room for philosophical criticism of the assumptions involvedEee
Sure.

Starting from the fact that we don't know the answer to the Continuum Hypothesis. Which tells us quite plainly that we still don't understand everything about mathematical infinity.
• 159
Sure.

Starting from the fact that we don't know the answer to the Continuum Hypothesis. Which tells us quite plainly that we still don't understand everything about mathematical infinity.
ssu

Right. And then one can think about constuctivism, finitism, etc. Or whether math is ultimately justified within a culture by its application. Its 'internal' justification (proofs) aren't necessarily why it is trusted or esteemed, especially as proofs get too complex for non-experts.

On forums I see those who appear to have no training approaching it 'metaphysically,' seemingly assuming that mathematicians themselves do it this way. But that misses what's essential, that it's a game with rules. It's agnostic about things outside those rules, even if particular mathematicians philosophize.
• 159
This is perhaps the easiest diagonal argument. https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

One can still ask philosophical questions about the 'frame' or set rules that makes this argument possible (set theory and classical logic), but the argument itself is beautiful and mind-opening. Because I call it beautiful or mind-opening, I do imply that the argument has intuitive content. But the argument doesn't depend on this intuitive content.
• 7.2k

It truly is mind opening. Even now it's a puzzle for us just what it opens to us.

When we show with Cantor's diagonal argument that there isn't a bijection between N and R, it's not anymore such a simple proof that we are used to, but an reductio ad absurdum proof. And this has profound implications, which shows itself with the Continuum Hypothesis.

Furthermore, we get using a similar technique as the diagonal argument, Gödel's incompleteness theorem's and Turing's answer to the Entscheidungsproblem. And in another way Russell's paradox. All of them in one way or another use what I'd call a negative self-reference.
• 159

Indeed. I have also studied those other results, especially in Kleene's Mathematical Logic. When I was first exposed to cardinality issues, I was, frankly, amazed and seduced. And I was myself guilty of raising objections I wasn't qualified to raise, too impatient to do the work required. Though I eventually did the work and saw the futility of merely intuitive/metaphysical approach. A person should probably write (at least) a few hundred proofs before philosophizing much about mathematics.

FWIW, I do think self-reference is one of the centers of philosophical opportunity. (Strange loops!)
• 13.9k
I understand Cantor's argument well enough to see that there's a pair (1-to-1 correspondence) between the natural numbers and even numbers.

Natural numbers N = {1, 2, 3, 4, n, ...}
Even numbers E = {2, 4, 6, 8,, 2n...}
2 = 2 x 1
4 = 2 x 2
6 = 2 x 3
.
.
.
n = 2n

This then is used to "prove" that the set E is equivalent to set N

I get that and thanks for clarifying.

However I can see another pairing (1-to-1 correspondence) of numbers in the two sets as follows:

N = {2, 4, 6, 8,...,1, 3, 5,...} As you can see I've divided the set N into two parts viz. the even numbers and the odd numbers but note they're included in the same set N

The set of even numbers E = {2, 4, 6, 8,...}

As you can I see can form a pairing (1-to-1 correspondence) between E and the even numbers in set N like so: (2,2), (4,4), etc. and that leaves the odd numbers without a corresponding pair in the set E.

Basically two different bijections are possible. One agrees with Cantor's "proof" but the other contradicts Cantor. You'll have to show that Cantor's bijection is the correct one and the alternative is nonsensical. Can you do that?

NOTE: I've excluded zero from the set of even numbers for simplification purposes
• 159
Basically two different bijections are possible.

I'm guessing that an infinite number of bijections are possible. We can flip segments of length k and proceed as before. This works for any k >= 2.

For instance, let k = 3.

Then f = { (1,6),(2,4),(3,2),(4,12),(5,10),(6,8),...}.

Note that a function is itself just a set of ordered pairs (satisfying a condition that ensures an unambiguous output).

But all we need for equivalence, by definition, is a single bijection.

N = {2, 4, 6, 8,...,1, 3, 5,...}

Note that sets are not ordered. {1,2} = {2,1}, for instance. The order is in the bijection. And, as you know, the easiest bijection is $f(n) = 2n,$ with inverse $f^{-1}(e) = e/2.$ The alternative bijections mentioned above probably have complicated algebraic forms, despite the simplicity of the idea behind them.

As you can I see can form a pairing (1-to-1 correspondence) between E and the even numbers in set N like so: (2,2), (4,4), etc. and that leaves the odd numbers without a corresponding pair in the set E.

What you say is a contradiction. A 1-to-1 correspondence is a bijection. As I understand you, you are presenting $g : E \to N$ such that $g(e) = e$. Because odd numbers are not in the range of g, this function is not a surjection, though it is an injection (1-to-1). A bijection is simultaneously a surjection and an injection. https://en.wikipedia.org/wiki/Bijection

Please consider that there are uncountably many functions from E to N. One can use a diagonal argument to prove this. Assume not. Well clearly $f_k(e) = ke$ is a countably infinite family of functions. So the functions from E to N are at least countably infinite. So by our assumption (in pursuit of a contradiction), we can arrange the functions from E to N in an countably infinite list $f_n$. Then we define our diagonal function $f(e) = f_e(e) +1$ where the $f_n$ is the nth function in a merely countable list of functions from E to N.

Since $f(n) = f_n(n) + 1$, it differs from every $f_n$ at $n$ and is not on the list, despite being a function from E to N. Contradiction! The point of the list $f_n$ was to catch all functions from E to N. Hence our assumption that such functions are countable is incorrect. And they are at least countable, so they must be uncountable. Or you can interpret this as: since any possible listing allows for its own diagonal function not on that list, no listing gets them all (providing a bijection from N to the set of those functions.) Every listing casts a shadow or has a blind spot. We just slash diagonally to get something not on the list.

It's not surprising that you can find one such function that isn't a bijection. I'm guessing (someone feel like proving it?) that the probability of picking a bijection randomly is 0. Is the subset of bijections countably infinite? Sounds like a fun question.

This then is used to "prove" that the set E is equivalent to set N

Keep in mind that this is just one kind of equivalence. It only has as much metaphysical weight as a philosopher feels like giving it. Mathematicians can all agree that X is proven without having to agree on what that means outside of mathematics. 'There exists' has a formal meaning. If $x \in \Bbb R$ and $x \ne 0$, then $\exists y \in \Bbb R$ such that $xy = 1$. That's an axiom. It's a rule that allows you to put a new piece on the board. Despite the intuitions and applications that quietly drive the 'game,' the game itself is 'safer' than that. Computers can, in theory, check proofs. In practice this is not often considered necessary or desirable.

It's like learning a language. Once you learn it, lots of proofs are easy to judge for their correctness.
• 2.6k
This then is used to "prove" that the set E is equivalent to set N

No, that's a great source of confusion. If there exists a bijection between two sets, even a single one, even if there are plenty of functions that aren't bijections, then we DEFINE the two sets as being cardinally equivalent. It's a definition, not a proof.

Given the naturals N and the evens E, there exists a bijection. So we say, by definition, that the two sets have the same cardinality. The fact that there are many functions between the two sets that aren't bijections is irrelevant. The condition is an existential, not universal, quantification. If out of all the functions from one set to another there happens to be a single one that's a bijection, then the two sets are cardinally equivalent, by definition.

As has been noted, this is not the only way to compare the relative sizes of sets. There's the subset relation. Clearly E is a proper subset of N so E is "smaller" than N with respect to the proper subset relation

Yet another way that was mentioned a few posts back is natural density, also known as asymptotic density. Using this method we see that the limit as n gets large of the proportion of even numbers among the first n numbers goes to 1/2. So the natural density of E in N is 1/2. Likewise the natural density of the multiples of 3 in N is 1/3; and the natural density of the primes is 0. [Proof by the interested reader for that last assertion].

So there are lots of ways to compare the relative size of sets. Cardinality happens to be one way. It's not a very fine-grained one. For example the intervals [0,1] and [0,2] of real numbers have the same cardinality, since there's a bijection between them: namely f(x) = 2x. But [0,1] has length 1 and [0,2] has length 2. The generalization of the idea of length is called measure, and it's yet another way to compare the relative size of sets. In fact measure theory underlies modern probability theory, so it's very important. But as we saw with the intervals, cardinality does not respect measure. In that sense cardinality is a very crude way of thinking about the relative sizes of sets.

Just as we use a hammer for one thing and a spatula for another and a torque wrench for yet something else, mathematicians have a lot of tools in the toolbox. Cardinality, as defined by bijection, is just one tool, to be used as appropriate.

Basically two different bijections are possible. One agrees with Cantor's "proof" but the other contradicts Cantor. You'll have to show that Cantor's bijection is the correct one and the alternative is nonsensical.

Cantor's definition of cardinal equivalence via bijection is not right or wrong. It's a definition. In the past 140 years it has proven to be both interesting and useful, which is why it's stuck around. But it's not the only way of comparing sets; and it's neither right nor wrong. It's just one of the tools in the mathematical toolbox. E and N have the same cardinality. The natural density of E in N is 1/2. And E is indeed a proper subset of N. All three points of view are equally valid. One or the other viewpoint might be more useful in a particular context.
• 13.9k
No, that's a great source of confusion. If there exists a bijection between two sets, even a single one, even if there are plenty of functions that aren't bijections, then we DEFINE the two sets as being cardinally equivalent. It's a definition, not a proof.

That's where the problem is isn't it?

The definition is inadequate for the reason that, on one hand, Cantor's "preferred" bijection leads to an equivalence between the set of even numbers and natural numbers but on the other hand there exists another bijection that shows that the set of natural numbers is not equivalent to the set of natural numbers.
• 2.6k
That's where the problem is isn't it?

The definition is inadequate for the reason that, on one hand, Cantor's "preferred" bijection leads to an equivalence between the set of even numbers and natural numbers but on the other hand there exists another bijection that shows that the set of natural numbers is not equivalent to the set of natural numbers.

It's a definition. It can't be right or wrong.

You do agree that there exists at least one bijection between N and E, namely f(n) = 2n. You agree with that, yes?

Then by definition the two sets have the same cardinality. That's all it means. If there exists a bijection, then the sets are said to have the same cardinality.

It's true that there are many functions between E and N that aren't bijections, but it only takes one to satisfy the definition.

Do you agree that even if you don't like the definition, E and N satisfy it by virtue of that one bijection?

there exists another bijection that shows that the set of natural numbers is not equivalent to the set of natural numbers.

But no. The existence of a non-bijection doesn't prove anything. As long as there's a single bijection, the definition is satisfied. Not because it's right or wrong, but because that's the definition.
• 13.9k
It's a definition. It can't be right or wrong.

• 2.6k

It doesn't.

Do you agree that there exists at least one bijection from E to N?

If you agree, then you must agree that E and N have the same cardinality, because the definition says that there must be at least one bijection between them, and this is manifestly the case.

ps -- It's like a guy who cheats on his wife. She says to him, "You're a cheater." He says no! Think about all the times I DIDN"T cheat on you.

But that's not the point. If you cheat once, that's the definition of a cheater. If you cheated Monday but not on Tuesday or Wednesday, you can't say you're not a cheater because you didn't cheat on Wednesday. Right? The definition is doing it once.

Likewise the definition of cardinal equivalence is that there's at least one bijection. It doesn't matter that some other function isn't a bijection.
• 7.2k
I understand Cantor's argument well enough to see that there's a pair (1-to-1 correspondence) between the natural numbers and even numbers.
That's not technically Cantor's diagonal argument. That proof comes into use only with the reals R.

Basically two different bijections are possible.
Please understand you are not talking of a bijection! It isn't a bijection if one group has more members.
It's either an injection or an surjection. It's the most simple math there is an actually one of the most hardest. And, if I understand your thought correctly, you are basically saying that there's an injection from E to N. But when you can prove there's a bijection, it doesn't go that it's only an injection.

Yet, understand that you are talking about infinite series. Have you ever heard about the Hilbert Hotel? • 41

I don't presuppose a finite stick. They are the norm. Given the definition of infinite, without limit or boundary, and the fact that infinite is not a number or quantifier, a one ended stick is not measurable/quantifiable. You already described the futility of such an effort.
Cantor was an illusionist and fooled many people.
• 8.5k
Nope, the futility is in your effort to impose your own (mis)understanding. Error and ignorance is the province of every person. Once pointed out, however - the process of education, one way or another - it's not merely error and ignorance any more. So in your case, what is it?
• 41

I read Cantor's biography. It helps to understand his motivation to write.
I agree, ignorance is abundant.
• 13.9k
It doesn't.

Do you agree that there exists at least one bijection from E to N?

If you agree, then you must agree that E and N have the same cardinality, because the definition says that there must be at least one bijection between them, and this is manifestly the case.

ps -- It's like a guy who cheats on his wife. She says to him, "You're a cheater." He says no! Think about all the times I DIDN"T cheat on you.

But that's not the point. If you cheat once, that's the definition of a cheater. If you cheated Monday but not on Tuesday or Wednesday, you can't say you're not a cheater because you didn't cheat on Wednesday. Right? The definition is doing it once.

Likewise the definition of cardinal equivalence is that there's at least one bijection. It doesn't matter that some other function isn't a bijection.

Do you agree that there exists at least one bijection from E to N?

So there was nothing wrong when Socrates defined humans as featherless bipeds and someone came along with a chicken plucked of all its feathers and declared "this is a human"? After all there was/is at least one human that fit the definition.
• 13.9k
Thank you very much for the colorful explanation. Appreciate it.

However I am actually talking about there being an injection correspondence between even numbers and natural numbers and so bijection correspondence isn't the only game in town. Ergo, the set of even numbers isn't equivalent to the set of natural numbers.
• 310

From a programmer's point of view, cardinality equivalence between two sets is about their expressibility through each other.

card(N) = card(E) tells me that if I want to define an encoding of the elements of E through the elements of N, or N through elements of E, I can. Thus, I can write/store n to represent "the n-th even number", and 2*n to represent "the ordinal n". In any case, as long as I standardize my representation upfront, I am going to be able to decode it uniquely later.

card(N) < card(R) tells me that I can never represent a real number through a natural number, no matter how I try to tip-toe around the issue. I can muster the strangest encodings, but it is logical impossibility. Thus, I will be able to express only some real numbers ordinally (or even out of order), but not all of them.

P.S. Thus your dilemma can be rephrased as the ability to encode some set and a strictly smaller set through the same representation set. This may be awkward in some sense, but it is just a fact of life.
• 2.2k
And everyone has been at pains to explain to you that sets with the same cardinality are just that - sets with the same cardinality. They are not (necessarily) equal. They are not "equivalent" - that's not a set theory term. They have the same number of elements only in the special case of finite sets (cardinality is a generalization of set size).

It's like as if someone told you that Sarah and Anil are the same age, and you objected that Sarah is a woman and Anil is a man, Sarah is American and Anil is Indian, Sarah is smaller than Anil, so how could they be equivalent?! Cardinality is just one measure of sets, nothing less, nothing more. Get over this already.
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal