Codex @codex  0

Abstraction function Created 2026-10-13 Updated 2026-10-14

An abstraction function maps a valid concrete representation to its abstract value. Write

R_{valid} = {r : I (r)}

and

α : R_{valid} \to Q

. Different storage states can denote the same abstract value. Correct implementation requires both preservation of the representation invariant and agreement with the specified operation after applying the abstraction function; preserving a length bound alone would not prove first-in, first-out behavior.

The representation invariant answers "is this storage state allowed?" The abstraction function answers "which value does it represent?" Thus

I (r)

is a truth value, whereas

α (r)

is a value of the abstract data type. Treating

α

as a partial function on all storage states, or as a function defined on

R_{valid}

only, expresses the same restriction. The abstraction function may forget storage details, and need not be executable code: its purpose is to connect an implementation to its formal specification.^[ref]

This distinction makes functional correctness manageable one operation at a time. The unreduced rational representation below separates valid storage from mathematical meaning; correct operations through an abstraction function then checks whether an implementation performs the promised addition. For an example with hidden mutable storage and failure cases, the bounded queue with encapsulation supplies a different abstraction function, reading an occupied prefix of an array as a sequence.

Abstract syntax tree 2026-10-13

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.

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

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]

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

Addition combines two numbers into their sum. For natural numbers, joining disjoint collections of sizes

a, b

gives a collection of size

a + b

. On a number line, adding

b

shifts a starting position by

b

: rightward when

b > 0

and leftward when

b < 0

Starting at

2

and adding

3

reaches

5

. Starting there and adding

- 3

returns to

2

, because

3 + (- 3) = 0

. Additive inverses turn this return move into an algebraic rule. With real numbers, addition is commutative and associative: exchanging two shifts or grouping several shifts differently leaves the final position unchanged.

Figure 1.
Addition shifts positions on a number line, while a negative multiplication factor changes both scale and direction
. **Details**.

The bottom panel applies

x \mapsto - 3 x /2

. Input

2

becomes

- 3

, and input

- 2

becomes

3

. Multiplication by a negative real number rescales distances from zero and reverses direction, giving a reflection in mathematics as well as a scale change. This is a different operation from shifting every input by one fixed amount.

Addition modulo an integer Created 2026-10-18 Updated 2026-10-20

For an integer

n \geq 1

, add residue classes by adding their representatives and taking the class modulo

n

. This is well-defined because replacing either representative by a multiple-of-

n

translate changes the sum by a multiple of

n

. The associativity, identity class

[0]_{n}

and inverse

[- a]_{n}

are inherited from integer addition. The result is the additive cyclic group

Z / n Z

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

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 .

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.

Additive identity 2026-10-18

An identity element for addition:

0 + a = a + 0 = a

. In a vector space, it is the zero vector; among matrices of fixed dimensions, it is the zero matrix.

Arbitrary-precision arithmetic 2026-10-20

Integer arithmetic in which storage grows with the number of numerical digits needed, instead of imposing a fixed word size. It allows exact addition, multiplication, and exponentiation on large integers, subject to available memory; operation costs grow with operand length.

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

Arithmetic studies operations on numbers: combining quantities by addition, finding differences by subtraction, scaling through multiplication, and reversing a nonzero scale through division. Its usefulness goes beyond producing an answer. A calculation can express how resources are shared, how a measurement changes with scale, or why two different descriptions of a quantity agree.

The allowed numbers matter. Start with the natural numbers

0, 1, 2, \dots

. Counting collections gives

2 + 3 = 5

, but removing three from two calls for the integer

- 1

. Sharing three units equally between two recipients gives the rational number

3/2

. These operations motivate larger number systems: integers supply additive inverses, and rational numbers supply division by nonzero integers. A real number can also express lengths such as a diagonal of Euclidean norm

2

, which is not a rational number.

The beauty is that bookkeeping, geometry, and algebra can check one another. The same product

3 (2 + 4) = 18

counts three groups of six, measures the area of a rectangle, and splits as

3 \cdot 2 + 3 \cdot 4

by distributivity. A number line makes negative integers visible as positions; a fraction records an exact share even when its decimal representation does not terminate. An arithmetic rule becomes easier to remember when these interpretations fit together.

Arithmetic circuit 2026-10-18

An arithmetic circuit is a Directed acyclic graph whose input nodes are variables or constants in a field, and whose internal gates perform addition, subtraction, or multiplication. Gates may reuse earlier outputs, so the circuit can represent a polynomial without listing all its monomials.

Array multiset Created 2026-10-25 Updated 2026-10-31

A multiset of keys in a fixed finite integer range represented by one nonnegative count per key. The abstraction function extends the stored array counts by zero outside the range. Single-key additions, removals and queries use constant array work, provided overflow and operation preconditions are handled. Encapsulation of the count array is necessary to preserve its representation invariant.

Associative property 2026-10-14

The associative property says that regrouping three inputs does not change the result of a binary operation:

(a * b) * c = a * (b * c)

for every

a, b, c

in its domain of a function. It changes parentheses while keeping the order of the inputs. Commutativity instead exchanges two inputs; the two properties are different.

For addition modulo three,

(2 + 1) + 1 \equiv 2 + (1 + 1) \equiv 1 (mod 3)

. For subtraction modulo three,

(2 - 1) - 1 \equiv 0, 2 - (1 - 1) \equiv 2 (mod 3),

so the second binary operation fails the associative property. One failed triple disproves associativity; checking a few successful triples does not establish it for all inputs.

The useful consequence is that a finite ordered sequence can be combined in chunks. For an associative operation,

(a * b) * (c * d)

has the same value as

((a * b) * c) * d

. Intermediate results can therefore summarize parts of a computation without retaining their internal parentheses. The order must still be preserved when the binary operation is not commutative. Function composition and concatenation provide examples where grouping is harmless but exchanging entries changes the result.

Automorphism Created 2026-09-24 Updated 2026-10-14

An automorphism is an isomorphism

f : X \to X

: a structure-preserving self-map that can be undone by another structure-preserving self-map. Equivalently, it is an invertible endomorphism. Its inverse satisfies

f^{- 1} \circ f = f \circ f^{- 1} = 1_{X},

where

1_{X}

is the identity morphism. Both maps must be morphisms in the chosen category. For ordinary groups, rings, and vector spaces over a fixed field, a bijective morphism automatically has a compatible inverse. For topological spaces, an automorphism is a homeomorphism from the space to itself: a continuous bijection needs a continuous inverse as well. See Riehl, Category Theory in Context, Definition 1.1.10 and Example 1.1.11.

For example,

T (x, y) = (x + y, y)

is an automorphism of the vector space

R^{2}

over the real numbers, with inverse

T^{- 1} (u, v) = (u - v, v)

. Both are linear maps. The linear endomorphism

P (x, y) = (x, 0)

from endomorphism preserves addition and scalar multiplication too, but discards a coordinate and cannot be undone. Preserving the structure and preserving enough information for reversal are separate requirements.

The automorphisms of a fixed object in a locally small category form a group under composition in a category: the identity morphism is the identity element, and the inverse element of a composite reverses the order of its factors. This makes reversible internal changes calculable. For a group, the resulting automorphism group records which relabelings preserve all products; the examples in group automorphism show how restrictive that condition can be.

Binary array sum by recursion 2026-10-18

Keep an array

A

unchanged, and sum entries in the half-open integer interval of array indices

[l, r)

. The precondition requires integers

0 \leq l \leq r \leq length (A)

and exact, terminating integer addition. An empty range returns the empty sum zero; a one-entry range returns that entry. Every longer range splits at its middle array index:

S(A, l, r):
    require integer indices with 0 <= l <= r <= length(A)
    size = r - l
    if size == 0:
        return 0
    if size == 1:
        return A[l]
    middle = l + floor(size / 2)
    left_sum = S(A, l, middle)
    right_sum = S(A, middle, r)
    return left_sum + right_sum

For the original array

A = [6, - 2, 5, 1]

, call

S (A, 0, 4)

. The left half returns

6 + (- 2) = 4

, the right half returns

5 + 1 = 6

, and the original invocation returns

4 + 6 = 10

. The right half's left endpoint increases from zero to two: what decreases is range length

r - l

, not every argument. Negative entries affect the answer but do not affect algorithm termination.

Figure 1.
Seven calls compute an array sum with only three frames active at once
. Original binary tree of invocations for $A = [6, - 2, 5, 1]$ , with integer intervals labeling ranges and upward arrows labeling returned sums. Small numbers give the order in which invocations begin when the left child runs first. The highlighted graph path contains the three active stack frames while the entry $- 2$ is read; the result $6$ from the completed left sibling is retained by its parent. **Details**.

For range length

n = r - l \geq 2

, the children have lengths

⌊ n /2 ⌋

and

⌈ n /2 ⌉

, both positive and strictly less than

n

. The floor function chooses the split; the ceiling function gives the other length. Algorithm termination follows by this natural number measure. For algorithm correctness, apply mathematical induction on

n

: the two base cases return the specified sum; for a larger range, the two disjoint child ranges cover every original array index exactly once, so addition of their correct sums gives the required sum.

For

n \geq 1

, the invocation tree is a full binary tree with

n

leaves, one per array entry. If

I

is its number of nonleaf vertices, counting edges gives

2 I = I + n - 1

, so

I = n - 1

. Thus the total invocation count is

2 n - 1

, and there are

n - 1

combining additions. Here

n = 4

gives seven calls and three combining additions. For

n = 1

, there is one call and no combining addition; for

n = 0

, there is also one call and no combining addition, but no entry leaf, so the

2 n - 1

formula does not apply.

The call stack holds the active branch, rather than the entire invocation tree. Execute the left child completely before the right child, retaining the left result in the parent stack frame. The maximum number of active stack frames is

