请输入您要查询的字词:

 

单词 1132InductionAndRecursionOnCauchyReals
释义

11.3.2 Induction and recursion on Cauchy reals


In order to do anything useful with 𝖼, of course, we need to give its inductionMathworldPlanetmath principle.As is the case whenever we inductively define two or more objects at once, the basic induction principle for 𝖼 and requires a simultaneous induction over both at once.Thus, we should expect it to say that assuming two type families over 𝖼 and , respectively, together with data corresponding to each constructor, there exist sectionsPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath of both of these families.However, since is indexed on two copies of 𝖼, the precise dependencies of these families is a bit subtle.The induction principle will apply to any pair of type families:

A:𝖼𝒰
B:x,y:𝖼A(x)A(y)ϵ:+(xϵy)𝒰.

The type of A is obvious, but the type of B requires a little thought.Since B must depend on , but in turn depends on two copies of 𝖼 and one copy of +, it is fairly obvious that B must also depend on the variables x,y:𝖼 and ϵ:+ as well as an element of (xϵy).What is slightly less obvious is that B must also depend on A(x) and A(y).

This may be more evident if we consider the non-dependent case (the recursion principle), where A is a simple type (rather than a type family).In this case we would expect B not to depend on x,y:𝖼 or xϵy.But the recursion principle (along with its associated uniqueness principle) is supposed to say that 𝖼 with ϵ is an “initial objectMathworldPlanetmath” in some categoryMathworldPlanetmath, so in this case the dependency structureMathworldPlanetmath of A and B should mirror that of 𝖼 and ϵ: that is, we should have B:AA+𝒰.Combining this observation with the fact that, in the dependent case, B must also depend on x,y:𝖼 and xϵy, leads inevitably to the type given above for B.

It is helpful to think of B as an ϵ-indexed family of relationsMathworldPlanetmathPlanetmath between the types A(x) and A(y).With this in mind, we may write B(x,y,a,b,ϵ,ξ) as (x,a)ϵξ(y,b).Since ξ:xϵy is unique when it exists, we generally omit it from the notation and write (x,a)ϵ(y,b); this is harmless as long as we keep in mind that this relation is only defined when xϵy.We may also sometimes simplify further and write aϵb, with x and y inferred from the types of a and b, but sometimes it will be necessary to include them for clarity.

Now, given a type family A:𝖼𝒰 and a family of relations as above, the hypotheses of the induction principle consist of the following data, one for each constructor of 𝖼 or :

  • For any q:, an element fq:A(𝗋𝖺𝗍(q)).

  • For any Cauchy approximation x, and any a:(ϵ:+)A(xϵ) such that

    (δ,ϵ:+).(xδ,aδ)δ+ϵ(xϵ,aϵ),(11.3.1)

    an element fx,a:A(𝗅𝗂𝗆(x)).We call such a a dependent Cauchy approximationover x.

  • For u,v:𝖼 such that h:(ϵ:+).uϵv, and all a:A(u) and b:A(v) such that(ϵ:+).(u,a)ϵ(v,b),a dependent path a=𝖾𝗊𝖼(u,v)Ab.

  • For q,r: and ϵ:+, if -ϵ<q-r<ϵ, we have(𝗋𝖺𝗍(q),fq)ϵ(𝗋𝖺𝗍(r),fr).

  • For q: and δ,ϵ:+ and y a Cauchy approximation, and b a dependent Cauchy approximation over y, if 𝗋𝖺𝗍(q)ϵ-δyδ, then

    (𝗋𝖺𝗍(q),fq)ϵ-δ(yδ,bδ)(𝗋𝖺𝗍(q),fq)ϵ(𝗅𝗂𝗆(y),fy,b).
  • Similarly, for r: and δ,ϵ:+ and x a Cauchy approximation, and a a dependent Cauchy approximation over x, if xδϵ-δ𝗋𝖺𝗍(r), then

    (xδ,aδ)ϵ-δ(𝗋𝖺𝗍(r),fr)(𝗅𝗂𝗆(x),fx,a)ϵ(𝗋𝖺𝗍(q),fr).
  • For ϵ,δ,η:+ and x,y Cauchy approximations, and a and b dependent Cauchy approximations over x and y respectively, if we have xδϵ-δ-ηyη, then

    (xδ,aδ)ϵ-δ-η(yη,bη)(𝗅𝗂𝗆(x),fx,a)ϵ(𝗅𝗂𝗆(y),fy,b).
  • For ϵ:+ and x,y:𝖼 and ξ,ζ:xϵy, and a:A(x) and b:A(y), any two elements of (x,a)ϵξ(y,b) and (x,a)ϵζ(y,b) are dependently equal over ξ=ζ.Note that as usual, this is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath to asking that takes values in mere propositions.

