San José State University

applet-magic.com
Thayer Watkins
Silicon Valley
& Tornado Alley
USA

Dedekind Cuts: Real Numbers as Partitions
of the Ordered Field of Rational Numbers

Real numbers are the bedrock of mathematical analysis. People used the concept on an intuitive basis long before anyone inquired into their basis. Most people presume that real numbers are simply sequences, possibly unending, of decimal digits. This is not entirely satisfactory because the sequence 1.000… and 0.999… represent the same number, namely unity. For more on the nature of real numbers see Real.

In the 19th century mathematicians began to find ways to derive the real numbers. One such formulation was due to the French mathematician Augustin-Louis Cauchy (1789-1857) and identified real numbers with convergent sequences. See Cauchy. Another was from the German mathematician Richard Dedekind (1831-1916) and his formulation is the topic of the material which follows.

The modern formulation is to define real numbers by a set of axioms and characterize Cauchy's and Dedekind's formulation as models for the axiomatically defined real numbers. From this point of view the real numbers are simply a completely ordered field. A mathematical field consists of a set S of entities for which two operations (binary functions) are defined, usually called addition (+) and multiplication (·). These operations must be

There must exist additive and multiplicative identities; i.e., elements of S, say z and u, such that for all a belonging to S, a+z=a and a·u=a. Usually the additive and multiplicative identities are denoted as 0 and 1, respectively.

There must exist additive inverses; i.e., for any a belonging to S there exists a b in S such that a+b=0. The additive inverse of a is denoted as −a.

For all elements of S except the additive identity there must exist a multiplicative inverse; i.e., if a≠0 there exists b in S such that a·b=1. The multiplicative inverse of a is denoted as a-1 or 1/a.

In addition to the two operations of addition and multiplications there must be an order relation (a binary function from S×S to the boolean values {true, false}). For the moment the order relation is denoted as (|). For all a and b in S, a|b is either true or false. This order relation must have the properties of

Usually the order relation is denoted as ≤ but this denotes only a generic order relation. For the case of dedekind sets the inclusion of equality may create some confusion. In the definition of dedekind sets the order relation is the strict inequality < whereas the relation among dedekind sets can include equality; i.e., ≤.

In addition to the previous properties the order relation must be compatible with the operations. This means

Finally it must hold that if X is a set of elements of S and X has an upper bound under the order relation then X has a least upper bound; i.e., if there exist a v in S such that for all x in X x<v then there exists in S an element u which is an upper bound for X and such that for any upper bound v of X, v≤u.

Dedekind Cuts (Schnitten)

Dedekind's formulation is now called Dedekind cuts. Consider ordered pairs of sets of rational numbers, say (R, S), where R and S are nonempty and S is the complement of R. That is to say (R, S) constitute a partition of the rational numbers. Let Q be the set of all rational numbers. Then R is neither the empty set nor the full set Q and R∪S=Q. The set R is closed downward but has no maximum element whereas S is closed upward. This means that if q belongs to R and r<q and then r also belongs to R. Likewise if t belongs to S and s>t then s also belongs to S.

There is no maximum element of R; i.e., for any element r belonging to R there is another element q belonging to R such that q>r.

This notion of (R, S) as an ordered pair of complementary sets is redundant. The partition can be exactly identified by either R or S. Later only the lower set R will be used in the analysis but for now the notion of a partition will be used briefly.

Let (M, N) and (P, Q) be two of these Dedekind partitions. An ordering is easily defined on these partitions. If M contains elements which P does not then M is said to be greater than P; i.e., M>P. If M and P contain the same elements then they are the same set and hence M=P as sets and (M,N)=(P,Q) as partitions. A partition (M,N) is positive, (M,N)>0, if M contains at least one positive element. A partition (M,N) is called non-negative if M contains non-negative elements. (It is not appropriate to say M is non-negative if it contains at least one non-negative element because if it contains only one non-negative element then that element is the maximum for the set M and M would not be a suitable set; i.e., one that has no maximum. The same would apply if M were to contain only a finite set of non-negative elements. One of that finite set would be the maximum for M. In general the number of elements of M that are greater than or equal to a value m must be either 0 or infinite; i.e., not finite.

Change of Terminology

Instead of a partitioning pair of sets (R, S) the presentation will be in terms of sets of rational numbers which are closed downward and which have no maximum elements. Such sets will ultimately be identified as real numbers, but temporarily it is appropriate to call them dedekind sets.

Note that there are some simple lemmas that hold for dedekind sets. For example:

An Arithmetic for Dedekind Sets

An arithmetic can be defined on these dedekind sets. First consider the definition of the sum and product. Let M and N be two dedekind sets.

There are other cases of multiplication to be considered but this is a convenient point to deal with the issues of whether the sum and product defined above are dedekind sets; i.e., sets which are closed downward and have no maximum element. Consider an element q belonging to M+N and another rational number r such that r<q. It must be shown that r also belongs to M+N. Let Δ=q-r. Since q belongs to M+N there exists m and n such that m+n=q and m∈M and n∈N. Now consider p=n-Δ. Since p<n, p∈N. Thus

m + p = m + (n-Δ) = (m+n) - Δ = q - Δ = r

Therefore r∈(M+N).

Now suppose (M+N) has a maximum element q. This element is in (M+N) only because there exists m in M and n in N such that m+n=q. Since m is in M and M has no maximum element there exists another element p in M such that m<p and likewise there exists s in N such that n<s. But p+s must be in (M+N) and (p+s)>(m+n)=q. This contradicts the hypothesis that q is a maximum element in (M+N).

Now consider the product of the positive elements of dedekind sets M and N. Suppose q∈M×N. This means that either there exists positive elements m and n of M and N such that m·n=q or that q is negative. Let r be any rational number less than q. If r is negative it belongs to M×N. If q is negative then r is also negative and thus belongs to M×N. If q is positive, there exists positive m and n such that m·n=q. If r is positive then there exists n(r/q) which is less than n and hence also in N. But

m·(n(r/q)) = (m·n)·(r/q) = q·(r/q) = r.

Thus r belongs to M×N. Thus M×N is closed downward.

Suppose M×N has a maximum element q. There would then exist m in M and n in N such that m·n=q. Since neither M or N have maximum elements there exists p∈M and s∈N such that p>m and s>n. But p·s > q, contradicting the assumption that M×N has a maximum element.

The Existence of an Additive Identity

Consider the set of all negative rational numbers. Call this set Z, for zero. The set Z is a dedekind set. (If n<m and m∈Z then m is negative and n is also negative and hence belongs to Z. Suppose Z had a maximum element q. Then q/2 would be less negative than q and still negative.)

Let M be any dedekind set. Consider (M+Z). To show that (M+Z)=M it will be shown that (M+Z)⊂M and M⊂(M+Z). Let q be any element of (M+Z). This means there exists m belong to M and z belonging to Z such that q=m+z. Remembering that z is negative consider q-z. This is equal to m which belongs to M. But q-z is greater than q. Since m>q and m belongs to M, q must belong to M. Thus (M+Z)⊂M.

Let p be any element of M. Since M has no maximum element there exists s>p belonging to M. Let z be equal to -(s-p). Then p=s+z=s-(s-p). Thus p belongs to (M+Z). Therefore M⊂(M+Z).

Thus (M+Z)=Z and hence Z is the additive identity.

The Existence of Additive Inverses

Let M be any dedekind set. Consider the set made up of the negatives of all rational numbers which are not in M. Call this set N. The set N contains all elements whose absolute value is larger than any element of positive element of M. Let m be any element of M and n any element of N. Consider m+n; -n>m, hence 0>m+n. Thus (M+N) conssiiiiists entirely of negative elements. In other words (M+N)⊂Z. Let z be any element of Z. This element z is negative. Choose any two elements of M and N, say m and n. Let q be m+n. By the previous material q is negative. Since N has no maximum element there is another element of N, say p, that is greater (less negative) than n. Therefore m+p is greater than m+n. Let z be any element of Z, i.e., any negative rational number. If z≤q then z belongs to (M+N). If z>q then by the previous argument there is another element of (M+N) that is greater than q. In particular q/2 belongs to (M+N) and hence q/2k for all non-negative integers k. For some k, z≤q/2k. Since q/2k belongs to (M+N) then so does z.

Thus Z⊂(M+N) and since (M+N)⊂Z this means (M+N)=Z. It is therefore appropriate to denote the dedekind set N as −M. Thus there exists an additive inverse for any dedekind set.

The Complete Definition of the Multiplication of Dedekind Sets

In the above multiplication was defined only for dedekind sets which are positive. Here are the definitions for the other cases.

The Imbedding of the Rational Numbers
in the Set of Dedekind Sets

For any rational number q let its associated dedekind set be Mq = {m: m∈Q and m<q}. The set Mq can be characterized in terms of open and closed intervals; i.e.,

Mq = (−∞, q)
and its complement as
[q, +∞)

This can only be done for a dedekind set defined for a rational number. There are dedekind sets such that there is no rational number b such that they are of the form (−∞, b).

The Representation of an Irrational Number as a Dedekind Set

Consider the square root of 2. The dedekind set will involve rational numbers such that their squares are less than 2. However if the definition included all rational numbers such that their squares are less than 2 the set would not be a dedekind set. It would be the interval (−√2, +√2). To get a dedekind set, one that is downwardly closed, it is necessary to union that set with all of the negative rationals; i.e., {q: q²<2}∪{q: q<0}.

Now back to the general structure.

The Multiplicative Identity

Let I be the set of all rational numbers which are less than 1. This is obviously a dedekind set. Let M be any dedekind set. Consider M×I. For M positive this consists of all the negative rationals plus all elements of the form m·i where m belongs to M and i belongs to I. Since m·i<m and m belongs to M, m·i belongs to M. This means (M×I)⊂M.

Now choose any element of M, say m. There necessarily exists a p belonging to M such that m<p. Then m=p·(m/p). Since (m/p)<1, (m/p)∈I. Thus m∈(M×I). This means M⊂(M×I).

Thus (M×I)=M and hence I is a multiplicative identity.

The Existence of Multiplicative Inverses
for Non-Zero Dedekind Sets

Consider first the simple for Q where Q is the dedekind set for a positive rational number q; i.e., the set of all rational numbers less than q. The multiplicative inverse for Q has to be the set of all rational numbers which are less than q-1 in value. This set can be constructed by taking all of the rational numbers which are greater than or equal to q, then taking their multiplicative inverses and finally adjoining that set with the negative rationals. (Special attention must be given to the case in which q=0.)

Now consider that definition applied to a more general dedekind set M. For simplicity let M be positive. Let N be the set of all reciprocals of the complement of M unioned with the set of nonpositive rationals.

Now consider M×N and let x be any positive element of M×N. This means that there exist m and n such that mn=x and that n is equal to p which is greater than any element of M; i.e., x=m/p and p>m. Thus x<1. This means M×N⊂I. Now consider any element y of I. This means y<1. Let m be any element of M. Any element of N is the reciprocal of elements all of which are greater than any element of M so there exists mn such that mn=y. But n is the reciprocal of p which is greater than m hence y∈M×N. Thus I⊂M×N. Therefore M×N=I and thus N is the multiplicative inverse of M.

The Other Properties

The associativity, commutativity and distributivity of addition and multiplication for dedekind sets follows from those properties of addition and multiplication for the rational numbers.

The seemingly difficult-to-prove but crucial property for dedekind sets is that if a set X of dedekind sets has an upper bound under the order relation then X has a least upper bound. The least upper bound is simply the set union of the sets in X. Let this set be denoted S. The set S is a dedekind set. Suppose there were a set T that is an upper bound for all of the sets in X and is less than S. This would mean that there is an element s which is in S but is not in T. But s being in S means that s belongs to at least one set in X. This would mean T is not an upper bound to that set and hence not an upper bound to the set of dedekind set X. This contradiction means that the set union of a set of dedekind sets is the least upper bound of that set.


HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins