Results 1 to 4 of 4

Thread: Recursion, Cardinality

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    29

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by eskimo343 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2009
    Posts
    29
    In my book, that just means that they have the same cardinality. Sorry, I should have said that.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by eskimo343 View Post
    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 $\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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recursion help.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 28th 2010, 02:23 PM
  2. recursion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 13th 2009, 07:00 AM
  3. transfinite recursion
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Oct 25th 2009, 07:57 PM
  4. Recursion
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Sep 30th 2008, 09:40 PM
  5. Recursion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 16th 2008, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum