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.
Well-founded pointed graphs have unique decorations
Statement
Every well-founded accessible pointed graph has a unique decoration . Its range is . If is extensional, is the unique isomorphism from onto membership on that transitive set.
Facts & Assumptions
Given: Work in ZF unless the statement explicitly weakens or supplements it; fix the objects and hypotheses of the statement.
An accessible pointed graph consists of a set of nodes, a root , and a relation . Draw an arrow precisely when . Accessibility means that for every there are and a function with , , and for . The path of length zero reaches the root. A decoration is a set function on such that for each node. A well-founded graph means that has the minimal-element property, not an unqualified no-infinite-path characterization. Extensionality is not part of the graph definition. No axiom of anti-foundation is assumed. Conventions and prerequisites: def-well-founded-setlike-relations. (Accessible pointed membership graphs)
A setlike relation on is extensional when implies for . If is also well-founded, its collapse map is the unique definable function Existence and uniqueness follow from well-founded recursion with , a set by Replacement. A collapse map is defined even without extensionality; injectivity is a further conclusion requiring extensionality. The construction for a supplied well-founded relation uses no ambient Foundation. Conventions and prerequisites: thm-recursion-on-well-founded-setlike-relations. (Extensional relations and collapse maps)
For every set , is transitive, contains as a subset, and is contained in every transitive set with . Moreover implies , and . In particular . (Minimality and closure laws of TC)
Every well-founded setlike extensional relation on a definable class is isomorphic to membership on a unique transitive definable class , by a unique definable isomorphism . For a set domain , the isomorphism and its image are sets. This holds without ambient Foundation. (Mostowski collapse for extensional relations)
Proof
The collapse recursion, which does not require extensionality for existence, supplies a unique decoration on the set . Its range is transitive by the recursion equation and contains as an element, so minimality gives .
Every node is reached from by a finite predecessor path. Along this path the decoration of each next node is a member of the decoration of the preceding node. Transitivity therefore puts in , starting with the root itself at path length zero. This gives the reverse inclusion.
When is extensional, Mostowski collapse makes the same decoration an isomorphism, unique among isomorphisms onto transitive targets. Step 2.1 identifies that target explicitly.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
8 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.
Sources
- Kozen and Ruozzi, Applications of Metric Coinduction (2009) — section 6 APG paragraph p.10; Marks 6.11 p.32. (standard reference, not scraped)