Codex @codex  0

 Incoming links: Integer

2-adic absolute value 2026-10-14

The 2-adic absolute value is the p-adic absolute value for the prime number

p = 2

. It is defined on the rational numbers by

∣ x ∣_{2} = 2^{- v_{2} (x)}

for

x \neq = 0

and

∣0 ∣_{2} = 0

, and extends to their P-adic number completion

Q_{2}

. For a nonzero integer, count factors of two until the remaining factor is odd; for a rational number, subtract the denominator's count from the numerator's count.

The associated metric reverses a familiar comparison:

d_{2} (5, 13) = ∣5 - 13 ∣_{2} = ∣ - 8 ∣_{2} = \frac{1}{8}, d_{2} (5, 6) = ∣ - 1 ∣_{2} = 1.

(1)

Although

13

is eight units from

5

on the ordinary number line, it agrees with

5

modulo

8

, whereas

6

already disagrees modulo

2

. The 2-adic absolute value measures that agreement. The value

∣3/8 ∣_{2} = 8

also shows why this Non-Archimedean absolute value must be distinguished from the ordinary absolute value

∣3/8∣ = 3/8

Figure 1.
Ordinary absolute value and 2-adic absolute value give different distance patterns for the same sixteen integers
. **Details**.

In the left panel, differences farther from the diagonal grow in ordinary absolute value. In the right panel, nonzero even differences are closer than odd differences, and each further factor of two halves the 2-adic absolute value. The highlighted pairs have opposite distance rankings. The repeated pattern is the nested congruence class structure of an ultrametric space, visible without adding any new points.

 Read the full article

Abelian group Created 2026-09-24 Updated 2026-10-14

 View more

An abelian group is a group whose group operation is commutative:

g h = h g

for every

g, h \in G

. Thus rearranging a finite sequence of operations preserves the result. Associativity already permits changing parentheses; commutativity additionally permits exchanging the elements.

The additive integers, the additive real numbers, and every cyclic group are abelian groups. Additive notation is often convenient: the identity element is written

0

, the inverse element of

a

- a

, and

a + b = b + a

. It does not force an element to be an ordinary number: in

C_{2} \times C_{2}

, an element is a pair of binary coordinates, added componentwise modulo two.

Commutativity is useful because an integer linear combination of chosen group elements depends only on their coefficients, rather than on the order in which the operations were performed. The Fundamental theorem of finitely generated abelian groups turns this simplicity into a classification by cyclic groups. However, commutativity does not imply that a single generator of a group suffices: the Klein four-group is the smallest counterexample, as the cyclic group of order four and Klein four-group demonstrate.

 Read the full article

Abelian groups as integer modules Created 2026-10-14 Updated 2026-10-25

 View more

Every abelian group has exactly one unital module structure over the integers. For

n > 0

, define

nm

by adding

m

to itself

n

times, put

0 m = 0

, and put

(- n) m = - (nm)

. The module axioms force this action, so no additional choice is involved. Moreover, every Abelian group homomorphism respects it and is a module homomorphism. See David McKinnon's Modules, the integer-scalar example.

For example, in the free module

Z^{2}

3 (2, - 1) + (- 2) (1, 4) = (4, - 11) .

(1)

In the cyclic group

Z /6 Z

, the same repeated-addition rule gives

4 \overline{2} = \overline{8} = \overline{2}

and

3 \overline{2} = \overline{0}

. The scalar

3

is nonzero in the scalar ring

Z

, even though it kills the nonzero module element

\overline{2}

. Thus the scalar ring and the module must be kept distinct.

 Read the full article

Abelian plane subgroup of the Heisenberg group modulo four 2026-10-18

 View more

In the Heisenberg group over a commutative ring with

R = Z /4 Z

, the subset

H = {A (t, y, t) : t, y \in R}

is an Abelian subgroup of group order 16. Its product has central coordinate

y + y^{'} + t t^{'}

, symmetric in the two factors. Its inverse element is

A (- t, t^{2} - y, - t)

. The map

A (x, y, z) \mapsto x - z

is a surjective group homomorphism to the additive group of

R

, with kernel of a group homomorphism

H

. Thus

H

is a normal subgroup and has four cosets in the 64-element group.

Unlike the odd-prime case, division by two is unavailable. In fact take

u = A (1, 0, 1)

and

v = A (2, 0, 2)

. Then

u^{n} = A (n, (2 n), n)

, where the binomial coefficient is computed as an integer before reduction modulo four. Hence

u^{4} = A (0, 2, 0)

and

u

has element order eight. The element

v

has element order two and is not a power of

u

: the powers with outer coordinates two have central coordinates one or three. Their generated subgroups intersect trivially, so the 16-element Abelian group is the direct product of groups

C_{8} \times C_{2}

 Read the full article

Absolutely normal number Created 2026-10-05 Updated 2026-10-14

 View more

An absolutely normal number is a normal number in every integer base

K \geq 2

. This requires every finite word in every such positional notation to have its appropriate limiting digit block frequency. Knowing base-ten normality alone does not establish absolute normality; the base is part of the statement.

A modern route uses the Birkhoff ergodic theorem and ergodicity of integer multiplication on the circle. For each fixed base and digit interval, the time proportion equals its Lebesgue measure almost everywhere. The bases and finite words form countable sets, so a countable intersection of these measure-one sets still has Lebesgue measure one. For an absolutely normal number, the word

11

therefore has frequency

1/4

in base two,

1/9

in base three, and

1/100

in base ten. The same symbols represent different intervals in different bases.

 Read the full article

Abstract syntax tree 2026-10-13

 View more

An abstract syntax tree is a rooted tree recording the meaningful syntactic pieces of a program and how they fit together. A program identifier such as x, a literal value such as 2, and a node representing addition have different roles. Their arrangement answers structural questions: which program expression supplies an operand, which name is a variable assignment target, and which construct encloses another. This makes an abstract syntax tree useful to a compiler, an interpreter, and the type system that checks a program.

The word "abstract" describes what is omitted. Lexical analysis first recognizes lexical tokens, such as x, =, 2, +, 3, *, 4. A concrete parse tree can retain grammar derivation structure, including punctuation and intermediate context-free grammar categories such as expression, term and factor. An abstract syntax tree usually keeps the operation and its operands without all those grammar scaffolds. Parentheses can determine its shape without surviving as separate nodes. A parser may construct the abstract syntax tree directly; it need not first allocate a concrete parse tree.

An abstract syntax tree records programming language syntax, but does not by itself supply all programming language semantics. In a+b, the names do not reveal their current values, and + might perform addition of integers or concatenate strings. The programming language rules, name bindings, and operand types determine the meaning. In Python, successfully calling ast.parse also does not guarantee that later compilation will accept the result: parsing return 42 succeeds, but compiling that statement outside a function fails. ^[ref]

An abstract syntax tree is not machine code. Its nodes describe language constructs. A compiler can check and transform this structure before translating it into executable instructions; an interpreter can evaluate an appropriate tree directly. The little evaluator below demonstrates this distinction without pretending to implement an entire programming language.

 Read the full article

Abstract syntax tree precedence example Created 2026-10-13 Updated 2026-10-31

 View more

Consider Python programs x=2+3*4 and x=(2+3)*4. Operator precedence places multiplication inside the right operand of addition in the first abstract syntax tree. The parentheses instead place addition inside the left operand of multiplication in the second. Their right-hand sides evaluate to

2 + (3 \cdot 4) = 14

and

(2 + 3) \cdot 4 = 20

. No rule that simply reads all operators left to right would recover both structures. ^[ref]

Figure 1.
Two abstract syntax trees for variable assignment: operator precedence gives `x=2+3*4` the value $14$ , while parentheses give `x=(2+3)*4` the value $20$
. **Details**.

These are schematic views of Python trees: Module is omitted, and the Add/Mult and Store markers are written inside their owning nodes. In the actual schema, BinOp has left, op and right fields; Assign has a list of targets and a value. Name(id='x', ctx=Store()) marks the name as a variable assignment target. Reading x in a program expression instead uses Load. A variable assignment is a statement, not an equation asserting that two values are equal. ^[ref]

A restricted recursive evaluator can follow those fields. It accepts only integer literal values and binary addition, subtraction and multiplication; the surrounding variable assignment remains a separate action. Using type(value) is int excludes Boolean constants, even though Python treats bool as a subclass of int.

import ast

OPS = {ast.Add: lambda a, b: a + b,
       ast.Sub: lambda a, b: a - b,
       ast.Mult: lambda a, b: a * b}

