A model-theoretic ultralimit is the elementary direct limit of a chain of successive ultrapowers along their diagonal embeddings. We will build two such chains with isomorphic limits. This is not a topological ultrafilter limit and does not require the stronger claim that one ultrapower of each structure is already isomorphic.
First prove the Frayne embedding lemma, including the relative form needed to make the diagrams commute. If , expand the language by constants naming every element of , and let be its complete elementary diagram. Index by finite subsets of this diagram. The finitely many constants in can be interpreted in so that holds: existentially quantifying them gives a sentence true in and hence in . Choose such interpretations, and give unused constants an arbitrary fixed value in the nonempty domain of .
For each diagram sentence , its cone has the finite intersection property with the other cones. Extend the generated filter to an ultrafilter . For , let be its chosen interpretation at coordinate . The map
is elementary by Łoś: every formula true of a tuple from , or its negation, is a diagram sentence and holds on its corresponding cone. In particular distinct named elements stay distinct.
If , the construction can keep every constant naming equal to that same at every coordinate. For a finite diagram fragment, existentially quantify just the names outside ; the resulting formula with parameters in is true in , hence true in . Thus the finite realizations still exist with all those old names fixed. Consequently
This relative extension of the diagonal map is the essential strengthening.
Now let . The nonrelative lemma embeds into an ultrapower of . Identify the image with a copy of inside . Since , the relative lemma embeds into an ultrapower of extending its diagonal map. Rename this larger structure so that the displayed copy of is a literal elementary substructure. Next apply the relative lemma over to embed into an ultrapower of fixing its diagonal copy. Continue alternately. We obtain a coherent elementary chain
with as well. Each inclusion is, up to these coherent identifications, the diagonal embedding into its ultrapower; the same holds for . It is the relative clause, not merely the existence of arbitrary elementary embeddings, which guarantees this.
By the elementary chain theorem, the unions of the two subsequences are elementary limits. They are the same structure: each lies in a subsequent , and each lies in . Hence the alternating ultrapowers give isomorphic ultralimits construction proves
Conversely each ultrapower and each elementary direct limit has the same first-order theory as its starting structure. Isomorphic ultralimits therefore imply as well. Thus the conclusion exactly characterizes elementary equivalence at the level of ultralimits.
We prove the Ehrenfeucht-Mostowski theorem by ordered products of ultrafilters, without using Ramsey's theorem. Choose a Skolem expansion of the infinite structure and distinct elements . Fix a nonprincipal ultrafilter on .
For a finite increasing subset of the desired index order , define the ordered Fubini product of ultrafilters on by
The notation means that the set of satisfying belongs to ; the leftmost quantifier is outermost. Upward closure and intersection follow successively at each coordinate, and applying complement at each step proves the ultrafilter dichotomy. Products are ordered; no false claim of symmetry is needed.
Put , with . If , pullback of a function by coordinate projection induces
For a cylinder condition involving only coordinates in , deleting the unused ultrafilter quantifiers makes its membership in exactly its membership in . The Łoś theorem therefore makes an elementary embedding, not merely a homomorphism. The projection identities give .
Take the directed limit of this system: elements from two stages are identified if their images agree at a common larger finite stage, and formulas are evaluated at such a stage. Elementary coherence makes this well-defined. It also makes each stage elementary in the limit: a formula uses finitely many parameters, and an existential witness at a later stage can be pulled back at the level of existential truth because the transition maps are elementary. Denote the limit by .
For each , let be the limit image of the coordinate function . These elements are distinct. For , after fixing , equality holds for at most one , a set not in ; hence equality fails in the two-coordinate ultrapower and therefore in the limit.
For any increasing , Łoś evaluates
The right-hand side depends on the formula and the number of increasing coordinates, not their particular indices. Thus is order-indiscernible for every formula of the expanded language simultaneously; no preliminary homogeneous thinning is used. If elements of were named before expanding, the same computation gives indiscernibility over those names and the initial stage embeds the original structure into the limit.
The Skolem hull of these generators is elementary by the witness property. Transporting the generators by any order automorphism of transports every term, with well-definedness and relation preservation supplied by the formula equivalence just proved. The inverse transport supplies an inverse automorphism. The ordered-ultrapower construction gives the full Ehrenfeucht–Mostowski model and its order automorphisms without Ramsey's theorem.
A useful precise form of the Ehrenfeucht-Mostowski theorem is this: for an infinite structure and any linear order , a model of can be generated as a Skolem hull by distinct order indiscernibles . Every order automorphism of extends to an automorphism of that hull in the chosen Skolem language. One may first name all elements of , giving an elementary extension containing the original structure. The generation and uniqueness assertions concern this specified expansion, not arbitrary automorphisms of its reduct.
Choose a Skolem expansion : for each existential formula add a function selecting a witness whenever one exists. Introduce constants for . Take the theory of , distinctness of these constants, and all equivalences
The formulas here are in the fixed expanded language, without the newly added as extra parameters. If naming , use its complete elementary diagram and allow those original names in the formulas.
Every finite fragment has a model by Ramsey's theorem. Only finitely many formulas and constants occur. Take a sequence of distinct elements of . For each arity appearing, color the increasing tuples from this sequence by the finite vector of truth values of all formulas of that arity. Successive Ramsey thinning gives an infinite subset homogeneous for each of these finitely many colorings. Assign the finitely many constants in increasing order to distinct elements of this subset. This satisfies every displayed equivalence in the fragment; the original theory is satisfied because the underlying structure remains . Compactness now gives a model of the full theory, with the required order-indiscernible sequence.
The substructure generated by the constants under the Skolem functions is elementary: any existential formula with parameters which are terms in the generators has its Skolem witness in that same hull. If is an order automorphism of , define
Indiscernibility makes this well-defined, by applying it to the equation between any two term representations using the increasing tuple of all their indices. The same argument preserves every relation and function; supplies the inverse. It is unique in the generated Skolem structure. This completes the Ramsey proof, rather than stopping at the existence of indiscernibles.
For simple typed set theory with atoms, use sorts and membership only from to . A set predicate distinguishes sets from atoms, extensionality compares sets of the same positive type, and comprehension produces in type every subset of defined by a well-typed formula. Atoms have no members. First-order models use Henkin semantics; they are not required to have their next domain equal to the full external power set. Typical ambiguity is the schema for each closed sentence, where every sort index in is raised by one.
We show finite satisfiability of this entire typed theory with ambiguity. Choose a list of ranks above , spaced by at least two. For a finite increasing selection of ranks , let
where is the set of objects declared to be sets at type . Membership from to is ordinary membership restricted to objects of ; all other type- objects are atoms. The spacing puts inside . Thus comprehension and set extensionality hold exactly, and atoms have no typed members. There are infinitely many objects at every visible type, so any usual typed infinity requirement also holds.
The auxiliary rank provides a uniform interpretation if a set predicate is allowed at type zero; no type-minus-one domain is used in the theory. This avoids artificially declaring all type-zero objects to be atoms, which would not be invariant under type-raising. If the language has no type-zero set predicate, simply ignore this auxiliary interpretation.
A finite set of ambiguity instances uses finitely many closed sentences of bounded highest type, say at most . Color increasing -tuples of ranks by their finite truth vector in the structure with visible domains and the auxiliary preceding rank. Ramsey's theorem gives an infinite homogeneous rank set. Choose consecutive ranks from it and build the hierarchy on all these ranks. The first window evaluates each original sentence; shifting the window one place evaluates its uniform type-raise. Homogeneity makes the truth vectors equal. All finite typed axioms and the selected ambiguity instances therefore hold together. Choosing large enough covers every sort needed by the finite fragment. Many-sorted compactness, equivalently ordinary first-order compactness after encoding sorts, yields
This is a model existence argument in the ambient set theory; no equality of adjacent type cardinalities is claimed. The gaps between ranks supply atoms, and the ambiguity is about truth of sentences, not a bijection between domains.
A well-quasi-ordering is a preorder in which every infinite sequence has with . A sequence without such a pair is a bad sequence. We use rooted-tree homeomorphic embedding: an injective map of vertices preserving lowest common ancestors, so edges may become paths and a source root may map below the host root. Labels, when present, must increase in their label preorder. This convention is important; adjacency-preserving embeddings do not give the same theorem.
We first prove the auxiliary Higman lemma. If is a well-quasi-order, its finite words are well-quasi-ordered by subsequence embedding with increased letters. Suppose not, and choose a minimal bad sequence of words: at each position choose one of least length among those permitting a bad continuation of the preceding prefix. No word is empty. Write by deleting its last letter. A well-quasi-order has an infinite nondecreasing subsequence of any sequence: if no member of an infinite subsequence had infinitely many later upper bounds within it, one could recursively avoid the finitely many upper bounds of earlier choices and construct a bad sequence. Choose a member with infinitely many later upper bounds, restrict to those bounds and repeat. Apply this to get .
The sequence is still bad. An earlier prefix word embedding into a would embed into , contrary to the original bad sequence. An embedding would extend by the comparable last letters to , equally impossible. But its next word at position is strictly shorter than , contradicting minimality. This proves Higman's lemma, including the possibility that a deleted word is empty, since that would make the proposed bad continuation impossible immediately.
We now prove the labelled version of Kruskal's tree theorem for labels in any well-quasi-order . Assume there is a bad sequence , and choose one minimal in vertex count at each position, subject to bad extendibility. Let be the collection of rooted subtrees obtained by deleting a root and taking one of its child branches, over all .
This collection is well-quasi-ordered. Otherwise take a bad sequence from . Only finitely many of these objects can come from any bounded initial segment of the , since that segment has only finitely many child branches and a bad sequence cannot repeat an object. Pass to a subsequence with a child branch of and . Then
is bad: a prefix tree embedding into would embed into , and the are already bad among themselves. The next object has fewer vertices than , contradicting the minimal bad choice. Notice that a child branch does embed into its full tree under the stated homeomorphic convention.
List each tree's child branches in any chosen order. The preceding result and Higman's lemma make these finite lists well-quasi-ordered. The product of two well-quasi-orders is well-quasi-ordered: first thin to an infinite nondecreasing subsequence in one coordinate and then find an increasing pair in the other. Therefore there are such that the root label of increases to that of , and the child list of embeds as a subsequence into the child list of , with each source branch homeomorphically embedding into its matched branch.
Map the root of to the root of , and use these branch embeddings below it. Different child branches map into different host branches, so their lowest common ancestor maps to the host root. Within each branch it is preserved by the chosen embedding. Thus the whole map is injective, preserves all lowest common ancestors and respects labels, contradicting badness. Finite rooted trees labelled by a well-quasi-order are well-quasi-ordered under homeomorphic embedding. Taking one label proves Kruskal's tree theorem. If one uses a root-preserving convention, mark the root by a separate label incomparable with all ordinary labels and apply the labelled theorem; the marked root then has to map to the marked root. No adjacency-preservation assertion is being made.
For Friedman's finite form of Kruskal's theorem, fix . The required finite conclusion is
Assume there were arbitrarily long bad sequences satisfying these size bounds. Form the tree of their finite prefixes, using rooted-tree isomorphism classes as objects. At position only finitely many finite rooted trees have at most vertices, so this prefix tree is finitely branching and has nodes at arbitrarily large depths. König infinity lemma supplies an infinite branch: at each step some child must still have arbitrarily deep extensions, because there are only finitely many children. The branch is an infinite bad sequence of finite rooted trees, contradicting Kruskal's theorem. Thus such an exists. The argument also works for any prescribed size-bound function, or any fixed finite label set, because each position then still has finitely many possible objects.
The Rieger-Bernays permutation model changes membership, not the underlying domain. In a model of ZF, let be a definable class bijection, with parameters allowed, and define
Every old set is the new extension of precisely the object . Translation of formulas replaces each membership assertion by this definable relation. Both images and inverse images of old sets under are sets by replacement.
Here are the axiom checks. Extensionality follows because equal new extensions mean and hence . The new empty set is and the new pair is . For an object , new union and power set have representatives
These formulas verify the actual new membership conditions. A definable subset of the new extension is an old set by separation after translation, and its representative gives new separation. Similarly, a functional new formula on that extension has an old set as range by replacement; apply to its range. For infinity, iterate the new successor operation
starting from the new empty set. Old recursion and replacement collect its finite iterates into a set , and is a new inductive set. Thus all axioms of ZF except possibly foundation hold.
Now swap the old objects and and fix everything else. The old object then satisfies , and its entire new extension is . It is a Quine atom, so foundation fails. Taking to be the identity gives the original model where foundation holds. Foundation is independent of the other ZF axioms, relative to consistency of ZF.
A full permutation of a model of choice does not destroy choice. Given a new family of nonempty new sets, old choice selects an element of each old extension ; replacement converts its graph into new ordered-pair coding. Thus simply repeating the preceding unrestricted permutation construction would not prove independence of choice. The extension needed is the hereditarily finite-supported Quine-atom model.
Start with a model of ZFC and simultaneously swap with for all . These transpositions have disjoint supports: none of these infinite ordinals is a singleton, and the ordinals and their singletons are separately distinct. Put , whose members now have new extensions . Build the universe over these Quine atoms by allowing arbitrary new sets of previously constructed objects at each successor stage, and taking unions at limit stages. More explicitly, begin with , put
and take the union over all ordinals. The singleton with sole member is already , as extensionality requires; it is not added as a different atom or set. Every other object's membership has a well-founded construction rank once these designated atomic self-loops are treated as rank-zero leaves.
Every permutation of extends to an automorphism of this universe: on atoms use , and on every non-atomic object recurse by
The inverse permutation gives its inverse, and the formula preserves . Call an object supported by a finite when every permutation fixing pointwise fixes that object. Retain only objects which are supported and all of whose members are hereditarily supported; the recursion here again stops at atoms, whose support is their singleton. Denote this class by .
We verify that is a model of ZF without foundation. It is membership-closed and hence retains extensionality. Pairing uses the union of the two parameter supports, and union uses the support of its input. For separation, use the finite union of the supports of the domain and all parameters: permutations fixing them preserve satisfaction in , so they fix the defined subset. Every member remains hereditary. For replacement, the same support fixes the image of a definable functional relation; its elements already lie in by the internal range condition, and old replacement supplies the underlying set of them. These assertions are legitimate class translations because construction ranks, supports and hereditary support are definable in the starting model.
For power set, start with the set of all new subsets of a supported set and retain exactly those lying in . The resulting collection is fixed by every permutation fixing the original set's support: the action preserves hereditary support and permutes its subsets. Every retained member is hereditary, so this is the internal power set. The empty set and the pure finite and infinite natural-number hierarchy have empty support, yielding infinity. The new pairing, union and comprehension representatives discussed above therefore remain inside . Foundation still fails because all the Quine atoms are in .
The set itself has empty support and hereditary members. So does the family of its two-element subsets, each of which has a finite support in a permutation action. If this family had a choice function , let be a finite support in a permutation action of , and choose distinct . The transposition of fixes and the unordered pair , but interchanges either possible chosen value . It cannot fix the function graph, contradicting its support. Thus choice fails in .
The unrestricted permutation model over the same initial ZFC model satisfies choice and fails foundation, whereas its hereditarily supported submodel fails both. Hence choice is independent of ZF with foundation omitted. These are relative-consistency constructions, not an assertion that ZF proves its own consistency. Starting with ZFC is harmless for the usual consistency comparison with ZF, by the constructible-universe relative-consistency theorem.
The arrow in the original PDF permits partial functions. A partial computable function is computed by a finite program which halts with the specified value on every input in its domain and diverges on inputs outside the domain. A total computable function is the special case with full domain. Coding finite tuples by a primitive recursive pairing function identifies the different finite arities effectively, without identifying total and partial computability.
One precise machine model is a Turing machine. Its finite transition rules and configurations admit effective numerical coding. Bounded simulation is primitive recursive, and unbounded execution gives the partial result. Equivalently, start from zero, successor and projections and close under composition, primitive recursion and unbounded minimization. The Kleene normal form theorem makes the equivalence concrete:
where is a primitive recursive predicate checking a coded halting computation and reads its output. If no computation exists, the minimum and hence the value are undefined. Checking a finite history is effective because every consecutive configuration must obey one of the finitely many transition rules.
The universal partial computable function evaluates the program indexed by on an input. The S-m-n theorem says that fixing finitely many input parameters can be done by a total computable operation on program Gödel numbers: a new program stores those parameters and calls the original universal evaluator. These facts explain both universal simulation and uniform reductions. A set is computably enumerable when it is the domain of a partial computable function, equivalently the range of an effective enumeration. It is recursive when its characteristic function is total computable. A set is recursive precisely when it and its complement are computably enumerable: dovetail the two enumerations to decide each input.
The diagonal halting problem is computably enumerable but not recursive. A total decider would yield a program which, on , diverges if the decider says and halts otherwise. Applying this program to its own index gives a contradiction. There is likewise no total computable universal listing of all total computable functions: the diagonal function would be total and absent from the listing.
Here is a full proof of the Rice theorem. Let be a nonempty proper class of partial computable functions whose property depends only on the function, not its program. First suppose the everywhere-undefined function is not in , and choose a program for a function . Given an index , construct uniformly a program which on first waits for to halt and, only then, simulates . The S-m-n theorem gives a total computable index map . If , then ; if , then . Thus
A decision procedure for the property would decide , impossible. If , apply the same argument to its nontrivial complement. Every nontrivial extensional property of partial computable functions has an undecidable index set. Totality, having finite domain, and taking a particular value somewhere are examples. A syntactic property such as program length is not covered; nor does the theorem say that no individual program's behaviour can be established.
Self-reference can also be made effective. For a total computable index transformation , let be an index for the program which first computes and then runs the program with that resulting index on its own input. The S-m-n theorem makes total computable. Choose an index for the total function , and put . Then
This proves the recursion theorem: every effective transformation of programs has a fixed point at the level of the function computed, though not necessarily at the level of its numerical code.
Finally, consider the Jockusch triple coloring computing the halting set. Fix computable finite approximations with union . For , define
This is a total recursive two-coloring because both stages are finite computations. Suppose is infinite and homogeneous. Its color cannot be one: fix , wait until every enumeration below has stabilized, and choose later from beyond that stage. Their color is zero.
If has color zero, it computes . On input , use to find and in . For arbitrarily large with , homogeneity gives . Taking stages sufficiently large to reach the final finite approximation gives . Consequently membership of in is decided by the finite stage . A recursive would therefore make recursive, a contradiction. There is a recursive partition of triples with no infinite recursive homogeneous set. This is the nontrivial finite-color meaning of the partition of an infinite domain; if “infinite partition” meant infinitely many colors, the coloring by the least member would already give a trivial example. Ramsey's theorem still guarantees infinite homogeneous sets for the displayed two-coloring, but every such set is computationally nontrivial.
Use one ring sort with and the usual unital commutative ring equations. Write for the coherent formula . Add the coherent sequents
This presents the coherent theory of local rings. For an ordinary nonzero ring satisfying these axioms, the nonunits form an ideal: a multiple of a nonunit cannot be a unit; and if nonunits had unit sum, multiplying by would make two nonunits sum to , contradicting the second axiom. They are also closed under additive inverses. This proper ideal contains every proper ideal, since a proper ideal contains no unit, and its quotient is a field; it is the unique maximal ideal. Conversely in a local ring, and cannot both belong to the unique maximal ideal, so one is a unit. The first sequent excludes the zero ring. In a topos, the disjunction asserts that these unit alternatives hold locally.
Let be a small skeleton of the opposite of the category of finitely presented unital commutative rings; write for the object corresponding to . The Zariski coverage on finitely presented rings is generated by
and the empty cover of . Localization is finitely presented, and its compatibility with base change proves the covering axioms.
Here is the classifying argument. For an internal commutative ring and a presentation , define as the subobject of satisfying the polynomial equations . Ring maps induce maps of these solution objects in the site direction. This is independent of presentation, and it preserves finite limits: finite colimits of finitely presented rings correspond to joining finite generators and equations, whose solution objects are finite limits. Conversely a left-exact functor reconstructs a commutative ring using the polynomial maps for addition, multiplication, constants and additive inverse. Presentations by generators and equations then show . Thus flat functors on correspond to internal commutative rings.
Under , the localization arrow above identifies its domain with the locus where evaluates to a unit; the inverse witness is unique. The family is jointly epimorphic exactly when these unit loci cover the solution object for . The locality axiom implies this for every unit-ideal family: from a finite sum , repeatedly apply the two-summand unit alternative, rescaling a unit partial sum when necessary; some , hence some , is a unit locally. Conversely the cover of by its localizations at and gives precisely the locality axiom, while the empty cover of the zero ring gives . Therefore continuous flat functors are exactly models of the displayed coherent theory. The Diaconescu equivalence for geometric morphisms now identifies
naturally in . This proves the asserted classifying topos identification.
Since the site is subcanonical, the generic local ring is the representable sheaf
Its ring operations are induced by polynomial substitution. Its infinitesimal subobject is likewise representable:
Products of representables correspond to tensor products of their rings. For every finitely presented , exponential adjunction and the Yoneda lemma give
Every element of this ring has a unique expression , because form an -basis. This holds even when has nilpotents or zero divisors. The expression is natural under every ring homomorphism , which sends its two coefficients to their images. The canonical morphism , transposed from , is consequently a bijection at every stage , with a natural inverse extracting the coefficients. Therefore
This proves the Kock-Lawvere axiom for the generic local ring. The uniqueness is an internal sheaf assertion tested at all finitely presented rings, including the ring with its generic square-zero element; restricting the test to fields would lose that element and would not prove uniqueness.
Work internally with the Heyting algebra and the truth value of . For , the identities
prove that it is an open local operator.
For a monomorphism with characteristic map , density means , equivalently . This says exactly that is contained in , or that the pullback mono is invertible. Consequently
An object is an -sheaf exactly when the canonical map , taking a value to its constant function on , is invertible. Indeed is dense for every . The sheaf condition makes bijective for every , which proves invertible by the Yoneda lemma. Conversely, if is invertible and is dense, the isomorphism gives
so is a sheaf.
The pullback functor has right adjoint , sending to . Every map is automatically over , since is subterminal object, proving this adjunction directly. Its counit is evaluation and is invertible. The inverse sends to its image in together with the constant function of value ; all elements of agree, so the composites are identities. The right adjoint is therefore full and faithful, and its image consists of objects fixed by . The sheaf characterization above proves
For a general local operator , its dense monomorphism classifier is the ordered subobject
A mono is j-dense exactly when its characteristic map factors through . If , then , which has least element . This is least internally over every parameter object, not just among global points.
Conversely suppose a global is internally least. Upward closure of gives exactly when , in every context. For let be its -closure, with characteristic predicate . The mono is dense: restricting to gives truth. Its characteristic map therefore lands in , so leastness of gives . Internally this is
On the other hand , and applying to gives . Inflationarity then gives . Both inequalities yield
This proves the least dense truth characterizes an open local operator criterion without replacing its internal order condition by the weaker condition on global truth values.
A coverage on a category specifies covering families stable under refinement along arrows: if covers and is any arrow, there is a covering family such that every factors through some . Equivalently one works with the associated saturated covering sieves on a category, satisfying maximality, pullback stability and local transitivity. These determine the same sheaves on a site. We use this sieve on a category formulation of .
An object is a J-irreducible object of a site if its only covering sieve on a category is the maximal sieve on a category. The coverage on a category is a rigid coverage if every object is covered by the sieve on a category generated by arrows whose domains are J-irreducible.
Assume has finitely many arrows and every idempotent morphism splits. There are finitely many sieves on a category on each object , so the intersection of all covering sieves on a category is a covering sieve on a category : finite intersections of covers are covers by the topology axioms. It is the least cover. Let be the collection of all arrows lying in . This is an idempotent ideal in a finite category.
Here are the details. It is closed under precomposition because is a sieve on a category. For , the sieve on a category covers ; minimality gives , so . Thus it is also closed under postcomposition. Local transitivity says that the sieve on a category
covers . It is contained in , while minimality gives the opposite inclusion. Hence , or .
We prove that such an ideal is generated by the identities it contains. Take . Since , repeatedly factor its remaining right factor to obtain
with every factor in . Write . Finiteness gives for some . Their domains coincide, and is an endomorphism in satisfying . Some positive power is idempotent: the powers are eventually periodic, so choose beyond the eventual threshold and divisible by its period. Then . Split with , and . Since is a two-sided ideal,
Thus factors through an object whose identity lies in . The latter means , hence ; every covering sieve on a category on must therefore be maximal. So is J-irreducible.
Every arrow of consequently factors through a J-irreducible object. The sieve on a category generated by arrows from all such objects contains and is a cover. This proves every coverage on the finite idempotent-complete category is rigid. If is empty, the same conclusion holds because the empty sieve on a category already covers .
Let be the full subcategory of J-irreducible objects. For a covering sieve on a category on and any with , the pulled-back sieve on a category covers and is maximal, so . Therefore . For a categorical presheaf on , define its extension by
This is the right Kan extension along the inclusion. Its adjunction gives
which is precisely unique amalgamation on . Hence is a sheaf. The Yoneda lemma gives for .
Conversely, if is a sheaf, its sections on all arrows from into determine a section on their covering sieve on a category. A compatible family extends to an arrow factoring through such a by restriction from its given -section. If an arrow has two factorizations, restrict to the covering sieve on a category generated by arrows from into its domain; compatibility makes the two restrictions equal, and the sheaf's uniqueness of amalgamation makes the sections equal. The resulting matching family glues uniquely over . Thus . Restriction and are inverse up to natural isomorphism, proving
A signature specifies sorts, finite-arity function symbols and finite-arity relation symbols. A coherent formula is built from atomic relations and equality using , finite conjunction, finite disjunction and existential quantification. A coherent theory consists of coherent sequents in finite typed contexts. The context expresses universal quantification of the free variables; unrestricted universal quantification or negation is not a formula constructor here.
Construct the coherent syntactic category as follows. Objects are formulas in context , modulo renaming and provable equivalence. An arrow to is a formula , modulo provable equivalence, for which the theory proves
These say that the relation is supported on the specified objects, total and single-valued. The identity is equality on the context, and composition is
The logical rules give associativity and the identity laws. The empty-context true formula is terminal; conjunction in disjoint contexts gives products; conjunction with equality of the two functional relations gives equalizers. Existential quantification gives images, and finite disjunction gives unions of subobjects. Substitution preserves these constructions, so images and unions are stable under pullback. This makes a coherent category.
Let be a -model in a topos . Interpret each context as a finite product of its sort objects and each formula as its corresponding subobject. Define
The interpretation of an arrow relation is a total single-valued relation between these objects. Its projection to the domain is both an epimorphism, by totality, and a monomorphism, by single-valuedness, hence invertible in a topos. Its other projection therefore determines a unique morphism. Composition agrees with relational composition, so is a functor. Finite limits interpret equality and conjunction; images interpret existential quantification; finite unions interpret disjunction, including the empty union for . Consequently is a coherent functor.
Conversely there is a canonical syntactic model in . Interpret a sort by , a function symbol by its term graph, and a relation symbol by its atomic formula-in-context subobject. Induction on formulas identifies the interpretation of every in with its formula-in-context object. Every axiom is then an inclusion of the associated subobjects, because it is provable in .
For a coherent functor , set . Preservation of finite limits, images and unions proves inductively that preserves all coherent interpretations, so every axiom holds in . The same induction supplies natural isomorphisms
compatible with the functional relations defining arrows. Thus ; directly on the sorts, operations and relations, .
Finally these constructions agree on morphisms. A model homomorphism induces maps on finite contexts. Atomic relations are preserved by definition; finite conjunction and disjunction and existential witnesses then show that each formula object maps to the corresponding formula object. Compatibility with functional relations makes these maps a natural transformation . Conversely a natural transformation between coherent functors restricts to its components on sort objects; naturality for term graphs preserves operations, and naturality for relation inclusions preserves relations. It is therefore a model homomorphism. The two correspondences are inverse. We have proved the categorical, not merely objectwise, equivalence
A local operator is an inflationary, idempotent, finite-meet-preserving map with , expressed in the internal logic of a topos. For a subterminal object with truth value , the closed local operator and quasi-closed local operator are respectively
The first is a local operator by distributivity. For the second put . Then , is order-reversing, and : the first inequality gives , while its application to gives the reverse inequality. Thus is inflationary and idempotent, and .
For meet preservation, monotonicity gives . Conversely put . From and , we obtain . Intersecting with gives , hence . This proves all local-operator axioms. Also and . Equivalently, it is the largest local operator leaving fixed: if , then
This explains the quasi-closed terminology as relative double negation above the closed bottom .
The subobject classifier of is the closed-subobject classifier . Its bottom is , its meet is inherited, its join is , and implication between closed truth values is the ambient implication. To verify the last claim, if , then
It follows that ; inflationarity gives equality and also .
Suppose . Every closed lies above , and its complement in is , also closed because . We have . Moreover , so . Thus the fixed truth values form a Boolean algebra, and the sheaf topos is a Boolean topos.
Conversely suppose the sheaf topos is Boolean and put . Complementation in its classifier is . Applying the double-complement identity to , and using the implication calculation above, gives
Therefore
For the cover, work in the slice category . Its generic subterminal object is . Form its quasi-closed Boolean subtopos , and compose its embedding with the slice projection to obtain . The slice projection has inverse image , and sheafification is left exact, so this is a geometric morphism.
To prove surjectivity, take a monomorphism with characteristic predicate , and suppose makes it invertible. Pullback to the slice followed by sheafification makes this exactly the assertion that it is -dense. Internally on , therefore,
for the generic truth value . Substitute by pulling back along the graph . The left side becomes , so and the original mono is invertible. Thus reflects invertible monos. If it identifies two parallel arrows, their equalizer becomes invertible; reflection then shows the arrows were already equal. Hence is faithful, and
The generic truth value is essential: substituting only a fixed global value such as would give a Boolean subtopos, but need not give a surjection onto the original topos.
Let be a Cartesian comonad, so its endofunctor preserves finite limits. A coalgebra for a comonad is with , and . Its morphisms satisfy . Write for the forgetful functor and for the cofree coalgebra. Transposition is
The forgetful functor creates finite limits, since preserves them. We construct both exponential objects and the subobject classifier.
For coalgebras , set and in the ambient topos. Define by transposing
where . Their cofree transposes are coalgebra morphisms
Let be their coalgebra equalizer. For a coalgebra , an arrow corresponds to a map . Its evaluation respects coalgebra structure exactly when
Under the displayed transpositions this is precisely the condition that it equalize . Thus naturally, and is the required exponential in a coalgebra topos.
Let classify . In take the equalizer
The truth map into is and factors through this equalizer. To verify its universal property, take an underlying subobject of a coalgebra. It carries a compatible coalgebra structure exactly when maps into . Such a structure, if it exists, is unique because is monic; its laws follow by cancellation of . Moreover always: applying to a point of lands in . Thus stability is equivalent to .
If classifies , this last equality is exactly
The cofree transpose satisfies this equation precisely when it factors through . Indeed transposing the equality gives the equation above. Pulling back its truth map recovers , because classifies . Hence is the subobject classifier of a coalgebra topos. We have obtained finite limits, exponentials and a classifier, proving is a topos.
Now let be a geometric morphism, and put , , with unit . Both functors preserve finite limits, so is a Cartesian comonad on . Put . Its comparison functor
is left exact and has right adjoint
To check the adjunction, transpose an underlying map to . The coalgebra-morphism equation becomes exactly the equality of the two composites into , so the transposed arrow factors uniquely through the displayed equalizer.
The counit is invertible. Applying to the defining equalizer gives the equalizer of . The structure map is exactly that equalizer: it equalizes by coassociativity; if equalizes, apply to obtain , giving its unique factorization through . Thus the underlying comparison counit is an isomorphism, and the forgetful functor reflects isomorphisms. Therefore is full and faithful.
The adjunctions and define
Here is faithful, so is a surjective geometric morphism; is full and faithful, so is a geometric embedding. Their inverse-image composite is , establishing the surjection-embedding factorization of a geometric morphism.
For uniqueness, let be the class of arrows in inverted by . In any surjection-embedding factorization , conservativity of shows that is also the class inverted by . The essential image of the fully faithful consists exactly of the -local objects , namely those for which is bijective for every in . One direction follows from the adjunction. For the converse, the reflector unit belongs to ; locality gives a retraction, and locality of the reflected object makes that retraction also a right inverse. Thus the unit is invertible. The image subcategory is consequently determined by , independently of the factorization. The two intermediate toposes are equivalent over , and their inverse-image composites with the embeddings determine the surjection legs. This proves uniqueness up to equivalence.
Use the elementary, or weak, topos axioms: finite limits and a power object for every object , naturally representing . No arbitrary products or coproducts are assumed. In particular is the subobject classifier. Inverse image of the membership relation defines for .
Interchanging the factors in a relation gives natural bijections
Thus the contravariant power-object functor has left adjoint . Its adjunction unit sends a generalized element to the predicate on given by membership of .
This unit is monic. If have the same image under , membership of and agrees in every -parameterized subobject of . Apply this to the graph of in : membership of is true, so membership of is true, which means . This argument uses parameterized relations, not an assumption that global elements detect morphisms.
The functor reflects isomorphisms. Suppose is invertible. Then is invertible, and naturality together with monicity of shows that is monic. Regard as a subobject of . Its inverse image along itself is the whole of , just as for the whole subobject of . Those two subobjects correspond to maps ; since is monic, they coincide. Therefore the subobject is all of , and is an isomorphism.
We now prove the preservation condition for the crude monadicity theorem. A reflexive pair in is a coreflexive pair in , with for some . Let be its equalizer. For any monomorphism , define on power objects by composing a parameterized subobject with ; no general image construction is needed because is monic. Inverse image followed by this extension obeys .
Here both are monic. For a parameterized subobject of , an element belongs to exactly when for some . Applying gives , so this condition is precisely and . Consequently, as morphisms of power objects,
If equalizes , these identities give
It therefore factors uniquely through , which is a split epimorphism with section . Since , also equalizes . Hence is their coequalizer. This proves explicitly that power objects turn coreflexive equalizers into coequalizers.
Finite equalizers in give all coequalizers of reflexive pairs in , and we have shown that preserves them and reflects isomorphisms. The crude monadicity theorem now yields
Fix a set of cardinality . If has -indexed products in a category, its Eilenberg-Moore category for the double-power monad has them, since the forgetful functor creates existing limits. The displayed equivalence then gives -products in , hence -coproducts in a category in .
For the converse, suppose those coproducts exist. The diagonal is a logical functor, because all the elementary topos structure in is pointwise, and it has left adjoint . Apply power-object monadicity to both toposes. Under their monadic identifications, is the lift of to the double-power Eilenberg-Moore categories. The base functor is a right adjoint to , so the adjoint lifting theorem for monad algebra functors gives a left adjoint to its algebra lift. Its required reflexive coequalizers exist in , since they are opposites of finite equalizers in . Taking opposites gives a right adjoint to , which is exactly the -product functor. Thus the products and coproducts of fixed cardinality in a topos satisfy

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact