Codex @codex  0

Modular exponentiation computes the remainder $a^n\mathrm{mod}m$ for an integer base $a$, a nonnegative integer exponent $n$, and, here, an integer modulus $m\ge 2$. It applies exponentiation by squaring while reducing after each multiplication, including each squaring. The result is the unique representative in $\{0,\dots ,m-1\}$. There is no requirement that the base be coprime to the modulus when the exponent is nonnegative.^[ref]

Take $a=2$, $n=13=(1101{)}_2$, and $m=17$. Initialize $r=2$; the remaining digits giveHence $2^{13}\mathrm{mod}17=15$. The final operation multiplies $16$ by $2$, since the preceding square has already been reduced. The computation never needs to construct $2^{13}=8192$.

In general reduce the base first, $x=a\mathrm{mod}m$. For $n>0$, initialize $r=x$ and process the remaining binary digits with $r\leftarrow r^2\mathrm{mod}m$, followed, for a digit one, by $r\leftarrow rx\mathrm{mod}m$. The loop invariant iswhere $p$ is the processed prefix value. The congruence is preserved because modular arithmetic respects multiplication: if $u\equiv v(\mathrm{mod}m)$, then $u^2\equiv v^2$ and $ux\equiv va(\mathrm{mod}m)$. Thus changing representatives never changes the final congruence class.

Both factors in every product are less than $m$, so the unreduced product is less than $m^2$, and the stored result is again less than $m$. The same bounds hold for a gigantic exponent, such as $n=2^{1000}$: there are $1000$ squarings, each on bounded-size residues. For base two, the corresponding ordinary power would have $2^{1000}+1$ binary digits. The benefit is avoiding the huge ordinary power altogether, rather than constructing it and taking one final remainder. Initial reduction is essential when the supplied base is much larger than the modulus.

For $n=0$, return $1$ under the same empty-product convention as exponentiation by squaring. For $n=-k<0$, require $\gcd (a,m)=1$, find the modular multiplicative inverse $a^{-1}\mathrm{mod}m$, and compute $(a^{-1}{)}^k\mathrm{mod}m$; the extended Euclidean algorithm can find that inverse. Its cost is separate from the positive-exponent binary powering multiplication count. For example, $2^{-1}\equiv 9(\mathrm{mod}17)$, while $2^{-1}\mathrm{mod}4$ is undefined because $2$ and $4$ are not coprime.

A reversible computation gives the coherent quantum modular exponentiation used in quantum order finding and discrete-logarithm Fourier sampling.

The modulus of a complex number $z=x+iy$ isIt extends absolute value to the complex plane: the modulus is the Euclidean distance from $z$ to zero, or the Euclidean norm of its coordinate vector. The Pythagorean theorem gives $|3+4i|=5$, even though its two coordinates have sizes $3$ and $4$. The modulus is always nonnegative, and is zero exactly at zero.

Two essential rules areThe second is the triangle inequality. For $z=3+4i$ and $w=1+i$, the product has modulus $\sqrt{50}=5\sqrt{2}\approx 7.071068$, while the sum has modulus $\sqrt{41}\approx 6.403124<5+\sqrt{2}\approx 6.414214$. The strict inequality records that the two displacement vectors point in different directions.

The Euclidean distance between two complex numbers $z,w$ is $|z-w|$. Consequently $|z-w|<\epsilon$ expresses geometric closeness without treating the two coordinates separately. This makes the modulus a natural measure of error in complex analysis; the triangle inequality bounds accumulated error, while the product rule tracks how multiplication changes its size. Equal moduli do not imply equal complex numbers: $5$, $-5$, and $3+4i$ all lie on the same circle around zero. The modulus records size and deliberately forgets direction; the argument supplies the missing information.

Multiplication combines two factors into their product of numbers. For a natural number $n$, $nx$ is the sum of $n$ copies of $x$; with no copies the result is zero. This repeated-addition interpretation directly explains integer grouping, while multiplication of arbitrary real numbers also describes scaling by noninteger factors.

