Splitting an infinite set into two equal infinite subsets.

[mathboy]

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?

 

[ice109]

an equality goes both ways

 

[Hurkyl]

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.

 

[mathboy]

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.

 

[Dragonfall]

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".

 

[mathboy]

So ordinals must be used to prove this?

 

[Dragonfall]

What's important is the bijection. Of course there might be other ways.

 

[mathboy]

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]

I observe that your conjecture is a consequence of |A|=|AxA|. That can be proven without choice, right?

 

[Dragonfall]

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 |

 

[Dragonfall]

Well-order I.

This uses choice.

 

[mathboy]

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?

 

[ice109]

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 $\aleph_0 + \aleph_0 =\aleph_0$ 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 $\aleph_0 = \aleph_0 + \aleph_0$.

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| $$\stackrel{?}{=}$$ |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.

 

[mathboy]

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.

 

[ice109]

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]

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]

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|.

 

[mathboy]

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.

 

[gel]

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.

 

[mathboy]

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.

 

[gel]

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 A_i be the image of {(a,i): a in A} under f. This gives the required partition.

 

[mathboy]

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 A_i 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?

 

[gel]

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 A_x 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 A_x 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.

 

[gel]

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 2²ⁿ if n >= 0 and 2^-2n-1 if n <0.
Let A_n consist of all numbers of the form m f(n) for odd m.


...ok, to be pedantic, A_n is a partition of the non-zero integers. You can add 0 to A₀ to make it a partition of Z.

 

[andytoh]

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.

 

[gel]

To make my example above for the partition of R a bit more precise.

Let x(n) be the n'th digit of x, and sign(x) = 1 if x >= 0 and -1 if x < 0.
So $x = {\rm sign}(x)\sum_{n=-\infty}^\infty 10^n x(n)$.

For every real x, you can define $f(x)= {\rm sign}(x)\sum_{n=-\infty}^\infty 10^n x(2n)$, and the partition is given by A_x = f^-1({x}).

This takes care of the problem of repeating 9s in the decimal expansion of x.

 

[ice109]

To make my example above for the partition of R a bit more precise.

Let x(n) be the n'th digit of x, and sign(x) = 1 if x >= 0 and -1 if x < 0.
So $x = {\rm sign}(x)\sum_{n=-\infty}^\infty 10^n x(n)$.

For every real x, you can define $f(x)= {\rm sign}(x)\sum_{n=-\infty}^\infty 10^n x(2n)$, and the partition is given by A_x = f^-1({x}).

This takes care of the problem of repeating 9s in the decimal expansion of x.

i don't understand this

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?

yes the proof requires zorn's lemma

 

[andytoh]

To make my example above for the partition of R a bit more precise.

Let x(n) be the n'th digit of x, and sign(x) = 1 if x >= 0 and -1 if x < 0.
So $x = {\rm sign}(x)\sum_{n=-\infty}^\infty 10^n x(n)$.

For every real x, you can define $f(x)= {\rm sign}(x)\sum_{n=-\infty}^\infty 10^n x(2n)$, and the partition is given by A_x = f^-1({x}).

This takes care of the problem of repeating 9s in the decimal expansion of x.

gel is following the classic bijection of [0,1)x[0,1) to [0,1), moving all decimal places to double the decimal position. For example, if x = 123.456, then A_x is the set of all real numbers of the form ..._0_0_0_1_2_3_._4_5_6_0_0_0_... .

 

[mathboy]

Wow! Excellent guys! Does anyone dare give an explicit partition of the power set P(R) of the reals into |P(R)| disjoint subsets each with cardinality |P(R)| ?

 

[andytoh]

Wow! Excellent guys! Does anyone dare give an explicit partition of the power set P(R) of the reals into |P(R)| disjoint subsets each with cardinality |P(R)| ?

For each subset S={x_i|i in I} of R, let A_S be the collection of all subsets of R of the form {y_i|i in I}, with each y_i obtained from x_i by the doubling the digit positions again and padding between those digits with any digits. P(R) is certainly the union of all the A_S, and there are |P(R)| many such A_S.

Wait, |A_S|=|R| not |P(R)|. Arggh, this is a bit messed up!

 

[ice109]

why does it seem to me like this is verging on trying to make onto functions from a function onto it's powerset? even before mathboy mentioned the p(r)

 

[Hurkyl]

P(A + B) and P(A) x P(B) are naturally bijective sets, right? So all you need to do is find sets A and B, and bijections

A + B ~ R
A ~ R
B ~ R

And voilà! You have a bijection P(R) ~ P(R) x P(R).

 

[andytoh]

Bijection F:P(R) x P(R) -> P(R):

Start with two subsets S and T of R. Get the characteristic functions (chi_S, chi_T). Get the characteristic function f:R -> {0,1} defined by

f(x)= (chi_S)(lnx) if x>0, (chi_T)(ln(-x)) if x<0. (problems with x=0, so someone find a better bijection from Rx{1,2} to R)

From the characteristic function f, get your unique subset of R corresponding to f. This subset of R is our F(S,T),
i.e. F(S,T)= {x|f(x)=1}.

Given S from P(R), let
A_S = F(P(R)x{S}).

The collection {A_S| S in P(R)} is the desired partition of P(R). All the A_S are pairwise disjoint, |A_S|=|P(R)|, and P(R) = U (A_S) .

Can someone find a better bijection from Rx{1,2} to R ?

 

[andytoh]

f:R->{0,1}

f(x)=
(chi_S)(ln(x+1)) if x is a non-negative integer
(chi_S)(lnx) if x>0 and not and integer,
(chi_T)(ln(-x)) if x<0.

Yuck. Can someone think of a better one?

 

[Hurkyl]

What's so yuck about it?

Anyways, observe the following: if you split the real line up into two or more intervals, at least one of them must be either a closed or a half-open interval. Such intervals cannot be homeomorphic to R.

Your method looks like one of the standard tricks for creating a point out of "thin air", so I don't see why it's so yucky.


Anyways, thinking about yours did lead me to a different, cute example: split the real line into half open intervals
... + [-2, -1) + [-1, 0) + [0, 1) + [1, 2) + [2, 3) + ...
then do your favorite rearrangement of Z into two copies of Z.