An atomic model is a model in which every finite tuple's complete type over the empty set is isolated by a formula. An omega-saturated model realizes every complete type in finitely many variables over every finite parameter set; equivalently it realizes all one-variable types over finite parameter sets, then successive realizations give the finite-tuple version.
Suppose is countable and omega-saturated. Every type in is realized by a tuple in , so is countable. This is a compact Hausdorff Stone space with a clopen basis. Its isolated points are dense. Indeed, if a nonempty clopen subset had no isolated point, split it into two disjoint nonempty clopen subsets and recursively split every resulting subset. Such splits exist because each subset has at least two points and the space is zero-dimensional. Compactness supplies a point in each nested sequence along an infinite binary branch, while disjoint siblings make different branches yield different points. This would give uncountably many points, contradicting countability.
For each , let consist of the negations of all formulas that isolate complete -types. Density of isolated types means that every consistent formula has a consistent refinement to an isolating formula ; this refinement excludes the member of . Thus locally omits every . The omitting types theorem gives a countable model omitting them all. Every tuple in therefore satisfies some isolating formula, so is atomic. If some is itself inconsistent, its omission is automatic and does not obstruct this argument.
The converse about existence is false. Here is a countable atomic model without a countable saturated model. Take a countable set with unary predicates , , such that every finite Boolean pattern of the predicates occurs infinitely often. For example, use finite binary words paired with a natural number, with recording the th bit when it exists and false otherwise. Add a constant naming each element, and put in this countable language. Every tuple of has its type isolated by equations to its named coordinates, so is a countable atomic model.
For each infinite binary sequence , the family
is finitely satisfiable in : realize its finitely many predicate requirements while avoiding finitely many named elements. By compactness theorem, it extends to a complete one-type. Different sequences give different types, so is uncountable. Any omega-saturated model must realize all these empty-parameter types, which a countable model cannot do. This disproves the existence converse, rather than merely exhibiting an atomic model that is itself nonsaturated.
The local omission of a partial type by a consistent first-order theory means that, for every formula consistent with , there is some such that
is consistent. Equivalently, no formula consistent with implies every member of . Thus every possible local condition has a compatible refinement excluding at least one proposed type formula.
The omitting types theorem states: in a countable first-order language, if is consistent and locally omits each of countably many finite-arity families , then it has a countable model omitting them all. Omission means that no tuple satisfies every formula in the family. In the case of a complete type, local omission is equivalent to the type being nonisolated. Countability of the language and of the list of omission requirements is essential to this formulation.
Let consist of all universal-existential sentences entailed by , and take . By (c), there is an existential embedding of into . By (b), embeds in with . After replacing structures by isomorphic copies, arrange these maps as inclusions. Since , it also satisfies and the construction can be repeated. This produces
The two interleaved chains have the same union . The elementary chain theorem gives . The are an ordinary chain of models of , so the assumed closure under unions of chains gives . Therefore . This proves
Conversely, universal-existential axioms are preserved in such unions: a finite universal tuple occurs in one stage, which already supplies its existential witnesses. The quantifier-free matrix has the same truth value in that stage and in the union. This also explains the inductive first-order theory characterization.
Here denotes universal-existential sentences, with quantifier-free matrix and possibly empty blocks. Add constants for and consider
We show that is consistent. Suppose a finite subset is inconsistent. Combine its diagram facts as and its finitely many negative existential facts as . Replacing the new constants by a variable tuple gives the consequence
This is equivalent to a universal-existential sentence: move all the existential blocks to the front of the disjunction, using the usual nonempty-domain convention. If there are no negative existential facts, the consequence is simply . By hypothesis satisfies the displayed consequence. Its named tuple satisfies but none of the existential alternatives, a contradiction.
A model of contains a diagram copy of . Every existential formula false in is still false in ; every one true in is preserved by the embedding. Thus
Both preservation and reflection are required here; the atomic diagram alone would give only an ordinary embedding.
Identify with its image under . In a language naming every element of , use the same names for elements of in the two sets of sentences
This union is consistent. To see finite satisfiability, conjoin the finitely many diagram facts about into a quantifier-free formula and the finitely many elementary-diagram facts about into , where the elements in have names outside . Since , the 1-embedding property gives a witnessing tuple in . Interpret the finitely many new names by that tuple. The resulting expansion of satisfies as well as .
By compactness theorem, a model of this union exists. Its named copy of gives an embedding , while its named copy of is elementary. Consequently
The naming ensures that the two maps agree on the original copy of .
A 1-embedding, or existential embedding, is a structure embedding satisfying
for every quantifier-free and every parameter tuple from . The forward direction is automatic for an embedding; reflection of existential formulas is the extra property. For an inclusion this says that is simply closed in . This is weaker than requiring an elementary embedding, which preserves all formulas.
In the language of a single edge relation , axiomatize an undirected loop-free graph by
For every pair of nonnegative integers , add the extension axiom demanding, for any distinct , a new vertex such that
These axioms form the theory of the random graph. Repetition of the fresh-vertex requirement also forces infinitude.
To prove quantifier elimination, first eliminate one existential quantifier from a quantifier-free formula. Put that formula into disjunctive normal form, so it suffices to consider a conjunction of literals in a new variable and the parameter variables. There are two possibilities for a witness: equals one of the parameters, in which case substitution gives a quantifier-free condition; or is distinct from all of them. In the latter case, the graph axioms reduce all requirements involving to specified adjacency or nonadjacency to the distinct parameter vertices. A requirement is impossible, and conflicting requirements at equal parameter vertices are impossible. Every other consistent adjacency pattern is realized by the extension axiom.
There are only finitely many equality patterns of the given parameter tuple. For each, consistency of the literals is a quantifier-free condition, including the unchanged relations among the parameters. Their finite disjunction describes exactly when a witness exists. Thus is equivalent to a quantifier-free formula whenever is quantifier-free. Mathematical induction on formulas now eliminates all quantifiers, using . Hence the random-graph theory eliminates quantifiers. The extension axioms also yield the usual countable random graph by a back-and-forth construction.
We use the hypothesis for the two target structures when they are models of ; the common source is their generated substructure and need not itself be a model of . If the hypothesis is read as applying to all target structures, it is stronger and the same proof applies.
Suppose tuples and , with , have the same complete quantifier-free type. The substructures they generate are isomorphic by the map
for every term . Equality of the quantifier-free types makes this map well defined and injective and makes it preserve and reflect all relations. Identify these generated substructures with one common structure. The assumption then implies that and have the same truth value. Thus the truth of is determined by the tuple's quantifier-free type.
For any realization of in a model of , let be its complete quantifier-free type. The preceding paragraph makes inconsistent. By compactness theorem, a finite conjunction of members of satisfies
Choose such a conjunction for every quantifier-free type realized by a -tuple. These conjunctions cover every realization of . Another application of compactness theorem, to together with and the negations of all the chosen conjunctions, gives a finite subcover . Therefore
The right side is a quantifier-free formula. If there are no realizations of , use the always-false quantifier-free formula. This proves the common-substructure test for quantifier elimination for the given formula; it does not assume that the source structures are models of the theory.
Let be the set of all existential sentences entailed by . Certainly every model of satisfies . Conversely, take . Part (c) gives embedded in an elementary extension of . After identifying with its image, is a superstructure of a model of . The assumed closure under superstructures implies . Since , it follows that as well. Hence
This supplies an existential axiomatization. Conversely, an existential sentence is preserved under embeddings because its finite tuple of witnesses and the quantifier-free facts about them persist, explaining why this is the appropriate syntactic class.
Let be all universal sentences true in . The theory is consistent. Indeed, if a finite conjunction of sentences from were inconsistent with , then . A finite conjunction of universal sentences is universal, so its negation is equivalent to an existential sentence. By the hypothesis would satisfy , whereas it satisfies .
Choose . Now expand the language by names for every element of and consider its elementary diagram . Its universal consequences in the original language are exactly : any such consequence is true in the named copy of , while any original-language sentence true in already belongs to its elementary diagram. Part (b), applied to and this expanded theory, gives a structure embedding of into a model of . The named copy of is an elementary substructure of . Identifying that copy with , we obtain
Thus the required target is an elementary extension of , although itself need not be a model of .
Name every element by a new constant , distinct from the symbols already in . Let be its full atomic and negated atomic diagram of a structure. A model of this diagram contains an isomorphic copy of as an -substructure. We claim
is satisfiable.
Otherwise compactness theorem gives a finite diagram conjunction inconsistent with . Replace these new constants by variables. Since says nothing about the new names, it then entails the universal sentence
The conjunction uses only symbols of , so this is one of the universal -consequences assumed true in . But satisfies , a contradiction. A model of the consistent enlarged theory gives an embedding of into the -reduct of a model of . Negated atomic facts and disequalities in the diagram ensure that this is a structure embedding, not merely a homomorphism.
The compactness theorem for first-order logic says that a set of first-order sentences has a model if and only if every finite subset of has a model. It applies to arbitrary languages, including expansions by arbitrarily many new constants. Equivalently, if entails a sentence, some finite subset already entails it. We will use both formulations with the diagram of a structure.
For , let the players alternately choose natural numbers, producing ; I wins exactly when . A strategy assigns a move to each finite position at which its player moves. It is winning if every compatible completed play is won by that player. A game is determined when one player has a winning strategy. The axiom of determinacy is
We can prove determinacy for open and closed payoffs, including clopen payoffs; finite games are covered by backward induction. Here is the full open-payoff argument. For an open , let consist of finite positions whose entire cylinder of continuations is contained in . Recursively put
and take unions at limits. Since positions form a set, this process reaches a fixed point . More explicitly, a strict increase at each stage would assign a distinct position to each stage beyond the Hartogs bound of the position set, which is impossible; for natural-number moves the least newly added position in a fixed enumeration makes that assignment explicit.
If the initial position belongs to , I can win. At an I-position first added at a successor stage, choose the least move to a position of smaller first-entry rank. At an II-position first added at a successor stage, every successor already has smaller rank. A play following this strategy cannot have an infinite strictly descending sequence of ordinal ranks, so reaches in finitely many steps; all its further continuations lie in . If the initial position is outside , II keeps the play outside : at an I-position no successor is in , and at an II-position at least one successor is outside , so II chooses the least such move. The play never reaches a winning prefix. Since is open, membership in would have been certified by some finite prefix, so the resulting play is outside . Thus every open game is determined. Applying this argument to the open complement of a closed payoff, with the players' objectives interchanged, proves closed determinacy too. The argument needs no choice of moves beyond taking the least available natural number.
To refute AD under AC, first use binary moves. There are strategies for each player, since its positions form a countable set. Enumerate them as and . Each fixed strategy admits exactly compatible plays: the other player's arbitrary binary sequence determines the completed play injectively. Recursively choose a play following and a play following , each different from all earlier reservations and from each other. This is possible because at stage fewer than plays have been reserved. No regularity assumption on is used: every ordinal has cardinality below , and doubling an infinite smaller cardinal does not reach .
Set . Strategy loses on , while loses on . Thus this binary game is undetermined. Turn it into a natural-number game by declaring that the first player to play a number outside loses. Formally its I-payoff is
A winning strategy in this game could not prescribe an illegal move after a compatible legal history, since the opponent could thereby win. Its restriction to legal histories would therefore give a winning binary strategy, contradicting the construction. Hence the choice diagonalization of an undetermined game proves
This does not contradict open or closed determinacy: the diagonal payoff has no such regularity requirement.
A useful form of the Ehrenfeucht-Mostowski theorem says that, for an infinite first-order structure and any total order , there is a model of generated as a Skolem hull by distinct order indiscernibles . Every order automorphism of extends uniquely to an automorphism of the specified Skolem expansion of that hull. The model can be obtained inside an elementary extension of a Skolem expansion of ; the generated hull itself need not contain .
Choose a Skolem expansion by iteratively adjoining witness functions: for each existential formula in the current language choose a function returning a witness whenever one exists, with an arbitrary value otherwise. Repeat for countably many rounds. Every formula in the final language uses finitely many symbols, so has a witness function from a later round. Thus the expansion is Skolemized for its own formulas, as required for elementarity of its hull. Add constants for to the complete theory of , require them to be distinct, and impose the scheme
for every formula in the Skolem language. If an elementary extension of is desired, also add its elementary diagram with separate names for its elements.
Every finite part of this theory is satisfiable. Choose infinitely many distinct elements of . For each of the finitely many arities in that fragment, color increasing index tuples by the finite vector of truth values of the formulas occurring. Repeated applications of the infinite Ramsey theorem give an infinite subset on which all these vectors are constant. Interpret the finitely many in increasing-index order from that subset. This satisfies the finite indiscernibility requirements and distinctness, while the elementary diagram is satisfied by the named original structure. The compactness theorem gives a structure satisfying the whole theory.
Let be the closure of the under the Skolem functions, including nullary ones. It is elementary in : whenever an existential formula with parameters from is true in , its Skolem witness lies in . This is the Tarski-Vaught test, whose proof is induction on formulas, using precisely this witness property for the existential step. Hence the reduct of is a model of .
For an order automorphism , define
This is well-defined. If two terms denote the same element, write their equality as a formula on the combined increasing tuple of their indices; indiscernibility preserves that formula after transport by . The same argument preserves every relation and function. Applying gives the inverse, so is an automorphism. Since all elements are terms in the generators, it is the unique automorphism of this Skolem expansion extending . This proves the theorem.
One may require the indiscernibles to lie in any specified infinite sequence of the starting structure, or to satisfy additional finite-tuple properties holding along that sequence: the same finite satisfiability proof chooses its homogeneous subsequence there. This strengthened form is what the rank-domain construction of NFU uses. Uniqueness is asserted in the Skolem expansion, not for all automorphisms of its reduct.
For a presheaf of sets on a topological space , define and . Then the adjoints to constant presheaves on open sets are
To prove the first adjunction, a natural transformation must satisfy by naturality at the inclusion . Hence it is uniquely determined by a function . Every such function defines a natural transformation by this formula, because restriction maps compose. This gives .
For the second adjunction, a natural transformation satisfies , so it is uniquely determined by a function . Every such function defines the remaining components by restriction, giving . Evaluation acts on presheaf morphisms componentwise, so these object assignments are indeed functors. The use of is essential: a constant presheaf of sets has value there, whereas a sheaf has a singleton value there. No sheaf condition is imposed in this question.
The two adjoints of inverse image on power sets are
These maps and are monotone functions on the inclusion-ordered power sets. For and ,
The first equivalence follows by following each element of through . For the second, every fiber over must lie in , which is precisely the defining condition for . These are the two Galois connections, proving . In particular, a point outside has an empty fiber and belongs to even when is empty; omitting this case would give an incorrect right adjoint.
Each hom-set in a poset is either empty or a singleton. Thus a natural bijection is precisely the condition
The naturality squares commute automatically, because maps between the relevant singleton hom-sets are unique. This is a Galois connection. Equivalently, the adjunction unit and adjunction counit are the inequalities and . These inequalities imply the displayed equivalence: gives , and gives .
Given the two natural transformations, define
Naturality of and the second triangle identity for an adjunction give
Naturality of and the first triangle identity for an adjunction give
The maps are natural in , since the defining compositions commute with precomposition in and postcomposition in by naturality of . They therefore define an adjunction . Their values on identity morphisms recover precisely . Conversely any adjunction with these unit and counit of an adjunction must have the same transpose formulas, so it is unique with the prescribed unit and counit.
Using the transpose formulas of the preceding part,
Similarly,
Thus the adjunction unit and adjunction counit satisfy both triangle identities for an adjunction,
Write the adjunction as a natural bijection . The adjunction unit and adjunction counit are defined by
Naturality of implies for and for , so these are natural transformations and . More explicitly, naturality at and gives the two transpose formulas
These formulas will also prove the triangle identities for an adjunction.

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