What is the cardinality of the set of all sequences of non-negative integers?

Question

Consider the set of all possible sequences {a_n}, where the terms of each sequence a_1, a_2, a_3 ... are each non-negative integers. What is the cardinality of this set? Prove it.

Hint: If the possible values of a_1, a_2, etc. were restricted to {0,1, 2, 3, 4, 5, 6, 7, 8, 9}, it would be obvious that each sequence could be mapped to exactly one real number in [0, 1], so the cardinality of the set of sequences is AT LEAST as big as C (the cardinality of the real numbers in [0, 1]). But each of the members of the sequence can take on any positive integer value, so it could be larger than C.

This has implications. This cardinality is the same as that of the set of all functions that map rational numbers into rational numbers.

anthony: Any one of the a_n can have an unlimited number of digits. That’s the problem. The point is to find another way.

ksoileau: Your mapping is not 1-1. I could also map every sequence to the number 42, but that doesn’t prove that the cardinality of the set of sequences is 1.

Pascal: You are arguing from notation. If you can back this up with a real mapping, please do so.

I don’t know if it will be possible to make further remarks; I hope so!

Pascal:
I will look into your text later. In the meantime, I have, by a long process of construction, arrived at a mapping that does the trick:
If a_k is a sequence of non-negative integers, map {a_k} to
f({a_k}) = 1 - 3*( 4^(-1) /2^(a_1)
- 4^(-2) /2^(a_1 + a_2)
- 4^(-3) /2^(a_1 + a_2 + a_3) ......)

I claim:
a) f(0,0,0,0...) = 0
b) f({a_k} < 1 for all sequences a_k
c) for any sequence a_k and integer n, if you vary the term a_n while fixing the rest of the terms, the larger the a_n is, the larger the value of f({a_k})
d) f is injective: If two sequences differ, find the first term, a_m, at which they differ. The sequence that is larger for that term will map to a value higher than the other sequence, no matter what happens to the remainder of the two sequences.

This took a lot of thinking to construct. I wondered if someone had a different approach. Your modification of ksoileau's concept seems OK.

anthony: You are falling into the same trap that ksoileau did originally: You cannot prevent two different sequences that use the same order of digits from being mapped to the same real number. Example: the sequence: 1, 11, 2, 22,.. will map to the same number as the sequence: 11, 1, 22, 2...

Pascal's trick: Map the sequence to the string: 1A11A2A22 and interpret that as a representation of a real number in base-11: the value:
x = 1*(1/11) + A*(1/11)^2 + 1*(1/11)^3 + 1*(1/11)^4 + A*(1/11)^5 + 2*(1/11)^6 + ...
where A = ten.
This is now a unique real number, and two different sequences will always give different values.
It's a simple trick, but I didn't think of it myself.

The answer I propose also works, but proving requires study.
I'll look at Pascal's main proposal more carefully later.

Pascal:

I’m afraid I don’t get your points:

On principle 1: It seems that a much more straight-forward proof would be:
If A ≼ B, there is an injection g: A → B. Consider any element f of A^C: f: C → A, so for any c ε C, f(c.) = a ε A. Now if we define h(c.) = g∘f(c.), h ε B^C. So the mapping α: A^C → B^C: α(f) = g∘f is already an injection, and hence A^C ≼ B^C.

On principle 2: It also seems this can be done more easily:
If A ≼ B, any function f: A→C can be mapped to f’(g^-1(a)) = f(a) ; of course this function’s domain doesn’t include those b (ε B) which are not ε g^-1(A). So extend this function by mapping all such left-out b’s to an arbitrary constant element of C. This creates a function ε C^B which corresponds to f, and this mapping is an injection. Hence C^A ≼ C^B.

On principle 3:
If α(f):B×C → A takes (x,y) to f(y)(x), then don’t you mean that x ε B and y ε C ? Also, don’t you mean that x and f(y) ε A ? But that doesn’t seem to be consistent with the rest of your argument: “

Unfortunately, you main proof depends on Principle 3.

The missing remainder of your argument that got cut earlier:
"ince f maps every y in C to some function in A^B, and thus f(y) is is a function from B to A and may accept an argument x in B"

Berkeley,

No, I do not want the cardinality of mappings from integers to non-negative reals. I want the cardinality of mappings from integers to integers.

Pascal,

I am still mulling over your one-line proof. I believe I understand the principles 1-3, but they haven't yet come together coherently in my mind to make a convincing impression.

Soon...

Answer 1

This set of sequences is simply ℕ^ℕ, and we know that:

ℶ₁ = 2^ℵ₀ ≤ |ℕ^ℕ| ≤ (2^ℵ₀)^ℵ₀ = 2^(ℵ₀×ℵ₀) = 2^ℵ₀ = ℶ₁

Therefore, |ℕ^ℕ| = ℶ₁

By the way, to the first poster, the real numbers do not necessarily have cardinality ℵ₁. The real numbers do have cardinality ℶ₁ = 2^ℵ₀, but whether 2^ℵ₀ = ℵ₁ is an undecidable proposition in set theory. One of the reasons the beth numbers exist is to provide a simple way of referring to the cardinality of powersets of common mathematical structures (such as ℕ and ℝ) without making assumptions such as the continuum hypothesis.

Edit: to the second poster, your function is not an injection. If {12, 23, 12, 12, 4567, 1, 3456789,...} is mapped to 0.12231212456713456789, but so is {1223, 12, 12, 4567, 1, 3456789, ...}.