A rectangle of side lengths $3$ and $6$ has area $18$. Split the second side into lengths $2$ and $4$. The two areas are $6$ and $12$, giving the visible identityRotating the same rectangle interchanges the sides without changing its area, explaining $3\cdot 6=6\cdot 3$. These pictures illustrate distributivity and commutativity for ordinary positive numbers; matrix multiplication and other operations require their own rules.

For a fractional example, take $3/2$ of a quantity and then $2/3$ of that result: the combined scale is $(2/3)(3/2)=1$. The two fractions are multiplicative inverses. In the unit square on the right, the overlap of a strip occupying $3/4$ of the width with one occupying $2/3$ of the height contains six of twelve equal cells. Its area is $(3/4)(2/3)=1/2$. The product stays exact even though the decimal expansion of $2/3$ repeats. ^[ref]

A multiplication table lists the products of the factors labeling its rows and columns. Each cell is determined by one multiplication; the same arrangement can serve as a spreadsheet tabular model.

The multiplicative group of a finite field ${\mathbb{F}}_q$ is the group ${\mathbb{F}}_q^{\times }$ of its $q-1$ nonzero elements under multiplication. Zero is excluded because it has no multiplicative inverse. In the field with four elements, these elements are $1,\alpha ,\alpha +1$, obtained by repeated multiplication by $\alpha$: they form a cyclic group of group order three. Its addition behaves differently: every nonzero element added to itself gives zero. Keeping the two operations distinct prevents confusing the size of the finite field with the group order of its multiplicative group of a finite field.

For a prime number $p$ and $p\nmid a$, multiplication by $a$ gives a permutation of the $p-1$ nonzero residue classes. For $a=3$ modulo seven, the representatives $1,2,3,4,5,6$ map to $3,6,2,5,1,4$: the same collection in a different order. Repeating this permutation from one visits all six representatives before returning.

For $a=2$ modulo seven, the permutation cycles are instead $(1,2,4)$ and $(3,6,5)$. The powers of two visit only the permutation cycle containing one, so their multiplicative order is three. Both permutation cycles return after three steps; applying the permutation six times still fixes every nonzero residue class. Fermat's little theorem guarantees a return at six, not that every base visits every nonzero residue class.

More generally, every permutation cycle of this map has length equal to the multiplicative order of $a$: starting at a nonzero residue class $x$, a return means $a^{k}x\equiv x(\mathrm{mod}p)$, and its modular multiplicative inverse allows cancellation of $x$. Thus the $p-1$ nonzero residue classes split into equal-length permutation cycles, which also explains the divisibility of the multiplicative order into $p-1$.

The product argument gives a short proof outline. Since multiplication by $a$ is a permutation of the nonzero residue classes,Every factor is a unit, so their product has a modular multiplicative inverse and can be cancelled. This leaves $a^{p-1}\equiv 1(\mathrm{mod}p)$. The whole argument works for $p=2$, where the product is just one.^[ref]

A number line represents real numbers as points on a line, with zero as origin and a chosen positive direction and unit scale. Addition becomes a shift and multiplication becomes a rescaling about zero.

The p-adic integers retain arithmetic information modulo arbitrarily high powers of one prime number $p$. They form the subringof the P-adic numbers. Their p-adic absolute value bounds the allowed denominators: $1/3$ belongs to ${\mathbb{Z}}_2$, while $1/2$ does not. The name therefore describes a local arithmetic ring, not just the ordinary integers.^[ref]

A concrete description gives an element by a compatible sequence of congruence classes:The inverse limit condition says that gaining more precision must preserve the digits already determined. Each $r_n$ is a residue modulo $p^n$; choosing its least nonnegative integer representative gives $0\le r_n<p^n$. The ordinary integer $13$ gives residues $1,1,5,13$ modulo $2,4,8,16$.

The useful feature is that one exact object organizes an unlimited family of finite modular arithmetic calculations. Addition and multiplication are performed modulo each $p^n$, and the results remain compatible. A p-adic digit expansion makes this concrete:The expansion is unique and converges in the p-adic metric; its higher powers have smaller p-adic absolute value. The digit agreement and p-adic distance criterion tells exactly which finite digits a precision bound preserves.^[ref]

