Every countable structure in a countable first-order language has a Scott sentence whose countable models are precisely its isomorphic copies. In particular two countable structures with the same countable infinitary logic sentences are isomorphic. Countability of both structures is essential to the back-and-forth conclusion; the sentence need not exclude uncountable models.
Let be a nonempty countable structure in a countable first-order language. The countable infinitary logic permits countable logical conjunctions and logical disjunctions, but only finite strings of quantifiers and finitely many free variables in each formula. We construct a Scott formula for every finite tuple from and every countable ordinal .
At stage zero, let be the conjunction of all atomic formulas true of and the negations of all atomic formulas false of . Include atomic formulas involving arbitrary terms and constants, not just relation symbols applied directly to variables. There are only countably many such formulas. This complete atomic description ensures that matching tuples determine a partial isomorphism of structures.
At successors put
At a nonzero limit ordinal , put . All these are formulas of countable infinitary logic: each indexing set is countable, and the free variables are only the fixed finite tuple. Rename bound variables when necessary. Transfinite induction also shows .
For tuples of the same length within , define by . Induction identifies this with the usual symmetric back-and-forth method equivalence: the tuples have the same atomic description at stage zero, and at a successor every one-element extension on either side has a matching extension at the previous stage. Thus these are decreasing equivalence relations, simultaneously for every finite tuple length.
There are only countably many pairs of finite tuples in . A pair can cease to be equivalent at most once. The supremum of the first separation stages of all pairs that separate below is a countable ordinal. Choose a countable at least that supremum. No pair can first separate at , so
This justifies stabilization without assuming that all tuples stabilize at one predetermined finite stage.
Now form the following Scott sentence, where the case has no displayed variables or quantifiers:
It is a sentence of countable infinitary logic, because the family of all finite tuples is countable. The stabilization above and the truth of show .
Suppose a countable structure satisfies . Start with the empty matching tuples, and maintain . The corresponding conjunct of upgrades this to . The existential conjuncts extend the match by any specified element of . The universal-disjunction conjunct extends it by any specified element of . The atomic formula information makes a new element on one side match a new element on the other, and makes repeated elements agree with their earlier matches.
Enumerate both structures and alternate these two extension steps, including the least element not yet covered at each step. The union is a bijection preserving and reflecting every atomic formula, hence an isomorphism; for function symbols, eventually include both a tuple and the value of its function term to see explicitly that the function is preserved. For finite structures the same construction stops when both are covered. Conversely every isomorphic copy of satisfies , since isomorphisms preserve formulas of countable infinitary logic by induction on their construction. Therefore
If countable have the same sentences, satisfies this Scott sentence of and is isomorphic to . This proves Scott isomorphism theorem.
Fix an effective enumeration of partial computable functions, implemented by deterministic machines, and put
These are disjoint computably enumerable sets. To see that they are recursively inseparable sets, suppose a computable set contains and avoids . Its indicator function has some index . If , then , contradicting that output. If , then , contradicting . Thus neither output is possible.
Let be a nonstandard model of Peano arithmetic. A recursive presentation of a structure here means a presentation on in which its arithmetic operations are total computable functions; equality of presentation codes is ordinary equality. Write for the element represented by the standard numeral . The presentation codes of are fixed constants, so is a total computable function obtained by repeated addition. Presentation codes and the arithmetic values they name must be kept distinct.
Use bounded simulation of a computation predicates saying that machine , on input , has halted by time with output . We can choose these as primitive recursive predicates represented in Peano arithmetic. Determinism and induction on the computation length give, provably in Peano arithmetic, monotonicity in and
A genuine standard halting computation has a finite certificate which Peano arithmetic verifies. Consequently, if or , the corresponding holds in for some standard .
Choose a nonstandard element of . It exceeds every standard numeral. Let be the th prime number, starting with . Peano arithmetic proves the prime-divisibility coding of a finite set needed here: for each , an element can be formed as the product of precisely those with for which holds. Formally,
This is an internally finite product, not a claim that its externally observed index set is finite. Its existence follows by mathematical induction on the cutoff: start with , multiply by the next distinct prime number when its predicate holds, and otherwise retain the product. Unique prime factorization ensures that earlier divisibility decisions are preserved. The standard prime enumeration and these finite-product constructions are provably total in Peano arithmetic.
Define the external subset . If , its standard halting time is below , and monotonicity gives , so . If , its output-one certificate and the provable incompatibility above exclude , so . Hence separates and .
Finally is a computable set. Given standard , compute the ordinary integer and its numeral in the presentation. Enumerate all presentation codes , and for each test the finitely many standard remainders for
Each test is decidable using the assumed total computable functions. The division theorem of Peano arithmetic guarantees a quotient and a remainder below the standard numeral . Every element below that numeral is one of , so the search terminates; the remainder is unique. Return yes exactly when . This makes a computable set, contradicting the recursively inseparable sets construction. Therefore
The required condition is the common-refinement condition for nonempty-sieve coverage: for every pair , , there are arrows , with
Necessity follows by pulling back the nonempty sieve generated by along : a member of the pullback sieve supplies such an . Conversely, this condition makes the pullback of every nonempty sieve on a category nonempty. The maximal sieve is nonempty, and the transitivity axiom holds: if a sieve is locally covering along every member of a nonempty covering sieve , choose and then ; their composite is in . Hence the nonempty sieves form a Grothendieck topology, called the atomic topology.
For all functions between nonempty finite sets, the two maps from a singleton to different points of a two-point set have no common refinement. Every potential domain remains nonempty, so the two constant composites cannot agree. The condition fails.
For surjections it holds: is nonempty and both projections are surjective. Work from now on in a small skeleton of nonempty finite sets and surjections. Every morphism is a regular epimorphism, with kernel pair , and is the coequalizer of that pair in .
A matching family in a representable on the sieve generated by is determined by a surjection equalizing that kernel pair. It factors uniquely through a function , which is surjective because is. This gives the unique amalgamation. A general nonempty covering sieve contains such an ; after amalgamating there, common refinements with any other member force agreement on the entire sieve. Therefore every representable is a sheaf, so this atomic site is subcanonical.
For any sheaf , every restriction is injective: equality after a covering arrow forces equality by the separated part of the sheaf condition. We shall also use descent along any surjection :
is an equalizer of sets. These are the descent identities for the atomic finite-surjection site.
Consider primitive , with a common restriction along , . Suppose have but . Let identify just the two points . Define the finite nonempty set
Both projections are surjective, since contains every diagonal pair. There is also a surjection
Indeed the target consists of diagonal pairs, which are reached because is surjective, and the two off-diagonal pairs corresponding to , reached by and .
Since , the common-restriction equality gives . If are the target kernel-pair projections, this is
Injectivity of gives the kernel-pair matching condition on . Descent along then writes , contradicting primitivity. Thus ; interchange the roles to obtain equality. This is the primitive-element kernel rigidity lemma.
Equal kernels produce a unique bijection with . Now , and injectivity implies
In particular equivalent primitive elements have the same cardinality and differ only by transport along a bijection.
Every element descends to a primitive one: whenever it is not primitive, descend along a surjection reducing the cardinality by one; this process terminates at or before cardinality one. Kernel rigidity shows that all primitive ancestors of lie in one equivalence class. Let be the elements with primitive-ancestor class . Restriction along a surjection preserves this class, so each is a subfunctor and
pointwise. Each is a sheaf. A matching family glues in , and one member along a nonempty covering arrow already determines the primitive class of the glued element; it must be .
Choose a representative primitive of . The Yoneda map named by has image exactly . It reaches all descendants of , and every equivalent primitive ancestor is its transport along a bijection. It is therefore pointwise surjective onto and is epic as a map of sheaves. We obtain the primitive decomposition of an atomic finite-surjection sheaf
This includes the empty coproduct for an empty sheaf.
Each nonempty is an atom in a topos. If a sheaf subobject has an element at some , membership descends along the covering surjection , so belongs to . All its restrictions then belong to , giving . Thus every subobject of any selects entire components of this coproduct, and its complementary selection is again a sheaf subobject. Its characteristic map sends selected components to and all others to .
The constant two-element presheaf is a sheaf: a matching family on a nonempty sieve has the same value on all its arrows, since any two have a common refinement. The value extends uniquely. It therefore supplies these characteristic maps, with truth the inclusion of the value. Equivalently, a J-closed sieve here is either empty or maximal, because every nonempty sieve covers. Hence

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