Results 1 to 6 of 6

Math Help - Set Theory: Help with a proof

  1. #1
    Newbie
    Joined
    Nov 2010
    Posts
    5

    Set Theory: Help with a proof

    Prove that exist X ⊂ P(N)

    P(N) is a power set of natural numbers
    1 cardinality of X is continuum
    2 for each A (element of X) in X, A is infinite
    3 for each A and B in X, A is not equal to B, A intersection with B is finite

    Please, I have no idea how to solve this
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    First, I'd state it more clearly:

    Let N be the set of natural numbers.
    Let P be the powerset operation.
    Let R be the set of real numbers.

    Show that there exists an X such that:

    X is a subset of PN
    card(X) = card(R)
    Every A in X is infinite
    If A and B are distinct members of X then the intersection of A and B is finite
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2010
    Posts
    5
    thank you very much for the ideas!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    I haven't had time to think about solving, but a fact might help.

    R is 1-1 with the set of infinite subsets of N.

    So maybe we can cut that set down to a set of members that have pairwise only finite intersections, while also keeping enough to have a 1-1 with R.

    And is the axiom of choice used? (If so, let W be a well ordering of R, then maybe use transfinite recursion on R to define a function f such that for each x in R we have f(x) is an infinite subset of N that has only a finite intersection with any f(y) for y such <y x> in W?)

    By the way, what book is this from?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2010
    Posts
    5
    Our professor gave us this task at the last lecture (I study in Estonia) so I don't know if it is from any particular book.
    And thank you once again
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    780
    Hint: consider a complete infinite binary tree.

    Apparently, this is a theorem by W. Sierpinski. For example, this article by Erdős et al. says the following. Two sets A_1 and A_2 are called almost disjoint if |A_1\cap A_2|<A_i\quad(i=1,2). "An old and well known theorem of W. Sierpinski is that an infinite set of power m contains more than m subsets of power m which are pairwise almost disjoint." One can take m=\aleph_0. I am not sure whether continuum hypothesis is needed to bridge the gap between "more than m subsets" and "continuum subsets."

    I also found this fact in Google Books, but the pages with the hint are missing.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with set theory proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 8th 2011, 10:25 AM
  2. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  3. A Set Theory Proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 1st 2009, 02:53 PM
  4. Set Theory Proof Help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: March 2nd 2009, 01:34 PM
  5. Set Theory Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 13th 2006, 01:54 PM

Search Tags


/mathhelpforum @mathhelpforum