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.

Suppose $f:X\rightarrow Y$ is a surjection and you want to show that there exists $g:Y\rightarrow X$ s.t. $f\circ g=\mathrm{id}_Y$. You need the AC to show this.

However, suppose $f$ is a injection and you want show there is $g$ s.t. $g\circ f=\mathrm{id}_X$. Then, according to my textbook, you don't need the AC to show this.

This is counterintuitive to me, because it's like you need a special axiom to claim that an infinite product of big sets is nonempty, while you don't need one to claim that an infinite product of singleton sets is nonempty, which seems smaller than the former.

So why don't you need the AC to show the latter?

EDIT: $X$ should be nonempty.

EDIT 2: I realized (after asking this) that my question mostly concerns whether the AC is needed to say that an infinite product of finite sets is nonempty, and why.

share|improve this question
    
I can't fix your details (Asaf will probably see to that) but here's the intuition: Why do we need AC? Because with big sets, the problem is specifying how to pick the elements. No such problem with singleton sets! –  Ragib Zaman Apr 16 '12 at 13:32
    
Making one choice (or some fixed finite number of choices) doesn't require Axiom of Choice. It's entailed by first-order logic, q.v. Rule C. –  hardmath Apr 16 '12 at 13:42
    
hardmath: your comment is best in answering my question as I hold in my heart. Could you please elaborate on that? –  Pteromys Apr 16 '12 at 13:47
    
@Pteromys: Read this answer to why we can choose from non-empty sets. Finitely many choices follow by induction. –  Asaf Karagila Apr 16 '12 at 13:48
2  
@Pteromys: As others have noted, the Axiom of Choice is needed to deal with infinite products of different sets, even in the case those sets each contain two elements. We've moved sufficiently far from your original Question, it might be best to formulate a new one if you want elaboration! –  hardmath Apr 16 '12 at 14:58

1 Answer 1

up vote 10 down vote accepted

The need for the axiom of choice is to choose arbitrary elements. Injectivity eliminates this need.

Assume that $A$ is not empty, if $f\colon A\to B$ is injective this means that if $b\in B$ is in the range of $f$ then there is a unique $a\in A$ such that $f(a)=b$.

This means that we can define (from $f$) what is the $a$ to which we send $b$.

So if $f$ is not onto $B$ we have two options:

  1. $b\in B$ in the range of $f$, then we have exactly one option to send $b$ to.
  2. $b\in B$ not in the range of $f$. Since $A$ is not empty fix in advance some $a_0\in A$ and send $b$ to $a_0$.

Another way to see this is let $B=B'\cup Rng(f)$, where $B'\cap Rng(f)=\varnothing$. Fix $a_0\in A$ and define $g|_{B'}(x)=a_0$. For every $b\in Rng(f)$ we have that $f^{-1}[\{b\}]=\{a\in A\mid f(a)=b\}$ is a singleton, so there is only one function which we can define in: $$\prod_{b\in Rng(f)}f^{-1}[\{b\}]$$

Now let the unique function in the product be $g|_{Rng(f)}$ and define $g$ to be the union of these two.


Your intuition about the need for the axiom of choice is true for surjections, if $f$ was surjective then we only know that $f^{-1}[\{b\}]$ is non-empty for every $b\in B$, and we need the full power of the axiom of choice to ensure that an arbitrary surjection has an inverse function.


To the edited question:

The axiom of choice is needed because we have models in which the axiom of choice does not hold, where there exists an infinite family of pairs whose product is empty.

There are weaker forms from which follow choice principles for finite sets. However these are still not provable from ZF on its own.

As indicated by Chris Eagle in the comments, and as I remark above, in a product of singletons there is no need for the axiom of choice since there is only one way to choose from a singleton.

Further reading:

  1. Finite choice without AC
  2. axiom of choice: cardinality of general disjoint union
share|improve this answer
    
Why not just "flip the graph" with $(x,y) \mapsto (y,x)$ to get a function $g: f(X) \to X$ (since $f$ is injective) and extend it to $Y \smallsetminus f(X)$ by $g(y) = x_0$ as you said? –  t.b. Apr 16 '12 at 13:42
    
@t.b.: Yes, this is essentially what I wrote there. The OP mentioned infinite products, so I chose that argument. Of course both are equal. –  Asaf Karagila Apr 16 '12 at 13:43

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.