nLab Dedekind completion

Dedekind completions

Dedekind completions

1. Idea

The Dedekind completion of a linear order LL is a new strict linear order L¯\widebar{L} that contains suprema for all inhabited bounded subsets, and such that a supremum in LL is still a supremum in L¯\widebar{L}.

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.

2. Definitions

Let SS be a set equipped with the structure of a dense linear order without top or bottom elements (endpoints).

Definition 2.1. A cut in SS is a pair of subsets L,USL, U \subset S of SS that satisfy the following eight properties:

  1. LL is inhabited;
  2. Dually, UU is inhabited;
  3. If x<yLx \lt y \in L, then xLx \in L;
  4. Dually, if x>yUx \gt y \in U, then xUx \in U;
  5. If xLx \in L, then x<yLx \lt y \in L for some yy;
  6. Dually, xUx \in U, then x>yUx \gt y \in U for some yy;
  7. If x<yx \lt y, then xLx \in L or yUy \in U;
  8. If xLx \in L and yUy \in U, then x<yx \lt y.

Definition 2.2. The linearly ordered set SS is Dedekind complete if every cut (L,U)(L,U) is of the form

L={x|x<a},U={x|x>a} L = \{x \;| \;x \lt a\},\; U = \{x \;|\; x \gt a\}

for some unique aSa \in S.

Definition 2.3. If TT is also an unbounded dense strict linear order, SS is Dedekind complete, and we have a universal arrow u:TSu\colon T \to S in the category of strict linear orders, then SS (equipped with uu) is the Dedekind completion of TT.

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 SS, the set of Dedekind cuts is isomorphic to the reals as long as SS 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.

Using open intervals

A set FF with a strict linear order is Dedekind complete if

  • For all elements aFa \in F and bFb \in F, the open interval (a,b)(a,b) is inhabited.

  • For all elements aFa \in F, the upper unbounded open interval (a,)(a,\infty) is inhabited.

  • For all elements aFa \in F, the lower unbounded open interval (,a)(-\infty,a) is inhabited.

  • For all elements aFa \in F and bFb \in F, a<ba \lt b if and only if (b,)(b,\infty) is a subinterval of (a,)(a,\infty)

  • For all elements aFa \in F and bFb \in F, b<ab \lt a if and only if (,b)(-\infty,b) is a subinterval of (,a)(-\infty,a)

  • For all elements aFa \in F and bFb \in F, if a<ba \lt b, then FF is a subinterval of the union of (a,)(a, \infty) and (,b)(-\infty, b)

  • For all elements aFa \in F and bFb \in F, the intersection of (a,)(a,\infty) and (,b)(-\infty,b) is a subinterval of the open interval (a,b)(a,b)

3. Generalisations

In predicative constructive mathematics

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 L,U:toΣL, U: \mathbb{Q} to \Sigma representing the open subsets of \mathbb{Q} to define predicative cuts, where Σ\Sigma is a small σ \sigma -frame with an embedding ΣProp 𝒰\Sigma \to \mathrm{Prop}_\mathcal{U} into the large set of propositions for a universe 𝒰\mathcal{U}. The definitions then become

Definition 3.1. Given a small σ \sigma -frame Σ\Sigma that embeds into the large set of propositions Prop 𝒰\mathrm{Prop}_\mathcal{U} for a universe 𝒰\mathcal{U} and a linearly ordered set SS, a cut in SS is a pair of functions L,U:SΣL, U: S \to \Sigma that satisfy the following eight properties:

  1. There is an element aSa \in S such that L(a)=L(a) = \top.
  2. There is an element bSb \in S such that U(b)=U(b) = \top.
  3. If a<ba \lt b are elements of SS with L(b)=L(b) = \top, then L(a)=L(a) = \top.
  4. If a<ba \lt b are elements of SS with U(a)=U(a) = \top, then U(b)=U(b) = \top.
  5. If L(a)=L(a) = \top, then there is an element of SS a<ba \lt b such that L(b)=L(b) = \top.
  6. If U(b)=U(b) = \top, then there is an element of SS a<ba \lt b for some U(a)=U(a) = \top.
  7. If a<ba \lt b are elements of SS, then L(a)=L(a) = \top or U(b)=U(b) = \top.
  8. If L(a)=L(a) = \top and U(b)=U(b) = \top, then a<ba \lt b.

Definition 3.2. The linearly ordered set SS is Σ\Sigma-Dedekind complete if for every cut (L,U)(L,U) there exists a unique element aSa \in S such that for all elements xSx \in S, x<ax \lt a implies L(x)=L(x) = \top and x>ax \gt a implies U(x)=U(x) = \top.

Given any linearly ordered set SS, for any two σ\sigma-frames Σ\Sigma and Σ \Sigma^{'} that embed into Prop 𝒰\mathrm{Prop}_\mathcal{U} such that ΣΣ \Sigma \subseteq \Sigma^{'}, if AA is the Σ\Sigma-Dedekind completion of SS and BB is the Σ \Sigma^{'}-Dedekind completion of SS, then ABA \subseteq B.

Strict preorders

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 SS such that, given finite (here always meaning Kuratowski-finite) subsets FF and GG of SS such that x<zx \lt z whenever xFx \in F and zGz \in G, we have some yy in SS such that x<y<zx \lt y \lt z whenever xFx \in F and zGz \in G.

Note that, for SS a strict linear order, SS is a duisp iff SS is dense, unbounded, and inhabited, hence the term ‘duisp’. (Using linearity, we may assume that FF and GG 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 SS, a cut is a pair (L,U)(L,U) of subsets such that:

  1. LL is inhabited (which is a special case of (5) for FF the empty subset);
  2. Dually, UU is inhabited (a special case of (6));
  3. If x<yLx \lt y \in L, then xLx \in L;
  4. Dually, if x>yUx \gt y \in U, then xUx \in U;
  5. If FF is a finite subset of LL (which we may assume inhabited if we include (1)), then for some xLx \in L, every yFy \in F satisfies y<xy \lt x;
  6. Dually, if FF is a finite (inhabited) subset of UU, then for some xUx \in U, every yFy \in F satisfies y>xy \gt x;
  7. If L<x<UL \lt x \lt U and L<y<UL \lt y \lt U, then x=yx = y;
  8. If xLx \in L and yUy \in U, then x<yx \lt y.

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 XX; the Dedekind completion is the set of real-valued functions on XX.

Sections 4.31–39 of HAF do things in even more generality, but I don't really understand it yet.

4. One-sided Dedekind completions

At least in classical mathematics, considering only LL (for a lower cut) or UU (for an upper cut) doesn't really give us anything new for strict linear orders; we have only the technicality that (S,)\infty \coloneqq (S,\empty) or (,S)-\infty \coloneqq (\empty,S) is a cut (depending on the side), and we can rule even these out by simply requiring that LL have an upper bound or that UU 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 SS 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 GG a singleton, and an upper duisp need only satisfy the condition for FF 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 XX be a compactum and let SS be the strictly preordered set of continuous real-valued functions on XX. Then SS is a duisp, hence both a lower and upper duisp. Its lower Dedekind completion is the set of lower semicontinuous functions on XX taking values in the lower reals (which classically are all either real or \infty); and dually on the upper side. Even working classically and ignoring the technicality of \infty, semicontinuous functions are much more general than continuous ones.

5. References

Last revised on October 16, 2024 at 05:46:21. See the history of this page for a list of all contributions to it.