Questa non è nemmeno algebra, è teoria degli insiemi, e no, non puoi dimostrarlo senza assioma della scelta. Infatti (se ZF è consistente) esistono modelli di ZF in cui esistono bestialità come gli insiemi amorfi che praticamente hanno come sottoinsiemi solo i sottoinsiemi finiti e i loro complementari.
Comunque un modo più elementare di dimostrare quello che ti interessa è moltiplicarle l'insieme $X$ per un insieme con due elementi ${a, b} $usare che ha la stassa cardinalità dell'insieme di partenza e considerare $X\times{a} $ e $X\times{b} $.
Un'altra cosa che si può dire in merito a questa questione è che non serve la piena potenza dell'assioma della scelta, infatti basta la versione dipendente che ti garantisce che in un insieme infinito ha sempre un sottoinsieme numerabile (infinito) quindi preso lui e il complementare hai la tesi (a meno che l'insieme non sia numerabile ma allora è banale).
Nota che in questo caso i due insiemi non hanno la stessa cardinalità, mi pare infatti (ma non sono sicurissimo) che se li vuoi della stessa cardinalità diventa equivalente all'assioma della scelta.