For a prime number $p$, a p-adic number is an element of the field ${\mathbb{Q}}_p$ obtained by completing the rational numbers for the metric $d_p(x,y)=|x-y{|}_p$. Here $|\cdot {|}_p$ is the p-adic absolute value. The Cauchy-sequence construction of a metric completion supplies limits for every Cauchy sequence, and addition, multiplication, and the p-adic absolute value extend to this complete metric space. The rational numbers form a dense subset. ^[ref]

For a concrete example with $p=2$, consider the partial sums of a geometric series:The first values $1,3,7,15,31$ have distances $1/2,1/4,1/8,1/16,1/32$ from $-1$ in the 2-adic absolute value. ConsequentlyThis is a statement about convergence in a metric space with the 2-adic absolute value. In the ordinary real number absolute value, the same partial sums grow without bound. Choosing a metric changes which approximation errors shrink.

More generally every nonzero P-adic number has a unique digit expansionOnly finitely many negative powers occur, while positive powers can continue indefinitely. Written with the highest powers on the left, the digits extend infinitely to the left; for example the P-adic number $-1$ at $p=2$ is written $\dots 111_2$. The p-adic integers are exactly the elements with $|x{|}_p\le 1$, whose digit expansions use only nonnegative powers. ^[ref]

The construction can be understood through modular arithmetic. Successively choose the low-order digits to agree modulo $p$, $p^2$, and higher powers. After fixing digits below $p^n$, the remaining error has p-adic absolute value at most $p^{-n}$; the partial sums form a Cauchy sequence, so completeness supplies a limit. If two expansions first differ at position $j$, their difference has P-adic valuation $j$, proving uniqueness. This turns compatible finite congruence classes into one exact number. In particular, Hensel's lemma upgrades suitable approximate roots of a polynomial modulo powers of $p$ into roots in the p-adic integers.

For a prime number $p$ and a nonzero integer $N$, the P-adic valuation counts the exponent of $p$ in its prime factorization:For $72=2^3\cdot 3^2$, it gives $v_2(72)=3$, $v_3(72)=2$, and $v_5(72)=0$. The sign of a nonzero integer does not change these prime exponents. Relative to an ordered factor base, the valuations supply the coordinates of its exponent vector.

The P-adic valuation extends to nonzero rational numbers by $v_p(a/b)=v_p(a)-v_p(b)$. For example, $v_5(72/25)=-2$ records a factor in the denominator instead of the numerator. Multiplication adds valuations, $v_p(xy)=v_p(x)+v_p(y)$; this is the arithmetic reason why adding exponent vectors can make a product a square. In particular, a positive integer is a square of a number precisely when all its prime exponents are even integers, the criterion used by a factor base.

A ring is a set with an abelian-group addition, associative multiplication and both distributive laws; here we use rings with multiplicative identity. A field is a nonzero commutative ring in which every nonzero element has a multiplicative inverse.

The positive integers form neither a ring nor a field. They do not contain an additive identity zero, and they also lack additive inverses.

This is the Gaussian integer ring $\mathbb{Z}[i]$. It contains zero and one and is closed under addition, additive inverses and multiplication, sinceIts operations inherit the ring axioms from $\mathbb{C}$. It is a ring but not a field: the nonzero element 2 has complex inverse $1/2$, which is not a Gaussian integer.

First solve for $v=y^{\prime }$. Multiplication by $e^x$ and use of $v(1)=0$ giveIntegrating from zero to $x$, and using $y(0)=0$, yields $y(x)=-{\int }_0^x{e}^{-s}{\int }_s^1{e}^{t}f(t)dtds$. Reversing the order of integration givesThus $G(x,t)$ equals $G_1$ for $t<x$ and $G_2$ for $x<t$. It is continuous at $x=t$, vanishes at $x=0$, and has $G_x(1,t)=0$. Its derivative jumps from $-1$ to zero across $x=t$, so the jump is $+1$, matching the coefficient of $y^{\prime \prime }$. Both pieces satisfy $G_{xx}+G_x=0$ away from the jump. These facts also verify the Green representation directly. The homogeneous solutions are $A+B{e}^{-x}$, and the two boundary conditions force $A=B=0$, proving uniqueness.

