Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Splitting an infinite set into two equal infinite subsets.

  1. Apr 12, 2008 #1
    So if A is an infinite set, we know that |A|+|A|=|A|. But are we allowed to go backwards, i.e. divide A into two disjoint subsets B and C such that A = B U C, and |B|=|C|=|A|. For the integers and for the reals, this is clear, e.g. R = (-infinity,0) U [0, infinity), each with cardinality c. But are we allowed to do this for any infinite set of larger cardinality? I'm sure the answer is yes, but how do we go about proving this? Do we have to use the Axiom of Choice and transfinite induction? How complicated will the proof be?
  2. jcsd
  3. Apr 12, 2008 #2
    an equality goes both ways
  4. Apr 12, 2008 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I think you're misunderstanding the question: he's asking if, for an infinite set A, the the system of equations

    A = B U C
    |A| = |B|
    |A| = |C|

    has a solution for B and C.
  5. Apr 12, 2008 #4
    and B and C must be disjoint.

    A=Integers: B= even integers, C=odd integers. Done.
    A=Reals: B=(-infinity,0), C=[0, infinity). Done.
    A=P(R): B=? C=? The problem begins with cardinality greater than c.

    How about this: Well-order A. Put the first element in the left bin, the second in the right bin,...alternatingly put the elements of A
    in the left bin and right bin. By transfinite induction, this can be done for all elements of A. Then each bin has |A| elements.
    Last edited: Apr 12, 2008
  6. Apr 12, 2008 #5
    You need choice. By choice there exists a bijection between any set and an ordinal. Every ordinal can be written as A + n where n is a natural number. You can then split them into "even" and "odd".
  7. Apr 12, 2008 #6
    So ordinals must be used to prove this?
  8. Apr 12, 2008 #7
    What's important is the bijection. Of course there might be other ways.
  9. Apr 12, 2008 #8
    Here's my proof attempt without using ordinals.

    Let A={a_i| i in I}. Well-order I. Suppose all elements a_i can be placed alternatingly in bin B and bin C for i < j. Then a_j can be placed in B if the previous was placed in C (and vice versa). So by transfinite induction, this can be done for all i in I, so A=BUC. We have B and C disjoint, and |B|=|C|. Then
    |A|=|BUC|=|B|+|C|=2|B|=|B|=|C|. Sounds good?
  10. Apr 12, 2008 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I observe that your conjecture is a consequence of |A|=|AxA|. That can be proven without choice, right?
  11. Apr 12, 2008 #10
    Wait, wait, do you want A = B U C, or |A| = |B U C|? Because if it's the latter, all you have to do is notice that |A| = | {0}xA U {1}xA |
  12. Apr 12, 2008 #11
    This uses choice.
  13. Apr 12, 2008 #12
    Partition A into B U C, such that |B|=|C|=|A|. Actually, we should be able to generalize this to k partitions of A such that each partition has cardinatility |A|, and k is any (infinite) number less than |A|, right?
  14. Apr 12, 2008 #13
    i knew what he meant and what i said stands. c + c = c, and [itex]\aleph_0 + \aleph_0 =\aleph_0[/itex] if the sets are disjoint and if they're not they can be made so by using dragonfall's method. hence c = c + c and [itex]\aleph_0 = \aleph_0 + \aleph_0 [/itex].

    now that i reread his first post i don't understand the difficulty?

    if the question is this :

    |A| + |A| = |A| :1
    |B|=|C|=|A| :2

    |B|+|C| [tex]\stackrel{?}{=}[/tex] |A|

    how is it not immediate that by 2
    (|A|=|B|) + (|A|=|C|) = |B|+|C| = |A| ?

    this is of course taking for granted cardinal addition and equality.
    Last edited: Apr 13, 2008
  15. Apr 13, 2008 #14
    I'm not trying to prove that |B|+|C| = |A|. That follows immediately from |A| + |A| = |A|. I'm trying to prove that B and C exist such that B and C partition A and each have cardinality |A|. But I think I've already proven it now, and am wondering about the infinite partitioning case.
  16. Apr 13, 2008 #15
    again huh? what do you mean by partition? here are three theorems from my set theory book that might be what you're looking for :

    countable union of countable sets is countable
    any infinite set can written as the union of disjoint countably infinite sets.
    any infinite set A can be written as a disjoint union A = B U C where A,B, and C have the same cardinality.
  17. Apr 13, 2008 #16


    User Avatar
    Science Advisor
    Homework Helper

    This is what mathboy was asking about, I think. Does this require some form of choice?
  18. Apr 13, 2008 #17


    User Avatar

    That answers the question.
    Starting with the knowledge that |A|=|A|+|A|, no choice is required, it is just a matter of applying the definitions.

    More precisely, |A|=|A|+|A| just means that there are two disjoint sets B,C such that |B|=|C|=|A| and |A|=|B U C|. By definition B U C can be put into 1-1 correspondence with A. Let B' be the image of B and C' be the image of C. Then A = B' U C' and |B'|=|C'|=|A|.
  19. Apr 13, 2008 #18
    Yes, that was my original question (but I've generalized it now). How long is the proof in your textbook for this? What's the sketch of the proof? Does it depend on axiom of choice?

    Almost gives me what I seek. My generalized conjecture is:

    If A is infinite, then A can be written as the union of pairwise disjoint sets {B_i| i in I}, with |B_i| = |A| for each i in I, and |I| can be any finite number or any infinite number less than |A|.

    For example, the reals can be partitioned into
    ..., [-1,0), [0,1), [1,2), [2,3), .... .
    Each set is disjoint, each with cardinality |R|, and there are |Z|<|R| many of them.
    Last edited: Apr 13, 2008
  20. Apr 13, 2008 #19


    User Avatar

    That is equivalent to |A| = |A| x |I| using a similar argument to my previous post.
  21. Apr 13, 2008 #20
    I already know that for any two cardinal numbers a,b, that ab=max{a,b}.

    I am wondering if the partition is always possible for any infinite set A.
    Last edited: Apr 13, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook