Splitting an infinite set into two equal infinite subsets.

  • Thread starter mathboy
  • Start date
182
0

Main Question or Discussion Point

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?
 

Answers and Replies

1,703
5
an equality goes both ways
 
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,843
17
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.
 
182
0
and B and C must be disjoint.

e.g.
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:
1,028
4
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".
 
182
0
So ordinals must be used to prove this?
 
1,028
4
What's important is the bijection. Of course there might be other ways.
 
182
0
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?
 
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,843
17
I observe that your conjecture is a consequence of |A|=|AxA|. That can be proven without choice, right?
 
1,028
4
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 |
 
182
0
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 |
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?
 
1,703
5
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.
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?

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?
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:
182
0
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.
 
1,703
5
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.
 
CRGreathouse
Science Advisor
Homework Helper
2,817
0
any infinite set A can be written as a disjoint union A = B U C where A,B, and C have the same cardinality.
This is what mathboy was asking about, I think. Does this require some form of choice?
 
gel
533
5
So if A is an infinite set, we know that |A|+|A|=|A|.
an equality goes both ways
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|.
 
182
0
any infinite set A can be written as a disjoint union A = B U C where A,B, and C have the same cardinality.
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?


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.
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:
gel
533
5
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|.
That is equivalent to |A| = |A| x |I| using a similar argument to my previous post.
 
182
0
That is equivalent to |A| = |A| x |I| using a similar argument to my previous post.
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:
gel
533
5
I am wondering if the partition is always possible for any infinite set A.
Well, if |A| = |A| x |I| then there is a 1-1 mapping between A and A x I. Let this be f : AxI -> A. Then, for every i in I, let Ai be the image of {(a,i): a in A} under f. This gives the required partition.
 
Last edited:
182
0
Well, if |A| = |A| x |I| then there is a 1-1 mapping between A and A x I. Let this be f : AxI -> A. Then, for every i in I, let Ai be the image of {(a,i): a in A} under f. This gives the required partition.
Ah, yes. That does it!

Now since |R| = |R|x|R|, then that means that R (reals) can be partitioned into |R| many disjoint subsets each with cardinality |R|. What is an explicit such partition of R? R can be partitioned into
..., [-1,0), [0,1), [1,2), [2,3), .... ,
each subset with cardinality |R|, but there are only |Z| many of them.

Even stranger, how can Z (the integers) be partitioned into |Z| many subsets, each subset with cardinality |Z|? So we know it is possible. But what is an example?
 
Last edited:
gel
533
5
What is an explicit such partition of R?
For any real number x let x(n) be the digit in its n'th position (any n in Z).
Then, let Ax consist of the real numbers y satisfying y(2n)=x(n). I think that should do it.

Actually, I ignored the signs of x and y here. I should have insisted that Ax only contains non-negative numbers when x is non-negative, and negative numbers when x is negative. Also, you have to be careful to handle the possibility of repeating 9's in the expansion of x (you should allow them), and y (shouldn't allow them). That's all messy details though.
 
Last edited:
gel
533
5
Even stranger, how can Z (the integers) be partitioned into |Z| many subsets, each subset with cardinality |Z|? So we know it is possible. But what is an example?
For every integer n, let f(n) be 22n if n >= 0 and 2-2n-1 if n <0.
Let An consist of all numbers of the form m f(n) for odd m.


...ok, to be pedantic, An is a partition of the non-zero integers. You can add 0 to A0 to make it a partition of Z.
 
359
3
Even stranger, how can Z (the integers) be partitioned into |Z| many subsets, each subset with cardinality |Z|? So we know it is possible. But what is an example?
Let B_p be the set of all integers whose lowest prime factor is the pth prime number. |B_p|=|Z| for all p and they are disjoint, and there are |Z| many such p's since there are infinitely many prime numbers. Remove 0,1,-1 from Z.
 
Last edited:

Related Threads for: Splitting an infinite set into two equal infinite subsets.

  • Last Post
Replies
22
Views
3K
Replies
16
Views
4K
  • Last Post
Replies
8
Views
2K
Replies
7
Views
621
Replies
1
Views
1K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
3
Views
8K
Replies
16
Views
3K
Top