"There does not exist an uncountable subset of the real numbers which can not be expressed as the union of two uncountable sets which are disjoint from one another" is obviously true assuming choice. However, I'm looking for a proof of this statement that does not involve choice. I believe I have come up with one myself, but it's a little complicated. Is there any easy way to go about this?
[Math] Uncountable Sets that can not be expressed as a disjoint union of two Uncountable sets
axiom-of-choiceset-theory
Related Solutions
Suppose $A$ and $B$ are two sets of equal cardinalities, without any additional structure there are $2^{|A|}$ many bijections between them.
Using the axiom of choice we can choose $f_i\colon X_i\to Y_i$ which is a bijection, and using these bijections construct one from $\bigcup X_i$ to $\bigcup Y_i$ in the intuitive manner that you'd expect.
However since we are choosing from infinitely many sets at once we cannot just say that the sequence of bijections exists. Such assertion needs to be backed up, and the axiom of choice is exactly what allows us to back it up - the collections of bijections are nonempty, and so we may choose one from each one. From these choices we have a sequence of bijections which we can use to construct the bijection between the unions.
Without the axiom of choice it is possible that we cannot choose the bijections. It is possible to have that $A_i$ is countable for $i\in\omega$ but $|\bigcup A_i|=\aleph_1$, which is of course uncountable.
By your argument we could say that $A_i$ has a bijection with $\{i\}\times\omega$, however $\bigcup A_i$ is uncountable while $\bigcup(\{i\}\times\omega)=\omega\times\omega$ is countable. Therefore the unions are no longer in bijection.
Wait, it gets even worse. It is possible to have a countable family of disjoint pairs (sets of two elements each), and the union of is uncountable. Of course the uncountability of the union does not imply it has cardinality $\aleph_1$, but rather that it cannot be well ordered at all. On the other hand, we can write $\mathbb Z\setminus\{0\}$ as the pairs $\{-n,n\}$. The union of these countably many pairs is indeed countable.
With products the use of choice is even clearer. It is not trivial that the product is nonempty, but it does not imply that every product is empty.
In the above example of the pairs, we have countably many disjoint pairs $P_i$ such that $\prod P_i=\varnothing$. However if you take pairs of natural numbers, for example $\{2n,2n+1\}$ then the product is $2^\omega$ and the union is countable. This, once again, should hint you of the example.
So to answer both questions, the point we use the axiom of choice is in our choice of bijections to construct the bijection between the products or the unions. Of course this can be averted if additional structure exists on the sets, if they are all subsets of the same well ordering, for example.
Further reading on this site:
The answer is yes, under the axiom of choice, such a partition is possible. There are several ways of seeing this. For example, choice gives us that any set is in bijection with an infinite ordinal. But, for any infinite ordinal $\alpha$, there is a bijection between $\alpha$ and $\alpha\times \{1,\dots,n\}$. The bijection is in fact canonical, in the sense that there is a "uniform" procedure that applied to any infinite ordinal $\alpha$ produces such a bijection. If you are somewhat familiar with ordinal numbers, a proof can be found in this blog post of mine.
Of course, if $\alpha$ is in bijection with $X$, then $\alpha\times \{1,\dots,n\}$ is in bijection with $X\times \{1,\dots,n\}$, so the latter is in bijection with $X$. The required partition is then the image under the bijection of the sets $A_a=\{(a,i)\mid 1\le i\le n\}$, for $a\in X$.
(To mention but one other standard argument, using choice, we have that $X$ and $X\times X$ are in bijection so, invoking the Bernstein-Schroeder theorem, we conclude that $X$ and $X\times\{1,\dots,n\}$ are in bijection as well.)
On the other hand, the answer is no, without the axiom of choice it is in general not possible to produce such a partition. This is addressed at length in this MO answer, with details in the references linked there.
Best Answer
Let $x\in\mathbb{R}$. Define $$S_{\leq x}=S~\cap~(-\infty,x]~~~\mathrm{and}~~~S_{>x}=S~\cap~ (x,+\infty)$$ and define $S_{\leq}=\{$ the set of all $x$ such that $S_{\leq x}$ is uncountable $\}$, and $S_>=\{$ the set of all $x$ such that $S_{>x}$ is uncountable $\}$.
$S_{\leq}$ is a non empty$^{(*)}$ interval that extends to infinity on the right, and is therefore of the form $[a,+\infty)$ or $(a,+\infty)$ for some $a\in\mathbb{R}$ or is equal to the whole of $\mathbb{R}$.
Similarly, $S_>$ is a non empty$^{(*)}$ interval that extends to infinity on the left, and is thus of the form $(-\infty,b]$ or $(-\infty,b)$ for some $b\in\mathbb{R}$ or is equal to the whole of $\mathbb{R}$.
$^{(*)}$ : I have used some form of choice I believe when I say that $S_>$ and $S_{\leq}$ are non empty, because I use the fact that with some form of choice, the countable union of countable sets is still countable. Is it countable choice? Since $$S=\cup_{n\in\mathbb{N}}S_{\leq n}$$ is uncountable, at least one of the $S_{<n}$ must be uncountable, and so for some natural number $n$ you have $n\in S_{<}\neq\emptyset$.
Let's show that $S_>\cap S_{\leq}$ is non empty. If either one of $S_>$ or $S_{\leq}$ is the whole real line, there is no problem. So let's suppose none of them is the whole of $\mathbb{R}$.
Suppose $x\in S_{\leq}$ that is $S_{\leq x}=S~\cap~(-\infty,x]$ is uncountable. Since $$\bigcup_{n\in\mathbb{N}^*}S_{\leq x-\frac{1}{n}}\subset S_{\leq x}=S~\cap~(-\infty,x]\subset \{x\}\cup \bigcup_{n\in\mathbb{N}^*}S_{\leq x-\frac{1}{n}}$$ the already used fact that countable unions of countable sets are countable with some form of choice implies that at least one of the $S_{\leq x -\frac{1}{n}}$ is uncountable, which means that for some $n\in\mathbb{N}^*,~x -\frac{1}{n}\in L$ and thus $S_{\leq}$ is open, that is, $$\mathbf{S_{\leq}=(b,+\infty)}$$ for some real number $b$. Similarly, $$\mathbf{S_{>}=(-\infty,a)}$$ for some real number $a$.
Then $S_>\cap S_{\leq}$ is empty iff $a\leq b$. But this would entail that $$S=S_{\leq a}\cup S_{> a}$$ is countable as the union of two countable sets, since $a \notin (-\infty,a)=S_{\leq}$ means $S_{\leq a}$ is countable, and $a \notin (b,+\infty)=S_{>}$ means $S_{> a}$ countable.