To prove the elementary statement without using AC and AF I have little knowledge in set theory and I have difficulty in proving the following statement without using Axiom of Choice or Axiom of Foundation:
Let $A$ be a set. Then there exists a set $B$ satisfying the following conditions:
$A\cap B=0$ and there exists a one-to one function $f$ from $A$ onto $B$.
I considered $A\times \mathscr{P}(A)$, and assumed that $(A\times \{X\})\cap A\neq\varnothing$ for all $X\subset A$. Then, it gives a partition $\mathscr{C}$ of $A$ which seems larger than $A$. However, I failed to complete the proof without using AC, since I needed to construct an one-to-one function from $\mathscr{C}$ into $A$ to complete the proof. I also found the proof using axiom of foundation, but as the statement is elementary, I belive that there might be a way to prove the statement without the above axioms.
In summary, is the statement consistent over $\{ZF-\text{Axiom of Foundation}\}$?
 A: Copying my (unaccepted) answer to this other question:
Lemma. Given a set $A$, we can find a set $B$ such that $|A|=|B|$ and $A\cap B=\emptyset.$
Proof. Let
$$T=\{(S,a):S\subseteq A,\ a\in A,\ (S,a)\in A,\ (S,a)\notin S\}\subseteq A$$
and let
$$B=\{(T,a):a\in A\}.$$
Clearly $|A|=|B|.$ Assume for a contradiction that $A\cap B\ne\emptyset,$ i.e., there is an element $a\in A$ such that $(T,a)\in A.$ Then we get the Russell paradox in the form
$$(T,a)\in T\iff(T,a)\notin T.$$
A: This somewhat depends on how you are coding ordered pairs, as there are many ways to do so. But ultimately this consists of two steps:


*

*Find some $x$ such that $x$ is not in any ordered pair which may appear in $A$; and

*define $B$ to be $A\times\{x\}$.
Neither step is particularly difficult. Consider $X=\{u\mid\exists a(\langle a,u\rangle\in A\}\}$. Next define $x=\{S\in X\mid S\notin S\}$. The standard Russell argument shows that $x\notin X$, otherwise $x\in x$ and $x\notin x$.
Next, note that $f(a)=\langle a,x\rangle$ is a defined function, and indeed a bijection between $A$ and $A\times\{x\}$. Finally, if $u\in A\cap (A\times\{x\})$, then $u$ is an ordered pair of the form $\langle a,x\rangle$, in which case $x\in X$ by the definition of $X$; and since $x$ was taken as an element which is not in $X$, this is impossible.
