Proving that an uncountable set has an uncountable subset whose complement is uncountable.

Your idea is generally correct.

Using the axiom of choice, $|X|=|X|+|X|$, so there is a bijection between $X$ and $X\times\{0,1\}$. Clearly the latter can be partitioned into two uncountable sets, $X\times\{0\}$ and $X\times\{1\}$.

Therefore $X$ can be partitioned to two uncountable disjoint sets.

---

Indeed you need the axiom of choice to even have that every infinite set can be written as a disjoint union of two infinite sets, let alone uncountable ones.

Sorry for the necropost; I came across this and wanted to share a proof using only Zorn's lemma (i.e. an "elementary" proof).

Edit: "elementary" might not be the best word to use here. Perhaps "easy" is better. See comments.

---

Let $ P=\left\{ A \subset X\times X\colon\phi(A)\right\} $ where $\phi$ is the proposition given by: $$ \phi(A)=\forall(x,y)\in X\times X\colon(x,y)\in A\implies\psi(A,x,y) $$ and $$ \psi(A,x,y)=\forall(w,z)\in A\colon\left(x=w\iff y=z\right)\wedge x\neq z\wedge y\neq w. $$

Example: If $X=\mathbb{N}$, the set $A=\{(1,2),(3,4)\}$ would be in $P$, but the set $A^{\prime}=\{(1,2),(3,1)\}$ would not (the number $1$ appears twice).

Define a partial order on $P$ by inclusion $\subset$. Trivially, every chain in $P$ has an upper bound given by the union of the elements in that chain. By Zorn's lemma, $P$ has a maximal element, say $$ A^{\star}=\{(x_{\alpha},y_{\alpha})\}. $$ Let $X_{1}=\{x_{\alpha}\}$ and $X_{2}=\{y_{\alpha}\}$. Then $X_{1}$ and $X_{2}$ are disjoint by construction and necessarily uncountable (otherwise $X$ is not uncountable). Let $ Z= X_{1}\sqcup X_{2} $ and note that $X\setminus Z$ has at most one element, for otherwise we contradict the maximality of $A^{\star}$. Lastly, let $$ X_{1}^{\prime}= X_{1}\sqcup(X\setminus Z), $$ so that $X= X_{1}^{\prime}\sqcup X_{2}$, as desired.