# Recursion, Cardinality

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

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

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

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

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

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

What does $\displaystyle =_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 $\displaystyle A_f$ is, by the first part, a countable union of sets each of one has the same cardinality as $\displaystyle A$ , so being this an infinite one we're done.

Tonio