The Dedekind completion of a linear order is a new strict linear order that contains suprema for all inhabited bounded subsets, and such that a supremum in is still a supremum in .
While Dedekind completeness was traditionally described in the context of the real numbers, it can be stated for any strict linear order, although it really works best for dense? and unbounded (without top or bottom) strict linear orders. Intuitively, a strict linear order is Dedekind complete if Dedekind cuts don’t give any ‘new’ elements.
Let be a set equipped with the structure of a dense linear order without top or bottom elements (endpoints).
Definition 2.1. A cut in is a pair of subsets of that satisfy the following eight properties:
Definition 2.2. The linearly ordered set is Dedekind complete if every cut is of the form
for some unique .
Definition 2.3. If is also an unbounded dense strict linear order, is Dedekind complete, and we have a universal arrow in the category of strict linear orders, then (equipped with ) is the Dedekind completion of .
The set of Dedekind cuts of rational numbers –the set of real numbers– is Dedekind complete. In fact, starting with any unbounded dense linearly ordered set , the set of Dedekind cuts is isomorphic to the reals as long as is a countably infinite set.
The operation of forming the set of Dedekind cuts is idempotent, so the Dedekind completion can be constructed as the set of Dedekind cuts. More precisely, the Dedekind-complete strict linear orders form a reflective subcategory of the category of dense unbounded strict linear orders, so that Dedekind completion is a kind of completion in the abstract categorial sense.
A set with a strict linear order is Dedekind complete if
For all elements and , the open interval is inhabited.
For all elements , the upper unbounded open interval is inhabited.
For all elements , the lower unbounded open interval is inhabited.
For all elements and , if and only if is a subinterval of
For all elements and , if and only if is a subinterval of
For all elements and , if , then is a subinterval of the union of and
For all elements and , the intersection of and is a subinterval of the open interval
In predicative constructive mathematics, subsets are large and therefore are proper classes. Thus, any Dedekind completion of a dense linear order, and in particular the rational numbers, is a proper class. Instead, predicative constructive mathematicians typically use pairs of functions representing the open subsets of to define predicative cuts, where is a small -frame with an embedding into the large set of propositions for a universe . The definitions then become
Definition 3.1. Given a small -frame that embeds into the large set of propositions for a universe and a linearly ordered set , a cut in is a pair of functions that satisfy the following eight properties:
Definition 3.2. The linearly ordered set is -Dedekind complete if for every cut there exists a unique element such that for all elements , implies and implies .
Given any linearly ordered set , for any two -frames and that embed into such that , if is the -Dedekind completion of and is the -Dedekind completion of , then .
Any paragraph containing the string ‘duisp’ is original research (although lower duisps at least are known in domain theory).
One can generalise Dedekind completion from strict linear orders to strict preorders.
Definition 3.3. A duisp (dense unbounded inhabited strict preorder) is a strictly preordered set such that, given finite (here always meaning Kuratowski-finite) subsets and of such that whenever and , we have some in such that whenever and .
Note that, for a strict linear order, is a duisp iff is dense, unbounded, and inhabited, hence the term ‘duisp’. (Using linearity, we may assume that and are subsingletons; then two singleton subsets is denseness, one singleton subset and one empty subset is unboundedness, and two empty subsets is inhabitedness.)
Definition 3.4. Given a duisp , a cut is a pair of subsets such that:
We then define Dedekind-complete duisps and Dedekind completions of duisps the same as for dense linear orders, using this notion of cut.
A good example of a duisp is the set of rational-valued functions on any set ; the Dedekind completion is the set of real-valued functions on .
Sections 4.31–39 of HAF do things in even more generality, but I don't really understand it yet.
At least in classical mathematics, considering only (for a lower cut) or (for an upper cut) doesn't really give us anything new for strict linear orders; we have only the technicality that or is a cut (depending on the side), and we can rule even these out by simply requiring that have an upper bound or that have a lower bound.
In constructive mathematics, one-sided cuts are more general; see one-sided real number for a discussion of the case where is the strict linear order of rational numbers.
Even in classical mathematics, one-sided cuts do give us something new for strict preorders. Here, we have first more general one-sided notions of duisps: a lower duisp need only satisfy the condition of a duisp for a singleton, and an upper duisp need only satisfy the condition for a singleton. Then the lower Dedekind completion of a lower duisp is its set of lower cuts, and the upper Dedekind completion of an upper duisp is its set of upper cuts.
For example, let be a compactum and let be the strictly preordered set of continuous real-valued functions on . Then is a duisp, hence both a lower and upper duisp. Its lower Dedekind completion is the set of lower semicontinuous functions on taking values in the lower reals (which classically are all either real or ); and dually on the upper side. Even working classically and ignoring the technicality of , semicontinuous functions are much more general than continuous ones.
Page 249&250 of Continuous Lattices and Domains (Google book) covers lower Dedekind completions of duisps (although not under that name) in the context of domain theory.
Univalent Foundations Project, Homotopy Type Theory – Univalent Foundations of Mathematics (2013)
Auke B. Booij, Extensional constructive real analysis via locators, (arxiv:1805.06781)
Steve Vickers, “Localic Completion Of Generalized Metric Spaces I”, TAC
Davorin Lešnik, Synthetic Topology and Constructive Metric Spaces, (arxiv:2104.10399)
Last revised on October 16, 2024 at 05:46:21. See the history of this page for a list of all contributions to it.