Results 1 to 4 of 4

Math Help - Recursion, Cardinality

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    29

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

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by eskimo343 View Post
    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
    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
    2
    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 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
    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: March 28th 2010, 03:23 PM
  2. recursion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 13th 2009, 08:00 AM
  3. transfinite recursion
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 25th 2009, 08:57 PM
  4. Recursion
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 30th 2008, 10:40 PM
  5. Recursion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 16th 2008, 07:24 PM

Search Tags


/mathhelpforum @mathhelpforum