Under these hypotheses, we deduce functions

f:x:𝖼A(x)
g:(x,y:𝖼)(ϵ:+)(ξ:xϵy)(x,f(x))ϵξ(y,f(y))

which compute as expected:

f(𝗋𝖺𝗍(q)):fq,(11.3.2)
f(𝗅𝗂𝗆(x)):fx,(f,g)[x].(11.3.2)

Here (f,g)[x] denotes the result of applying f and g to a Cauchy approximation x to obtain a dependent Cauchy approximation over x.That is, we define (f,g)[x]ϵ:f(xϵ):A(xϵ), and then for any ϵ,δ:+ we have g(xϵ,xδ,ϵ+δ,ξ) to witness the fact that (f,g)[x] is a dependent Cauchy approximation, where ξ:xϵϵ+δxδ arises from the assumptionPlanetmathPlanetmath that x is a Cauchy approximation.

We will never use this notation again, so don’t worry about remembering it.Generally we use the pattern-matching convention, where f is defined by equations such as (11.3.2) and (11.3.2) in which the right-hand side of (11.3.2) may involve the symbols f(xϵ) and an assumption that they form a dependent Cauchy approximation.

However, this induction principle is admittedly still quite a mouthful.To help make sense of it, we observe that it contains as special cases two separate induction principles for 𝖼 and for .Firstly, suppose given only a type family A:𝖼𝒰, and define to be constant at 𝟏.Then much of the required data becomes trivial, and we are left with:

  • for any q:, an element fq:A(𝗋𝖺𝗍(q)),

  • for any Cauchy approximation x, and any a:(ϵ:+)A(xϵ), an element fx,a:A(𝗅𝗂𝗆(x)),

  • for u,v:𝖼 and h:(ϵ:+).uϵv, and a:A(u) and b:A(v), we have a=𝖾𝗊𝖼(u,v)Ab.

Given these data, the induction principle yields a function f:(x:𝖼)A(x) such that

f(𝗋𝖺𝗍(q)):fq,
f(𝗅𝗂𝗆(x)):fx,f(x).

We call this principle 𝖼-induction; it says essentially that if we take ϵ as given, then 𝖼 is inductively generated by its constructors.

In particular, if A is a mere property, the third hypothesisMathworldPlanetmath in 𝖼-induction is trivial.Thus, we may prove mere properties of real numbers by simply proving them for rationals and for limits of Cauchy approximations.Here is an example.

Lemma 11.3.2.

For any u:Rc and ϵ:Q+, we have uϵu.

Proof.

Define A(u):(ϵ:+).(uϵu).Since this is a mere proposition (by the last constructor of ), by 𝖼-induction, it suffices to prove it when u is 𝗋𝖺𝗍(q) and when u is 𝗅𝗂𝗆(x).In the first case, we obviously have |q-q|<ϵ for any ϵ, hence 𝗋𝖺𝗍(q)ϵ𝗋𝖺𝗍(q) by the first constructor of .And in the second case, we may assume inductively that xδϵxδ for all δ,ϵ:+.Then in particular, we have xϵ/3ϵ/3xϵ/3, whence 𝗅𝗂𝗆(x)ϵ𝗅𝗂𝗆(x) by the fourth constructor of .∎

Theorem 11.3.3.

𝖼 is a set.

Proof.

We have just shown that the mere relationP(u,v):(ϵ:+).(uϵv)is reflexiveMathworldPlanetmathPlanetmath.Since it implies identity, by the path constructor of 𝖼, the result follows from \\autorefthm:h-set-refrel-in-paths-sets.∎

We can also show that although 𝖼 may not be a quotient of the set of Cauchy sequencesPlanetmathPlanetmath of rationals, it is nevertheless a quotient of the set of Cauchy sequences of reals.(Of course, this is not a valid definition of 𝖼, but it is a useful property.)We define the type of Cauchy approximations to be

𝒞:\\setofx:+𝖼|(ϵ,δ:+).xδδ+ϵxϵ.

The second constructor of 𝖼 gives a function 𝗅𝗂𝗆:𝒞𝖼.

Lemma 11.3.4.

Every real merely is a limit pointMathworldPlanetmathPlanetmath: (u:Rc).(x:C).u=lim(x).In other words, lim:CRc is surjective.

Proof.

By 𝖼-induction, we may divide into cases on u.Of course, if u is a limit 𝗅𝗂𝗆(x), the statement is trivial.So suppose u is a rational point 𝗋𝖺𝗍(q); we claim u is equal to 𝗅𝗂𝗆(λϵ.𝗋𝖺𝗍(q)).By the path constructor of 𝖼, it suffices to show 𝗋𝖺𝗍(q)ϵ𝗅𝗂𝗆(λϵ.𝗋𝖺𝗍(q)) for all ϵ:+.And by the second constructor of , for this it suffices to find δ:+ such that 𝗋𝖺𝗍(q)ϵ-δ𝗋𝖺𝗍(q).But by the first constructor of , we may take any δ:+ with δ<ϵ.∎

