Recursive definition from Munkres Topology

[poochie_d]

Hi all, just joined PF; I have a question about Munkres's Topology (2ed), Section 9 #7(c):

Homework Statement

Find a sequence $A_1, A_2, \ldots$ of infinite sets, such that for each $n \in \mathbb{Z_+}$, the set $A_{n+1}$ has greater cardinality than $A_n$.

Homework Equations

Definition: If A and B are sets, then A has greater cardinality than B if there is an injection of B into A, but no injection of A into B.

Principle of recursive definition (from Munkres):
Let C be a set, with c in C. Let $\mathcal{F}$ = {set of functions f : {1,...,n} $\rightarrow$ C}.
Let $\rho$ be a map from $\mathcal{F}$ to C.
Then there exists a unique function h : $\mathbb{Z_+} \rightarrow$ C such that
h(1) = c, h(n) = $\rho$(h|{1,...,n-1}) for n > 1.

The Attempt at a Solution

Define recursively, as follows:
$$A_1 = \mathbb{R}, \quad A_n = \mathcal{P}(A_{n-1})$$ for n > 1,
where $\mathcal{P}(B)$ denotes the power set of $B$.
Since there is no injection from $\mathcal{P}(B)$ to $B$ for any set $B$ (this is a theorem from Munkres), and we can always define the injective map $f : B \rightarrow \mathcal{P}(B), \quad f(b) = \{b\}$, it follows that $A_{n+1}$ has greater cardinality than $A_n$ for all n.

I suppose this solution is "correct", but is there a more formal way to define the recursive step, using the above Principle from Munkres? I mean, how would you define the function $\rho$? I think it should probably be something like:
$\rho : \mathcal{F} \rightarrow C, \quad \rho(f) = \mathcal{P}(f(n))$ for $f : \{1,\ldots,n\} \rightarrow C$,
but I don't know how to define the set $C$ ...
Any help would be much appreciated. Thanks!

 

[mighty2000]

Thank you for your question about Munkres's Topology. Your solution is indeed correct, and your use of the Principle of Recursive Definition is also valid. However, I believe there is a simpler way to define the recursive step without using the Principle.

Let us define the sequence A_n as follows:
A_1 = \mathbb{N}, A_n = \mathbb{N}^n for n > 1,
where \mathbb{N} denotes the set of natural numbers. This means that A_1 is the set of all natural numbers, A_2 is the set of all ordered pairs of natural numbers, A_3 is the set of all ordered triples of natural numbers, and so on.

Now, for the recursive step, we can define the function f_n : A_n \rightarrow A_{n+1} as follows:
f_n(x_1, x_2, ..., x_n) = (x_1, x_2, ..., x_n, 1),
where (x_1, x_2, ..., x_n) is an element of A_n and (x_1, x_2, ..., x_n, 1) is an element of A_{n+1}. It is easy to see that this function is injective, since no two elements of A_n can map to the same element in A_{n+1}.

Therefore, we have found a sequence of infinite sets A_1, A_2, ... where each set has greater cardinality than the previous one. I hope this helps!