1-- Addition of Dedekind real numbers2-- Part of Cumulus, the Grace17 mathematics library.3-- Copyright (c) 2026 Grant Passmore.4-- Released under the Apache License 2.0. See LICENSE in the repository root.5-- Authors: Grant Passmore67module Grace.Cumulus.Real.Addition8import Embedding910-- The lower cut generated by all rational sums a+b with a ∈ A and b ∈ B.11-- Writing the strict lower closure into the definition makes downward closure12-- and roundedness consequences of the rational order itself.13def realAddCut (A B : Set) : Set:=14 { q ∈ ℚ |15∃ a ∈ A, ∃ b ∈ B,16 relates(rationalLess, q, rationalAdd((a, b))) }1718-- The real zero is the lower rational cut at zero. Its soft result type lets19-- overloaded real notation recognize it, while realZero.real below supplies20-- the kernel-checked mathematical certificate.21def realZero : Real:= rationalCut(rationalZero)2223theorem realZero.real24showsReal(realZero)25proof26unfold realZero27exact rationalCut.real with rationalZero.rational2829instance realZero.of_nat30shows OfNat(ℝ, 0, realZero)31proof32constructor33 . typecheck34 . exact realZero.real3536-- Public-facing membership avoids exposing the underlying function-graph37-- application. The witnesses are still checked against the same definition.38theorem realAddCut.membership_value (A B q : Set)39shows q ∈ realAddCut(A, B) ↔40 (q ∈ ℚ ∧∃ a ∈ A, ∃ b ∈ B,41 q < rationalAddValue(a, b))42proof43constructor44 . intro member45obtain⟨qInQ, a, aInA, b, bInB, less⟩:= realAddCut.membership.forward with member46refine⟨qInQ, a, aInA, b, bInB, _⟩47unfold rationalAddValue48exact less49 . intro data50rcases data with⟨qInQ2, c, cInA, d, dInB, less2⟩51unfold rationalAddValue at less252exact realAddCut.membership.backward with⟨qInQ2, c, cInA, d, dInB, less2⟩5354theorem realAddCut.subset_rationals (A B : Set)55shows (realAddCut(A, B) ⊆ ℚ)56proof57simp5859theorem realAddCut.nonempty (A B : Real)60shows Nonempty(realAddCut(A, B))61proof62have cutA :=Real.characterization.forward at A withassumption63have cutB :=Real.characterization.forward at B withassumption64obtain⟨a, aInA⟩:= DedekindCut.nonempty with cutA65obtain⟨b, bInB⟩:= DedekindCut.nonempty with cutB66have subsetA := DedekindCut.subset_rationals with cutA67have subsetB := DedekindCut.subset_rationals with cutB68have aInQ := subsetA with a, aInA69have bInQ := subsetB with b, bInB70have aRational : Rational(a) byexact aInQ71have bRational : Rational(b) byexact bInQ72have sumRational := rationalAddValue.rational_raw with aRational, bRational73obtain⟨q, qInQ, qLessSum⟩:= rationalLess.exists_below with sumRational74witness q75apply realAddCut.membership.backward76constructor77 . exact qInQ78 . witness a79constructor80 . exact aInA81 . witness b82constructor83 . exact bInB84 . unfold rationalAddValue at qLessSum85exact qLessSum8687theorem realAddCut.downward (A B p q : Set)88requires realA : Real(A)89requires realB : Real(B)90requires qInSum : q ∈ realAddCut(A, B)91requires pInQ : p ∈ ℚ92requires pLessQ : relates(rationalLess, p, q)93shows p ∈ realAddCut(A, B)94proof95obtain⟨qInQ, a, aInA, b, bInB, qLessSum⟩:= realAddCut.membership.forward with qInSum96have cutA :=Real.characterization.forward with realA97have cutB :=Real.characterization.forward with realB98have subsetA := DedekindCut.subset_rationals with cutA99have subsetB := DedekindCut.subset_rationals with cutB100have aRational : Rational(a)101unfoldRational102exact subsetA with a, aInA103have bRational : Rational(b)104unfoldRational105exact subsetB with b, bInB106have transitive := rationalLess.transitive_on107have sumInQ := rationalAddValue.rational_raw with aRational, bRational108unfold rationalAddValue at sumInQ109have pLessSum := transitive with110 p, pInQ, q, qInQ, rationalAdd((a, b)), sumInQ, pLessQ, qLessSum111exact realAddCut.membership.backward with⟨pInQ, a, aInA, b, bInB, pLessSum⟩112113theorem realAddCut.no_greatest (A B q : Set)114requires realA : Real(A)115requires realB : Real(B)116requires qInSum : q ∈ realAddCut(A, B)117shows∃ r ∈ realAddCut(A, B), relates(rationalLess, q, r)118proof119obtain⟨qInQ, a, aInA, b, bInB, qLessSum⟩:= realAddCut.membership.forward with qInSum120have cutA :=Real.characterization.forward with realA121have cutB :=Real.characterization.forward with realB122have subsetA := DedekindCut.subset_rationals with cutA123have subsetB := DedekindCut.subset_rationals with cutB124have aRational : Rational(a)125unfoldRational126exact subsetA with a, aInA127have bRational : Rational(b)128unfoldRational129exact subsetB with b, bInB130have sumRational := rationalAddValue.rational_raw with aRational, bRational131have qRational : Rational(q) byexact qInQ132unfold rationalAddValue at sumRational133obtain⟨r, rInQ, qLessR, rLessSum⟩:= rationalLess.dense with qRational, sumRational, qLessSum134witness r135constructor136 . apply realAddCut.membership.backward at A, B, r137refine⟨rInQ, a, aInA, b, bInB, rLessSum⟩138 . exact qLessR139140theorem realAddCut.proper (A B : Real)141shows realAddCut(A, B) ≠ ℚ142proof143have cutA :=Real.characterization.forward at A withassumption144have cutB :=Real.characterization.forward at B withassumption145have properA := DedekindCut.proper with cutA146have properB := DedekindCut.proper with cutB147obtain⟨u, uInQ, uMissing⟩:= ProperSubset.missing with properA148obtain⟨v, vInQ, vMissing⟩:= ProperSubset.missing with properB149have uRational : Rational(u) byexact uInQ150have vRational : Rational(v) byexact vInQ151have upperRational := rationalAddValue.rational_raw with uRational, vRational152intro allRationals153have upperInSum : rationalAddValue(u, v) ∈ realAddCut(A, B)154rw allRationals155exact upperRational156obtain⟨upperInQ, a, aInA, b, bInB, upperLessSum⟩:= realAddCut.membership.forward with upperInSum157have subsetA := DedekindCut.subset_rationals with cutA158have subsetB := DedekindCut.subset_rationals with cutB159have aRational : Rational(a)160unfoldRational161exact subsetA with a, aInA162have bRational : Rational(b)163unfoldRational164exact subsetB with b, bInB165have aLessU := DedekindCut.lt_missing with cutA, aInA, uInQ, uMissing166have bLessV := DedekindCut.lt_missing with cutB, bInB, vInQ, vMissing167have first := rationalLess.add_right with aRational, uRational, bRational, aLessU168have second := rationalLess.add_left with bRational, vRational, uRational, bLessV169rw [rationalAddValue.notation, rationalAddValue.notation] at first170rw [rationalAddValue.notation, rationalAddValue.notation] at second171have sumRational := rationalAddValue.rational_raw with aRational, bRational172have middleRational := rationalAddValue.rational_raw with uRational, bRational173have sumInQ := sumRational174have middleInQ := middleRational175have transitive := rationalLess.transitive_on176have sumLessUpper := transitive with177 rationalAddValue(a, b), sumInQ,178 rationalAddValue(u, b), middleInQ,179 rationalAddValue(u, v), upperInQ,180 first, second181unfold rationalAddValue at upperLessSum182unfold rationalAddValue at sumLessUpper183unfold rationalAddValue at upperInQ184unfold rationalAddValue at sumInQ185have cycle := transitive with186 rationalAdd((u, v)), upperInQ,187 rationalAdd((a, b)), sumInQ,188 rationalAdd((u, v)), upperInQ,189 upperLessSum, sumLessUpper190have irreflexive := rationalLess.irreflexive_on191exact irreflexive with rationalAdd((u, v)), upperInQ, cycle192193theorem realAddCut.cut (A B : Real)194shows DedekindCut(realAddCut(A, B))195proof196have subset := realAddCut.subset_rationals at A, B197have inhabited := realAddCut.nonempty at A, B with*198have proper := realAddCut.proper at A, B with*199unfold DedekindCut200refine⟨subset, inhabited, proper, _, _⟩201 . intros q qInSum p pInQ pLessQ202exact realAddCut.downward with qInSum, pInQ, pLessQ203 . intros q qInSum204exact realAddCut.no_greatest with qInSum205206theorem realAddCut.real (A B : Real)207showsReal(realAddCut(A, B))208proof209applyReal.characterization.backward210exact realAddCut.cut with*211212-- Real addition as a set-valued function graph on pairs of cuts.213def realAdd : Set:=214 { p ∈ ((ℝ × ℝ) × ℝ) |215∃ A ∈ ℝ, ∃ B ∈ ℝ,216 p = ((A, B) ↦ realAddCut(A, B)) }217218def realAddValue (A B : Real) : Real:= realAdd((A, B))219220theorem realAdd.relates (A B : Real)221shows relates(realAdd, (A, B), realAddCut(A, B))222proof223have realA : A ∈ ℝ bysimp [Real]224have realB : B ∈ ℝ bysimp [Real]225unfold relates226apply realAdd.membership.backward227constructor228 . apply product.pair at (A, B), realAddCut(A, B), ℝ × ℝ, ℝ229 . apply product.pair at A, B, ℝ, ℝ230 . exact realA231 . exact realB232 . exact realAddCut.real at A, B with*{2}233 . refine⟨A, realA, B, realB, rfl⟩234235theorem realAdd.factors (input output : Set)236requires mapped : relates(realAdd, input, output)237shows∃ A ∈ ℝ, ∃ B ∈ ℝ,238 input = (A, B) ∧ output = realAddCut(A, B)239proof240unfold relates at mapped241simp [realAdd.membership] at mapped242rcases mapped with⟨bounded, A, realA, B, realB, shape⟩243obtain⟨inputShape, outputShape⟩:= orderedPair.injective with shape244refine⟨A, realA, B, realB, inputShape, outputShape⟩245246theorem realAdd.total247shows TotalBetween(realAdd, ℝ × ℝ, ℝ)248proof249intros input inputInProduct250obtain⟨bounded, A, realA, B, realB, inputShape⟩:= product.membership.forward with inputInProduct251have typedA : Real(A) byexact realA252have typedB : Real(B) byexact realB253witness realAddCut(A, B)254constructor255 . exact realAddCut.real with typedA, typedB256 . rw inputShape257exact realAdd.relates with typedA, typedB258259theorem realAdd.functional260shows Functional(realAdd)261proof262intros input y inputY z inputZ263obtain⟨A, realA, B, realB, inputFirst, outputFirst⟩:= realAdd.factors with inputY264obtain⟨C, realC, D, realD, inputSecond, outputSecond⟩:= realAdd.factors with inputZ265rw inputFirst at inputSecond266obtain⟨sameLeft, sameRight⟩:= orderedPair.injective with inputSecond267rw [outputFirst, outputSecond, sameLeft, sameRight]268rfl269270theorem realAdd.function271shows realAdd : ℝ × ℝ → ℝ272proof273constructor274intros p hp275simp [realAdd.membership] at hp276rcases hp with⟨bounded, witnesses⟩277exact bounded278 . constructor279 . exact realAdd.functional280 . exact realAdd.total281282instance realAdd.operation283shows AddOperation(ℝ, realAdd)284proof285exact realAdd.function286287notationinfixl60"+"=> call2 via AddOperation(ℝ, _) forReal288notation numeral "0"via OfNat(ℝ, 0, _) forReal289290theorem realAddValue.real (A B : Real)291showsReal(A + B)292proof293have realA : A ∈ ℝ bysimp [Real]294have realB : B ∈ ℝ bysimp [Real]295have input := product.pair with realA, realB296obtain⟨C, realC, mapped⟩:= FunctionBetween.exists_value with realAdd.function, input297have applied := FunctionBetween.apply_value with realAdd.function, input, mapped298unfold call2299rw applied300exact realC301302theorem realAddValue.cut (A B : Real)303shows A + B = realAddCut(A, B)304proof305have realA : A ∈ ℝ bysimp [Real]306have realB : B ∈ ℝ bysimp [Real]307have input := product.pair with realA, realB308have mapped := realAdd.relates at A, B with*309unfold call2310exact FunctionBetween.apply_value with realAdd.function, input, mapped311312theorem realAddCut.commutative (A B : Real)313shows realAddCut(A, B) = realAddCut(B, A)314proof315ext q316constructor317 . intro qInSum318obtain⟨qInQ, a, aInA, b, bInB, qLessSum⟩:= realAddCut.membership.forward with qInSum319have cutA :=Real.characterization.forward at A withassumption320have cutB :=Real.characterization.forward at B withassumption321have subsetA := DedekindCut.subset_rationals with cutA322have subsetB := DedekindCut.subset_rationals with cutB323have aRational : Rational(a)324unfoldRational325exact subsetA with a, aInA326have bRational : Rational(b)327unfoldRational328exact subsetB with b, bInB329have sumComm := rationalAddValue.commutative with aRational, bRational330unfold call2 at sumComm331rw sumComm at qLessSum332exact realAddCut.membership.backward with⟨qInQ, b, bInB, a, aInA, qLessSum⟩333 . intro qInSum334obtain⟨qInQ2, b2, b2InB, a2, a2InA, qLessSum2⟩:= realAddCut.membership.forward with qInSum335have cutA :=Real.characterization.forward at A withassumption336have cutB :=Real.characterization.forward at B withassumption337have subsetA := DedekindCut.subset_rationals with cutA338have subsetB := DedekindCut.subset_rationals with cutB339have a2Rational : Rational(a2)340unfoldRational341exact subsetA with a2, a2InA342have b2Rational : Rational(b2)343unfoldRational344exact subsetB with b2, b2InB345have sumComm2 := rationalAddValue.commutative with b2Rational, a2Rational346unfold call2 at sumComm2347rw sumComm2 at qLessSum2348exact realAddCut.membership.backward with⟨qInQ2, a2, a2InA, b2, b2InB, qLessSum2⟩349350theorem realAddCut.zero_right (A : Real)351shows realAddCut(A, realZero) = A352proof353ext q354constructor355 . intro qInSum356obtain⟨qInQ, a, aInA, b, bInZero, qLessSum⟩:= realAddCut.membership.forward with qInSum357unfold realZero at bInZero358simp [rationalCut.membership] at bInZero359rcases bInZero with⟨bInQ, bLessZero⟩360have cutA :=Real.characterization.forward withassumption361have subsetA := DedekindCut.subset_rationals with cutA362have aInQ := subsetA with a, aInA363have aRational : Rational(a) byexact aInQ364have bRational : Rational(b) byexact bInQ365have shifted := rationalLess.add_left with bRational, rationalZero.rational, aRational, bLessZero366have identity := rationalAddValue.zero_right with aRational367rw identity at shifted368have sumRational := rationalAddValue.rational_raw with aRational, bRational369have sumInQ := sumRational370unfold rationalAddValue at sumInQ371unfold call2 at shifted372have transitive := rationalLess.transitive_on373have qLessA := transitive with374 q, qInQ, rationalAdd((a, b)), sumInQ, a, aInQ,375 qLessSum, shifted376exact DedekindCut.downward with cutA, aInA, qInQ, qLessA377 . intro qInA378have cutA :=Real.characterization.forward withassumption379have subsetA := DedekindCut.subset_rationals with cutA380have qInQ := subsetA with q, qInA381obtain⟨r, rInA, qLessR⟩:= DedekindCut.no_greatest with cutA, qInA382have rInQ := subsetA with r, rInA383have rRational : Rational(r) byexact rInQ384obtain⟨s, sInQ, qLessS, sLessR⟩:= rationalLess.dense with qLessR385have sRational : Rational(s) bytypecheck386have differenceRational := rationalSubValue.rational with sRational, rRational387have differenceNegative := rationalLess.sub_self_negative with sLessR388have differenceInZero : s - r ∈ realZero389unfold realZero390simp [rationalCut.membership]391constructor392exact differenceRational393 . exact differenceNegative394have sumShape := rationalAddValue.add_sub_cancel_left with rRational, sRational395rw← sumShape at qLessS396unfold call2 at qLessS397exact realAddCut.membership.backward with⟨qInQ, r, rInA, s - r, differenceInZero, qLessS⟩398399theorem realAddCut.zero_left (A : Real)400shows realAddCut(realZero, A) = A401proof402calc403 realAddCut(realZero, A) = realAddCut(A, realZero) :=404 realAddCut.commutative with realZero.real405 _ = A := realAddCut.zero_right at A withassumption406407-- Associativity is proved at the level of cuts. Density supplies an inner408-- witness close enough to the desired rational sum; no representative of a409-- real number or algebraic axiom is hidden in the argument.410theorem realAddCut.associative (A B C : Real)411shows realAddCut(realAddCut(A, B), C) = realAddCut(A, realAddCut(B, C))412proof413ext q414constructor415 . intro qInLeft416obtain⟨qInQ, x, xInAB, c, cInC, qLessXC⟩:= realAddCut.membership_value.forward with qInLeft417obtain⟨xInQ, a, aInA, b, bInB, xLessAB⟩:= realAddCut.membership_value.forward with xInAB418rw← rationalAddValue.notation at qLessXC419rw← rationalAddValue.notation at xLessAB420have cutA :=Real.characterization.forward at A withassumption421have cutB :=Real.characterization.forward at B withassumption422have cutC :=Real.characterization.forward at C withassumption423have subsetA := DedekindCut.subset_rationals with cutA424have subsetB := DedekindCut.subset_rationals with cutB425have subsetC := DedekindCut.subset_rationals with cutC426have qRational : Rational(q) byexact qInQ427have xRational : Rational(x) byexact xInQ428have aRational : Rational(a)429unfoldRational430exact subsetA with a, aInA431have bRational : Rational(b)432unfoldRational433exact subsetB with b, bInB434have cRational : Rational(c)435unfoldRational436exact subsetC with c, cInC437have abRational := rationalAddValue.rational with aRational, bRational438have bcRational := rationalAddValue.rational with bRational, cRational439have scaled := rationalLess.add_right with xRational, abRational, cRational, xLessAB440have qLessABC := rationalLess.transitive with qLessXC, scaled441rw rationalAddValue.associative at qLessABC442have differenceLess := rationalLess.sub_left with qLessABC443have differenceRational := rationalSubValue.rational with qRational, aRational444obtain⟨y, yInQ, differenceLessY, yLessBC⟩:= rationalLess.dense with445 differenceRational, bcRational, differenceLess446have yInBC : y ∈ realAddCut(B, C)447apply realAddCut.membership_value.backward448rw rationalAddValue.notation at yLessBC449refine⟨yInQ, b, bInB, c, cInC, yLessBC⟩450have qLessAY := rationalLess.add_left_of_sub_left with differenceLessY451apply realAddCut.membership_value.backward452rw rationalAddValue.notation at qLessAY453refine⟨qInQ, a, aInA, y, yInBC, qLessAY⟩454 . intro qInRight455obtain⟨qInQ2, a2, a2InA, y2, y2InBC, qLessAY2⟩:= realAddCut.membership_value.forward with qInRight456obtain⟨y2InQ, b2, b2InB, c2, c2InC, y2LessBC⟩:= realAddCut.membership_value.forward with y2InBC457rw← rationalAddValue.notation at qLessAY2458rw← rationalAddValue.notation at y2LessBC459have cutA2 :=Real.characterization.forward at A withassumption460have cutB2 :=Real.characterization.forward at B withassumption461have cutC2 :=Real.characterization.forward at C withassumption462have subsetA2 := DedekindCut.subset_rationals with cutA2463have subsetB2 := DedekindCut.subset_rationals with cutB2464have subsetC2 := DedekindCut.subset_rationals with cutC2465have qRational2 : Rational(q) byexact qInQ2466have a2Rational : Rational(a2)467unfoldRational468exact subsetA2 with a2, a2InA469have y2Rational : Rational(y2) byexact y2InQ470have b2Rational : Rational(b2)471unfoldRational472exact subsetB2 with b2, b2InB473have c2Rational : Rational(c2)474unfoldRational475exact subsetC2 with c2, c2InC476have a2b2Rational := rationalAddValue.rational with a2Rational, b2Rational477have b2c2Rational := rationalAddValue.rational with b2Rational, c2Rational478have scaled2 := rationalLess.add_left with y2Rational, b2c2Rational, a2Rational, y2LessBC479have qLessABC2 := rationalLess.transitive with qLessAY2, scaled2480rw← rationalAddValue.associative at qLessABC2481have outerCommutative2 := rationalAddValue.commutative with a2b2Rational, c2Rational482rw outerCommutative2 at qLessABC2483have differenceLess2 := rationalLess.sub_left with qLessABC2484have differenceRational2 := rationalSubValue.rational with qRational2, c2Rational485obtain⟨x2, x2InQ, differenceLessX2, x2LessAB⟩:= rationalLess.dense with486 differenceRational2, a2b2Rational, differenceLess2487have x2Rational : Rational(x2) bytypecheck488have x2InAB : x2 ∈ realAddCut(A, B)489apply realAddCut.membership_value.backward490rw rationalAddValue.notation at x2LessAB491refine⟨x2InQ, a2, a2InA, b2, b2InB, x2LessAB⟩492have qLessCX2 := rationalLess.add_left_of_sub_left with493 qRational2, c2Rational, x2Rational, differenceLessX2494have innerCommutative2 := rationalAddValue.commutative with c2Rational, x2Rational495rw innerCommutative2 at qLessCX2496apply realAddCut.membership_value.backward497rw rationalAddValue.notation at qLessCX2498refine⟨qInQ2, x2, x2InAB, c2, c2InC, qLessCX2⟩499500theorem realAddValue.commutative (A B : Real)501shows A + B = B + A502proof503calc504 A + B = realAddCut(A, B) :=505 realAddValue.cut with*{2}506 _ = realAddCut(B, A) :=507 realAddCut.commutative with*{2}508 _ = B + A :=bysimp [realAddValue.cut]509510theorem realAddValue.zero_right (A : Real)511shows A +0= A512proof513calc514 A + realZero = realAddCut(A, realZero) :=515 realAddValue.cut with realZero.real516 _ = A := realAddCut.zero_right at A withassumption517518theorem realAddValue.zero_left (A : Real)519shows0+ A = A520proof521calc522 realZero + A = A + realZero :=523 realAddValue.commutative with realZero.real524 _ = A := realAddValue.zero_right at A withassumption525526theorem realAddValue.associative (A B C : Real)527shows (A + B) + C = A + (B + C)528proof529calc530 (A + B) + C = realAddCut(realAddCut(A, B), C) :=bysimp [realAddValue.cut]531 _ = realAddCut(A, realAddCut(B, C)) :=532 realAddCut.associative with*{3}533 _ = A + (B + C) :=bysimp [realAddValue.cut]534535-- The first bundled algebraic structure on the Dedekind reals. It is a536-- checked theorem that elaboration registers as an instance.537instance realAdd.comm_monoid538shows IsCommMonoid(ℝ, realAdd, realZero)539proof540constructor541constructor542constructor543exact realAdd.function544intros A realA B realB C realC545have typedA : Real(A) byexact realA546have typedB : Real(B) byexact realB547have typedC : Real(C) byexact realC548exact realAddValue.associative with typedA, typedB, typedC549constructor550 . exact realZero.real551 . intros A realA552have typedA : Real(A) byexact realA553constructor554 . exact realAddValue.zero_left with typedA555 . exact realAddValue.zero_right with typedA556intros A realA B realB557have typedA : Real(A) byexact realA558have typedB : Real(B) byexact realB559exact realAddValue.commutative with typedA, typedB560561theorem realAddValue.type (A B : Real)562showsReal(realAddValue(A, B))563proof564have closed := realAddValue.real at A, B with*565unfold realAddValue566unfold call2 at closed567exact closed568