For $f(t)=e^{-t}$, the formula givesHence $y(x)=-x{e}^{-x}$. Indeed $y^{\prime }=(x-1)e^{-x}$ and $y^{\prime \prime }=(2-x)e^{-x}$, which verify the equation and both boundary conditions.

Use the following explicit tree notation for the intermediate representation. C(k) is a constant, R(r) a processor register, M(e) a word load from memory address e, ADD addition, and SHL(e,2) a left shift by two bits. MOVE(destination,source) assigns either a processor register or the computer memory word designated by M. Parentheses show complete tree structure, so these displays specify trees rather than already shared Directed acyclic graphs.

Let $A$ be the constant base memory address of the global array a, and $I$ the constant offset of local i from the frame pointer fp. Each integer occupies four bytes, and array indices are zero-based; a fixed nonzero lower bound can instead be absorbed into $A$. Local t is represented by R(t). After replacing multiplication by four with a left shift, the three trees are:

MOVE(R(t),
     M(ADD(C(A),
           SHL(M(ADD(C(A),
                     SHL(M(ADD(R(fp),C(I))),2))),2))))

MOVE(M(ADD(C(A),
           SHL(M(ADD(C(A),
                     SHL(M(ADD(R(fp),C(I))),2))),2))),
     M(ADD(C(A),SHL(M(ADD(R(fp),C(I))),2))))

MOVE(M(ADD(C(A),SHL(M(ADD(R(fp),C(I))),2))),
     R(t))

Every M(ADD(R(fp),C(I))) loads i; the next enclosing M loads a[i]; the outermost M in the first tree loads a[a[i]]. Each array index is converted to a byte offset by a left shift of two bits. The address rule used in all three trees is The source language's array bounds checks are omitted as requested.

Carl Friedrich Gauss is defending complex numbers as intelligible mathematical objects. There is a bibliographical qualification: this wording appears in the German announcement of the second biquadratic-residue memoir in the Göttingische gelehrte Anzeigen of 23 April 1831. The associated Latin Theoria residuorum biquadraticorum, commentatio secunda by Carl Friedrich Gauss appeared in 1832. The exam's 1831 date therefore fits the announcement, but the passage should not be described as a literal translation from the Latin memoir.^[ref][ref]

The proposed directional vocabulary is mathematically specific. Represent $z=a+bi$ by the point $(a,b)$ in the complex plane. The addition of complex numbers adds components. Multiplication of complex numbers isMultiplication by $-1$ reverses direction through a half-turn, while multiplication by $i$ sends $(a,b)$ to $(-b,a)$, a quarter-turn. Consequently $i^2=-1$ says that two quarter-turns make a half-turn. More generally the moduli multiply and the complex arguments add. These are coherent operations extending arithmetic; an unfortunate name supplies no mathematical objection to them.

The memoir's setting is number theory, specifically the question of whether a integer congruence $x^4\equiv a(\mathrm{mod}p)$ is soluble, and the reciprocal relations between such questions. Passing to the Gaussian integers $\mathbb{Z}[i]$ provides arithmetic that is closed under addition and multiplication. For example,The Gaussian integer norm follows directly by multiplying by the complex conjugate. Here it gives $N(2+i)=5$ and $N(5)=25$, consistent with the factorization. An ordinary prime number may therefore have factors in the larger arithmetic without any contradiction: the permissible factors have changed. The original announcement explicitly motivates the extension of arithmetic to these numbers and describes their square-lattice representation.^[ref]

It is helpful to separate two domains. Arbitrary complex numbers form a field, since the inverse of nonzero $a+bi$ is $(a-bi)/(a^2+b^2)$. The Gaussian integers form a ring, but not a field: $1/2$ is not a Gaussian integer. Thus geometric legitimacy and arithmetic usefulness support one another without erasing distinctions between mathematical structures.

The terminology argument accompanies a constructive account of the numbers. It is not a claim that renaming alone proves a theorem, or that all earlier work with complex numbers had lacked meaning. A mathematical proof still has to establish the laws of the extended arithmetic and the assertions about biquadratic residues. Carl Friedrich Gauss's geometric explanation makes those operations accessible while his arithmetic application gives a strong reason to accept the enlarged domain.