Edit 2: Actually, the "notation" is based on well-established principles of cardinal arithmetic. I will assume that you are least familiar with the notation -- i.e. you know that A^B is the set of functions from B to A and that 2 is the set {0, 1}. I will also use the symbol ≼, where A≼B means "there is an injection from A to B", and ≈, where A≈B means "there is a bijection between A and B). Obviously, the relations ≼ and ≈ are transitive. Also, per the Cantor–Bernstein–Schroeder theorem, (A≼B ∧ B≼A) ⇔ A≈B.

Now, there are three principles of cardinal arithmetic used in the above.

Principle 1: A ≼ B ⇒ A^C ≼ B^C
Proof: Suppose A ≼ B. Then there is an injection from A to B -- let f be such an injection. Then we can construct α:A^C → B^C by defining α(g) = f∘g. Now, suppose that α(g) = α(h). Then ∀x∈C, α(g)(x) = α(h)(x), thus per the definition of α, f(g(x)) = f(h(x)). But since f is an injection, this implies g(x) = h(x), and since this holds for all x∈C, g = h. Thus α(g) = α(h) ⇒ g = h, so α is an injection from A^C to B^C, thus A^C ≼ B^C.

Principle 2: If A≠∅, A ≼ B ⇒ C^A ≼ C^B
Proof: Suppose A ≼ B. Then there is an injection from A to B -- let f be such an injection. Then construct the function g:B → A as follows: Pick an element c in A (possible because A≠∅). If x is in the range of f, let g(x) = f⁻¹(x), otherwise let g(x)=c. The construct the function α:C^A → C^B by defining α(h) = h∘g. Now, suppose h≠i. Then ∃x∈A such that h(x)≠i(x). Since f(x) is in the range of f, we have that g(f(x)) = f⁻¹(f(x)) = x, so this means h(g(f(x))) ≠ i(g(f(x))), which means α(g)(f(x)) ≠ α(h)(f(x)), so α(g) ≠ α(h). Thus h≠i ⇒ α(h)≠α(i), so α is an injection from C^A to C^B, thus C^A ≼ C^B.

Principle 3: (A^B)^C ≈ A^(B×C)
Proof: Define α:(A^B)^C → A^(B×C) as follows: let α(f):B×C → A be the function that takes (x, y) ↦ f(y)(x) (this is valid, since f maps every y in C to some function in A^B, and thus f(y) is is a function from B to A and may accept an argument x in B). Suppose that α(f) = α(g). Then ∀x, y, α(f)(x, y) = α(g)(x, y), which means that f(y)(x) = g(y)(x). Now, for any particular y, this holds for all x∈B, so f(y) = g(y). And since this holds for all y∈C, f=g. Thus α(f)=α(g) ⇒ f=g, so this is an injection. To show that it is a surjection, let f∈A^(B×C). Then define g:C→A^B to be the function that takes an element y in C to the function from B to A that takes x to f(x, y). Then ∀x, y, α(g)(x, y) = g(y)(x) = f(x, y), so α(g) = f. Since we can find such a g for any f in A^(B×C), α is a bijection.

From the above, it's easy to see how to validate the cardinal arithmetic given at the beginning of my post. Still, if your assignment requires you to construct injections explicitly, it may be easier simply use the original argument of the second poster (whose post is now gone) with a minor modification -- given a sequence x₁, x₂, x₃... map them to the sequence x₁ + A + x₂ + A + x₃ + A..., where + means string concatenation and A is just the letter A. Then interpret the result as a base-11 decimal expansion (assuming x₁, x₂, x₃... are given in base 10). It is easy then to recover the original sequence from the resulting base-11 decimal, so this is an injection. However, I feel that it will ultimately be more productive for you to learn the cardinal arithmetic, since it reduces some very complex arguments into 1-line proofs.

Edit 3: Although the arguments in principles 1 and 2 might be simplified somewhat, the parts of the proofs you left out are indispensable, since they are necessary to show that no two functions in A^B get mapped to the same function in A^C, and that no two functions in C^A get mapped to the same function in C^B.

In principle 3, yes I do mean x∈B and y∈C. f is an element of (A^B)^C -- that is, f:C → A^B, and f(y) is a function (specifically, f(y):B → A). Neither x nor f(y) are elements of A.

What's confusing, I think, is that in most cases where functions are considered, they are in a separate and distinct category from "elements", whereas all three of the arguments above require freely operating with functions whose domain and codomain are themselves sets of functions. For instance, in the third argument above, f is a function that takes an element in C and outputs a function from B to A. So if y∈C, f(y) is itself a function from B to A, and can thus be applied to an element x in B to obtain f(y)(x). The idea behind the third proof is that if you have a function f∈(A^B)^C, for each pair of elements x∈B and y∈C, you can obtain in a canonical fashion an element in A by first applying f to y to obtain f(y)∈A^B, and then applying f(y) to x to obtain an element in A. So each function f∈(A^B)^C induces in this canonical fashion a function from B×C to A which takes (x, y) ↦ f(y)(x). The function induced in this manner is α(f). Conversely, if we have a function f∈A^(B×C), for each element y in C, we can obtain in a canonical fashion a function g_y:B → A by letting g_y(x) = f(x, y) for every x∈B. So each function f∈A^(B×C) induces in this canonical fashion a function g from C to the set of functions from B to A, which takes y ↦ g_y. And this function g happens to be exactly α⁻¹(f). So the set (A^B)^C is isomorphic to the set A^(B×C) under the mapping α.

Is that any clearer, or are you still confused?

Answer 2

Let c be the cardinality of the reals R. Then c = the cardinality of the non-negative reals R+ as well. Let aleph0 be the cardinality of the natural numbers, N. You want the cardinality of all functions from N to R+.

It is c^aleph0. But c = 2^aleph0 and aleph0^2 = aleph0.

So the answer is 2^aleph0, which is c.