The limit form of the Special adjoint functor theorem is as follows. Let be a locally small category, a complete category, and a well-powered category, and suppose it has a small cogenerating family . Let be a locally small category. Then a functor has a left adjoint if and only if it preserves all small categorical limits. The dual exchanges completeness, well-poweredness and cogenerators for cocompleteness, well-copoweredness and generators, and characterizes functors with a right adjoint.
Here a cogenerating set distinguishes unequal parallel maps by postcomposition into one of the . A well-powered category has a set of subobjects of each fixed object. Completeness means existence of all small categorical limits. We use the initial-object lemma for complete categories with a weakly initial set: a complete category that is locally small has an initial object exactly when it has a weakly initial set. A proof is given in Question 5(c). We also use the fact that when preserves small categorical limits, the comma category is complete, with its limits constructed in ; local smallness is inherited from . Finally, having an initial object in for each is the universal arrow from an object to a functor characterization of a left adjoint.
Assume preserves small categorical limits, and fix . We will construct a weakly initial set in , rather than assume a solution set. Start with an arbitrary object , where . Call a subobject supporting if for some . There is at least one, namely . Because preserves pullbacks in a category, it preserves monomorphisms: the self-pullback characterization of a monic map is preserved. Consequently each is unique.
There is a set of supporting subobjects by well-poweredness. Their intersection of subobjects exists by completeness; write it . Applying to this intersection categorical limit gives a unique lifting all the , and hence . Minimality says that any subobject supporting is invertible: supports , so factors through , giving a right inverse to the monic .
If satisfy , their equalizer supports , since preserves that equalizer. It is therefore an isomorphism, and . We have obtained an injective function
Let be its image, a subset of the fixed set . The evaluation embedding into cogenerator products is a monomorphism
Indeed each corresponds to a unique map , and the cogenerating set property makes the resulting family jointly monic. Notice that we use the realized subsets , not all of : there need not be a map available for an unused index.
There is a set of tuples , since and every are sets. For each resulting , choose representatives of its subobjects; these form a set by well-poweredness. For every representative , include every map , a set by local smallness of . All resulting pairs form a set. Our given receives a map from such a pair: transport along the isomorphism between and the chosen representative, then compose its inverse with . Thus these pairs form a weakly initial set in . This is the cogenerator bound for comma-category solution sets.
The initial-object lemma for complete categories with a weakly initial set gives an initial object . For , define by the unique equation
Uniqueness proves the functor laws and gives the natural bijections
Thus . Conversely, a right adjoint preserves small categorical limits: its adjunction identifies maps into the proposed limiting object with compatible families of maps into the diagram. This proves both directions of the limit form of the special adjoint functor theorem. Applying the argument to the opposite categories proves the dual statement. Choices of representatives and adjoint objects are understood in the usual ambient-universe convention for large categories.
For subsets , a many-one reduction is a total computable function such that
A Turing reduction is an oracle machine that, using membership queries to , halts on every input and computes the indicator function of . It may make several adaptive queries, and need not preserve the yes/no answer to a single query. A many-one reduction yields a Turing reduction by computing and querying once. Two sets have the same Turing degree when each is Turing reducible to the other. Write for the degree of the diagonal halting set .
We prove the Kleene–Post incomparability theorem by an oracle-assisted finite-extension construction. Fix an effective list of all Turing functionals. We shall build increasing finite binary strings whose unions are the indicator functions of . A finite oracle computation means that the computation halts with output and every oracle query is strictly below . Its answers are supplied by . By the finite oracle use property, every infinite oracle extending preserves this computation.
Here is the decision available from . Given and a finite string , consider
This predicate is semidecidable: enumerate all finite extensions of and dovetail their finite oracle simulations, stopping at the first halting binary output. There is a computably produced program which, on its own index as well as on every other input, performs this search and halts exactly if it succeeds. Membership of its code in therefore decides . In a yes case, running the search finds an actual witness . The decision oracle is essential in a no case; merely waiting would not produce a terminating construction.
Start with empty strings. At stage first ensure
Choose , which is not yet assigned in . Ask whether holds. If yes, find a witness , extend the current string to , and append the bit to the current string. If no, leave the current string unchanged and append to the current string. The yes case permanently forces disagreement at , since later strings extend both commitments. In the no case no final oracle extending the current string can give a binary output at : any such convergent computation would use finitely many bits and hence supply a forbidden finite witness. Thus it cannot be the indicator function of either, regardless of whether it diverges or returns a nonbinary value.
Next, using the strings just obtained, ensure
by the same procedure with the roles reversed. Choose equal to the current length of the string, ask the analogous extension question about the current string, and, if it has witness output , extend to that witness and append to . Otherwise append to . Finally pad both strings with zeros if necessary so that each length is at least , and call the resulting strings . Every operation is computable using the membership oracle and terminates. Earlier disagreements remain protected because no already fixed bit is ever changed.
Set and . The length condition makes these total binary functions. To compute either bit with oracle , run the construction through stage , when both strings have length at least , and read that bit. Consequently . Every Turing functional has been defeated in both directions, so
Neither set is computable, since a computable set is Turing reducible to every oracle. Neither can have degree : if , then , contrary to incomparability; the other case is symmetric. Therefore
This proves the requested theorem. The argument does not claim or is computably enumerable; it constructs sets computable in . Obtaining incomparable computably enumerable degrees is the stronger Friedberg–Muchnik theorem, which is not needed for the printed request.
Let enumerate all computably enumerable sets, with finite uniformly computable approximations increasing to . For example, take and
We construct a simple set by meeting the requirements : if is infinite, then . Begin with no enumerated elements and all requirements unmarked. At stage , process in this order. For an unmarked , if there is an with , enumerate the least such into and mark permanently. All membership tests at a stage are finite, and marking requires no test for eventual infinitude. The sparse-witness construction of a simple set therefore gives a computably enumerable set ; it is semidecidable by simulating this enumeration and halting when the input appears.
Each requirement enumerates at most one element. If an element in is enumerated by , then , so . At most elements of that interval can therefore enter , even if some requirements choose the same element. Consequently
The complement of a set is infinite.
If is infinite, it contains some , and that element eventually belongs to at a stage with . If has already acted, it already placed an element of in . Otherwise it acts by this stage and does so now. Thus every infinite semidecidable set meets . Equivalently, its infinite complement of a set is an immune set. The constructed is semidecidable, coinfinite, and meets every infinite semidecidable set.
As a useful check on the construction, cannot be a computable set. If it were, its infinite complement of a set would also be a computably enumerable set disjoint from , contradicting the property just proved. The argument requires neither deciding which are infinite nor protecting a prechosen infinite list of omitted numbers; the numerical witness bound provides all the required room.
A function in intension is a finite description of a computation, such as a program or a formal construction expression. A function in extension is the resulting input-output map, including its domain if it is partial. Different descriptions may have the same extension: the programs that return directly and that compute describe the same function. Finite descriptions have Gödel numbers; equality of the resulting partial computable functions is a separate semantic question.
The primitive recursive functions are the smallest class of numerical functions containing the zero functions, the successor function and all projection functions, and closed under function composition in recursion theory and primitive recursion. More explicitly, from and the latter operation forms
For function composition in recursion theory, an -ary and -ary give . Zero functions of all allowed arities can be included, with nullary zero included if arity is part of the coding convention. Every resulting function is total: the initial functions are total, function composition in recursion theory preserves totality, and mathematical induction on verifies totality of primitive recursion. Applying structural induction for primitive recursive functions then covers all construction expressions.
Use a fixed effective Gödel numbering of finite tagged construction trees with decidable decoding. A node is tagged as zero, successor, projection, composition, or recursion. The primitive recursive syntax and arity checking algorithm first checks that the input decodes as a finite tree, then works upwards from its leaves. A projection tag is legal exactly when , with output arity . A composition node declares its output arity and is legal when its outer child has arity , there are exactly inner children, and each has arity ; its arity is . The declared arity also handles the case . A recursion node is legal when its base child has arity and its step child has arity ; its arity is . Zero and successor tags have their declared arities. Ill-formed nodes are rejected. The process terminates because there are only finitely many nodes. Thus, for each fixed ,
This is a syntactic assertion about functions in intension. It does not assert that arbitrary machine indices computing primitive recursive functions form a decidable set. That extensional property is nontrivial, hence undecidable by Rice theorem. For an explicit reduction, given a program construct a program that, on every input, waits for to halt and then returns . Its extension is a primitive recursive function if , and otherwise is nowhere defined and so is not a primitive recursive function. A decision procedure for this latter semantic set would decide the diagonal halting set.
Enumerate the decidable syntax set in increasing code order as . There are infinitely many such descriptions; iterating successor after a unary zero expression already supplies infinitely many. Let be the extension of a valid construction and define
To compute , find by the syntax test and interpret its finite construction tree. Evaluate function composition in recursion theory by evaluating the children, and evaluate primitive recursion by the prescribed finite loop of length equal to its final input. Termination follows from the totality argument above, so and are total computable functions.
If were a unary primitive recursive function, some construction would have extension . Then the diagonal argument gives
which is impossible. The displayed is total and computable but not primitive recursive. Repetitions of extensions in the enumeration cause no problem: every possible extension is represented, which is all the diagonal argument needs. The same argument shows that the two-variable interpreter cannot itself be primitive recursive.
Take and fix a standard effective enumeration of the unary partial computable functions by program texts. Write
The diagonal halting set is not a computable set: a supposed decision procedure would give a program that halts on input exactly when , contradicting its own index. Each is finite and uniformly decidable by bounded simulation of a computation, and with union .
For , define the computable colouring
This is a two-part decidable set partition on three-element subsets: sort the three inputs and perform the two finite simulations. Here . The halting-stage colouring of triples cannot have an infinite homogeneous set for a colouring of colour . Indeed, fix its least element . The finitely many bits of eventually stabilize. Choose two later elements of the putative homogeneous set for a colouring beyond that stabilization stage; the corresponding triple has colour .
Now suppose is an infinite homogeneous set for a colouring of colour . Its membership oracle computes : to decide whether , search for with , and return whether . For every above , homogeneity gives . Since is unbounded, taking such arbitrarily large proves that this common finite set is . Thus
If were a computable set, the displayed Turing reduction would decide , a contradiction. The displayed decidable two-colouring has no infinite decidable homogeneous set.
For the second construction, let be the finite binary strings, with coordinates starting at , and define the computable binary tree
Membership is decided by finitely many tests using bounded simulation of a computation. It is a binary tree of finite strings: if a string satisfies the tests, each prefix satisfies its shorter and fewer tests. The infinite paths through a binary tree are exactly
This set is nonempty: at a coordinate whose diagonal computation halts with a binary value choose the other value, and choose either bit elsewhere. This is an existence argument, not a proposed computable decision procedure for convergence. No member is a total computable function. If were a total binary-valued function, the condition at would say . Thus each member is a binary diagonally noncomputable function.
Moreover, has no isolated point. There are arbitrarily large indices of programs that never halt: for example, distinct program texts with successively more unused instructions followed by an infinite loop provide infinitely many such indices in the usual syntactic program coding. At every one of these coordinates the bit is unrestricted. Given any and any prefix length , change its bit at one such index and leave all other bits unchanged. The resulting different path still belongs to and has the same length- prefix. Since a path space is closed in Cantor space, is decidable, is nonempty and perfect, and no infinite path is computable.
There is a definition issue with the adjective “perfect”. The preceding conclusion uses perfect path space, allowing finite dead ends in the decidable presentation. If “perfect tree” instead requires every node to have two incompatible extensions in the tree, the requested combination is impossible. Such a nonempty tree has no terminal nodes. Starting at the empty string, test the two immediate successors and choose the first that belongs to the tree; one always exists. This constructs a total computable function whose successive prefixes remain in the tree. Thus computable pruned binary trees have computable paths. Our necessarily has dead ends; its subtree consisting only of prefixes of infinite paths is perfect in the pruned sense but is not decidable. The construction therefore supplies the intended perfect closed path space and also resolves the stronger, inconsistent interpretation.
Present the Grothendieck topos as for a small site. Let be sheafification and the inclusion. The standard sheafification construction supplies , with preserving finite limits. Concretely, matching-family constructions commute with finite limits, and their directed refinement over covering sieves does so as well. Limits of sheaves are computed in the presheaf category, so has finite limits; its colimits are sheafifications of presheaf colimits.
For sheaves , form the presheaf exponential
It is a sheaf. Indeed, for a covering sieve , one has . Exponential adjunction, sheafification adjunction and left exactness give
These are the restriction comparisons, proving the sheaf condition. Restricting the presheaf exponential adjunction to sheaves now makes in .
The subobject classifier is the sheaf of J-closed sieves. A sieve on is J-closed when, for every , implies . Pullback of sieves defines its restrictions, and the maximal sieve defines truth. Local sieve data glue by taking the J-closure of their compatible generated sieve; uniqueness follows because membership in a J-closed sieve is local. This proves that is a sheaf.
For a subsheaf , the characteristic morphism sends to
This sieve is J-closed because local membership in a subsheaf descends by its gluing axiom. Pulling truth back recovers exactly . Conversely, pulling back truth along any morphism into gives a subsheaf, and the same formula recovers that morphism. Finite limits, exponentials and this classifier make every Grothendieck topos an elementary topos.
Here are the explicit Heyting operations on subsheaves of an object . Intersections give meets:
The top is . Arbitrary joins are local unions:
Equivalently, locally lies in one of the , with the index allowed to vary across the covering arrows. This is the J-closure of the pointwise union, or its sheafification. It is the smallest subsheaf containing every , since any such subsheaf must contain sections locally in it.
The bottom is the empty join, namely the initial subobject. Its value at consists of all if the empty sieve covers , and is empty otherwise. This detail matters on sites with empty covers; it is not safe to use an always-empty presheaf as the initial sheaf.
Implication is described without any pointwise-complement assumption:
Restrictions preserve this condition. It is also local: pull a covering sieve back along an arbitrary , use membership in on those restrictions, then descend their membership in . Thus it is a subsheaf. It satisfies the defining Heyting algebra adjunction
For the forward direction take the identity restriction. For the reverse direction every restriction of a section of remains in , so membership in forces membership in . Negation is . These formulas give the complete Heyting algebra structure on ; in general negation is a pseudocomplement rather than a set-theoretic complement.

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