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

  • Thread starter Thread starter Swlabr1
  • Start date Start date
  • Tags Tags
    Injection
AI Thread Summary
The discussion revolves around the relationship between injections and surjections in set theory, particularly in the context of the Axiom of Choice (AOC). It is established that for an injection from set X to set Y, a surjection from Y to X can be constructed without invoking AOC, provided X is nonempty. The conversation highlights that while finite sets allow for straightforward selection of elements, issues arise when dealing with infinite or uncountable sets, complicating the ability to select elements without AOC. Participants express skepticism about the feasibility of selecting elements from arbitrary collections of non-empty sets, especially if those sets are uncountable. Ultimately, the consensus leans toward the idea that while AOC is crucial for infinite collections, it may not be necessary for finite cases, and valid constructions can be achieved within ZF set theory.
Swlabr1
Messages
15
Reaction score
0
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?
 
Physics news on Phys.org
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.
 
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.
 
Last edited by a moderator:
Evgeny.Makarov said:
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.
 
Deveno said:
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.
 
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.
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top