How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Models of the elementary diagram yield elementary embeddings
Statement
For nonempty -structures , an elementary embedding exists iff has an -expansion satisfying . In any such expansion the map is elementary. Conversely an elementary embedding gives such an expansion by setting . The embedding may also be represented as a literal elementary inclusion into an isomorphic copy of .
Facts & Assumptions
Given: Work in ZF, using the disjoint new constants of the elementary diagram. All formulas have finitely many symbols and free variables.
The elementary diagram consists of all true sentences of the expansion naming every element; it contains whenever . (Elementary diagrams)
Elementary maps preserve and reflect truth on all finite parameter tuples; equality makes them injective and the atomic function/relation formulas make them embeddings. (Elementary embeddings, substructures and chains)
If is free for in , satisfaction of equals satisfaction of with assigned the value of . (Free-for substitution commutes with satisfaction)
Satisfaction and term values are unchanged upon reduct to a smaller language; finite free-variable tuples determine truth. (Coincidence for term values and satisfaction)
Satisfaction is given by term equality, interpreted relations, Boolean clauses and existential witnesses in the carrier. (Existence and uniqueness of set satisfaction)
Constructor induction applies to terms and formulas. (Structural induction and recursion on syntax)
The Kuratowski ordered pair is . (The Kuratowski ordered pair )
Ordered pairs satisfy iff and . ( if and only if and )
Foundation excludes membership cycles of length three. (Under Foundation, for every set , there are no sets with , and there are no sets with )
Proof
For an -formula and tuple covering its free variables, replace those free variables by the corresponding constants, obtaining a sentence . A constant has no free variables, so each replacement is free for its variable; replacements for distinct variables do not alter earlier inserted constants. Iterating F3 and then F4 shows that iff , and for any expansion of it shows iff . For the empty tuple this is just reduct invariance.
Conversely let be elementary and interpret each name by . For a sentence of , only finitely many new constants occur. Replace the distinct occurring names by distinct variables absent everywhere from , giving an -formula ; such variables exist because a finite word uses finitely many variables and the variable supply is . No binder in binds any of the newly introduced variables. Substituting the corresponding constants back into those free positions recovers exactly . By F3, its truth in is truth of at the corresponding tuple from , and its truth in the proposed expansion of is truth of at the image tuple. Elementarity equates these truth values. Thus every in the diagram is true in the proposed expansion, as required. If no new constants occur, use the empty tuple.
For completeness of the inclusion formulation, replace the elements of by the tagged copy . This is a set by Replacement. If , then F7 gives the forbidden membership cycle , so F9 proves . By F8 the map is injective. Put and define by and otherwise. Injectivity of makes the first clause well defined; the clauses have disjoint ranges and are bijective onto and . Thus is a bijection and is literal inclusion.
Suppose and define . If , step 1.1 puts the named sentence in the diagram, so satisfies it and . If does not satisfy the instance, its named negation belongs to the diagram; thus . These two cases prove preservation and reflection. In particular gives by the diagram inequation, and F2 proves that is an elementary embedding.
Transport the structure along : put , , and iff . Bijectivity makes these interpretations well defined and total. Term induction shows values are carried by (variables, constants, then the displayed function identity). Atomic truth is then preserved and reflected, using injectivity for equality and the displayed relation identity. Negation and conjunction preserve this agreement, and an existential witness transfers in either direction by or . Formula induction therefore proves that preserves and reflects all formulas. Combining with the elementarity of , for every in truth in equals truth in at and hence truth in at . F2 gives the required substructure conditions and .
Depends on
- Elementary diagrams
- Elementary embeddings, substructures and chains
- Free-for substitution commutes with satisfaction
- Coincidence for term values and satisfaction
- Existence and uniqueness of set satisfaction
- Structural induction and recursion on syntax
- The Kuratowski ordered pair $(a,b) := \{\{a\},\{a,b\}\}$
- $(a,b) = (c,d)$ if and only if $a = c$ and $b = d$
- Under Foundation, $x \notin x$ for every set $x$, there are no sets with $x \in y \in x$, and there are no sets with $x \in y \in z \in x$
Used by
Dependency tree · two levels
24 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.