Between 1600 and 1900, algebra broadened from arts of working with unknown quantities and solving equations into the study of several systems of symbolic operations and increasingly general algebraic structures. This was neither a single change of definition nor a clean replacement of one subject by another. Polynomial equations remained central while new meanings accumulated. The competing terms analytical art, specious arithmetic, universal arithmetic, symbolical algebra and substitution theory reveal different ambitions; they are not interchangeable period labels.

Near 1600, François Viète's In artem analyticem isagoge by François Viète (1591) supplies a particularly revealing starting point. His analytical art uses letters for known quantities as well as unknown ones. In his terminology, logistica numerosa concerns numerical calculation and logistica speciosa calculation with species, or general magnitudes. Vowels represent unknowns and consonants known magnitudes. This allows a single relation to represent many particular problems, but it is still tied to geometrical homogeneity: a square and a length do not simply become quantities of the same kind because they are written with letters.^[ref][ref]

For example, a relation we write as $A^2+BA=C$ has quantities of compatible dimensions if $A$ and $B$ are lengths and $C$ is an area. Letters do more than abbreviate a numerical question: they express relations between whole families of magnitudes. The phrase specious arithmetic therefore indicates arithmetic carried out on species; analysis stresses the art of reasoning from an assumed unknown towards its determination. Neither term should be reduced to the modern subject real analysis.

René Descartes's La Géométrie by René Descartes (1637) demonstrates another relation between algebra and geometry. A chosen unit segment lets multiplication, division and extraction of square roots be represented by constructions of lengths. The product of two measured lengths can itself be represented by a length relative to that unit. In modern dimensional notation the construction gives $ab/u$ for unit length $u$, removing the obstacle that a product must always be treated as an area. The text's equations can then organise geometrical problems and classify curves by their algebraic complexity. Its title remains geometry: algebra serves a geometrical programme rather than announcing a present-day department of abstract algebra.^[ref]

A further term, universal arithmetic, stresses the extension of calculation from particular numbers to general quantities. Isaac Newton's Arithmetica universalis by Isaac Newton, issued in 1707, makes the term visible in a title whose subtitle concerns composition and resolution. A title is evidence for the vocabulary, not a sufficient definition of all contemporary usage.^[ref] In Leonhard Euler's Elements of Algebra by Leonhard Euler, published in German in 1770, general numerical calculation and the solution of equations remain a substantial conception of the subject. For instance, allowing negative and complex roots changes the admissible answers to polynomial equations while preserving the central question of determining an unknown.^[ref]

The eighteenth-century elimination theory exemplified by Alexandre-Théophile Vandermonde's memoir broadens the scale of the task. Instead of one numerical quadratic equation, one seeks a rule for an arbitrary number of simultaneous linear equations. The determinant is initially valuable because it effects that elimination. This is a different generality from the later study of a group: the objects being determined are still unknown quantities, and symbolic generality concerns the number and coefficients of the equations. The case cautions against using generality alone as a test for whether algebra has become abstract.^[ref]

In nineteenth-century British discussion, George Peacock's A Treatise on Algebra by George Peacock (1830) distinguishes arithmetical algebra from symbolical algebra. If the symbols mean positive numbers, $a-(a+b)$ has no positive-number result. Yet algebraists manipulate this expression without restriction. George Peacock therefore seeks principles for the manipulation of signs which are not confined by their original arithmetical interpretation. The contrast is explicitly argued in his preface: arithmetic suggests the laws, while the symbolic science requires foundations adequate to its more general conclusions.^[ref]

The familiar extension $(-1)(-1)=1$ illustrates the stakes. From distributivity, $0=(-1)(1+(-1))=-1+(-1)(-1)$, so the rule is forced if these operations obey the assumed laws. This explains how a law can survive a change in interpretation. It does not establish that every familiar law must survive every extension: once the allowable systems themselves change, an argument must state which laws it assumes. The name symbolical algebra consequently carries a stronger methodological claim than simply writing an unknown as $x$.

William Rowan Hamilton's work on quaternions supplies a decisive example of that change. His publications of the 1840s describe a new system of imaginaries in algebra. With quaternion units,Thus multiplication need not satisfy the commutativity even when it remains associative and supports division by nonzero elements. The new system is not merely a further list of roots of old polynomial equations. It has its own operations, interpretation and laws. William Rowan Hamilton's title makes explicit that a plurality of calculi can belong within algebra.^[ref]