Lemma 11.3.5.

If A is a set and f:CA respects coincidence of Cauchy approximations, in the sense that

(x,y:𝒞).𝗅𝗂𝗆(x)=𝗅𝗂𝗆(y)f(x)=f(y),

then f factors uniquely through lim:CRc.

Proof.

Since 𝗅𝗂𝗆 is surjective, by \\autoreflem:images_are_coequalizers, 𝖼 is the quotient of 𝒞 by the kernel pair of 𝗅𝗂𝗆.But this is exactly the statement of the lemma.∎

For the second special case of the induction principle, suppose instead that we take A to be constant at 𝟏.In this case, is simply an ϵ-indexed family of relations on ϵ-close pairs of real numbers, so we may write uϵv instead of (u,)ϵ(v,).Then the required data reduces to the following, where q,r denote rational numbers, ϵ,δ,η positive rational numbers, and x,y Cauchy approximations:

  • if -ϵ<q-r<ϵ, then𝗋𝖺𝗍(q)ϵ𝗋𝖺𝗍(r),

  • if 𝗋𝖺𝗍(q)ϵ-δyδ and𝗋𝖺𝗍(q)ϵ-δyδ,then 𝗋𝖺𝗍(q)ϵ𝗅𝗂𝗆(y),

  • if xδϵ-δ𝗋𝖺𝗍(r) andxδϵ-δ𝗋𝖺𝗍(r),then 𝗅𝗂𝗆(y)ϵ𝗋𝖺𝗍(q),

  • if xδϵ-δ-ηyη andxδϵ-δ-ηyη,then 𝗅𝗂𝗆(x)ϵ𝗅𝗂𝗆(y).

The resulting conclusionMathworldPlanetmath is (u,v:𝖼).(ϵ:+).(uϵv)(uϵv).We call this principle -induction; it says essentially that if we take 𝖼 as given, then ϵ is inductively generated (as a family of types) by its constructors.For example, we can use this to show that is symmetric.

Lemma 11.3.6.

For any u,v:Rc and ϵ:Q+, we have (uϵv)=(vϵu).

Proof.

Since both are mere propositions, by symmetry it suffices to show one implicationMathworldPlanetmath.Thus, let (uϵv):(vϵu).By -induction, we may reduce to the case that uϵv is derived from one of the four interesting constructors of .In the first case when u and v are both rational, the result is trivial (we can apply the first constructor again).In the other three cases, the inductive hypothesis (together with commutativity of additionPlanetmathPlanetmath in ) yields exactly the input to another of the constructors of (the second and third constructors switch, while the fourth stays put).∎

The general induction principle, which we may call (𝖼,)-induction, is therefore a sort of joint 𝖼-induction and -induction.Consider, for instance, its non-dependent version, which we call (𝖼,)-recursion, which is the one that we will have the most use for.Ordinary 𝖼-recursion tells us that to define a function f:𝖼A it suffices to:

  1. 1.

    for every q: construct f(𝗋𝖺𝗍(q)):A,

  2. 2.

    for every Cauchy approximation x:+𝖼, construct f(x):A,assuming that f(xϵ) has already been defined for all ϵ:+,

  3. 3.

    prove f(u)=f(v) for all u,v:𝖼 satisfying (ϵ:+).uϵv.

However, it is generally quite difficult to show 3 without knowing something about how f acts on ϵ-close Cauchy reals.The enhanced principle of (𝖼,)-recursion remedies this deficiency, allowing us to specify an arbitrary “way in which f acts on ϵ-close Cauchy reals”, which we can then prove to be the case by a simultaneous induction with the definition of f.This is the family of relations .Since A is independent of 𝖼, we may assume for simplicity that depends only on A and +, and thus there is no ambiguity in writing aϵb instead of (u,a)ϵ(v,b).In this case, defining a function f:𝖼A by (𝖼,)-recursion requires the following cases (which we now write using the pattern-matching convention).

  • For every q:, construct f(𝗋𝖺𝗍(q)):A.

  • For every Cauchy approximation x:+𝖼, construct f(x):A, assuming inductively that f(xϵ) has already been defined for all ϵ:+ and form a “Cauchy approximation with respect to ”, i.e. that (ϵ,δ:+).(f(xϵ)ϵ+δf(xδ)).

  • Prove that the relations are separated, i.e. that, for any a,b:A,((ϵ:+).aϵb)(a=b).

  • Prove that if -ϵ<q-r<ϵ for q,r:, then f(𝗋𝖺𝗍(q))ϵf(𝗋𝖺𝗍(r)).

  • For any q: and any Cauchy approximation y, prove thatf(𝗋𝖺𝗍(q))ϵf(𝗅𝗂𝗆(y)), assuming inductively that 𝗋𝖺𝗍(q)ϵ-δyδ and f(𝗋𝖺𝗍(q))ϵ-δf(yδ) for some δ:+, and that ηf(xη) is a Cauchy approximation with respect to .

  • For any Cauchy approximation x and any r:, prove thatf(𝗅𝗂𝗆(x))ϵf(𝗋𝖺𝗍(r)),assuming inductively that xδϵ-δ𝗋𝖺𝗍(r) and f(xδ)ϵ-δf(𝗋𝖺𝗍(r)) for some δ:+, and that ηf(xη) is a Cauchy approximation with respect to .

  • For any Cauchy approximations x,y, prove thatf(𝗅𝗂𝗆(x))ϵf(𝗅𝗂𝗆(y)),assuming inductively that xδϵ-δ-ηyη and f(xδ)ϵ-δ-ηf(yη) for some δ,η:+, and that θf(xθ) and θf(yθ) are Cauchy approximations with respect to .

