How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The contravariant power-set functor is monadic
Statement
The contravariant power-set functor
is monadic.
Facts & Assumptions
Given: The contravariant power-set functor between and .
An adjunction may be specified by a natural family of hom-set bijections (The unit-counit, hom-set, unit-universal, and counit-universal encodings of an adjunction are equivalent).
A conservative functor reflects isomorphisms (Conservative functor).
Direct and inverse image satisfy Beck–Chevalley for pullback squares of sets (Direct and inverse image satisfy Beck–Chevalley for pullback squares of sets).
A right adjoint equipped with a specified coequalizer for every reflexive pair is monadic when it preserves those coequalizers and reflects isomorphisms (Data-supplied crude monadicity theorem for reflexive coequalizers).
Every small diagram in has a limit (Set has all small limits, realized as compatible tuples in a set-indexed product).
Proof
A function is the same as a relation . Transposing gives a function , and transposition is natural and involutive. By [L1] this makes the power-set functor on the opposite side its own left adjoint.
If is bijective, then is surjective because otherwise and a singleton outside have the same preimage. It is injective because surjectivity of realizes each singleton of as a preimage, which separates points with different singleton membership. Thus is bijective and the functor is conservative by [L2], including when is empty.
A reflexive pair in corresponds to maps in with a common retraction , so . Define and let be inclusion. This formula supplies an equalizer for every such pair uniformly, so the opposite maps form the required specified family of reflexive coequalizers in .
The square with both left and top maps , and with bottom and right maps , is a pullback: if , applying gives . Hence [L3] gives for every ; the last equality also follows directly, while because .
Let satisfy . Applying this equality to and using step 2.1 gives . Define by . Then , and this factorization is unique because is surjective. Thus is the coequalizer of , so the power-set functor preserves every reflexive coequalizer in .
Step 1.3 supplies the required coequalizer family, while steps 1.1, 1.2, and 3.1 give the left adjoint, conservativity, and preservation hypotheses of [L4]. The crude monadicity theorem therefore proves that is monadic.
Depends on
- The unit-counit, hom-set, unit-universal, and counit-universal encodings of an adjunction are equivalent
- Data-supplied crude monadicity theorem for reflexive coequalizers
- Direct and inverse image satisfy Beck–Chevalley for pullback squares of sets
- Conservative functor
- Set has all small limits, realized as compatible tuples in a set-indexed product
- Opposite category $\mathcal C^{\mathrm{op}}$
- The power set $\mathcal{P}(x) = \{\, z : z \subseteq x \,\}$
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
25 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- E. Riehl, Category Theory in Context, 2nd ed., Theorem 5.5.9 (standard reference, not scraped)
- D. Mehrle, Category Theory Part III, Theorem 5.21 (standard reference, not scraped)