1 + ⌈ lo g_{2} n ⌉

for

n \geq 1

, and one for

n = 0

. Balanced splitting therefore needs

O (lo g n)

frames for

n \geq 2

, compared with the

O (n)

frames of the factorial recursive process. Assuming constant-cost array access, index operations and addition, its time complexity is

O (n)

and its auxiliary space complexity is

O (lo g n)

machine words for

n \geq 2

, excluding the stored input. Pass the same array with different endpoints, rather than copying slices. These bounds require all stored indices and partial sums to fit in a constant number of machine words; exact unbounded integer addition and storage require a separate bit cost analysis.

Binary operation Created 2026-09-24 Updated 2026-10-13

A binary operation on a set

S

is a function

* : S \times S \to S

. It takes two ordered inputs from the same set and returns exactly one output in that set. The codomain is part of the definition: ordinary subtraction is a binary operation on the integers, but not on the positive integers, since

2 - 3 = - 1

leaves that set. Ordinary division is not a total binary operation on the real numbers, because division by zero is undefined; it is one on the nonzero real numbers.

The same set can carry several different binary operations. On

S = {0, 1, 2}

, both

a * b = (a + b) mod 3

and

a ⋄ b = (a - b) mod 3

return an element of

S

, using modular arithmetic. Yet the addition operation is commutative and associative, while the subtraction operation is neither. Specifying the allowed inputs and outputs tells us what can be evaluated; additional laws tell us how expressions may be transformed. ^[ref].

For a finite set, a Cayley table records every ordered pair and its result. This turns abstract laws into checkable examples. It also makes the order of the inputs explicit: the row gives the first input, and the column gives the second.

Boolean matrix multiplication 2026-10-31

For Boolean matrices, replace numerical addition by logical disjunction and multiplication by logical conjunction. Applied to adjacency matrices, the product records a walk formed by following one segment represented by the first matrix and one represented by the second. For an adjacency matrix

A

n \geq 1

vertices, start from

I \lor A

. Repeated squaring then computes reflexive transitive closure once the exponent reaches

n - 1

: the identity entries pad shorter walks, and every reachable pair has a simple path of length at most

n - 1

Carry (arithmetic) Created 2026-10-18 Updated 2026-10-20

In positional notation with integer base

b \geq 2

, a carry transfers

b

units in one position into one unit in the next position during addition. Each such transfer lowers the sum of the numeral digits by

b - 1

Cauchy's functional equation Created 2026-09-24 Updated 2026-10-18

Cauchy's functional equation asks for functions

f : R \to R

satisfying

f (x + y) = f (x) + f (y) (x, y \in R) .

The identity must hold for every pair of real numbers, and a solution is an additive function. It says that combining two inputs before applying

f

gives the same result as combining their outputs.^[ref]

For example,

f (x) = 3 x

satisfies the identity because

3 (x + y) = 3 x + 3 y

. At

x = 2/3

and

y = 5/6

the two sides give

f (\frac{2}{3} + \frac{5}{6}) = f (\frac{3}{2}) = \frac{9}{2}, f (\frac{2}{3}) + f (\frac{5}{6}) = 2 + \frac{5}{2} = \frac{9}{2} .

(2)

For positive widths, a rectangle of height three makes this visible: cutting its width into

x

and

y

partitions its area into

3 x

and

3 y

. The same identity also holds for negative inputs, where

3 x

is a signed output rather than an ordinary area.

Figure 1.
The function f(x)=3x preserves addition: partitioning a rectangle and checking exact rational grid sums
. **Details**.

Every function

f (x) = c x

with a fixed real number

c

solves Cauchy's functional equation. The surprising question is whether these are all the solutions. Rational homogeneity of an additive function forces

f (q) = q f (1)

for every rational number

q

, but reaching an irrational number requires an additional argument. Continuity at just one point or being a bounded function on an interval of positive length supplies that argument; without such a condition, discontinuous additive functions exist.^[ref]

This makes Cauchy's functional equation a useful test of the boundary between algebra and analysis: a rule about addition fixes all rational multiples, while a tiny amount of continuity fixes the entire real line. For example, the continuous exponential functional equation reduces to an additive function after taking a logarithm, so this result explains why its nonzero solutions are exponential functions.

Cayley table 2026-10-14

A Cayley table records a binary operation on a finite set: the cell at row

a

, column

b

contains

a * b

. Every cell must contain an element of the specified set. With the same ordering of row and column labels, the table is symmetric across its main diagonal exactly when the binary operation is commutative. Checking the associative property instead requires comparing

(a * b) * c

with

a * (b * c)

for every triple; symmetry alone cannot establish it.^[ref]

Figure 1.
Cayley tables for addition and subtraction in modular arithmetic modulo three
. Read the first input from the row and the second from the column. Both tables give binary operations on ${0, 1, 2}$ . The addition table is symmetric; the subtraction table is not. The bottom calculation exhibits a failed associative property for subtraction. **Details**.