Note that in the last four proofs, we are free to use the specific definitions of f(𝗋𝖺𝗍(q)) and f(𝗅𝗂𝗆(x)) given in the first two data.However, the proof of separatedness must apply to any two elements of A, without any relation to f: it is a sort of “admissibility” condition on the family of relations .Thus, we often verify it first, immediately after defining , before going on to define f(𝗋𝖺𝗍(q)) and f(𝗅𝗂𝗆(x)).

Under the above hypotheses, (𝖼,)-recursion yields a function f:𝖼A such that f(𝗋𝖺𝗍(q)) and f(𝗅𝗂𝗆(x)) are judgmentally equal to the definitions given for them in the first two clauses.Moreover, we may also conclude

(u,v:𝖼).(ϵ:+).(uϵv)(f(u)ϵf(v)).(11.3.7)

As a paradigmatic example, (𝖼,)-recursion allows us to extend functions defined on to all of 𝖼, as long as they are sufficiently continuousMathworldPlanetmathPlanetmath.

Definition 11.3.8.

A function f:QRc is LipschitzPlanetmathPlanetmathif there exists L:Q+ (the Lipschitz constant) such that

|q-r|<ϵ(f(q)Lϵf(r))

for all ϵ:Q+ and q,r:Q.Similarly, g:RcRc is Lipschitz if there exists L:Q+ such that

(uϵv)(g(u)Lϵg(v))

for all ϵ:Q+ and u,v:Rc..

In particular, note that by the first constructor of , if f: is Lipschitz in the obvious sense, then so is the composite 𝑓𝖼.

Lemma 11.3.9.

Suppose f:QRc is Lipschitz with constant L:Q+.Then there exists a Lipschitz map f¯:RcRc, also with constant L, such that f¯(rat(q))f(q) for all q:Q.

Proof.

We define f¯ by (𝖼,)-recursion, with codomain A:𝖼.We define the relation :𝖼𝖼+𝖯𝗋𝗈𝗉 to be

(uϵv):(uLϵv).

For q:, we define

f¯(𝗋𝖺𝗍(q)):𝗋𝖺𝗍(f(q)).

For a Cauchy approximation x:+𝖼, we define

f¯(𝗅𝗂𝗆(x)):𝗅𝗂𝗆(λϵ.f¯(xϵ/L)).

For this to make sense, we must verify that y:λϵ.f¯(xϵ/L) is a Cauchy approximation.However, the inductive hypothesis for this step is that for any δ,ϵ:+ we have f¯(xδ)δ+ϵf¯(xϵ), i.e. f¯(xδ)Lδ+Lϵf¯(xϵ).Thus we have

yδf(xδ/L)δ+ϵf(xϵ/L)yϵ.

For proving separatedness, we simply observe that (ϵ:+).aϵb means (ϵ:+).aLϵb, which implies (ϵ:+).aϵb and thus a=b.

To completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the (𝖼,)-recursion, it remains to verify the four conditions on .This basically amounts to proving that f¯ is Lipschitz for all the four constructors of .

  1. 1.

    When u is 𝗋𝖺𝗍(q) and v is 𝗋𝖺𝗍(r) with -ϵ<|q-r|<ϵ, the assumption that f is Lipschitz yields f(q)Lϵf(r), hence f¯(𝗋𝖺𝗍(q))ϵf¯(𝗋𝖺𝗍(r)) by definition.

  2. 2.

    When u is 𝗅𝗂𝗆(x) and v is 𝗋𝖺𝗍(q) with xηϵ-η𝗋𝖺𝗍(q), then theinductive hypothesis is f¯(xη)Lϵ-Lη𝗋𝖺𝗍(f(q)), which provesf¯(𝗅𝗂𝗆(x))Lϵf¯(𝗋𝖺𝗍(q))by the third constructor of .

  3. 3.

    The symmetric case when u is rational and v is a limit is essentially identical.

  4. 4.

    When u is 𝗅𝗂𝗆(x) and v is 𝗅𝗂𝗆(y), with δ,η:+ such that xδϵ-δ-ηyη,the inductive hypothesis is f¯(xδ)Lϵ-Lδ-Lηf¯(yη), which proves f¯(𝗅𝗂𝗆(x))Lϵf¯(𝗅𝗂𝗆(y)) by the fourth constructor of .

