-4

Let be a set of something with infinite cardinality. Let ℕ be the set of natural numbers ℕ. There is a bijection f: ℕ → . They both have the same cardinality, denoted as |ℕ| = ||. Bijection means that every element of ℕ can be mapped to every element of . "Every" means that there are no further elements in ℕ that can be mapped to anything else. Now consider a new set ₂, which contains all the elements of , with the addition of element x, which is not an element of : ₂ = ∪ {x} (x ∉ ). Yet, it is a basic principle that || = | ∪ {x}|, in which case there is a bijection between ℕ and ₂. So there are no further elements in ℕ after mapping each of its elements to , and at the same time there is an extra element in ℕ which can be mapped to ₂. That is a contradiction.

To clarify:
Proposition (1): Each of the infinite elements of ℕ is used in the bijection between ℕ and . No elements of ℕ remain unused in this bijection.
Proposition (2): There is an element of ℕ remaining unused in this bijection, and it is this element that is required to create a new bijection between ℕ and ₂.
Proposition (1) contradicts Proposition (2).

The contradiction cannot be resolved by stating that we can create separate bijections for and ₂, since they are both bijections from the same set ℕ. Although ℕ has infinite cardinality, all its elements are employed in the bijection between it and (which also has infinite cardinality, and so requires the use of all elements of ℕ).
Such an attempted resolution amounts to saying that part of an infinite set is as large as the whole infinite set, which is clearly a logical contradiction.

Ariel
  • 1
  • 2
  • 2
    You don't have to use the same bijection for E as you do for E2. Try to work an example where E is the even integers, and $x = 1$. – Benjamin Wang Feb 22 '23 at 01:54
  • Agreed, but I'm not seeing how that resolves the contradiction. If every element of N is required to create a bijection between N and E, what is left in N to create a bijection between N and E2? – Ariel Feb 22 '23 at 01:56
  • 1
    Yup, you can change your bijection when the "target set" is changed. This is the basis of "The Hilbert Hotel", which you should be able to find many popular write-ups about. – JonathanZ Feb 22 '23 at 02:00
  • 1
    Change your first bijection: Have 2 go where 1 used to go, 3 go to where 2 used to go, etc.. Now 1 is "free" to go to your added element. – JonathanZ Feb 22 '23 at 02:01
  • 2
    The point is that to show that two sets have different cardinality, the burden is on you to show that no bijection ever exists between them. We cannot simply say that the one we had before doesn’t work. – Arkady Feb 22 '23 at 02:03
  • 3
    You've shown that the map $f:\mathbb{N} \to E$ does not extend to a bijection $\mathbb{N} \to E_2$. That doesn't imply that there isn't any bijection $\mathbb{N} \to E_2$. – anomaly Feb 22 '23 at 02:22
  • You haven't explained why it doesn't imply that. I have edited the question by adding a clarification to emphasize the logical contradiction. – Ariel Feb 22 '23 at 02:28
  • 2
    Just because one specific map can't be extended to a bijection doesn't mean that no bijection can exist. You're placing the burden of proof the wrong way. You need to prove that no bijection can exist. Why does your argument show that? (It doesn't.) – Robert Shore Feb 22 '23 at 02:30
  • Your latest edit mentions "Such an attempted resolution amounts to saying that part of an infinite set is as large as the whole infinite set", which (while you claim is a logical contradiction) is possible. For example there are bijections between $\mathbb N$ and the positive even numbers. – peterwhy Feb 22 '23 at 15:06
  • "The contradiction cannot be resolved by stating that we can create separate bijections for and ₂, since they are both bijections from the same set ℕ." By the same reasoning, you cannot have two feet if you've already established that you have two eyes. – JonathanZ Feb 26 '23 at 04:18

4 Answers4

2

There is no contradiction. Your usual intuition of cardinality with finite sets breaks down when you have infinite sets.

To generalize your problem a bit more, let's say there are infinitely many elements in $E_2$ that are not in $E$. For instance, take $E$ to be the set of positive even integers and $E_2=\mathbb{N}$. Obviously, $|E_2|=|\mathbb{N}|$ (choose the identity map for a bijection). However, we can still form a bijection between $\mathbb{N}$ and $E$ (different than one between $\mathbb{N}$ and $E_2$), namely $f:\mathbb{N}\to E$, $f(n)=2n.$ Hence, $E$ and $E_2$ have the same cardinality (both are countable).

Hilbert's hotel is a good illustration of how our intuitions of finite sets break down with infinite sets.

Golden_Ratio
  • 12,591
  • I understand, but I don't see how saying that "usual intuition" breaks down is different than saying, "yes, there is a logical contradiction here, but it's still true." – Ariel Feb 22 '23 at 02:05
  • 2
    Intuition is not the same as logic. There are many things that are logically true that are counterintuitive (e.g. Banach Tarski "paradox"). These "paradoxes" only reflect a problem with our ability to fully appreciate the definitions. – Golden_Ratio Feb 22 '23 at 02:16
  • The particular "usual intuition" that breaks down is that if you used an element to create one bijection, it was necessary and required to create that bijection. That's true for finite sets, but not for infinite ones, and it's what lead you to believe there was a contradiction. – JonathanZ Feb 22 '23 at 02:21
  • @Ariel Here is a cute illustrative video on Hilbert's Hotel that may help clarify things. – Golden_Ratio Feb 22 '23 at 13:57
2

