Entire relation, projective object and choice object, and the axiom of choice

axiom-of-choicecategory-theorytopos-theory

I was reading on the axiom of choice and I came across these few statements in nLab:

  1. Projective object: $P$ is projective if for any morphism $f: P \rightarrow B$ and any epimorphism $q: A \rightarrow B$, $f$ factors through $q$ by some morphism $P \rightarrow A$.

  2. The axiom of choice can be phrased as "all objects of the category of sets are projective".

  3. Entire relation: A binary relation from a set $X$ to a set $Y$ is called entire if every element $X$ is related to at least one element of $Y$.

  4. The axiom of choice says precisely that every entire relation contains a function.

  5. A set $A$ is projective iff every entire relation from $A$ to set $B$, for any $B$, contains a function $A \rightarrow B$.

  6. A set $B$ is choice iff every entire relation from a set $A$ to $B$, for any $A$, contains a function $A \rightarrow B$.

Statement 1, 2: https://ncatlab.org/nlab/show/projective+object

Statement 3, 4: https://ncatlab.org/nlab/show/entire+relation

Statement 5, 6: https://ncatlab.org/nlab/show/choice+object

My question is, how are the statements related. That is, how is (1) and (5) related, how is (2) and (4) related, and how does (6) sit in this whole picture (is there any significance of this statement)?

Best Answer

Perhaps lets start with the relations between surjections, entire relations, and indexed families of nonempty sets.

It turns out these three notions are equivalent.

Suppose $f:A\to B$ is a surjection. Define a relation $R:B\to A$ by $bRa\iff f(a)=b$. Since $f$ is surjective, this relation is entire. On the other hand, if $b\in B$, define $A_b = f^{-1}(\{b\})$, since $f$ is a surjection, each $A_b$ is nonempty, so we have a family of (disjoint) nonempty sets indexed by $B$.

Now suppose we have an entire relation $R:B\to A$. Define $A_b = \{a\in A: bRa\}$, which gives a family of nonempty sets indexed by $B$, since $R$ is entire. Finally, define $$A'=\bigsqcup_{b\in B} A_b,$$ and $f:A'\to B$ by $f(a,b)=b$.

Lastly, suppose we start with a family of nonempty sets indexed by $B$, $A_b$. Then again, we define $A'=\bigsqcup_{b\in B} A_b$, and $f:A'\to B$ by $f(a,b)=b$, which is surjective, since all the $A_b$ are nonempty. On the other hand, we can define an entire relation $R:B\to A'$ by $b R (a,b)$. (Or we could take $A=\bigcup_{b\in B} A_b$ and $R:B\to A$ by $bRa \iff a\in A_b$.)

Choice

One version of the axiom of choice says that if $A_b$ is a family of nonempty sets indexed by $B$, then there is a function $$g:B\to A'= \bigsqcup_{b\in B} A_b$$ such that $fg=1_B$, where $f:A'\to B$ is the surjective function constructed above. $g$ is called a choice function.

Now the relationship between the statements of choice in the question is the following:

The following are equivalent 1. Choice (as stated just now) 2. Every surjective function has a right inverse. 3. Every set is projective 4. Every entire relation contains a function

Proof

(1) $\implies$ (2): Given a surjective function $f:A\to B$, and applying choice to the family of sets $A_b=f^{-1}(b)$, we get a function $g:B\to A$ such that $fg =1_B$.

(2) $\implies$ (3): Suppose $f:A\to B$ is surjective, and $h:X\to B$ is any map of sets. To show that all sets are projective, it suffices to show that we can always lift $h$ to a map $\tilde{h}:X\to A$. However, if $g:B\to A$ is a left inverse, then we can take $\tilde{h}= gh$, since then $f\tilde{h}=fgh=h$.

(3) $\implies$ (1): Suppose $A_b$ is a family of nonempty sets. Then $f : A'\to B$ is surjective, and $B$ is projective, so we can lift $1_B$ along $f$ to a map $g:B\to A'$ such that $fg=1_B$, which is the statement of choice.

(4) $\implies$ (2): If $f:A\to B$ is surjective, and $R:B\to A$ is the entire relation constructed above, and $g:B\to A$ is a function contained in $R$, then by definition, $bRg(b)$, which means that $fg(b)=b$, so $g$ is a right inverse to $f$.

(1) $\implies$ (4): If $R : B\to A$ is an entire relation, then we defined a family of nonempty subsets $A_b=\{a\in A: bRa\}$. Letting $\tilde{g}:B\to A'$ be a choice function for this family, we have $\tilde{g}(b) = (a,b)$ for some $a$ with $bRa$, and we define $g:B\to A$ by $g(b)=a$, which gives a function contained in $R$. $\blacksquare$

The relations of the statements in your question

(1) is the definition of projective, which is used in statement (5).

I just showed (2) and (4) are equivalent to choice.

(6) is equivalent to saying that any family of nonempty sets indexed by $B$ has a choice function, so it's choice for sets indexed by that set.

Related Question