This completes the (𝖼,)-recursion, and hence the construction of f¯.The desired equality f¯(𝗋𝖺𝗍(q))f(q) is exactly the first computation rule for (𝖼,)-recursion, and the additional condition (11.3.7) says exactly that f¯ is Lipschitz with constant L.∎

At this point we have gone about as far as we can without a better characterizationMathworldPlanetmath of .We have specified, in the constructors of , the conditions under which we want Cauchy reals of the two different forms to be ϵ-close.However, how do we know that in the resulting inductive-inductive type family, these are the only witnesses to this fact?We have seen that inductive type families (such as identity types, see \\autorefsec:identity-systems) and higher inductive types have a tendency to contain “more than was put into them”, so this is not an idle question.

In order to characterize more precisely, we will define a family of relations ϵ on 𝖼 recursively, so that they will compute on constructors, and prove that this family is equivalent to ϵ.

Theorem 11.3.10.

There is a family of mere relations :RcRcQ+Prop such that

(𝗋𝖺𝗍(q)ϵ𝗋𝖺𝗍(r)):(-ϵ<q-r<ϵ)(11.3.10)
(𝗋𝖺𝗍(q)ϵ𝗅𝗂𝗆(y)):(δ:+).𝗋𝖺𝗍(q)ϵ-δyδ(11.3.10)
(𝗅𝗂𝗆(x)ϵ𝗋𝖺𝗍(r)):(δ:+).xδϵ-δ𝗋𝖺𝗍(r)(11.3.10)
(𝗅𝗂𝗆(x)ϵ𝗅𝗂𝗆(y)):(δ,η:+).xδϵ-δ-ηyη.(11.3.10)

Moreover, we have

(uϵv)(θ:+).(uϵ-θv)(11.3.10)
(uϵv)(vδw)(uϵ+δw)(11.3.10)
(uϵv)(vδw)(uϵ+δw).(11.3.10)

The additional conditions (11.3.10)–(11.3.10) turn out to be required in order to make the inductive definition go through.Condition (11.3.10) is called being rounded.Reading it from right to left gives monotonicity of ,

(δ<ϵ)(uδv)(uϵv)

while reading it left to right to openness of ,

(uϵv)(ϵ:+).(δ<ϵ)(uδv).

Conditions (11.3.10) and (11.3.10) are forms of the triangle inequalityMathworldMathworldPlanetmath, which say that is a “module” over on both sides.

Proof.

We will define :𝖼𝖼+𝖯𝗋𝗈𝗉 by double (𝖼,)-recursion.First we will apply (𝖼,)-recursion with codomain the subset of 𝖼+𝖯𝗋𝗈𝗉 consisting of those families of predicatesMathworldPlanetmath which are rounded and satisfy the one appropriate form of the triangle inequality.Thinking of these predicates as half of a binary relation, we will write them as (u,ϵ)(ϵu), with the symbol referring to the whole relation.Now we can write A precisely as

A:{:𝖼+𝖯𝗋𝗈𝗉|((u:𝖼).(ϵ:+).((ϵu)(θ:+).(ϵ-θu)))((u,v:𝖼).(η,ϵ:+).(uϵv)((ηu)(η+ϵv))((ηv)(η+ϵu)))}

As usual with subsets, we will use the same notation for an inhabitant of A and its first component .As the family of relations required for (𝖼,)-recursion, we consider the following, which will ensure the other form of the triangle inequality:

(ϵ):(u:𝖼).(η:+).((ηu)(ϵ+ηu))((ηu)(ϵ+ηu)).

We observe that these relations are separated.For assuming(ϵ:+).(ϵ),to show = it suffices to show (ϵu)(ϵu) for all u:𝖼.But ϵu implies ϵ-θu for some θ, by roundedness, which together with ϵ implies ϵu; and the converseMathworldPlanetmath is identical.

Now the first two data the recursion principle requires are the following.

  • For any q:, we must give an element of A, which we denote (𝗋𝖺𝗍(q)()).

  • For any Cauchy approximation x, if we assume defined a function +A, which we will denote by ϵ(xϵ()), with the property that

    (u:𝖼).(δ,ϵ,η:+).(xδηu)(xϵη+δ+ϵu),(11.3.11)

    we must give an element of A, which we write as (𝗅𝗂𝗆(x)()).

