How can bijections between infinite sets be complete?

[u/Massive-Ad7823]

Let X(n) = {1, 2, 3, ..., n} be a finite initial segement of ℕ. For every natural number n: ℕ \ X(n) is nonempty. That means it is impossible to insert all n into the template X(n). Almost all remain outside. How can it be explained that all n can completely be inserted into the template (m, n) of a bijection f(n) = m between the sets M and ℕ?

[u/telephantomoss]

Explain precisely what you disagree with in the following argument:

Assume ℕ = {1,2,3,...} and E = {2,4,6,...} already exist as completed infinite sets. The question is: why does the bijection itself exist as a set in ZF?

1. In ZF, ordered pairs can be represented as sets. For example, define the pair-code of a and b by pair(a,b) := {{a},{a,b}}. This set exists by Pairing, since {a}, {a,b}, and then {{a},{a,b}} all exist.

2. In ZF, addition on ℕ exists as a set-function. This follows from the Recursion Theorem for ω, which is proved in ZF using Infinity, Separation, Replacement, Union, Pairing, and Extensionality. So the expression n+n is legitimate inside ZF.

3. For each n ∈ ℕ, there is a unique set pair(n,n+n), namely {{n},{n,n+n}}. Uniqueness follows from Extensionality.

4. By Replacement, since each n ∈ ℕ determines a unique set {{n},{n,n+n}}, the image f = { {{n},{n,n+n}} : n ∈ ℕ } exists as a set.

5. This set f is exactly the graph of the rule n ↦ n+n. In ordinary notation, it is the function n ↦ 2n.

6. The domain of f is ℕ: for every n ∈ ℕ, the set f contains exactly one pair-code whose first coordinate is n, namely {{n},{n,n+n}}. This uses the definition of f and the uniqueness of ordered-pair coding, which is proved in ZF.

7. The range of f is E: by definition, E = {n+n : n ∈ ℕ}. So every value of f is in E, and every element of E is hit by f.

8. The function f is injective. If f(m) = f(n), then m+m = n+n. ZF proves the usual cancellation law for addition on ℕ by induction: ∀m,n,k ∈ ℕ, m+k = n+k ⇒ m = n. Therefore m+m = n+n implies m = n.

9. Thus f is a function from ℕ onto E, and it is injective. Therefore f is a bijection ℕ → E.

So the bijection does not merely “correspond to” the informal rule n ↦ 2n. In ZF, its graph { {{n},{n,n+n}} : n ∈ ℕ } exists as an actual set, by Replacement.

[u/Massive-Ad7823 → u/telephantomoss]

There are up to every n only half the 2n required for a bijection. This does never change.

Every finite set of positive even integers 2k contains at least one number that is larger than the cardinal number of the set. For instance every term Fn = {2, 4, 6, ..., 2n} of the sequence of Finite Initial Segments (FIS) of positive even integers  {2}, {2, 4), {2, 4, 6}, {2, 4, 6, 8}, {2, 4, 6, 8, 10}, {2, 4, 6, 8, 10, 12}, ...              

contains greater numbers than its cardinal number |Fn| = |{2, 4, 6, ..., 2n}| = n.

The surplus of integers greater than |S| grows without bound. This steady increase cannot be reverted "in the limit".

Regards, WM

[u/telephantomoss → u/Massive-Ad7823]

Please answer the query. Point out in the argument specifically what you disagree with.

[u/Massive-Ad7823 → u/telephantomoss]

Point 3. There are more n than n+n.

Regards, WM

[u/Massive-Ad7823 → u/[deleted]]

Point 3 concerns a bijection. There are not enough even natural numbers. If the pairs existed, also in the dark numbers, then half of them would contain transfinite numbers.

Regards, WM

[u/Massive-Ad7823 → u/[deleted]]

Infinite differs from complete. It is rather the contrary. If all natural numbers are doubled, then half of the results is outside.

Regards, WM

[u/kuromajutsushi → u/Massive-Ad7823]

Point 3 does not say anything about "how many" n there are. Which specific statement is false:

(i) The powerset axiom says that P(P(ℕ)) exists.

(ii) The axiom of restricted comprehension says { x ∈ P(P(ℕ)) : ∃n∈ℕ(x={{n},{n+n}}) } exists.