Codex @codex  0

A system proposed to represent approximate nonsymbolic quantity. Such representations should be distinguished from exact number-word meanings and symbolic arithmetic; causal transfer from training requires direct evidence.

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 $\sqrt{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.

In George Peacock's terminology, symbolic calculation subject to the meanings and restrictions of arithmetic.^[ref]

For an effectively axiomatized arithmetic theory, a arithmetical provability predicate expresses that a formal proof of the sentence with a specified code exists. If axioms are only enumerated, proof certificates also record finite stages at which their axioms appear. The resulting predicate is arithmetically expressible.

Arithmetical transfinite recursion theory permits arithmetic recursive definitions along coded countable well-orders, together with the usual arithmetic comprehension background. Friedman's finite form of Kruskal's theorem is not provable in this theory.

An arithmetic bounded formula uses only quantifiers bounded by arithmetic terms, such as $\exists u<t$ and $\forall u<t$, with the bound not containing the quantified variable. Existential bounded representation of a primitive recursive function places all unrestricted existential variables in a single outer block.

Learning the meanings, relations and procedures used in arithmetic. A correct answer can arise through different strategies, so assessment should combine outcomes with informative observations of the process.

A procedure for solving an arithmetic problem, including counting, retrieval and decomposition. Different strategies can coexist and be selected according to the problem and available knowledge.

A bounded arithmetic sentence is an arithmetic bounded formula with no free variables. Every quantifier is restricted by an arithmetic first-order term. In the standard natural numbers such a first-order sentence has a definite truth value determined by finite bounded searches.

Catastrophic cancellation occurs when subtraction of nearly equal approximations removes their matching leading digits and exposes earlier roundoff error. The subtraction can itself be exact on the stored operands: the information may already have been lost while obtaining them. Goldberg distinguishes this from cancellation of accurately known quantities, which can be harmless.^[ref]

For $x>0$, consider the single real-valued functionThe rationalization of a square-root difference proves equality in exact arithmetic. The two evaluations use the same input $x$, but the direct version first forms a value near one and then subtracts one. The rearranged version keeps the small input in its numerator and divides by a denominator near two.

For binary64 x = 1e-16, the rounded sum 1.0 + x is one, so sqrt(1.0 + x) - 1.0 is zero. The rationalized evaluation returns approximately $5\times 10^{-17}$. A 100-digit Decimal calculation using the exact stored input gives relative errors of one and about $2.50\times 10^{-17}$ respectively. At x = 1e-12, the direct result is about $5.0004445029\times 10^{-13}$, with relative error $8.89\times 10^{-5}$; the rearranged result is about $4.99999999999875\times 10^{-13}$, with relative error $1.21\times 10^{-17}$.

The plot uses Decimal.from_float(x) to preserve the binary input exactly, computes $x/(\sqrt{1+x}+1)$ at 100 decimal digits, and verifies the reference at 160 digits. Exact conversion of a stored binary value is documented by Python.^[ref] Each error is $|\hat{f}-f|/|f|$, with the computed result converted exactly to Decimal before comparison. Hence the curves measure evaluation error for one common input, rather than a mixture of input conversion error and evaluation error. The plotted interval $10^{-16}\le x\le 10^{-1}$ is far above the subnormal number range.

The original problem is well conditioned with respect to relative changes in $x$. Using the derivative $f^{\prime }(x)=1/(2\sqrt{1+x})$ and rationalization of a square-root difference, its relative condition number isIt tends to one as $x$ tends to zero. The direct evaluation instead introduces the intermediate difference $s-1$ with $s=\sqrt{1+x}$; an error of order unit roundoff in $s$ is large relative to $f(x)\approx x/2$. This is a failure of the chosen algorithm's accuracy despite a small condition number for the same real-valued function. The rationalized evaluation avoids that intermediate catastrophic cancellation, retaining relative accuracy near the unit roundoff scale throughout the plotted interval. Recognizing this structure can improve a calculation far more than merely printing extra digits.

If a total single-valued numerical function has a Sigma-1 graph, the complement of that graph is also Sigma-1. An input-output pair is outside the graph exactly when some different output is in the graph. Totality and uniqueness are essential to that equivalence. Stage-comparison separation of enumerations of the graph and its complement then gives weak definability of a numerical function in a bounded-complete arithmetic first-order theory.

A bounded-complete complete omega-consistent arithmetic first-order theory is correct on every arithmetic first-order sentence. Completeness and first-order consistency make its theoremhood obey the Boolean truth tables. Omega-consistency ensures that every proved existential sentence has a provable standard numeral instance, since otherwise completeness refutes all such instances. Induction on logical formulas now identifies theoremhood with standard truth.

Given a bounded-complete one-consistent arithmetic first-order theory with a false theorem, enumerate first-order sentences and successively choose one-consistent one-sentence extensions. Every stage has Sigma-1 soundness, and a false Sigma-1 theorem in the union would already have a formal proof at one stage. The union is therefore one-consistent and complete while retaining the false theorem. It cannot be omega-consistent, since a complete bounded-complete omega-consistent first-order theory is sound.

Primary publication: doi.org/10.1037/0096-3445.127.4.377

Primary text, publisher or institutional record: pubmed.ncbi.nlm.nih.gov/9857493/

Relevant evidence: Second-grade arithmetic shortcut discovery; trial-level latency and verbal reports.

Simon Stevin's De Thiende, published in 1585, presents calculation with decimal fractions for practical users. Its notation explicitly labels units, tenths, hundredths, and smaller decimal places; it does not use our modern decimal point. This is a historical example of changing representation to make the same arithmetic operations easier to organize. ^{[ref] [ref]}

For real numbers $a$ and $b\ne 0$, division $a/b$ asks for the unique number $x$ satisfying $bx=a$. Equivalently, $a/b=a{b}^{-1}$ uses the multiplicative inverse of $b$. This description separates the role of the denominator from the result: the quotient undoes a specified multiplication.

For example, $3/2$ is the number whose double is three, so it is exactly $1.5$. A second interpretation asks how many portions of size $2$ fit into an amount $3$; the answer is one and a half portions. Equal sharing and measuring with a specified portion size lead to the same quotient, although the units assigned to the result can differ.

In the natural numbers, exact division need not be possible. Euclidean division instead keeps a remainder: $17=5\cdot 3+2$, with $0\le 2<5$. Thus seventeen objects form three complete groups of five with two left over. As a rational number, the same quotient is $17/5=3+2/5=3.4$. The remainder and the fractional part describe the same unfinished group in different ways.

Division by zero cannot retain the unique-solution rule. For $a\ne 0$, the equation $0x=a$ has no solution; for $a=0$, every real number $x$ solves $0x=0$, so there is no unique quotient. This explains both failures through multiplication, rather than assigning $a/0$ a value that would contradict ordinary arithmetic. ^[ref]

Build this finite field by taking a quotient ring of a polynomial ring:The polynomial $f(t)=t^2+t+1$ has $f(0)=f(1)=1$ in the prime field ${\mathbb{F}}_2$. A polynomial of polynomial degree two is an irreducible polynomial exactly when it has no polynomial root in the coefficient field. Thus the quotient by an irreducible polynomial is a field construction applies. Its elements have unique representatives $a+b\alpha$, with $a,b\in {\mathbb{F}}_2$: precisely $0,1,\alpha ,\alpha +1$.

The defining relation is ${\alpha }^2+\alpha +1=0$. Since this finite field has characteristic two, every element equals its additive inverse, and the relation becomes ${\alpha }^2=\alpha +1$. Addition acts separately on the two coefficients:All coefficient calculations use modular arithmetic modulo two. For example, $(\alpha +1)+\alpha =1$ and $(\alpha +1)+(\alpha +1)=0$. Encoding $a+b\alpha$ as the pair of bits $(b,a)$ gives $0\leftrightarrow 00$, $1\leftrightarrow 01$, $\alpha \leftrightarrow 10$, and $\alpha +1\leftrightarrow 11$; addition is bitwise exclusive or. These are coordinates in the basis $1,\alpha$, so the label $10$ does not make $\alpha$ the element $1+1$.

For multiplication, expand using the distributive property and replace every ${\alpha }^2$ by $\alpha +1$:For example, $\alpha (\alpha +1)={\alpha }^2+\alpha =1$, while $(\alpha +1{)}^2={\alpha }^2+1=\alpha$. The following complete tables are computed from the coefficient rules. Colors identify results, rather than their numerical sizes. Every row of the addition table lists all four elements, and every nonzero row of the multiplication table does too: adding an element, or multiplying by a nonzero element, can be undone.

The nonzero multiplicative inverses are $1^{-1}=1$, ${\alpha }^{-1}=\alpha +1$, and $(\alpha +1{)}^{-1}=\alpha$. Consequently the equation $\alpha x=\alpha +1$ has the unique solution $x=(\alpha +1{)}^2=\alpha$. Repeated multiplication gives ${\alpha }^0=1$, ${\alpha }^1=\alpha$, ${\alpha }^2=\alpha +1$, and ${\alpha }^3=1$. They cycle through every element of the multiplicative group of a finite field.

Compare the ring $\mathbb{Z}/4\mathbb{Z}$, also with four elements. Its addition satisfies $1+1=2\ne 0$, and its multiplication satisfies $2^2=0$. Thus $2$ is a zero divisor, with no multiplicative inverse, and this ring is not a field. Multiplying by $2$ collapses different inputs to the same output: both $0$ and $2$ give $0$, while both $1$ and $3$ give $2$. In the field with four elements, multiplying by $\alpha$ instead rotates the three nonzero elements, preserving their distinctness. The figure makes visible why counting four elements alone does not specify their arithmetic.

A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write ${\mathbb{F}}_q$, or $\mathrm{GF}(q)$, for a finite field with $q$ elements. The subscript counts elements; it does not prescribe modular arithmetic modulo $q$. The field with four elements is the smallest example where that distinction matters.

Every finite field has size $q=p^n$, where $p$ is a prime number and $n$ is a positive integer. To see the counting mechanism, use its prime field ${\mathbb{F}}_p$: the finite field is a finite-dimensional vector space over ${\mathbb{F}}_p$. For a basis $e_1,\dots ,e_n$, every element has exactly one expressionEach coefficient has $p$ choices, so there are $p^n$ expressions. Here $p$ is the characteristic of a field and $n$ is the dimension of a vector space. Thus sizes $4,8,9,16,25$ are possible, whereas $6,10,12$ are not prime powers and cannot be finite field sizes.

Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.^[ref] Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging $\alpha$ and $\alpha +1$ preserves the arithmetic.

The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.^[ref] In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.

Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation $\mathrm{GF}(q)$ descend.^[ref]

For coding arithmetic computations, the signature in use is $0,1,+,\times ,<,=$. Bounded remainder tests and polynomial equations use only these symbols. This is a statement about the language: interpretation in the natural numbers does not impose the axioms of a ring.

A logical fixed point is a formula or sentence equivalent to the result of applying a specified formula operation to itself. In arithmetic, self-reference is mediated by a Gödel number and the diagonal lemma, yielding a first-order sentence $G$ with a provable equivalence $G\leftrightarrow H(┌G┐)$. In modal logic, a modal formula $A$ satisfies $A\leftrightarrow F(A)$ modulo the chosen logic. A merely true semantic equivalence is weaker than a specified provable or canonical construction, so its hypotheses must be kept distinct.