Inverting Injections and Surjections: A Discussion of the Axiom of Choice

[Swlabr1]

If there exists an injection $f: X\rightarrow Y$ then there `obviously' exists a surjection $g:Y\rightarrow X$, got by noting that the restriction of $f$ to $f(X)$ is a bijection between $X$ and $f(X)$ and so invertible, and then mapping everything else in $Y$ to some fixed element in $X$. However, we have to `choose' this element, and I was wondering if there are any problems in doing this (w.r.t. the axiom of choice)?

If we do have to invoke AOC, is there any way of `inverting' an injection to get a surjection without using AOC?

 

[Evgeny.Makarov]

I believe it is not needed here. Note that, given an injection from X to Y, we need to require that X is nonempty to be able to find a surjection from Y to X. Now, if follows from the axiom (or definition) of the empty set that a nonempty set has an element. This element can be used to map the rest of the elements of Y.

AC is important when when there is an infinite collection of nonempty sets and one has to build a single function that chooses an element of each set. If there is just one or finitely many nonempty sets, then such function can be described in a finite way.

 

[mvCristi]

In ZFC, try to use Axiom schema of specification with Axiom schema of replacement (with Axiom schema of collection). I did not check, but it should work. Functions on sets are morphisms in set theory. My educated guess is that ZF (without the Axiom of choice) are strong enough to allow such an algebraically fundamental concept.

 

[Deveno]

I believe it is not needed here. Note that, given an injection from X to Y, we need to require that X is nonempty to be able to find a surjection from Y to X. Now, if follows from the axiom (or definition) of the empty set that a nonempty set has an element. This element can be used to map the rest of the elements of Y.

AC is important when when there is an infinite collection of nonempty sets and one has to build a single function that chooses an element of each set. If there is just one or finitely many nonempty sets, then such function can be described in a finite way.

i see a problem, here. what if X IS such a collection of non-empty sets? i sincerely doubt that there exists a way to select "any" element from an abitrary single set in a finite way. what if X is uncountable? the problem is: just calling X "a single set" does not mean X has a simple internal structure that can be finitely described.

 

[Opalg]

i see a problem, here. what if X IS such a collection of non-empty sets? i sincerely doubt that there exists a way to select "any" element from an abitrary single set in a finite way. what if X is uncountable? the problem is: just calling X "a single set" does not mean X has a simple internal structure that can be finitely described.

Calling X "a single set" means that X is a set. On the other hand, "a collection of non-empty sets" need not be a set.

One of the basic ingredients in set theory is that the definition of a set has to be constrained (so as to avoid Russell's paradox), so that an arbitrary collection of elements is not necessarily a set. However, if X is a set, then it is legitimate, within ZF without C, to choose an element of X.

Given an injection $f:X\to Y$, it is implicit that the domain $X$ is a set. The OP's argument for constructing a surjection from $Y$ to $X$ (a left inverse for $f$, in fact) is valid in ZF with no need for AoC.

 

[Deveno]

i understand that a family of sets need not be a set itself. but suppose that our "X" is a Hamel basis for the real numbers over the rational field. X is a subset of the real numbers, and so it's clearly a set. there is a natural injection (inclusion) of this basis into the real numbers. in fact, we can consider the subset X' = X - {1}, and inclusion is still an injection. so we pick an element of X'...how?

with a countable set X, we can leverage the bijection and well-ordering of N to pick a "least" element of X. i am uncertain how one goes about generating a well-defined choice from an uncountable set. this may be sheer ignorance on my part, if so...please, enlighten me.