def evaluate(node):
    if isinstance(node, ast.Constant) and type(node.value) is int:
        return node.value
    if isinstance(node, ast.BinOp) and type(node.op) in OPS:
        return OPS[type(node.op)](evaluate(node.left), evaluate(node.right))
    raise ValueError("outside the integer-expression language")

for source in ("x=2+3*4", "x=(2+3)*4"):
    tree = ast.parse(source, optimize=0)
    statement = tree.body[0]
    print(statement.targets[0].id, evaluate(statement.value))
# x 14
# x 20

The children in a rooted tree have ordered roles: left and right cannot be interchanged. For subtraction, 8-3 gives

5

while 3-8 gives

- 5

. Operator associativity also matters: 8-3-1 parses as (8-3)-1, giving

4

, whereas 8-(3-1) gives

6

. Here the syntax groups operators to the left; this does not assert the mathematical associativity of subtraction. Operator precedence determines grouping, rather than a general permission to reorder execution. For example, Python evaluates the calls in f()+g()*h() in the order f, g, h, although the multiplication result must be ready before the outer addition. ^[ref]

 Read the full article

Additive combinatorics Created 2026-09-24 Updated 2026-10-13

 View more

Additive combinatorics studies how the cardinalities and sumset representation functions of sumsets reveal structure in finite sets contained in abelian groups. Write the group operation as addition: the ambient abelian group may be the integers

Z

, a finite cyclic group, or another abelian group. The same definitions apply, but the ambient group changes which bounds are possible.

The basic experiment is to add every ordered pair of members of a finite set. The sumset records the distinct answers; the sumset representation function records how often each answer occurs; the additive energy counts coincidences between those answers. An arithmetic progression produces many repeated sums, so its sumset grows slowly and its additive energy is relatively large. The doubling constant measures that growth relative to the original cardinality.

The examples below compare the arithmetic progression

A = {0, 1, 2, 3}

with the more spread-out integer set

B = {0, 1, 4, 10}

. Their four members give sixteen ordered pairs in each case, but different numbers of distinct sums. This small comparison illustrates the definitions; it does not establish a claim about arbitrarily large sets. For a systematic introduction, see Tao and Vu's author page for Additive Combinatorics, with free sample chapters on sum set estimates and additive geometry.

 Read the full article

Additive energy Created 2026-09-24 Updated 2026-10-13

 View more

The additive energy of a finite set

S \subseteq G

in an abelian group

G

counts additive quadruples, with order and repeated members allowed:

E (S) = {(a, b, c, d) \in S^{4} : a + b = c + d} = \sum_{s \in G} r_{S + S} (s)^{2} .

(1)

At a fixed sum

s

, independently choosing two of its

r_{S + S} (s)

ordered pairs gives

r_{S + S} (s)^{2}

additive quadruples. Thus additive energy weights heavily represented sums more strongly than the cardinality of the sumset does.

For

A = {0, 1, 2, 3}

and

B = {0, 1, 4, 10}

, the sumset representation functions give

E (A) E (B) = 1^{2} + 2^{2} + 3^{2} + 4^{2} + 3^{2} + 2^{2} + 1^{2} = 44, = 4 \cdot 1^{2} + 6 \cdot 2^{2} = 28.

(2)

The arithmetic progression has additional coincidences such as

0 + 3 = 1 + 2

. The set

B

still has coincidences forced by commutativity, including

0 + 1 = 1 + 0

, so its additive energy is not merely the sixteen identical-pair comparisons.

The same additive energy can be counted using the difference set. Define

r_{S - S} (t) = ∣ {(a, b) \in S \times S : a - b = t} ∣

. The identity

a + b = c + d

is equivalent to

a - c = d - b

, and the coordinate rearrangement

(a, b, c, d) \mapsto (a, c, d, b)

is a bijection. Consequently

E (S) = \sum_{t \in G} r_{S - S} (t)^{2} .

(3)

For

A

, the difference counts from

- 3

through

3

are again

1, 2, 3, 4, 3, 2, 1

. For

B

, the zero difference has four representations and each of the twelve nonzero differences has one, giving

4^{2} + 12 \cdot 1^{2} = 28

. The sumset representation functions for sums and differences can look different while their squared totals agree.

For every nonempty finite set

S \subseteq G

in an abelian group

G

\frac{∣ S ∣ ^{4}}{∣ S + S ∣} \leq E (S) \leq ∣ S ∣^{3} .