In both cases, we give the required definition by using a nested (𝖼,)-recursion, with codomain the subset of +𝖯𝗋𝗈𝗉 consisting of rounded families of mere propositions.Thinking of these propositionsPlanetmathPlanetmathPlanetmath as zero halves of a binary relation, we will write them as ϵ(ϵ), with the symbol referring to the whole family.Now we can write the codomain of these inner recursions precisely as

C:{:+𝖯𝗋𝗈𝗉|(ϵ:+).((ϵ)(θ:+).(ϵ-θ))}

We take the required family of relations to be the remnant of the triangle inequality:

(ϵ):(η:+).((η)(ϵ+η))((η)(ϵ+η)).

These relations are separated by the same argumentMathworldPlanetmath as for , using roundedness of all elements of C.

Note that if such an inner recursion succeeds, it will yield a family of predicates :𝖼+𝖯𝗋𝗈𝗉 which are rounded(since their image in +𝖯𝗋𝗈𝗉 lies in C) and satisfy

(u,v:𝖼).(ϵ:+).(uϵv)((()u)ϵ(()u)).

Expanding out the definition of , this yields precisely the third condition for to belong to A; thus it is exactly what we need.

It is at this point that we can give the definitions (11.3.10)–(11.3.10), as the first two clauses of each of the two inner recursions, corresponding to rational points and limits.In each case, we must verify that the relation is rounded and hence lies in C.In the rational-rational case (11.3.10) this is clear, while in the other cases it follows from an inductive hypothesis.(In (11.3.10) the relevant inductive hypothesis is that (𝗋𝖺𝗍(q)()yδ):C, while in (11.3.10) and (11.3.10) it is that (xδ()):A.)

The remaining data of the sub-recursions consist of showing that (11.3.10)–(11.3.10) satisfy the triangle inequality on the right with respect to the constructors of .There are eight cases — four in each sub-recursion — corresponding to the eight possible ways that u, v, and w in (11.3.10) can be chosen to be rational points or limits.First we consider the cases when u is 𝗋𝖺𝗍(q).

  1. 1.

    Assuming 𝗋𝖺𝗍(q)ϕ𝗋𝖺𝗍(r) and -ϵ<|r-s|<ϵ, we must show 𝗋𝖺𝗍(q)ϕ+ϵ𝗋𝖺𝗍(s).But by definition of , this reduces to the triangle inequality for rational numbers.

  2. 2.

    We assume ϕ,ϵ,δ:+ such that 𝗋𝖺𝗍(q)ϕ𝗋𝖺𝗍(r) and 𝗋𝖺𝗍(r)ϵ-δyδ, and inductively that

    (ψ:+).(𝗋𝖺𝗍(q)ψ𝗋𝖺𝗍(r))(𝗋𝖺𝗍(q)ψ+ϵ-δyδ).(11.3.12)

    We assume also that ψ,δ(𝗋𝖺𝗍(q)ψyδ) is a Cauchy approximation with respect to , i.e.

    (ψ,ξ,ζ:+).(𝗋𝖺𝗍(q)ψyξ)(𝗋𝖺𝗍(q)ψ+ξ+ζyζ),(11.3.13)

    although we do not need this assumption in this case.Indeed, (11.3.12) with ψ:ϕ yields immediately 𝗋𝖺𝗍(q)ϕ+ϵ-δyδ, and hence 𝗋𝖺𝗍(q)ϕ+ϵ𝗅𝗂𝗆(y) by definition of .

  3. 3.

    We assume ϕ,ϵ,δ:+ such that 𝗋𝖺𝗍(q)ϕ𝗅𝗂𝗆(y) and yδϵ-δ𝗋𝖺𝗍(r), and inductively that

    (ψ:+).(𝗋𝖺𝗍(q)ψyδ)(𝗋𝖺𝗍(q)ψ+ϵ-δ𝗋𝖺𝗍(r)).(11.3.14)
    (ψ,ξ,ζ:+).(𝗋𝖺𝗍(q)ψyξ)(𝗋𝖺𝗍(q)ψ+ξ+ζyζ).(11.3.14)

    By definition, 𝗋𝖺𝗍(q)ϕ𝗅𝗂𝗆(y) means that we have θ:+ with 𝗋𝖺𝗍(q)ϕ-θyθ.By assumption (11.3.14), therefore, we have also 𝗋𝖺𝗍(q)ϕ+δyδ, and then by (11.3.14) it follows that 𝗋𝖺𝗍(q)ϕ+ϵ𝗋𝖺𝗍(r), as desired.

  4. 4.

    We assume ϕ,ϵ,δ,η:+ such that 𝗋𝖺𝗍(q)ϕ𝗅𝗂𝗆(y) and yδϵ-δ-ηzη, and inductively that

    (ψ:+).(𝗋𝖺𝗍(q)ψyδ)(𝗋𝖺𝗍(q)ψ+ϵ-δ-ηzη),(11.3.14)
    (ψ,ξ,ζ:+).(𝗋𝖺𝗍(q)ψyξ)(𝗋𝖺𝗍(q)ψ+ξ+ζyζ),(11.3.14)
    (ψ,ξ,ζ:+).(𝗋𝖺𝗍(q)ψzξ)(𝗋𝖺𝗍(q)ψ+ξ+ζzζ).(11.3.14)

    Again, 𝗋𝖺𝗍(q)ϕ𝗅𝗂𝗆(y) means we have ξ:+ with 𝗋𝖺𝗍(q)ϕ-ξyξ, while (11.3.14) then implies 𝗋𝖺𝗍(q)ϕ+δyδ and (11.3.14) implies 𝗋𝖺𝗍(q)ϕ+ϵ-ηzη.But by definition of , this implies 𝗋𝖺𝗍(q)ϕ+ϵ𝗅𝗂𝗆(z) as desired.