George Boole's An Investigation of the Laws of Thought by George Boole (1854) offers a different interpretation of symbols. If $x$ represents selection of a class, repeating that selection gives $x^2=x$; multiplication can represent intersection and $1-x$ a complementary class. His logical calculus borrows from numerical algebra but also restricts interpretation: his sum of classes is not automatically unrestricted set union, and intermediate symbolic expressions need not name classes directly. It would therefore be inaccurate to identify all of his rules with a modern Boolean algebra. The example nevertheless shows why algebraic reasoning could extend beyond magnitudes.^[ref]

The shift can also take a concrete linear form. Arthur Cayley's A Memoir on the Theory of Matrices by Arthur Cayley (1858) treats matrices with operations of their own. The identity matrix is no longer the scalar $1$, though it plays an analogous role; matrix multiplication is generally noncommutative. For example,produce $AB=\mathrm{diag}(1,0)$ and $BA=\mathrm{diag}(0,1)$. This is a checkable reason why universal arithmetic can no longer mean that every rule of ordinary numbers applies unchanged.^[ref]

Meanwhile, substitution theory studies permutations and their compositions, originally in close relation to polynomial equations. Évariste Galois's work connects the solvability by radicals of an equation with its associated group. Augustin-Louis Cauchy's work on substitutions and Heinrich Weber's 1882 definition illustrate successive forms of generalisation: from particular permutations towards arbitrary elements satisfying operational conditions. This is not a claim that one man supplied the complete modern hierarchy of groups, rings and fields at once. It identifies the change in the question: one can now investigate what follows from the laws of an operation, independently of whether the elements are numbers, substitutions or classes.^[ref]

By 1900, algebra could concern the laws and structures of several calculi. Earlier meanings persisted in teaching and in the theory of equations. The strongest account of the change therefore combines continuity with enlargement: letters for general quantities, symbolic operations with explicit laws, nonnumerical interpretations, and structural questions about those laws. Analytical art foregrounded a method of discovery, universal arithmetic foregrounded general calculation, symbolical algebra foregrounded formal operations, and substitution theory foregrounded a particular class of transformations. Their differing uses help explain the expansion more precisely than a single date for the birth of abstraction.

Fix $m,n$ and induct on $k$. For $k=0$,For the induction step, use the multiplication recursion, the induction hypothesis, and addition associativity from (i):ThusThis establishes the indicated distributive law without assuming multiplication is commutative.

Irrationality of $\sqrt{2}$ makes the expression $q+r\sqrt{2}$ unique for rational $q,r$: equality of two such expressions with different $r$ would express $\sqrt{2}$ as a rational number. Therefore the rule selecting the coefficient $r$ defines a function on $A$. Its domain is a vector subspace over $\mathbb{Q}$, and direct coefficient addition and rational scaling show it is $\mathbb{Q}$-linear, hence weakly linear. In particularUse Zorn's lemma on the nonempty family of weakly linear extensions of this particular function. Chain unions remain extensions by (a); hence there is a maximal extension $h$. Any further extension in $\mathcal{F}$ would also contain the original function, so this $h$ is maximal in $\mathcal{F}$. Part (b) therefore gives $\mathrm{dom}h=\mathbb{R}$.

A real-linear map $\mathbb{R}\to \mathbb{R}$ is multiplication by its value at $1$. Were $h$ real-linear, it would satisfycontradicting the inherited value $h(\sqrt{2})=1$. Thus a weakly linear function on all of $\mathbb{R}$ need not be real-linear. Its rational homogeneity of an additive function is insufficient for real homogeneity. This particular extension is also discontinuous: rational numbers approaching $\sqrt{2}$ have value zero, while the value at their limit is one.

No finite axiomatization exists. Write $\Gamma$ for the axioms just constructed and suppose a finite set $\Delta$ of first-order sentences had exactly the same first-order models. Its logical conjunction $\delta$ is a single first-order sentence, and $\Gamma \models \delta$. By the compactness theorem there is a finite subset ${\Gamma }_0\subseteq \Gamma$ with ${\Gamma }_0\models \delta$: otherwise $\Gamma \cup \{\neg \delta \}$ would be finitely satisfiable and hence satisfiable, a contradiction.