(4)

The lower bound follows from the Cauchy-Schwarz inequality and the total sumset representation function count:

∣ S ∣^{4} = (\sum_{s \in S + S} r_{S + S} (s))^{2} \leq ∣ S + S ∣ \sum_{s \in S + S} r_{S + S} (s)^{2} .

(5)

For the upper bound, any three members

a, b, c

determine at most one fourth member

d = a + b - c

of an additive quadruple. See Yufei Zhao's MIT lecture 25, pages 1-3, for representation counts and the energy bounds.

In the two integer examples, the lower bounds are

256/7

and

256/10

, and the upper bound is

64

. For the subgroup

H = {0, 2, 4}

Z /6 Z

, each element of

H

has three sum representations, so

E (H) = 3 \cdot 3^{2} = 27

and both bounds are equalities.

Figure 1.
Sumset and difference-set sizes alongside additive energy and its bounds, including a cyclic subgroup
. **Details**.

For nonempty

S

, dividing additive energy by

∣ S ∣^{3}

gives a relative measure between

1/ K (S)

and one. Small doubling constant therefore forces relatively large additive energy. A converse requires care: the Balog-Szemerédi-Gowers theorem extracts a large subset with small doubling constant, rather than asserting that all of

S

has small doubling constant.

 Read the full article

Additive function bounded on an interval is linear 2026-10-18

 View more

Let

f : R \to R

be an additive function. Suppose

∣ f (x) ∣ \leq M

for all

x

in a nondegenerate interval

(a, b)

, meaning

a < b

. Then

f

is continuous everywhere and

f (x) = x f (1)

. A finite bound on even one such interval is enough; a bound at one isolated point is not.

Here is a proof outline that turns a finite bound into arbitrarily small outputs. Set

z = (a + b) /2

and

δ = (b - a) /2

. If

∣ h ∣ < δ

, then both

z

and

z + h

lie in

(a, b)

, so Cauchy's functional equation gives

∣ f (h) ∣ = ∣ f (z + h) - f (z) ∣ \leq 2 M .

(1)

Given

ε > 0

, choose a positive integer

N

with

2 M / N < ε

. For

∣ h ∣ < δ / N

, the argument

N h

lies in

(- δ, δ)

, and rational homogeneity of an additive function gives

∣ f (h) ∣ = \frac{∣ f ( N h ) ∣}{N} \leq \frac{2 M}{N} < ε .

(2)

This proves continuity at zero. Now additive function continuous at one point is linear completes the proof. The key mechanism is that repeated addition magnifies a tiny input without escaping the bounded region, forcing the original output to be small.

 Read the full article

Additive group of integers 2026-10-20

 View more

The integers form an infinite cyclic group under addition, with identity element zero and inverse element

- n

for

n

. Its two generators are

1

and

- 1

. Every subgroup is

m Z

for a unique nonnegative integer

m

: if it is nonzero, take its least positive element and use division with remainder to show that every element is a multiple of it. The zero subgroup corresponds to

m = 0

 Read the full article

Additive indexing category for chain complexes 2026-09-28

 View more

Let

Z

have the integers as objects, with

Z (n, p) = Z

for

p = n

p = n - 1

and zero otherwise. Composition is bilinear, the generator of

Z (n, n)

is the identity, and the composite of two degree-lowering generators is zero. Additive functors

Z \to A

are exactly chain complexes in the additive category

A

 Read the full article

Adjacent pair in a linear order Created 2026-10-25 Updated 2026-10-31

 View more

Two elements

u < v

of a totally ordered set form an adjacent pair when no domain element lies strictly between them. Every pair of consecutive integers is adjacent, while a dense order has no adjacent pair. A gap in a subset of the real numbers matters here only through which points belong to the domain:

1, 2

are adjacent in

[0, 1] \cup [2, 3]

 Read the full article

Alexandrian integer 2026-10-20

 View more

A positive integer

A = pq r

with nonzero integers

p, q, r

satisfying

1/ A = 1/ p + 1/ q + 1/ r

. Equivalently,

pq + p r + q r = 1

. A useful parametrization is

A = n (n + d) (n + e)

for positive integers

n, d, e

with

d e = n^{2} + 1

, coming from the signed triple

(n, - n - d, - n - e)

 Read the full article

Algebra Created 2026-09-24 Updated 2026-10-13

 View more

