1
$\begingroup$

I am trying to prove that if cardinality of A is greater than cardinality of B, then there is no surjection from B onto A. Or any logically equivalent implication.

Formally,

card($A$) > card($B$) $\implies$ $\forall$ $f \in A^{B}$, $\exists$ $a \in A$ : $\forall b \in B$, $f(b) \neq a$.

It is my goal to avoid the use of the axiom of choice. Earlier I arrived at the equivalent implication

There exists a surjection from B onto A implies there exists an injection from A into B

But after defining the family of sets and failing to sufficiently arrive at the consequence I did some research and found that this statement does require the AC.

So I suppose my specific question is: can any logically equivalent statement be proven without the AC? Or is it just the direct proof of the second highlighted statement that requires AC?

Lastly, to be clear, the definition I am working with for card($A$) > card($B$) is there exists a set C that is a subset of A such that there is a bijection from $B$ onto $C$ but there is no bijection from $B$ into $A$

I will be on the computer for the next while and will be happy to post further information regarding my approaches and attempts if anyone wishes. Also I read through all the information here Overview of basic results on cardinal arithmetic regarding cardinals with and w/o AC and still couldn't deduce an answer.

$\endgroup$

marked as duplicate by Asaf Karagila elementary-set-theory Jan 18 '16 at 8:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

The assertion "if $\operatorname{card}A\gt\operatorname{card}B$ then there is no surjection from $B$ to $A$" can not be proved without the axiom of choice.

Let $A=\mathbb R\cup\Omega$ where $\mathbb R$ is the set of all real numbers and $\Omega$ is the set of all countable ordinals, and let $B=\mathbb R.$

There is a surjection from $B$ to $A$. To see this, partition $\mathbb R$ into two disjoint sets $X$ and $Y$ where $\operatorname{card}X=\operatorname{card}Y=\operatorname{card}\mathbb R.$ Then there is a bijection from $X$ to $\mathbb R,$ and there is a bijection from $Y$ to $\mathcal P(\mathbb N\times\mathcal N),$ and there is a surjection from $\mathcal P(\mathbb N\times\mathbb N)$ to $\Omega$; that last surjection maps each subset of $\mathbb N\times\mathbb N,$ which happens to be a well-ordering relation, to its order type.

Without the axiom of choice, you can't prove that there is an uncountable set of real numbers which can be well-ordered. If no uncountable set of real numbers can be well-ordered, or in other words there is no injection from $\Omega$ to $\mathbb R,$ then $\operatorname{card}A\gt\operatorname{card}B.$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.