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.
Linear-order completion and density
Statement
Let be a linear order. A completion of means a linear order satisfying the following exact clauses:
- (C1) , with the same order on ;
- (C2) every subset of , including the empty set, has a least upper bound and a greatest lower bound in ;
- (C3) every is the least upper bound in of some subset of ; and
- (C4) if is the least upper bound in of , then it remains the least upper bound of in .
Every linear order has such a completion, and any two completions are uniquely isomorphic over . If is dense, then it is order-dense in every completion. If in addition has no endpoints, has no uncountable pairwise disjoint family of nonempty open intervals, and no nonempty open interval of is separable in its order topology, then deleting the possible first and last elements of a completion produces a dense, no-endpoint, boundedly complete order with the same two latter properties.
Facts & Assumptions
Given: A linear order ; for the transfer clause, the additional hypotheses displayed in the statement.
A linear order is a partial order in which every two elements are comparable; least upper bounds are unique by antisymmetry. Partial order and partially ordered set
Open intervals are endpoint-excluding order-convex sets; we use the same displayed interval notation in an arbitrary linear order. Intervals of : the nine order-convex forms, nondegeneracy, and length
A subset is dense exactly when it meets every nonempty open set. Dense, nowhere dense and codense subsets of a topological space, and the criterion by basic open sets
Separability means the existence of an at most countable dense subset. Separability: the existence of an at most countable dense subset
“Countable” means finite or countably infinite. Finite, countably infinite, countable, uncountable
AC supplies simultaneous witnesses from families of nonempty intervals. The Axiom of Choice
Proof
Let consist of the subsets such that (i) implies , and (ii) whenever has a least upper bound in , one has . Order by inclusion. These are the downward-closed cuts with every already-existing -supremum closed in.
The inclusion order on is linear. Indeed, if and , then every satisfies (otherwise downward closure would put in ), and hence ; thus .
Every family has a supremum. Put . If has no least upper bound in , then and is the union-supremum. If exists, downward closure gives , which lies in and is the least cut above every member of . This includes . Infima then exist as suprema of sets of lower bounds, so is complete.
Send to . Each is a cut, and holds exactly when , so is an order embedding. Replacing by its named copy if necessary gives literal inclusion as required by C1.
Every cut is , including the empty cut. If for , then is an upper bound of ; any cut above every for contains every , and it contains either because or because clause (ii) closes under the supremum . Hence . Thus the constructed order satisfies C2-C4.
Let be any completion satisfying C1-C4 and define . This is a cut: downward closure is immediate, while if , C4 makes its supremum in , which also equals by C3, so . If , C3 gives an with , so . Conversely the traces reflect order. For every cut , if , then : an in the trace cannot upper-bound , and if , then and cut closure puts in . Thus is an onto isomorphism from to and fixes . Applying this to two completions gives the unique isomorphism over , since C3 forces any such isomorphism to send each to .
Suppose now that is dense and is a completion. If in , C3 supplies with . If , density in gives for some . If and there were no with , then would be the least upper bound in of the -points below ; C4 would make that supremum equal both and , a contradiction. Hence in all cases some satisfies , so is order-dense in .
If were pairwise disjoint nonempty open intervals of , order-density and A1 would choose in . The nonempty -intervals would remain pairwise disjoint, contradicting the corresponding hypothesis on . Thus the interval ccc passes to .
Suppose a nonempty open interval of had a countable dense set . Choose in . The set is nonempty and countable; list it as , repeating entries in the finite case. For every pair , use order-density and A1 to choose with . The set is countable by diagonal enumeration of the pairs of natural indices. Given in , density of first gives and then , so . Therefore is dense in the nonempty -interval , contradicting the hypothesis on . No nonempty open interval of is separable.
Finally assume that has no endpoints, and delete from its first and last elements when they exist. Neither deleted point belongs to . The remainder still contains the order-dense copy of , is dense and has no endpoints, and retains the conclusions of steps 6.1-6.2. If a nonempty is bounded above there, then lies above a member of and below an upper bound in , so it is neither deleted endpoint and belongs to ; hence is boundedly complete. This proves every assertion and records the precise use of AC.
Depends on
- Partial order and partially ordered set
- Intervals of $\mathbb{R}$: the nine order-convex forms, nondegeneracy, and length
- Dense, nowhere dense and codense subsets of a topological space, and the criterion by basic open sets
- Separability: the existence of an at most countable dense subset
- Finite, countably infinite, countable, uncountable
- The Axiom of Choice
Used by
Dependency tree · two levels
19 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
- Monk, Set theory following Jech, Theorems 9.14-9.15 and Corollary 9.16, printed pp. 69-72 (standard reference, not scraped)