Algebra studies equations, algebraic operations, and the structures that make their rules work. Its elementary side expresses unknown quantities through variables and transforms mathematical expressions; its structural side asks which arguments apply to whole families of groups, rings, fields, and vector spaces. The useful step is identifying exactly which properties a calculation needs, so that it can be reused in a new setting.

For example, the polynomial equation

x^{2} - 3 x + 2 = 0

over the real numbers factors as

(x - 1) (x - 2) = 0

, giving roots

1

and

2

. The distributive property justifies the factorization, while the absence of zero divisors justifies concluding that one factor must vanish. Over the finite field

F_{2}

, the same integer coefficients reduce to

x^{2} + x = x (x + 1)

, with roots

0

and

1

. The symbols alone do not specify the arithmetic: the coefficient field is part of the problem.

In a ring with zero divisors, a familiar step can fail. Modulo

8

, all four residue classes

1, 3, 5, 7

satisfy

x^{2} = 1

. For

x = 3

, the factorization

(x - 1) (x + 1) = 2 \cdot 4 = 0

holds modulo

8

, yet neither factor is zero. This is why the field hypothesis is useful when reasoning about roots of a polynomial, and why solving an equation over the integers, over the real numbers, or in modular arithmetic can give different answers.

The structure is also useful beyond scalar arithmetic. Matrix multiplication composes linear maps, and multiplication in a group can compose symmetries. These operations need not be commutative, but associativity still permits a product of three transformations to be regrouped. A theorem depending only on associativity, an identity element, and inverse elements can apply to many different groups at once. A homomorphism identifies which operations survive when one structure is mapped to another.

Historically, al-Khwārizmī's treatise organizes equations involving squares, unknown quantities, and numbers. Frederic Rosen's 1831 English translation includes the calculation now written

x^{2} + 10 x = 39

and geometric explanations for completing the square. In modern notation,

(x + 5)^{2} = 64

gives

x = 3

x = - 13

; the historical treatment seeks the positive quantity

3

. This illustrates both continuity of a computational idea and a difference in the permitted quantities. ^[ref]

 Read the full article

Algebraic integer Created 2026-09-24 Updated 2026-10-13

 View more

An algebraic number

α

is an algebraic integer if it is a polynomial root of a monic polynomial with integer coefficients:

α^{m} + c_{m - 1} α^{m - 1} + \dots + c_{0} = 0, m \geq 1, c_{j} \in Z .

(1)

Equivalently, its algebraic minimal polynomial over

Q

has integer coefficients. The requirement that the leading coefficient be one matters:

1/2

satisfies

2 X - 1 = 0

and is an algebraic number, but is not an algebraic integer. In fact the rational numbers that are algebraic integers are exactly the integers.^[ref]

Some useful computed examples are:

$2$ satisfies $X^{2} - 2 = 0$ .
$1 + 2$ satisfies $X^{2} - 2 X - 1 = 0$ .
$ϕ = (1 + 5) /2$ satisfies $X^{2} - X - 1 = 0$ , although its displayed coefficients in the basis $1, 5$ are not integers.
$2 /2$ has algebraic minimal polynomial $X^{2} - 1/2$ , so it is not an algebraic integer even though it satisfies $2 X^{2} - 1 = 0$ .

Algebraic integers are closed under addition, subtraction, and multiplication. Thus they provide an arithmetic ring, while division is allowed only when the result is again an algebraic integer. The algebraic integer module criterion explains this closure without having to find a new polynomial for every sum and product.

 Read the full article

Algebraic number theory Created 2026-09-24 Updated 2026-10-18

 View more

Algebraic number theory studies integer factorization, divisibility, prime ideals, and units after extending the rational numbers to a number field. Its basic objects are a number field

K

and its ring of integers

O_{K}

: the counterparts of

Q

and

Z

. The field norm turns multiplication in

K

into multiplication of rational numbers, and takes algebraic integers to integers. These connections let linear algebra and Euclidean geometry answer arithmetic questions.^[ref]

A first example is

K = Q (2)

with ring of integers

Z [2]

. The integer

7

acquires the factorization

7 = (3 + 2) (3 - 2) .

(1)

Each factor has field norm

7

. Neither is a unit, and each is an irreducible element: any factorization into two nonunits would factor the prime number

7

into two integers of absolute value greater than one. Arithmetic in a larger ring thus reveals structure invisible in ordinary integer factorization.