If $f:\mathbb N \to E$ is your bijection, and $x$ is your new element that's not in $E$, then $ g:\mathbb N \to E \cup \{x\}$ given by $$ \begin{align} g(1) &= x\\ g(n) &= f(n-1) \textrm{ for }n \ne 1\\ \end{align} $$

is also a bijection.

When you say

So there are no further elements in ℕ after mapping each of its elements to , and at the same time there is an extra element in ℕ which can be mapped to ₂.

the 'map' in "... after mapping each ..." refers to the map $f$, and the 'map' in "... which can be mapped ..." refers to the map $g$.

Additionally, when you say in your comment that

If every element of N is required to create a bijection between N and E,

you're mistaken. Not every element of $\mathbb N$ is required to create a bijection with $E$ - you could create one with just $\{15, 16, 17 ....\}$. That's the fundamentally weird thing about infinite sets: they can be put in 1-1 correspondence with a proper subset of themselves.

JonathanZ
  • 10,615
  • I could map {15, 16, 17...} with the 15th, 16th, 17th etc. elements of E, but if I'm not using {1...14} of N, nothing would be left to map to elements 1 through 14 of E. In essence, this is the same contradiction as that of the main question. You are restating the contradiction ("that's the fundamentally weird thing about infinite sets"), without acknowledging or resolving the inherent logical contradiction that is involved here. – Ariel Feb 22 '23 at 02:35
  • 1
    @Ariel "Proposition 2" in your post is incorrect. Please read the other comments on your post carefully. – Golden_Ratio Feb 22 '23 at 02:51
  • 1
    @Ariel - Yes, you could map like that, and the map you build would fail to be a bijection. There are lots of ways to build a map that isn't a bijection, but that doesn't mean one can't be built. So if you do the following: Map 15 to element #1, map 16 to element #2, 17 to element #3, and so on. That would produce the desired bijection. – JonathanZ Feb 22 '23 at 03:22
  • 1
    You seem to be thinking that once we use a number to map to some element one time, it is required that we always map that number to that same element forevermore. That is not a requirement. As noted, your Proposition 2 is wrong. If you want to understand what happens in definition of $g$ above (do you?), you can think of it happening in multiple steps: Initially, there is no unused element. Then, we utterly modify our bijection so 2 points where 1 did, 3 points where 2 did, etc. This frees up 1, as now ${2,3,4,...}$ covers all of $E$. .... – JonathanZ Feb 22 '23 at 03:30
  • 1
    Now we have an unused element (1), that we use to create the bijection with $E_2$. Can you see how this is a description of the definition of $g$ in my answer? – JonathanZ Feb 22 '23 at 03:32
  • Thanks. Yes, I'm trying to understand, but am not convinced that we've got to the root of the issue. Where have you conjured up that "unused element" from? All the infinite elements in ℕ have been used in f already! – Ariel Feb 22 '23 at 10:29
1

To judge whether one thing exists, an example of other things alone is irrelevant.

To judge whether there's a lion outside your village, catching a wolf and then claiming "this animal is not a lion" is irrelevant.

To judge whether there's a bijection from $\mathbb N$ to $\mathbb E_2$, proposing a function that is not surjective (hence not a bijection) is irrelevant. If one can propose an actual bijection, then there's a bijection.

peterwhy
  • 22,256
-3

"The Case Against Infinity", which I have now found (https://philarchive.org/rec/SEWTCA), by Kip K Sewell, argues much better than I can why, indeed, the contradiction I identify, and many more, mean that infinity is not a coherent or logical concept, even if it can be used operationally in mathematics. Well worth a read, and I think is a more detailed answer to my question than any of the previous answers given. Specifically, with regards to an infinite set of marbles used as an example, he writes:

by virtue of being complete, the infinite set of marbles can be divided up leaving two infinite sets with one for you just as in the equation ℵ0 - ℵ0 = ℵ0. However, by virtue of being limitless, the infinite set of marbles cannot be divided up, and so one person is left without any marbles just as the equation ℵ0 - ℵ0 = 0 states. The mathematical contradiction in the quantity left over is a result of the logical contradiction of an infinite set being both “divisible” and yet “not divisible.” Conversely, the mathematical contradictions in dividing or subtracting infinite sets also imply logical contradictions in “removing” infinite subsets from infinite sets of objects, like marbles, in the real world. Subtracting or “removing” the odd numbered subset of marbles from the total set of marbles (ℵ0 - ℵ0) cannot leave a remainder that is both infinite (ℵ0) and not infinite (0) simultaneously, which is both a mathematical and a logical contradiction. Since logical contradictions cannot manifest in reality, there can be no infinite set of marbles or an infinite set of anything else in the real world.

This relates directly to my original question, and I consider it the correct answer.

Ariel
  • 1
  • 2
  • 5
    The author seems to assume that $ℵ_0-ℵ_0$ must be well-defined and hence arrives at a "contradiction," when in fact, it is not. Also, a mathematical abstraction need not manifest itself in the "real" world. – Golden_Ratio Feb 24 '23 at 20:36
  • Also, despite my commenting, I didn't downvote your post :) – Golden_Ratio Feb 24 '23 at 20:45
  • 1
    All you care about is that there be some contradiction, and you seem to be willing to accept the weakest of arguments if it ends there, and will reject the most rigorous of arguments if they come to some other conclusion. This is the first time in seven years that I feel like I've wasted my energy replying to a question here. – JonathanZ Feb 26 '23 at 04:15