Now we move on to the cases when u is 𝗅𝗂𝗆(x), with x a Cauchy approximation.In this case, the ambient inductive hypothesis of the definition of (𝗅𝗂𝗆(x)()):A is that we have (xδ()):A, so that in addition to being rounded they satisfy the triangle inequality on the right.

  1. 5.

    Assuming 𝗅𝗂𝗆(x)ϕ𝗋𝖺𝗍(r) and -ϵ<|r-s|<ϵ, we must show 𝗅𝗂𝗆(x)ϕ+ϵ𝗋𝖺𝗍(s).By definition of , the former means xδϕ-δ𝗋𝖺𝗍(r), so that above triangle inequality implies xδϵ+ϕ-δ𝗋𝖺𝗍(s), hence 𝗅𝗂𝗆(x)ϕ+ϵ𝗋𝖺𝗍(s) as desired.

  2. 6.

    We assume ϕ,ϵ,δ:+ such that 𝗅𝗂𝗆(x)ϕ𝗋𝖺𝗍(r) and 𝗋𝖺𝗍(r)ϵ-δyδ, and two unneeded inductive hypotheses.By definition, we have η:+ such that xηϕ-η𝗋𝖺𝗍(r), so the inductive triangle inequality gives xηϕ+ϵ-η-δyδ.The definition of then immediately yields 𝗅𝗂𝗆(x)ϕ+ϵ𝗅𝗂𝗆(y).

  3. 7.

    We assume ϕ,ϵ,δ:+ such that 𝗅𝗂𝗆(x)ϕ𝗅𝗂𝗆(y) and yδϵ-δ𝗋𝖺𝗍(r), and two unneeded inductive hypotheses.By definition we have ξ,θ:+ such that xξϕ-ξ-θyθ.Since y is a Cauchy approximation, we have yθθ+δyδ, so the inductive triangle inequality gives xξϕ+δ-ξyδ and then xξϕ+ϵ-ξ𝗋𝖺𝗍(r).The definition of then gives 𝗅𝗂𝗆(x)ϕ+ϵ𝗋𝖺𝗍(r), as desired.

  4. 8.

    Finally, we assume ϕ,ϵ,δ,η:+ such that 𝗅𝗂𝗆(x)ϕ𝗅𝗂𝗆(y) and yδϵ-δ-ηzη.Then as before we have ξ,θ:+ with xξϕ-ξ-θyθ, and two applications of the triangle inequality suffices as before.

This completes the two inner recursions, and thus the definitions of the families of relations (𝗋𝖺𝗍(q)()) and (𝗅𝗂𝗆(x)()).Since all are elements of A, they are rounded and satisfy the triangle inequality on the right with respect to .What remains is to verify the conditions relating to , which is to say that these relations satisfy the triangle inequality on the left with respect to the constructors of .The four cases correspond to the four choices of rational or limit points for u and v in (11.3.10), and since they are all mere propositions, we may apply 𝖼-induction and assume that w is also either rational or a limit.This yields another eight cases, whose proofs are essentially identical to those just given; so we will not subject the reader to them.∎

We can now prove:

Theorem 11.3.14.

For any u,v:Rc and ϵ:Q+ we have (uϵv)=(uϵv).

Proof.

Since both are mere propositions, it suffices to prove bidirectional implication.For the left-to-right direction, we use -induction applied to C(u,v,ϵ):(uϵv).Thus, it suffices to consider the four constructors of .In each case, u and v are specialized to either rational points or limits, so that the definition of evaluates, and the inductive hypothesis always applies.