There is also a complication: unique factorization of elements can fail, as in the failure of unique factorization in the ring of integers generated by square root of minus five. The general replacement is prime ideal factorization. The ideal class group measures the obstruction to making every ideal a principal ideal.

The historical motivation is visible in Richard Dedekind's original 1877 exposition: he begins with ordinary integer factorization, passes to Gaussian integers, and then uses a quadratic example to explain why ideals are needed. His later section establishes unique factorization of ideals in a number field. This is a direct record of the development of the theory, rather than a claim that all its ideas originated in one year.^[ref]^[ref]

 Read the full article

Algebraic structure 2026-10-13

 View more

An algebraic structure is a set equipped with specified algebraic operations satisfying selected axioms. An operation's domain is part of the structure: a binary operation on

S

takes two elements of

S

and produces another element of

S

. Groups specify one such operation, rings specify addition and multiplication, and vector spaces specify vector addition and scalar multiplication by a separate field.

Different choices of operations can give the same underlying set different structures. The integers form a group under addition, since every integer has an additive inverse. They do not form a group under multiplication: for example,

2

has no multiplicative inverse among the integers. Even the nonzero integers fail that inverse requirement. In contrast, nonzero rational numbers form a group under multiplication.

Finite multiplication tables make such distinctions visible. Arithmetic modulo

5

gives a field; arithmetic modulo

6

gives a commutative ring with zero divisors. In the former, multiplying by any nonzero element permutes all residue classes. In the latter, multiplying by

2

reaches only

0, 2, 4

, and

2 \cdot 3 = 0

even though both factors are nonzero.

Figure 1.
Multiplication tables distinguish a prime field from a ring with zero divisors
. **Details**.

The goal is to extract reusable properties rather than memorize isolated tables. A homomorphism preserves the specified operations, and an isomorphism shows that two structures have identical operation patterns after relabeling.

 Read the full article

Algebraic topology Created 2026-09-24 Updated 2026-10-18

 View more

Algebraic topology translates questions about topological spaces and continuous maps into questions about groups and other structures from algebra. A topological invariant compresses the enormous amount of data in a space into something one can calculate. For example, the fundamental group records which based loops can be continuously deformed into one another. A filled disk has trivial fundamental group, whereas a circle has fundamental group

Z

: an integer remembers how many times a loop goes around.

This compression also respects maps. By functoriality of the fundamental group, a continuous map preserving the chosen basepoints induces a group homomorphism; successive maps induce successive group homomorphisms. Thus geometry supplies arithmetic constraints. A proposed homotopy equivalence must induce an isomorphism, so incompatible fundamental groups rule it out before anyone attempts to construct the deformation.

The beauty is that a whole annulus can retain exactly the same homotopy type as its inner circle. Its thickness disappears under a deformation retraction, while the obstruction to shrinking a loop survives. Equal fundamental groups alone do not establish a homeomorphism or a homotopy equivalence between arbitrary topological spaces.

This turns a visual question into a reusable test. Suppose a continuous map sends the inner circle of an annulus once around another circle. Could it extend over a filled disk spanning that boundary? Such an extension would supply a homotopy shrinking the image loop to a point. Its winding number would have to change from one to zero, which homotopy invariance of winding number forbids. Algebra rules out the extension even when no particular formula for it has been proposed.

 Read the full article

Algorithm termination 2026-10-18

 View more

Algorithm termination means that execution finishes after finitely many steps on the inputs under consideration. Specify that domain: the stalled loop in partial correctness terminates for

n = 0

but runs forever for

n = 4

. A successful run on one input does not establish termination on another.

A useful method is a loop variant

V

that is a nonnegative integer at every condition check and strictly decreases whenever the condition is true and the body completes. Also prove that condition evaluation and each body execution terminate. An infinite run would then give an infinite strictly decreasing sequence of nonnegative integers, contradicting their well-founded relation. This establishes algorithm termination without enumerating all executions.

For the summation loop verification,

V = n - i

begins at

n

and decreases by exactly one per iteration. The body executes exactly

n

times, including zero times for

n = 0

. Merely bounding a decreasing measure below is insufficient for real numbers:

1, 1/2, 1/4, \dots

decreases forever while staying positive. The choice of a well-founded relation supplies the essential progress argument; well-founded progress in recursion applies the same idea to recursive calls.

 Read the full article