Domain of a binary relationship and cardinality

Question

I need to write the proof of the following exercise: if $A\subset X \times Y$ is a binary relationship and $\operatorname{dom}(A)=\{a \in X \mid \exists b \in Y \; (a,b) \in A\}$ prove that $|\operatorname{dom}(A)|\leq|A|$. My solution is to note that the function $\pi\colon A \rightarrow \operatorname{dom}(A)$ is surjective and then the statement using AC. I would like to write a proof that doesn't require AC. Any suggestion?

Answer 1

You can't prove this without the axiom of choice.

Suppose that $X$ is an amorphous set, or really just a set such that $[X]^{<\omega}=\{Y\subseteq X\mid Y\text{ is finite}\}$ is itself Dedekind-finite. Then consider the relation $\{(n,Y)\mid Y\in[X]^{<\omega}, |Y|=n\}$, then the domain is $\omega$, but if there is an injection from $\omega$ into the relation, then we can find an infinite sequence of distinct sets in $[X]^{<\omega}$ which is impossible, since it is a Dedekind-finite set.

---

More generally, if $f\colon X\to Y$ is a surjective function, but there is no injection from $Y$ to $X$, then $f^{-1}$ is an example of a relation whose domain is $Y$, but there is no injection from $Y$ into $f^{-1}$, because that would define an injection into $X$.

So in other words, the statement you're trying to prove is equivalent to the Partition Principle, which states "If there is a surjection from $X$ onto $Y$, then there is an injection from $Y$ into $X$".

PP proves, amongst other things, that every infinite set is Dedekind-infinite, choice from well-ordered families, and a few more things. It is currently an open problem whether or not PP implies AC.