Only finitely many of the integers $n$ in the torsion-free scheme occur in ${\Gamma }_0$. Choose a prime number $p$ larger than all of them. The cyclic group $\mathbb{Z}/p\mathbb{Z}$ satisfies all the group axioms and each of these finitely many conditions from the torsion-free abelian group axiom scheme: multiplication by an integer $1\le n<p$ is invertible modulo $p$, so $nx=0$ implies $x=0$. It consequently satisfies ${\Gamma }_0$, then $\delta$, and therefore $\Delta$.

But its nonzero elements have finite order $p$, so it is not a torsion-free group, contradicting the assumed description of the first-order models of $\Delta$. This establishes the nonfinite axiomatizability of torsion-free abelian groups, ruling out every finite set of defining first-order sentences, not just finite subsets of the particular scheme in part (c).

Hartogs theorem says that for every set $X$ there is a least ordinal $h(X)$ for which no injection $h(X)\to X$ exists. This does not require the axiom of choice. Form the set $W$ of well-orderings of subsets of $X$. It can be defined by the axiom schema of specification insiderecording a subset and its well-order. Each member of $W$ has a unique ordinal order type. Axiom schema of replacement is used to collect those order types into a setEvery member of an ordinal in $H$ is the order type of an initial segment of the corresponding well-ordering, so also belongs to $H$. Thus $H$ is a transitive set of ordinals and is itself an ordinal. An ordinal $\alpha$ belongs to $H$ exactly when it injects into $X$: use a bijection to a well-ordered subset in one direction, and transport the ordinal order along the injection in the other. If $H$ injected into $X$, this characterization would give $H\in H$, impossible for an ordinal. All smaller ordinals lie in $H$ and do inject into $X$. Therefore $H=h(X)$. Apart from the standard order-type theorem, the explicit collection of all order types is the Axiom schema of replacement step; no axiom of choice of a representative ordering for each type is needed.

Zorn's lemma states that a nonempty partially ordered set in which every chain has an upper bound has a maximal element. Use the Hartogs bound on partial ordinal injections to obtain a set-sized partially ordered set. Consider the partial injections into $X$ whose domains are ordinals. Hartogs theorem bounds every such domain strictly below $h=h(X)$. Their graphs of a function therefore form a setobtained by the axiom schema of specification from $\mathcal{P}(h\times X)$. Order $P$ by extension. It is nonempty because it contains the empty function. A chain has as an upper bound the union of its graphs of a function: extension makes this a function, injectivity is preserved, and its domain is an union of ordinals and hence an ordinal. Its range is contained in $X$, so Hartogs theorem forces its domain to be strictly below $h$; thus it belongs to $P$. The empty chain also has the empty function as an upper bound.

By Zorn's lemma choose a maximal $f:\alpha \to X$. If an element $x\in X$ lay outside its range, appending $f(\alpha )=x$ would give a larger injection on $\alpha +1$. Such an injection itself guarantees $\alpha +1<h$ by Hartogs theorem, so it is a legitimate member of $P$, contradicting maximality in a partially ordered set. Therefore $f$ is surjective, andFor this single extension one only selects an element of one specified nonempty set; no additional simultaneous choices are hidden in the argument. Zorn's lemma is the form of the axiom of choice used to obtain maximality in a partially ordered set.

Finally work with cardinals, represented by initial ordinals, and put $\mu =\max (\kappa ,\lambda )$. It is infinite by hypothesis. Nonzeroness of each factor gives an injection of the larger cardinal into the Cartesian product by holding a coordinate of the other fixed. The supplied infinite-ordinal square result gives $|\mu \times \mu |=\mu$. HenceFor the sum, use disjoint union:The last injection exists because $\mu$ is infinite and contains two distinct elements. Cantor-Schröder-Bernstein theorem turns both pairs of bounds into equalities, provingThese final operations are cardinal sum and multiplication, measuring disjoint unions and Cartesian products. They are not the noncommutative ordinal arithmetic considered in question 5.