Recursion, Cardinality

**eskimo343** · March 26th 2010, 01:45 PM

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.

**tonio** · March 26th 2010, 01:55 PM

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

**eskimo343** · March 26th 2010, 01:57 PM

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

**tonio** · March 26th 2010, 02:06 PM

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

Thread: Recursion, Cardinality

LinkBack

Thread Tools

Display

Recursion, Cardinality

Similar Math Help Forum Discussions

Recursion help.

recursion

transfinite recursion

Recursion

Recursion

Search Tags