For the right-to-left direction, we use 𝖼-induction to assume that u and v are rational points or limits, allowing to evaluate.But now the definitions of , and the inductive hypotheses, supply exactly the data required for the relevant constructors of .∎

Stretching a point, one might call a fibrationMathworldPlanetmath of “codes” for , with the two directions of the above proof being 𝖾𝗇𝖼𝗈𝖽𝖾 and 𝖽𝖾𝖼𝗈𝖽𝖾 respectively.By the definition of , from \\autorefthm:RC-sim-characterization we get equivalences

(𝗋𝖺𝗍(q)ϵ𝗋𝖺𝗍(r))=(-ϵ<q-r<ϵ)
(𝗋𝖺𝗍(q)ϵ𝗅𝗂𝗆(y))=(δ:+).𝗋𝖺𝗍(q)ϵ-δyδ
(𝗅𝗂𝗆(x)ϵ𝗋𝖺𝗍(r))=(δ:+).xδϵ-δ𝗋𝖺𝗍(r)
(𝗅𝗂𝗆(x)ϵ𝗅𝗂𝗆(y))=(δ,η:+).xδϵ-δ-ηyη.

Our proof also provides the following additional information.

Corollary 11.3.15.

is rounded and satisfies the triangle inequality:

(uϵv)(θ:+).uϵ-θv(11.3.15)
(uϵv)(vδw)(uϵ+δw).(11.3.15)

With the triangle inequality in hand, we can show that “limits” of Cauchy approximations actually behave like limits.

Lemma 11.3.16.

For any u:Rc, Cauchy approximation y, and ϵ,δ:Q+, if uϵyδ then uϵ+δlim(y).

Proof.

We use 𝖼-induction on u.If u is 𝗋𝖺𝗍(q), then this is exactly the second constructor of .Now suppose u is 𝗅𝗂𝗆(x), and that each xη has the property that for any y,ϵ,δ, if xηϵyδ then xηϵ+δ𝗅𝗂𝗆(y).In particular, taking y:x and δ:η in this assumption, we conclude that xηη+θ𝗅𝗂𝗆(x) for any η,θ:+.

Now let y,ϵ,δ be arbitrary and assume 𝗅𝗂𝗆(x)ϵyδ.By roundedness, there is a θ such that 𝗅𝗂𝗆(x)ϵ-θyδ.Then by the above observation, for any η we have xηη+θ/2𝗅𝗂𝗆(x), and hence xηϵ+η-θ/2yδ by the triangle inequality.Hence, the fourth constructor of yields 𝗅𝗂𝗆(x)ϵ+2η+δ-θ/2𝗅𝗂𝗆(y).Thus, if we choose η:θ/4, the result follows.∎

Lemma 11.3.17.

For any Cauchy approximation y and any δ,η:Q+ we have yδδ+ηlim(y).

Proof.

Take u:yδ and ϵ:η in the previous lemma.∎

Remark 11.3.18.

We might have expected to have yδδlim(y), but this fails in examples.For instance, consider x defined by xϵ:ϵ.Its limit is clearly 0, but we do not have |ϵ-0|<ϵ, only .

As an application, \\autorefthm:RC-sim-lim-term enables us to show that the extensionsPlanetmathPlanetmath of Lipschitz functions from \\autorefRC-extend-Q-Lipschitz are unique.

Lemma 11.3.19.

Let f,g:RcRc be continuous, in the sense that

(u:𝖼).(ϵ:+).(δ:+).(v:𝖼).(uδv)(f(u)ϵf(v))

and analogously for g.If f(rat(q))=g(rat(q)) for all q:Q, then f=g.

Proof.

We prove f(u)=g(u) for all u by 𝖼-induction.The rational case is just the hypothesis.Thus, suppose f(xδ)=g(xδ) for all δ.We will show that f(𝗅𝗂𝗆(x))ϵg(𝗅𝗂𝗆(x)) for all ϵ, so that the path constructor of 𝖼 applies.

Since f and g are continuous, there exist θ,η such that for all v, we have

(𝗅𝗂𝗆(x)θv)(f(𝗅𝗂𝗆(x))ϵ/2f(v))
(𝗅𝗂𝗆(x)ηv)(g(𝗅𝗂𝗆(x))ϵ/2g(v)).

Choosing δ<min(θ,η), by \\autorefthm:RC-sim-lim-term we have both 𝗅𝗂𝗆(x)θyδ and 𝗅𝗂𝗆(x)ηyδ.Hence

f(𝗅𝗂𝗆(x))ϵ/2f(yδ)=g(yδ)ϵ/2g(𝗅𝗂𝗆(x))

and thus f(𝗅𝗂𝗆(x))ϵg(𝗅𝗂𝗆(x)) by the triangle inequality.∎

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 1:05:45