Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In DC Proof I've defined equal cardinality to mean there are two onto functions $g:A\to B$ and $h:B\to A$. I want to prove this means there exists a function $f:A\to B$ that is both 1-1 and onto (which is an alternative definition of equal cardinality).

For finite equal cardinality sets onto implies 1-1, but I see no way to construct a 1-1 function when you can have a pair of non-injective onto functions.

share|improve this question
4  
Sounds like Bernstein-Cantor-Schroeder. But in your question you are given a pair of onto functions, rather than a pair of 1-1 functions. By the way, what is DC theory? –  Srivatsan Sep 3 '11 at 15:39
1  
@Mark: Abuse the axiom of choice: since $g$ and $h$ are both surjective, they have right inverses, which must be injective. Then use the Cantor–Bernstein—Schroeder theorem, as Srivatsan suggests above. But perhaps you are in a context where the axiom of choice is disallowed... –  Zhen Lin Sep 3 '11 at 15:47
    
@SrivatsanNarayanan: DC Proof is a formal proof system. –  Mark Hurd Sep 3 '11 at 15:49
    
I can use the Axiom of Choice if I have to. This just as a 'hobby'. –  Mark Hurd Sep 3 '11 at 15:50

2 Answers 2

up vote 3 down vote accepted

Under the axiom of choice it is quite simple to construct the bijection. We do it the following way:

Lemma: The axiom of choice implies the assertion that every surjective function admits an injective inverse.

Proof: Assuming the axiom of choice and $f\colon A\to B$ is onto $B$, let $A_b=\{a\in A\mid f(a)=b\}$. For every $b\in B$ we have that $A_b\neq\varnothing$ and therefore there is some a choice function $\check f(A_b)\in A_b$, since $b\mapsto A_b$ is a bijection we can define $\tilde f$ to be the map $b\mapsto \check f(A_b)$.

Now we have that $\tilde f$ is injective, and $f(\tilde f(b))=b$ by definition.

(While irrelevant to this case, there exists a proof in the other direction as well.)

Now we can simply turn the theorem you are seeking into the usual Cantor-Bernstein theorem.

Suppose $f\colon A\to B$ and $g\colon B\to A$ are surjective functions. Let $\tilde f\colon B\to A$ and $\tilde g\colon A\to B$ defined as in the lemma. By the Cantor-Bernstein theorem we have $h\colon A\to B$ which is a bijection.


As a side comment, I would recommend on defining cardinality in terms of injective functions rather than surjective functions. Of course that if the axiom of choice is assumed it is the same thing. However without the axiom of choice it the dual Cantor-Bernstein is provable without some choice, or without implying some choice. [T. Jech, The Axiom of Choice, Exercise 11.8, p. 162]

Therefore assuming injective functions makes cardinality an equivalence relation without the axiom of choice, while surjective functions will not form an equivalence relation, so $|A|=|B|$ and $|B|=|C|$ but we won't have $|A|=|C|$.

share|improve this answer

What you need is the dual Schröder-Bernstein theorem: if there are surjections from $A$ to $B$ and from $B$ to $A$, then there is a bijection between $A$ and $B$. For this you definitely need some axiom of choice.

Let BP be the statement that all subsets of $2^\omega$ have the Baire property; BP is inconsistent with AC. It’s known that Con(ZF) $\Rightarrow$ Con(ZF+BP), and Benjamin D. Miller has proved in ZF+BP that the dual Schröder-Bernstein theorem is false. Specifically, let $E$ be the equivalence relation on $2^\omega$ defined by $xEy \Leftrightarrow \exists n < \omega \forall m \ge n (x(m)=y(m))$; he’s shown that in ZF+BP there are surjections from each of $2^\omega$ and $2^\omega/E$ onto the other but no injection from $2^\omega/E$ into $2^\omega$.

The result can be found in the note The dual Schröder-Bernstein theorem and Borel equivalence relations, available here. You’ll find a little more information in this MathOverflow question and the ensuing discussion.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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