In the foundations of mathematics, it's interesting to consider the axiom that the Category of Sets Has Enough Projectives; in short: CoSHEP (pronounced /ko:-shep/). This is more commonly known as the presentation axiom: PAx. It is a weak form of the axiom of choice.
In elementary terms, CoSHEP states
The full axiom of choice states that every surjection has a section; hence in the above may be chosen to be itself.
This should be read in view of the definition of projective objects:
Accordingly, in a topos the CoSHEP axiom says equivalently
Borrowing from the philosophy of constructivism, we may also call this a complete presentation.
The dual axiom, that has enough injectives (that is, every set admits an [injection into an injective set) is true in every topos: every power object is an injective object, and every object embeds in its power object via the singleton map .]
Although perhaps not well known in the literature of constructive mathematics, the CoSHEP axiom may be justified by the sort of reasoning usually accepted to justify the axioms of countable choice and dependent choice (which it implies, by Proposition 1 below).
To be explicit, every set should have a ‘completely presented’ set of ‘canonical’ elements, that is elements given directly as they are constructed without regard for the equality relation imposed upon them. For canonical elements, equality is identity, so the BHK interpretation of logic justifies the axiom of choice for a completely presented set. This set is , and is obtained from it as a quotient by the relation of equality on . This argument can be made precise in many forms of type theory (including those of Martin-Löf and Thierry Coquand), which thus justify CoSHEP, much as they are widely known to justify dependent choice.
The existence of sufficiently many projective presentations plays a central role in homological algebra as a means to construct projective resolutions of objects. Tradtionally one often uses the axiom of choice to prove that categories of modules have enough projectives, on the grounds that the free modules are projective.
But the weaker assumption of CoSHEP is already sufficient for this purpose: while not every free module will be projective, one can still use CoSHEP to find a projective presentation for every free module (and thus for every module). This is discussed in more detail here.
Note that we normally assume (3) for the category of sets, which is true in any (constructively) well-pointed pretopos and true internally in any pretopos whatsoever, so one normally says that DC and CC simply follow from the existence of enough projectives (CoSHEP). Equivalently, internal DC and internal CC follow from internal CoSHEP.
Condition 1 easily implies 2. Condition 2 says precisely that the natural numbers object is externally projective, and since is a retract of , it is projective under condition 2, so 2 implies 3. It remains to show 3 implies 1.
Let be inhabited, so there exists an entire relation given by a jointly monic span
and similarly let
be an entire binary relation. Let be a projective cover. Since is assumed projective, the cover admits a section , and the element lifts through to an element . Next, in the diagram below, lifts through the epi to a map , and then lifts through to a map (since is projective):
By the universal property of (see recursion), there exists a unique map rendering commutative the diagram
Clearly factors through , i.e., , thus proving that dependent choice holds under CoSHEP.
A topos in which CoSHEP holds but is not projective is , where is the category with three objects and exactly two non-identity arrows . For if is a functor with , , and , with and , then the map is epi but has no section, so is not projective. On the other hand, as noted below, every presheaf topos satisfies CoSHEP, assuming that itself does.
CoSHEP also implies several weaker forms of choice, such as the axiom of multiple choice and WISC. In weakly predicative mathematics, it can be combined with the existence of function sets to show the subset collection axiom.
When working in the internal logic of a topos, the “internal” meaning of CoSHEP is “every object is covered by an internally projective object.” (Compare with the internal axiom of choice: every object is internally projective.) As regards foundational axioms for toposes (in the sort of sense that the axiom of choice is regarded as “foundational”), the internal version of the presentation axiom should be taken as the default version.
Suppose that is (externally) projective in . Then satisfies PAx whenever it satisfies internal PAx.
Internal PAx does not follows from external PAx; see Example 3. However, if every object is projective (AC), then every object is internally projective (IAC).
A stronger version of PAx may be worth considering. Say that an object is stably projective if its pullback to any slice category is projective. Then stably projective objects are internally projective (proof?). Similarly, if we say that a topos satisfies stable PAx if every object is covered by a stably projective object, then a topos satisfies internal PAx if it satisfies stable PAx.
However, not every presheaf topos validates internal PAx, even though every presheaf topos validates external PAx. As an example, let be the category where is the disjoint sum , and preordered by taking the reflexive transitive closure of relations , , . The claim is that neither , nor any presheaf that maps epimorphically onto , can be internally projective. Indeed, consider the presheaf defined by and , with the evident inclusion. Let be the support of , so that we have an epi .
The objects , and are subterminal and . The set is empty because there is no (it would give a section of , but none exists), whereas is inhabited by . For any covering , the set is empty (because any section of induces a function ), and the set is inhabited (the map induces a map ). Thus the map cannot be epic.
Any topos that violates countable choice, of which there are plenty, must also violate internal PAx.
An interesting example of a topos that has enough projectives and satisfies internal CoSHEP (at least, assuming the axiom of choice in Set), although it violates the full (internal) axiom of choice, is the effective topos, and more generally any realizability topos. The reason for this is quite similar to the intuitive justification for CoSHEP given above. Technically, it results from the fact that realizability toposes are exact completions; an explanation is given in this remark.
Since Set is (essentially regardless of foundations) an exact category, if it has enough projectives then it must be the free exact category generated by its subcategory of projective objects. By the construction of the ex/lex completion , it follows that every set is the quotient of some “pseudo-equivalence relation” in ; i.e., the result of imposing an equality relation on some completely presented set. See SEAR+ε for an application of this idea.
flat object, flat resolution
Its relationship to some other weak axioms of choice is studied in