# Thread: Recursion, Cardinality

1. ## Recursion, Cardinality

Suppose $C$ is a well orderable set, $f: C \times C \rightarrow C$, $A \subseteq C$, and let $A_f =_{df} \cap \{ X \subseteq C | A \subseteq X \text{ }\& \text{ }f[X \times X] \subseteq X \}$ be the closure of $A$ under $f$. Define the sets $\{ A_n \}_{n \in \mathbb{N}}$ by the recursion $A_0=A$, $A_{n+1}=A_n \cup f[A_n \times A_n]$. Then we have that $A_f=\cup_{n \in \mathbb{N}} A_n$.

Show that if A is infinite, then $A_f =_c A$.

I am having trouble proving this part now [that if $A$ is infinite, then $A_f =_c A$]. I know that by the first part we have that $A_f=\cup_{n \in \mathbb{N}} A_n$. However, I do not see how to show that if $A$ is infinite, then $A_f =_c A$. I need help on this. Thanks.

2. Originally Posted by eskimo343
Suppose $C$ is a well orderable set, $f: C \times C \rightarrow C$, $A \subseteq C$, and let $A_f =_{df} \cap \{ X \subseteq C | A \subseteq X \text{ }\& \text{ }f[X \times X] \subseteq X \}$ be the closure of $A$ under $f$. Define the sets $\{ A_n \}_{n \in \mathbb{N}}$ by the recursion $A_0=A$, $A_{n+1}=A_n \cup f[A_n \times A_n]$. Then we have that $A_f=\cup_{n \in \mathbb{N}} A_n$.

Show that if A is infinite, then $A_f =_c A$.

I am having trouble proving this part now [that if $A$ is infinite, then $A_f =_c A$]. I know that by the first part we have that $A_f=\cup_{n \in \mathbb{N}} A_n$. However, I do not see how to show that if $A$ is infinite, then $A_f =_c A$. I need help on this. Thanks.

What does $=_c$ mean?

Tonio

3. In my book, that just means that they have the same cardinality. Sorry, I should have said that.

4. Originally Posted by eskimo343
In my book, that just means that they have the same cardinality. Sorry, I should have said that.

So you want to prove that the cardinalities of are the same...but $A_f$ is, by the first part, a countable union of sets each of one has the same cardinality as $A$ , so being this an infinite one we're done.

Tonio