# Recursion, Cardinality

• Mar 26th 2010, 01:45 PM
eskimo343
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.
• Mar 26th 2010, 01:55 PM
tonio
Quote:

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
• Mar 26th 2010, 01:57 PM
eskimo343
In my book, that just means that they have the same cardinality. Sorry, I should have said that.
• Mar 26th 2010, 02:06 PM
tonio
Quote:

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 http://www.mathhelpforum.com/math-he...0c9ece57-1.gif 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