proof of equivalence of definitions of valuation


We will start with a lemma:

Lemma Let || be a valuationMathworldPlanetmath according to the definition of the parent entry with constant C2. Then |i=1nxi|2nmaxi=1n|xi|.

Proof:   We will start with the case where n is a power of two: n=2r We shall prove that |i=12rxi|2rmaxi=1n|xi| by induction. The assertion is certainly true when n=2 by hypothesis. Assume that it also holds when n=2r-1. Then we have

|i=1nxi|=|i=12r-1xi+i=2r-1+12rxi|22r-1maxi=12r-1|xi|+22r-1maxi=2r-1+12r|xi|22rmaxi=12r|xi|

To deal with the case where n is not a power of two, we shall pad the sum with zeros. That is to say, we shall define xi=0 when i>n. Let r be the greatest integer such that 2rn. Then 2n>2r and we have

|i=1nxi|=|i=12rxi|2rmaxi=12r|xi|2nmaxi=1n|xi|

Q.E.D.

Corollary Let || be a valuation according to the definition of the parent entry with constant C2. Then, if n is a positive integer, |n|<2n.

Proof:   Write n=i=1n1. Then, by the lemma,

|n|=|i=1n1|<2n|1|

However, since || is a valuation |1|0 since 10 and |1|=|1||1| so |1|=1, hence

|n|2n.

Q.E.D.

Having established this lemma, we will now use it to prove the main theorem:

Theorem If || is a valuation according to the definition of the parent entry with constant C2, then || satisfies the identity

|x+y||x|+|y|.

Proof:   Let n be a positive integer. Then we have

|x+y|n=|(x+y)n|=|m=0n(nm)xmyn-m|

Using the lemma, we can bound this:

|x+y|n2(n+1)maxm=0n|(nm)xmyn-m|

Using the corollary to the lemma, we can bound the binomial coefficientMathworldPlanetmath to obtain

|x+y|n4(n+1)maxm=0n(nm)|x|m|y|n-m

Using the obvious inequalityMathworldPlanetmath

maxm=0n(nm)|x|m|y|n-mm=0n(nm)|x|m|y|n-m,

we obtain

|x+y|nm=0n4(n+1)(nm)|x|m|y|n-m=4(n+1)(|x|+|y|)n.

If either x=0 or y=0, then the theorem to be proven is trivial. If not, then |x|+|y|0 and we can divide by (|x|+|y|)n to obtain

(|x+y||x|+|y|)n4(n+1)

By the theorem on the growth of exponential function, it follows that this inequality could not hold for all n unless

|x+y||x|+|y|1,

in other word, unless |x+y||x|+|y|.

Q.E.D.

Title proof of equivalence of definitions of valuation
Canonical name ProofOfEquivalenceOfDefinitionsOfValuation
Date of creation 2013-03-22 14:56:00
Last modified on 2013-03-22 14:56:00
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 12
Author rspuzio (6075)
Entry type Proof
Classification msc 11R99
Classification msc 12J20
Classification msc 13A18
Classification msc 13F30