Algebra is a branch of mathematics sibling to geometry, analysis(calculus), number theory, combinatorics, etc. Although algebra hasits roots in numerical domains such as the reals and the complexnumbers, in its full generality it differs from its siblings inserving no specific mathematical domain. Whereas geometry treatsspatial entities, analysis continuous variation, number theory integerarithmetic, and combinatorics discrete structures, algebra is equallyapplicable to all these and other mathematical domains.

Elementary algebra, in use for centuries and taught insecondary school, is the arithmetic of indefinite quantities orvariables \(x, y,\ldots\). Whereas the definite sum \(3+4\) evaluatesto the definite quantity 7, the indefinite sum \(x+y\) has no definitevalue, yet we can still say that it is always equal to \(y+x\), or to\(x^2 -y^2\) if and only if \(x\) is either \(-y\) or \(y+1\).

Elementary algebra provides finite ways of managing the infinite. Aformula such as \(\pi r^2\) for the area of a circle of radius \(r\)describes infinitely many possible computations, one for each possiblevaluation of its variables. A universally true law expressesinfinitely many cases, for example the single equation \(x+y = y+x\)summarizes the infinitely many facts \(1+2 = 2+1, 3+7 = 7+3\), etc.The equation \(2x = 4\) selects one number from an infinite set ofpossibilities. And \(y = 2x+3\) expresses the infinitely many pointsof the line with slope 2 passing through \((0, 3)\) with a finiteequation whose solutions are exactly those points.

Elementary algebra ordinarily works with real or complex values.However its general methods, if not always its specific operations andlaws, are equally applicable to other numeric domains such as thenatural numbers, the integers, the integers modulo some integer \(n\),the rationals, the quaternions, the Gaussian integers, the \(p\)-adicnumbers, and so on. They are also applicable to many nonnumericdomains such as the subsets of a given set under the operations ofunion and intersection, the words over a given alphabet under theoperations of concatenation and reversal, the permutations of a givenset under the operations of composition and inverse, etc. Each suchalgebraic structure, or simplyalgebra, consists ofthe set of its elements and operations on those elements obeying thelaws holding in that domain, such as the set \(Z = \{0, \pm 1, \pm 2,\ldots \}\) of integers under the integer operations \(x+y\) ofaddition, \(xy\) of multiplication, and \(-x\), negation, or the set\(2^X\) of subsets of a set \(X\) under the set operations \(X\cup Y\)of union, \(X\cap Y\) of intersection, and \(X'\), complement relativeto \(X\).

The laws are often similar but not identical. For example integermultiplication distributes over addition, \(x(y+z) = xy+xz\), but notconversely, for example \(2+(3\times 5) = 17\) but \((2+3)\times(2+5)= 35\). In the analogy that makes intersection the set theoreticcounterpart of multiplication and union that of addition, intersectiondistributes over union,

as for the integers, but unlike the integers union also distributesover intersection:

Whereas elementary algebra is conducted in a fixed algebra,abstract ormodern algebra treats classes ofalgebras having certain properties in common, typically thoseexpressible as equations. The subject, which emerged during the 19thcentury, is traditionally introduced via the classes of groups, rings,and fields. For example any number system under the operations ofaddition and subtraction forms an abelian (commutative) group; onethen passes to rings by bringing in multiplication, and further tofields with division. The common four-function calculator provides thefour functions of the field of reals.

The abstract concept of group in full generality is defined not interms of a set of numbers but rather as an arbitrary set equipped witha binary operation \(xy\), a unary inverse \(x^{-1}\) of thatoperation, and a unit \(e\) satisfying certain equationscharacteristic of groups. One striking novelty with groups notencountered in everyday elementary algebra is that theirmultiplication need not be abelian: \(xy\) and \(yx\) can bedifferent! For example the group \(S_3\) of the six possiblepermutations of three things is not abelian, as can be seen byexchanging adjacent pairs of letters in the worddan. If youexchange the two letters on the left before the two on the right yougetadn and thenand, but if you perform theseexchanges in the other order you getdna and thennda instead ofand. Likewise the group of43,252,003,274,489,856,000 operations on Rubik’s cube and theinfinite group \(SO(3)\) of rotations of the sphere are not abelian,though the infinite group \(SO(2)\) of rotations of the circle isabelian. Quaternion multiplication and matrix multiplication is alsononcommutative. Abelian groups are often called additive groups andtheir group operation is referred to as addition \(x+y\) rather thanmultiplication \(xy\).

Groups, rings and fields only scratch the surface of abstract algebra.Vector spaces and more generally modules are restricted forms of ringsin which the operands of multiplication are required to be a scalarand a vector. Monoids generalize groups by dropping inverse; forexample the natural numbers form a monoid but not a group for want ofnegation. Boolean algebras abstract the algebra of sets. Latticesgeneralize Boolean algebras by dropping complement and thedistributivity laws.

A number of branches of mathematics have found algebra such aneffective tool that they have spawned algebraic subbranches. Algebraiclogic, algebraic number theory, and algebraic topology are all heavilystudied, while algebraic geometry and algebraic combinatorics haveentire journals devoted to them.

Algebra is of philosophical interest for at least two reasons. Fromthe perspective of foundations of mathematics, algebra is strikinglydifferent from other branches of mathematics in both its domainindependence and its close affinity to formal logic. Furthermore thedichotomy between elementary and abstract algebra reflects a certainduality in reasoning that Descartes, the inventor of CartesianDualism, would have appreciated, wherein the former deals with thereasoning process and the latter that which is reasoned about, asrespectively the mind and body of mathematics.

Algebra has also played a significant role in clarifying andhighlighting notions of logic, at the core of exact philosophy formillennia. The first step away from the Aristotelian logic ofsyllogisms towards a more algebraic form of logic was taken by Boolein an 1847 pamphlet and subsequently in a more detailed treatise,The Laws of Thought, in 1854. The dichotomy betweenelementary algebra and modern algebra then started to appear in thesubsequent development of logic, with logicians strongly dividedbetween the formalistic approach as espoused by Frege, Peano, andRussell, and the algebraic approach followed by C. S. Peirce,Schroeder, and Tarski.

• 1. Elementary Algebra
  • 1.1 Formulas
  • 1.2 Laws
  • 1.3 Word problems
  • 1.4 Cartesian geometry
• 2. Abstract Algebra
  • 2.1 Semigroups
  • 2.2 Groups
  • 2.3 Rings
  • 2.4 Fields
  • 2.5 Applications
• 3. Universal Algebra
  • 3.1 Concepts
  • 3.2 Equational Logic
  • 3.3 Birkhoff’s Theorem
• 4. Linear Algebra
  • 4.1 Vector Spaces
  • 4.2 Associative Algebras
• 5. Algebraization of mathematics
  • 5.1 Algebraic geometry
  • 5.2 Algebraic number theory
  • 5.3 Algebraic topology
  • 5.4 Algebraic logic
• 6. Free algebras
  • 6.1 Free monoids and groups
  • 6.2 Free rings
  • 6.3 Free combinatorial structures
  • 6.4 Free logical structures
  • 6.5 Free algebras categorially
• Bibliography
• Academic Tools
• Other Internet Resources
• Related Entries

1. Elementary algebra

Elementary algebra deals with numerical terms, namelyconstants 0, 1, 1.5, \(\pi\),variables \(x,y,\ldots\), and combinations thereof built withoperationssuch as \(+\), \(-\), \(\times\) , \(\div\) , \(\sqrt{\phantom{x}}\),etc. to form such terms as \(x+1, x\times y\) (standardly abbreviated\(xy\)), \(x + 3y\), and \(\sqrt{x}\).

Terms may be used on their own informulas such as \(\pir^2\), or in equations serving aslaws such as \(x+y = y+x\),or asconstraints such as \(2x^2 -x+3 = 5x+1\) or \(x^2 + y^2= 1\).

Laws are always true; while they have the same form as constraintsthey constrain only vacuously in that every valuation of theirvariables is a solution. The constraint \(x^2 +y^2 = 1\) has acontinuum of solutions forming ashape, in this case a circleof radius 1. The constraint \(2x^2 -x+3 = 5x-1\) has two solutions,\(x = 1\) or 2, and may be encountered in the solution ofwordproblems, or in the determination of the points of intersectionof two curves such as the parabola \(y = 2x^2 -x+3\) and the line \(y= 5x-1\).

1.1 Formulas

A formula is a term used in the computation of values by hand ormachine. Although some attributes of physical objects lend themselvesto direct measurement such as length and mass, others such as area,volume, and density do not and must be computed from more readilyobserved values with the help of the appropriate formula. For examplethe area of a rectangle \(L\) inches long by \(W\) inches wide isgiven by the formula \(LW\) in units of square inches, the volume of aball of radius \(r\) is \(4\pi r^3 /3\), and the density of a solid ofmass \(M\) and volume \(V\) is given by \(M/V\).

Formulas may be combined to give yet more formulas. For example thedensity of a ball of mass \(M\) and radius \(r\) can be obtained bysubstituting the above formula for the volume of a ball for \(V\) inthe above formula for the density of a solid. The resulting formula\(M/(4\pi r^3 /3)\) is then the desired density formula.

1.2 Laws

Laws or identities are equations that hold for all applicable valuesof their variables. For example the commutativity law

holds for all real values of \(x\) and \(y\). Likewise theassociativity law

holds for all real values of \(x, y\) and \(z\). On the other hand,while the law \(x/(y/z) = zx/y\) holds for all numerical values of\(x\), it holds only for nonzero values of \(y\) and \(z\) in order toavoid the illegal operation of division by zero.

When a law holds for all numerical values of its variables, it alsoholds for all expression values of those variables. Setting \(x = M, y= 4\pi r^3\), and \(z = 3\) in the last law of the preceding paragraphyields \(M/(4\pi r^3 /3) = 3M/(4\pi r^3)\). The left hand side beingour density formula from the preceding section, it follows from thisinstance of the above law that its right hand side is an equivalentformula for density in the sense that it gives the same answers as theleft hand side. This new density formula replaces one of the twodivisions by a multiplication.

1.3 Word problems

If Xavier will be three times his present age in four years time, howold is he? We can solve thisword problem using algebra byformalizing it as the equation \(3x = x + 4\) where \(x\) isXavier’s present age. The left hand side expresses three timesXavier’s present age, while the right hand side expresses hisage in four years’ time.

A general rule for solving such equations is that any solution to itis also a solution to the equation obtained by applying some operationto both sides. In this case we can simplify the equation bysubtracting \(x\) from both sides to give \(2x = 4\), and thendividing both sides by 2 to give \(x = 2\). So Xavier is now two yearsold.

If Xavier is twice as old as Yvonne and half the square of her age,how old is each? This is more complicated than the previous example inthree respects: it has more unknowns, more equations, and terms ofhigher degree. We may take \(x\) for Xavier’s age and \(y\) forYvonne’s age. The two constraints may be formalized as theequations \(x = 2y\) and \(x = y^2 /2\), the latter being of degree 2orquadratic.

Since both right hand sides are equal to \(x\) we can infer \(2y = y^2/2\). It is tempting to divide both sides by \(y\), but what if \(y =0\)? In fact \(y = 0\) is one solution, for which \(x = 2y = 0\) aswell, corresponding to Xavier and Yvonne both being newborns. Settingthat solution to one side we can now look for solutions in which \(y\)is not zero by dividing both sides by \(y\). This yields \(y = 4\), inwhich case \(x = 2y = 8\). So now we have a second solution in whichXavier is eight years old and Yvonne four.

In the absence of any other information, both solutions arelegitimate. Had the problem further specified that Yvonne was atoddler, or that Xavier was older than Yvonne, we could have ruled outthe first solution.

1.4 Cartesian geometry

Lines, circles, and other curves in the plane can be expressedalgebraically usingCartesian coordinates, named for itsinventor Rene Descartes. These are defined with respect to adistinguished point in the plane called theorigin, denoted\(O\). Each point is specified by how far it is to the right of andabove \(O\), written as a pair of numbers. For example the pair (2.1,3.56) specifies the point 2.1 units to the right of \(O\), measuredhorizontally, and 3.56 units above it, measured vertically; we call2.1 the \(x\) coordinate and 3.56 the \(y\) coordinate of that point.Either coordinate can be negative: the pair \((-5, -1)\) correspondsto the point 5 units to the left of \(O\) and 1 unit below it. Thepoint \(O\) itself is coordinatized as (0, 0).

Lines. Given an equation in variables \(x\) and \(y\), apoint such as (2, 7) is said to be asolution to thatequation when setting \(x\) to 2 and \(y\) to 7 makes the equationtrue. For example the equation \(y = 3x+5\) has as solutions thepoints (0, 5), (1, 8), (2, 11), and so on. Other solutions include(.5, 6.5), (1.5, 9.5), and so on. The set of all solutions constitutesthe unique straight line passing through (0, 5) and (1, 8). We thencall \(y = 3x+5\) theequation of that line.

Circles. By Pythagoras’s Theorem the square of thedistance between two points \((x, y)\) and \((x', y')\) is given by\((x'-x)^2 +(y'-y)^2\). As a special case of this, the square of thedistance of the point \((x, y)\) to the origin is \(x^2 +y^2\). Itfollows that those point at distance \(r\) from the origin are thesolutions in \(x\) and \(y\) to the equation \(x^2 +y^2 = r^2\). Butthese points are exactly those forming the circle of radius \(r\)centered on \(O\). We identify this equation with this circle.

Varieties The roots of any polynomial in \(x\) and \(y\) forma curve in the plane called aone-dimensional variety ofdegree that of the polynomial. Thus lines are of degree 1,being expressed as polynomials \(ax+by+c\), while circles centered on\((x', y')\) are of degree 2, being expressed as polynomials\((x-x')^2 +(y-y')^2 -r^2\). Some varieties may contain no points, forexample \(x^2 +y^2 +1\), while others may contain one point, forexample \(x^2 +y^2\) having the origin as its one root. In generalhowever a two-dimensional variety will be a curve. Such a curve maycross itself, or have a cusp, or even separate into two or morecomponents not connected to each other.

Space The two-dimensional plane is generalized tothree-dimensional space by adding to the variables \(x\) and \(y\) athird variable \(z\) corresponding to the third dimension. Theconventional orientation takes the first dimension to run from west toeast, the second from south to north, and the third from below toabove. Points are then triples, for example the point \((2, 5, -3)\)is 2 units to the east of the origin, 5 units to the north of it, and3 units below it.

Planes and spheres. These are the counterparts in space oflines and circles in the plane. An equation such as \(z = 3x + 2y\)defines not a straight line but rather a flat plane, in this case theunique plane passing through the points (0, 1, 2), (1, 0, 3), and (1,1, 5). And the sphere of radius \(r\) centered on the origin is givenby \(x^2 +y^2 +z^2 = r^2\). The roots of a polynomial in \(x, y\) and\(z\) form a surface in space called a two-dimensional variety, ofdegree that of the polynomial, just as for one-dimensional varieties.Thus planes are of degree 1 and spheres of degree 2.

These methods generalize to yet higher dimensions by adding yet morevariables. Although the geometric space we experience physically islimited to three dimensions, conceptually there is no limit to thenumber of dimensions of abstract mathematical space. Just as a line isa one-dimensional subspace of the two-dimensional plane, and a planeis a two-dimensional subspace of three-dimensional space, eachspecifiable with an equation, so is ahyperplane athree-dimensional subspace of four-dimensional space, also specifiablewith an equation such as \(w = 2x - 7y + z\).

2. Abstract Algebra

Elementary algebra fixes some domain, typically the reals or complexnumbers, and works with the equations holding within that domain.Abstract ormodern algebra reverses this picture byfixing some set \(A\) of equations and studying those domains forwhich those equations are identities. For example if we take the setof all identities expressible with the operations of addition,subtraction, and multiplication and constants 0 and 1 that hold forthe integers, then the algebras in which those equations holdidentically are exactly the commutative rings with identity.

Historically the term modern algebra came from the title of the firstthree editions of van der Waerden’s classic text of that name,renamed simply “Algebra” for its fourth edition in 1955.Volume 1 treated groups, rings, general fields, vector spaces, wellorderings, and real fields, while Volume 2 considered mainly linearalgebra, algebras (as vector spaces with a compatible multiplication),representation theory, ideal theory, integral algebraic elements,algebraic functions, and topological algebra. On the one hand modernalgebra has since gone far beyond this curriculum, on the other thisconsiderable body of material is already more than what can be assumedas common knowledge among graduating Ph.D. students in mathematics,for whom the typical program is too short to permit mastering all thismaterial in parallel with focusing on their area ofspecialization.

A core feature of abstract algebra is the existence of domains wherefamiliar laws fail to hold. A striking example is commutativity ofmultiplication, which as we noted in the introduction need not holdfor the multiplication of an arbitrary group, even so simple a groupas the six permutations of three letters.

2.1 Semigroups

We begin with the concept of a binary operation on a set \(X\), namelya function \(f: X^2 \rightarrow X\) such that \(f(x, y)\) is anelement of \(X\) for all elements \(x, y\) of \(X\). Such an operationis said to beassociative when it satisfies \(f(f(x, y), z) =f(x, f(y, z))\) for all \(x, y, z\) in \(X\).

Asemigroup is a set together with an associative operation,called themultiplication of the semigroup and notated \(xy\)rather than \(f(x, y)\).

The product \(xx\) of an element with itself is denoted \(x^2\).Likewise \(xxx\) is denoted \(x^3\) and so on.

Concatenation \(uv\) of words \(u, v\) is associative because when aword is cut into two, the concatenation of the two parts is theoriginal word regardless of where the cut is made. The concatenationofal andgebra is the same as thatofalgeb andra, illustratingassociativity of concatenation for the case \(x = \)al, \(y =\)geb, \(z =\)ra.

Composition \(f\cdot g\) of two functions \(f\) and \(g\) isassociative via the reasoning

for all \(x\) in \(X\), whence \(f\cdot(g\cdot h) = (f\cdot g)\cdoth\).

A semigroup \(H\) is asubsemigroup of a semigroup \(G\) when\(H\) is a subset of \(G\) and the multiplication of \(G\) restrictedto \(H\) coincides with that of \(H\). Equivalently a subsemigroup of\(G\) is a subset \(H\) of \(G\) such that for all \(x, y\) in \(H,xy\) is in \(H\).

A binary operation is calledcommutative when it satisfies\(f(x, y) = f(y, x)\) for all \(x, y\) in \(X\). Acommutativesemigroup is a semigroup whose operation is commutative. All theexamples so far have been of noncommutative semigroups. The followingillustrate the commutative case.

An element \(x\) of \(X\) is aleft identity for \(f\) when\(f(x, y) = y\) for all \(y\) in \(X\), and aright identitywhen \(f(y, x) = y\) for all \(y\) in \(X\). Anidentity for\(f\) is an element that is both a left identity and a right identityfor \(f\). An operation \(f\) can have only one identity, because when\(x\) and \(y\) are identities they are both equal to \(f(x,y)\).

Amonoid is a semigroup containing an identity for themultiplication of the semigroup, notated 1.

A monoid \(H\) is asubmonoid of a monoid \(G\) when it is asubsemigroup of \(G\) that includes the identity of \(G\).

2.2 Groups

When two elements \(x, y\) of a monoid satisfy \(xy = 1\) we say that\(x\) is the left inverse of \(y\) and \(y\) is the right inverse of\(x\). An element \(y\) that is both a left and right inverse of \(x\)is called simply an inverse of \(x\).

Agroup is a monoid every element of which has aninverse.

Asubgroup of a group \(G\) is a submonoid of \(G\) closedunder inverses. The monoids of natural numbers and of even integersare both submonoids of the monoid of integers under addition, but onlythe latter submonoid is a subgroup, being closed under negation,unlike the natural numbers.

Anabelian group is a group whose operation is commutative.The group operation of an abelian group is conventionally referred toas addition rather than multiplication, and abelian groups aresometimes called additive groups.

Acyclic group is a group \(G\) with an element \(g\) suchthat every element of \(G\) is of the form \(g^i\) for some positiveinteger \(i\). Cyclic groups are abelian because \(g^{i}g^j = g^{i +j} = g^j g^{i}\). The group of integers under addition, and the groupsof integers mod \(n\) for any positive integer \(n\), all form cyclicgroups, with 1 as a generator in every case. All cyclic groups areisomorphic to one of these. There are always other generators when thegroup is of order 3 or more, for example \(-1\), and for groups ofprime order every nonzero element is a generator.

2.3 Rings

Aring is an abelian group that is also a monoid by virtue ofhaving a second operation, called themultiplication of thering. Zeroannihilates, meaning that \(0x = x0 = 0\).Furthermore multiplication distributes over addition (the groupoperation) in both arguments. That is, \(x(y+z) = xy + xz\) and\((x+y)z = xz + yz\).

In all but the last example, the integers (other than the integer\(n\) giving the size of the matrices) may be replaced by any of therationals, the reals, or the complex numbers. When replacing theintegers with the reals the fourth example becomes simply the ring ofreals because even if \(b\) is zero \(a\) can be any real. Howeverwhen replacing with the rational numbers the ring includes therationals, but is more than that because \(\sqrt{2}\) is irrational,yet it does not contain for example \(\sqrt{3}\).

2.4 Fields

Afield is a ring for which the multiplicative monoid ofnonzero ring elements is an abelian group. That is, multiplicationmust be commutative, and every nonzero element \(x\) must have areciprocal \(1/x\).

The last example does not generalize directly to other moduli. Howeverfor any modulus that is a power \(p^n\) of a prime, it can be shownthat there exists a unique multiplication making the group \(Z_{p^n}\)a ring in a way that makes the nonzero elements of the ring a cyclic(and therefore abelian) group under the multiplication, and hencemaking the ring a field. The fields constructed in this way are theonly finite fields.

2.5 Applications

Why study entire classes? Well, consider for example the set \(Z\) ofintegers along with the binary operation of addition \(x+y\), theunary operation of negation \(-x\), and the constant 0. Theseoperations and the constant satisfy various laws such as \(x+(y+z) =(x+y)+z, x+y = y+x, x+0 = x\), and \(x+(-x) = 0\). Now consider anyother algebra with operations that not only have the same names butalso satisfy the same laws (and possibly more), called amodel of those laws. Such an algebra could serve any of thefollowing purposes.

(i) It could tell us to what extent the equational laws holding of theintegers characterize the integers. Since the set \(\{0, 1\}\) ofintegers mod 2 under addition and negation satisfies all the laws thatthe integers do, we immediately see that no single equational propertyof the integers tells us that there are infinitely many integers. Onthe other hand any finite model of the equational theory of theintegers necessarily satisfies some law that the integers don’tsatisfy, in particular the law \(x+x+\ldots +x = 0\) where the numberof \(x\)\(s\) on the left hand side is the size of themodel. Since the equational theory of the integers contains no suchlaw we can tell from its theory as a whole that the integers must bean infinite set. On the other hand the rational numbers under additionand negation satisfy exactly the same equational properties as theintegers, so this theory does not characterize the algebra of integersunder addition and subtraction with sufficient precision todistinguish it from the rationals.

(ii) It could provide us with a useful new domain that can besubstituted for the integers in any application depending only onequational properties of the integers, but which differs from theintegers in other (necessarily nonequational) useful respects. Forexample the rationals, which satisfy the same laws as we just noted,differ in having thedensity property, that between any tworationals there lies another rational. Another difference is that itsupports division: whereas the ratio of two integers is usually not aninteger, the ratio of two rationals is always a rational. The realsalso satisfy the same equations, and like the rationals are dense andsupport division. Unlike the rationals however the reals have thecompleteness property, that the set of all upper bounds ofany nonempty set of reals is either empty or has a least member,needed for convergent sequences to have a limit to converge to.

This idea extends to other operations such as multiplication anddivision, as with fields. A particularly useful case of such ageneralization is given by the use of complex numbers in Cartesiangeometry. When \(x\) and \(y\) range over the field of reals, \(x^2+y^2 =1\) describes the ordinary Euclidean circle in two dimensions,but when the variables range over the complex numbers this equationdescribes the complex counterpart of the circle, visualizable as atwo-dimensional surface embedded in four real dimensions (regardingthe complex plane as having two real dimensions). Or if the variablesrange over the integers mod 7, which form a field under the usualarithmetic operations mod 7, the circle consists of eight points,namely \((\pm 1, 0), (0, \pm 1)\), and \((\pm 2, \pm 2)\). Certaintheorems about the Euclidean circle provable purely algebraicallyremain provable about these other kinds of circles because all theequations on which the proof depends continue to hold in these otherfields, for example the theorem that a line intersects a circle in atmost two points.

(iii) It could help us decide whether some list of equational lawsintended to axiomatize the integers iscomplete in the sensethat any equation holding of the integers follows from the laws inthat list. If some structure satisfies all the axioms in the list, butnot some other equation that holds of the integers, then we have awitness to the incompleteness of the axiomatization. If on the otherhand we can show how to construct any algebra satisfying the axiomsfrom the algebra of integers, limiting ourselves only to certainalgebraic constructions, then by a theorem of Birkhoff applicable tothose constructions we can infer that the axiomatization iscomplete.

(iv) It could give another of way of defining a class, besides thestandard way of listing axioms. In the case at hand, the class of allalgebras with a constant, a unary operation, and a binary operation,satisfying all the laws satisfied by the integers, is exactly theclass of abelian groups.

3. Universal Algebra

Universal algebra is the next level of abstraction after abstractalgebra. Whereas elementary algebra treats equational reasoning in aparticular algebra such as the field of reals or the field of complexnumbers, and abstract algebra studies particular classes of algebrassuch as groups, rings, or fields, universal algebra studies classes ofclasses of algebras. Much as abstract algebra numbers groups, rings,and fields among its basic classes, so does universal algebra countvarieties, quasivarieties, and elementary classes among its basicclasses of classes.

Amodel of a theory is a structure for which all theequations of that theory are identities. Terms are built up fromvariables and constants using the operations of the theory. Anequation is a pair of terms; it is satisfied by an algebra when thetwo terms are equal under all valuations of (assignments of values to)the \(n\) variables appearing in the terms, equivalently when theydenote the same \(n\)-ary operation. A quasiequation is a pairconsisting of a finite set of equations, called the premises orantecedents, and another equation, the conclusion; it is satisfied byan algebra when the two terms of the conclusion are equal under allvaluations of the \(n\) variables appearing in the terms satisfyingthe premises. A first order formula is a quantified Booleancombination of relational terms.

Avariety is the class of all models of a set of equations. Aquasivariety is the class of all models of a set ofquasiequations. Anelementary class is the class of allmodels of a set of first-order formulas.

Quasivarieties have received much less attention than either varietiesor elementary classes, and we accordingly say little about them here.Elementary classes are treated in sufficient depth elsewhere in thisencyclopedia that we need not consider them here. We therefore focusin this section on varieties.

Abelian groups, groups, rings, and vector spaces over a given fieldall form varieties.

A central result in this area is the theorem that a lattice arises asthe lattice of subalgebras of some algebra if and only if it arises asthe lattice of congruences on some algebra. Lattices of this sort arecalledalgebraic lattices. When the congruences of an algebrapermute, its congruence lattice is modular, a strong conditionfacilitating the analysis of finite algebras in particular.

3.1 Concepts

Familiar theorems of number theory emerge in algebraic form foralgebras. An algebra \(A\) is called directly irreducible orsimple when its lattice of congruences is the two-elementlattice consisting of \(A\) and the one-element algebra, parallelingthe notion of prime number \(p\) as a number whose lattice of divisorshas two elements \(p\) and 1. However the counterpart of thefundamental theorem of arithmetic, that every positive integer factorsuniquely as a product of primes, requires a more delicate kind ofproduct than direct product. Birkhoff’s notion of subdirectproduct enabled him to prove the Subdirect Representation Theorem,that every algebra arises as the subdirect product of its subdirectlyirreducible quotients. Whereas there are many subdirectly irreduciblegroups, the only subdirectly irreducible Boolean algebra is theinitial or two-element one, while the subdirectly irreducible ringssatisfying \(x^n = x\) for some \(n \gt 1\) are exactly the finitefields.

Another central topic is duality: Boolean algebras are dual to Stonespaces, complete atomic Boolean algebras are dual to sets,distributive lattices with top and bottom are dual to partiallyordered sets, algebraic lattices are dual to semilattices, and so on.Duality provides two ways of looking at an algebra, one of which mayturn out to be more insightful or easier to work with than the otherdepending on the application.

The structure of varieties as classes of all models of some equationaltheory is also of great interest. The earliest result in this area isBirkhoff’s theorem that a class of algebras is a variety if andonly if it is closed under formation of quotients (homomorphicimages), subalgebras, and arbitrary (including empty and infinite)direct products. This “modern algebra” result constitutesa completeness theorem for equational logic in terms of its models.Its elementary counterpart is the theorem that the equational theorieson a free algebra \(F(V)\), defined as the deductively closed sets ofequations that use variables from \(V\), are exactly its substitutivecongruences.

A locally finite variety is one whose finitely generated free algebrasare finite, such as pointed sets, graphs (whether of the directed orundirected variety), and distributive lattices. A congruencepermutable variety is a variety all of whose algebras are congruencepermutable. Maltsev characterized these in terms of a necessary andsufficient condition on their theories, namely that \(F\)(3) containan operation \(t(x, y, z)\) for which \(t(x, x, y) = t(y, x, x) = y\)are in the theory. Analogous notions are congruence distributivity andcongruence modularity, for which there exist analogous syntacticcharacterizations of varieties of algebras with these properties. Amore recently developed power tool for this area is McKenzie’snotion of tame congruences, facilitating the study of the structure offinite algebras.

Within the algebraic school, varieties have been defined with theunderstanding that the operations of a signature form a set. Insightsfrom category theory, in particular the expression of a variety as amonad, defined as a monoid object in the category \(C^C\) ofendofunctors of a category \(C\) (Set in the case of ordinaryuniversal algebra) indicate that a cleaner and more general notion ofvariety is obtained when the operations can form a proper class. Forexample the important classes of complete semilattices, CSLat, andcomplete atomicBoolean algebras, CABA, form varieties only with this broader notion of signature. Inthe narrow algebraic sense of variety, the dual of a variety can neverbe a variety, whereas in the broader monadic notion of variety, thevariety Set of sets is dual to CABA while CSLat is self-dual.

3.2 Equational Logic

Axiom systems. Identities can also be used to transformequations to equivalent equations. When those equations are themselvesidentities for some domain, the equations they are transformed intoremain identities for that domain. One can therefore start from somefinite set of identities and manufacture an unlimited number of newidentities from them.

For example if we start from just the two identities \((x+y)+z =x+(y+z)\) and \(x+y = y+x\), we can obtain the identity \((w+x)+(y+z)= (w+y)+(x+z)\) via the following series of transformations.

This process of manufacturing new identities from old is calleddeduction. Any identity that can be generated by deductionstarting from a given set \(A\) of identities is called aconsequence of \(A\). The set of all consequences of \(A\) iscalled thedeductive closure of \(A\). We refer to \(A\) asanaxiomatization of its deductive closure. A set that is itsown deductive closure is said to bedeductively closed. It isstraightforward to show thata set is deductively closed if andonly if it is the deductive closure of some set.

Anequational theory is a deductively closed set ofequations, equivalently the set of all consequences of some set \(A\)of equations. Every theory always has itself as its ownaxiomatization, but it will usually also have smaller axiomatizations.A theory that has a finite axiomatization is said to befinitelybased orfinitely axiomatizable.

Effectiveness. Finitely based theories canbe effectively enumerated. That is, given a finite set \(A\) ofequations, one can write a computer program that prints consequencesof \(A\) for ever in such a way that every consequence of \(A\) willappear at some finite position in the infinite list of allconsequences. The same conclusion obtains when we weaken therequirement that \(A\) be finite to merely that it can be effectivelyenumerated. That is, if the axiomatization is effectively enumerableso is its deductive closure.

(In reconciling the finite with the infinite, bear in mind that if welist all the natural numbers 0, 1, 2, … in order, we obtain aninfinite list every member of which is only finitely far from thebeginning, and also has a well-defined predecessor (except for 0) andsuccessor. Only if we attempt to pad this list out at the“end” with infinite numbers does this principle breakdown.

One way to visualize there being an “end” that could havemore elements beyond it is to consider the rationals of the form\(1/n\) for all nonzero integers \(n\), in increasing order. This liststarts out \(-1/1, -1/2, -1/3,\ldots\) and after listing infinitelymany negative rationals of that form, with no greatest such, switchesover to positive rationals, with no first such, finally ending with1/3, 1/2, 1/1. The entire list is discrete in the sense that everyrational except the endpoints \(-1/1\) and 1/1 has a well-definedpredecessor and successor in this subset of the rationals, unlike thesituation for the set of all rationals between \(-1/1\) and \(1/1\).This would no longer be the case were we to introduce the rational 0“in the middle”, which would have neither a predecessornor a successor.)

Equational Logic. Our informal account ofdeduction can be formalized in terms of five rules for producing newidentities from old. In the following, \(s\) and \(t\) denotearbitrary terms.

(R1)

From nothing infer \(t = t\).

(R2)

From \(s = t\) infer \(t = s\).

(R3)

From \(s = t\) and \(t = u\) infer \(s = u\).

(R4)

From \(s_1 = t_1, s_2 = t_2 , \ldots ,s_n = t_n\) infer \(f(s_1,s_2 , \ldots ,s_n)= f(t_1, t_2 , \ldots ,t_n)\), where \(f\) is an\(n\)-ary operation.

(R5)

From \(s = t\) infer \(s' = t'\) where \(s'\) and \(t'\) are theterms resulting from consistently substituting terms for variables in\(s\) and \(t\) respectively.

“Consistently” in this context means that if a term issubstituted for one occurrence of a given variable, the same term mustbe substituted for all occurrences of that variable in both \(s\) and\(t\). We could not for example appeal solely toR5 tojustify substituting \(u+v\) for \(x\) in the left hand side of \(x+y= y+x\) and \(v+u\) for \(x\) in the right hand side, though someother rule might permit it.

An equational theory as a set of pairs of terms amounts to a binaryrelation on the set of all terms. RulesR1–R3correspond to respectively reflexivity, symmetry, and transitivity ofthis binary relation, \(i.e\). these three rules assert that anequational theory is anequivalence relation. RuleR4 expresses the further property that this binary relationis acongruence. RuleR5 further asserts that therelation is a substitutive congruence. It can be shown that a binaryrelation on the set of terms is an equational theory if and only if itis a substitutive congruence. These five rules therefore completelyaxiomatize equational logic in the sense that every consequence of aset \(A\) of equations can be produced from \(A\) via finitely manyapplications of these five rules.

3.3 Birkhoff’s Theorem

A variety is by definition the class of models of some equationaltheory. In 1935 Birkhoff provided an equivalent characterization ofvarieties as any class closed under quotients (homomorphic images),direct products, and subalgebras. These notions are defined asfollows.

Given two algebras \((X, f_1 , \ldots f_k)\) and \((Y, g_1 , \ldotsg_k)\), ahomomorphism \(h: (X, f_1 , \ldots f_k) \rightarrow(Y, g_1 , \ldots g_k)\) is a function \(h: X \rightarrow Y\)satisfying \(h(f_i (x_0 , \ldots ,x_{n_{ i}-1 })) = g_i (h(x_0),\ldots ,h(x_{n_{ i}-1 })))\) for each \(i\) from 1 to \(k\) where\(n_i\) is the arity of both \(f_i\) and \(g_i\).

Asubalgebra of an algebra is a set of elements of thealgebra closed under the operations of the algebra.

Let \(I\) be an arbitrary set, which may be empty, finite, orinfinite. Afamily \(\langle A_{i}\rangle_{i\in I}\) ofalgebras \((X_i, f_{1}^i,\ldots, f_k^i)\) indexed by \(I\) consists ofone algebra \(A_i\) for each element \(i\) of \(I\). We define thedirect product \(\Pi A_i\) (or \(\Pi_{i\in I} A_i\) in full)of such a family as follows.

The underlying set of \(\Pi A_i\) is the cartesian product \(\Pi X_i\)of the underlying sets \(X_i\), and consists of those \(I\)-tupleswhose \(i\)-th element is some element of \(X_i\). (\(I\) may even beuncountable, but in this case the nonemptiness of \(\Pi X_i\) as aconsequence of the nonemptiness of the individual \(X_i\)’s isequivalent to the axiom of choice. This should be kept in mind for anyconstructive applications of Birkhoff’s theorem.)

The \(j\)-th operation of \(\Pi A_i\), of arity \(n_j\), takes an\(n_j\)-tuple \(t\) of elements of \(\Pi X_i\) and produces the\(I\)-tuple \(\langle f_{j}^i(t_{1}^i , \ldots t_{n_{ j}}^i)\rangle_{i\in I}\) where \(t_k^i\) is the \(i\)-th component ofthe \(k\)-th component of \(t\) for \(k\) from 1 to \(n_j\).

Given two algebras \(A\), \(B\) and a homomorphism \(h: A \rightarrowB\), thehomomorphic image \(h(A)\) is the subalgebra of\(B\) consisting of elements of the form \(h(a)\) for \(a\) in\(A\).

Given a class \(C\) of algebras, we write \(P(C)\) for the class ofall algebras formed as direct products of families of algebras of \(C,S(C)\) for the class of all subalgebras of algebras of \(C\), and\(H(C)\) for the class of all homomorphic images of algebras of\(C\).

It is relatively straightforward to show that any equation satisfiedby all the members of \(C\) is also satisfied by all the members of\(P(C), S(C)\), and \(H(C)\). Hence for a variety \(V, P(V) = S(V) =H(V)\).

Birkhoff’s theorem is the converse: for any class \(C\) suchthat \(P(C) = S(C) = H(C), C\) is a variety. In fact the theorem isslightly stronger: for any class \(C\),HSP\((C)\) is avariety. That is, to construct all the models of the theory of \(C\)it suffices to close \(C\) first under direct products, then undersubalgebras, and finally under homomorphic images; that is, laterclosures do not compromise earlier ones provided \(P, S\), and \(H\)are performed in that order.

A basic application of Birkhoff’s theorem is in proving thecompleteness of a proposed axiomatization of a class \(C\). Given anarbitrary model of the axioms, it suffices to show that the model canbe constructed as the homomorphic image of a subalgebra of a directproduct of algebras of \(C\).

This completeness technique complements the completeness observed inthe previous section for the rules of equational logic.

4. Linear Algebra

4.1 Vector Spaces

Sibling to groups, rings, and fields is the class ofvectorspaces over any given field, constituting the universes of linearalgebra. Vector spaces lend themselves to two opposite approaches:axiomatic or abstract, and synthetic or concrete. The axiomaticapproach takes fields (whence rings, whence groups) as a prerequisite;it first defines a notion of \(R\)-module as an abelian group with ascalar multiplication over a given ring \(R\), and then defines avector space to be an \(R\)-module for which \(R\) is a field. Thesynthetic approach proceeds via the familiar representation of vectorspaces over the reals as \(n\)-tuples of reals, and of lineartransformations from \(m\)-dimensional to \(n\)-dimensional vectorspaces as \(m\times n\) matrices of reals. For the full generality ofvector spaces including those of infinite dimension, \(n\) need not belimited to finite numbers but can be any cardinal.

The abstract approach, as adopted by such classical texts as Mac Laneand Birkhoff, has a certain purist appeal and is ideally suited tomathematics majors. The concrete approach has the benefit of beingable to substitute calculus or less for groups-rings-fields as aprerequisite, suiting it to service courses for scientists andengineers needing only finite-dimensional matrix algebra, which enjoysenormous practical applicability. Linear algebra over other fields, inparticular finite fields, is used in coding theory, quantum computing,etc., for which the abstract approach tends to be better suited.

For any field \(F\), up to isomorphism there is exactly one vectorspace over \(F\) of any given finite dimension. This is a theorem inthe abstract approach, but is an immediate consequence of therepresentation in the concrete approach (the theorem is used inrelating the two approaches).

Another immediate consequence of the concrete approach is duality forfinite-dimensional vector spaces over \(F\). To every vector space\(V\), of any dimension, corresponds its dual space \(V^*\) comprisedof thefunctionals on \(V\), defined as the lineartransformations \(f: V\rightarrow F\), viewing the field \(F\) as theone-dimensional vector space. The functionals form a vector spaceunder coordinatewise addition \((f+g)(u) = f(u)+g(u)\) andmultiplication \((xf)(u) = x(f(u))\) by any scalar \(x\) in \(F\), andwe take \(V^*\) to be that space. This operation on vector spacesextends to the linear transformations \(f: U\rightarrow V\) as \(f^* :V^*\rightarrow U^*\) defined such that \(f\) maps each functional \(g:V\rightarrow F\) to \(g\cdot f: U\rightarrow F\). Repeating thisoperation produces a vector space that, in the finite-dimensionalcase, is isomorphic to \(V\), that is, \(V \cong V^{**}\), making theoperation an involution. The essence of duality for finite-dimensionalvector spaces resides in its involutary nature along with the reversalof the linear transformations.

This duality is easily visualized in the concrete approach by viewinglinear transformations from \(U\) to \(V\) as \(m\times n\) matrices.The duality simply transposes the matrices while leaving the machineryof matrix multiplication itself unchanged. It is then immediate thatthis operation is an involution that reverses maps—the \(m\timesn\) matrix linearly transforming an \(n\)-dimensional space \(U\) toan \(m\)-dimensional one \(V\) transposes to an \(n\times m\) matrixlinearly transforming the \(m\)-dimensional space \(V^*\) to the\(n\)-dimensional space \(U^*\).

4.2 Associative Algebras

The linear transformations \(f: V\rightarrow V\) on a vector space\(V\) can be added, subtracted, and multiplied by scalars, pointwisein each case, and hence form a vector space. When the space has finitedimension \(n\), the linear transformations are representable as\(n\times n\) matrices.

In addition they can be composed, whence they form a vector spaceequipped with a bilinear associative operation, namely composition. Inthe finite-dimensional case, composition is just the usual matrixproduct. Vector spaces furnished with such a product constituteassociative algebras. Up to isomorphism, all associativealgebras arise in this way whether of finite or infinite dimension,providing a satisfactory and insightful characterization of the notionin lieu of an axiomatic characterization, not given here.

Well-known examples of associative algebras are the reals, the complexnumbers, and the quaternions. Unlike vector spaces, many nonisomorphicassociative algebras of any given dimension greater than one arepossible.

A class of associative algebras of interest to physicists is that ofthe Clifford algebras. Clifford algebras over the reals (which asvector spaces are Euclidean spaces) generalize complex numbers andquaternions by permitting any number of formal quantities \(e\)analogous to \(i = \sqrt{-1}\) to be adjoined to the field of reals.The common feature of these quantities is that each satisfies either\(e^2 = -1\) or \(e^2 = 1\). Whereas there are a great manyassociative algebras of low dimension, only a few of them arise asClifford algebras. The reals form the only one-dimensional Cliffordalgebra, while the hyperbolic plane, defined by \(e^2 = 1\), and thecomplex plane, defined by \(e^2 = -1\), are the two two-dimensionalClifford algebras. The hyperbolic plane is just the direct square ofthe real field, meaning that its product is coordinatewise, \((a,b)(c, d) = (ac, bd)\), unlike that of the complex plane where itdefined by \((a, b)(c, d) = (ac - bd, ad+bc)\). The twofour-dimensional Clifford algebras are the \(2\times 2\) matrices andthe quaternions. Whereas the \(2\times 2\) matrices contain zerodivisors (nonzero matrices whose product is zero), and so form only aring, the quaternions contain no zero divisors and so form a divisionring. Unlike the complex numbers however, the quaternions do not forma field because their multiplication is not commutative. Complexmultiplication however makes the complex plane a commutative divisionring, that is, a field.

5. Algebraization of mathematics

A number of branches of mathematics have benefited from theperspective of algebra. Each of algebraic geometry and algebraiccombinatorics has an entire journal devoted to it, while algebraictopology, algebraic logic, and algebraic number theory all have strongfollowings. Many other more specialized areas of mathematics havesimilarly benefited.

5.1 Algebraic geometry

Algebraic geometry begins with what we referred to in the introductionas shapes, for example lines \(y = ax +b\), circles \(x^2 +y^2 =r^2\), spheres \(x^2 +y^2 +z^2 = r^2\), conic sections \(f(x, y) = 0\)where \(f\) is a quadratic polynomial in \(x\) and \(y\), quadricsurfaces \(f(x, y, z) = 0\) with \(f\) again quadratic, and so on.

It is convenient to collect the two sides of these equations on theleft so that the right side is always zero. We may then define a shapeorvariety to consist of the roots orzeros of apolynomial, or more generally the common zeros of a set ofpolynomials.

Ordinary analytical or Cartesian geometry is conducted over the reals.Algebraic geometry is more commonly conducted over the complexnumbers, or more generally over any algebraically closed field. Thevarieties definable in this way are calledaffinevarieties.

Sometimes however algebraic closure is not desirable, for example whenworking at the boundary of algebraic geometry and number theory wherethe field may be finite, or the rationals.

Many kinds of objects are characterized by what structure their mapshold invariant. Posets transform via monotone functions, leaving orderinvariant. Algebras transform via homomorphisms, leaving the algebraicstructure invariant. In algebraic geometry varieties transform viaregular \(n\)-aryfunctions \(f: A^n \rightarrowA\), defined as functions that are locally rational polynomials in\(n\) variables. Locally rational means that at each point of thedomain of \(f\) there exists a neighborhood on which \(f\) is theratio of two polynomials, the denominator of which is nonzero in thatneighborhood.

This notion generalizes to regular functions \(f: A^n \rightarrowA^m\) defined as \(m\)-tuples of regular \(n\)-ary functions.

Given two varieties \(V, V'\) in \(A^n\) and \(A^m\) respectively, aregular function from \(A^n\) to \(A^m\) whose restriction to \(V\) isa function from \(V\) to \(V'\) is called aregular function ofvarieties. The category of affine varieties is then defined tohave as its objects all affine varieties and as its morphisms allregular functions thereof.

Polynomials being continuous, one would expect regular functionsbetween varieties to be continuous also. A difficulty arises with theshapes of varieties, where there can be cusps, crossings, and othersymptoms of singularity. What is needed here is a suitable topology bywhich to judge continuity.

The trick is to work not in affine space but itsprojectivespace. To illustrate with Euclidean three-space, its associatedprojective space is the unit sphere with antipodal points identified,forming a two-dimensional manifold. Equivalently this is the space ofall (unoriented) lines through the origin. Given an arbitrary affinespace, its associated projective space is the space of all such lines,understood as a manifold.

The topology on projective space appropriate for algebraic geometry istheZariski topology, defined not by its open sets but ratherby its closed sets, which are taken to be the algebraic sets, namelythose sets constituting the common zeros of a set of homogeneouspolynomials. The crucial theorem is then that regular maps betweenaffine varieties are continuous with respect to the Zariskitopology.

5.2 Algebraic number theory

Algebraic number theory has adopted these generalizations of algebraicgeometry. One class of varieties in particular that has been of greatimportance to number theory is that of elliptical curves.

A celebrated success of algebraic number theory has been AndrewWiles’ proof of Fermat’s so-called “lasttheorem.” This had remained an open problem for over three and ahalf centuries.

5.3 Algebraic topology

Algebraic topology analyzes the holes and obstructions in connectedtopological spaces. A topologist is someone who imagines all objectsto be made of unbreakable but very pliable playdough, and thereforedoes not see the need to distinguish between a coffee cup and doughnutbecause either can be turned into the other. Topology is concernedwith the similarities and differences between coffee cups with \(n\)handles, surfaces with \(n\) holes, and more complicated shapes.Algebraic topology expresses the invariants of such shapes in terms oftheir homotopy groups and homology groups.

5.4 Algebraic logic

Algebraic logic got off to an early start with Boole’sintroduction of Boolean algebra in an 1847 pamphlet. The methods ofmodern algebra began to be applied to Boolean algebra in the 20thcentury. Algebraic logic then broadened its interests to first orderlogic and modal logic. Central algebraic notions in first order logicare ultraproducts, elementary equivalence, and elementary andpseudoelementary varieties. Tarski’s cylindric algebrasconstitute a particular abstract formulation of first order logic interms of diagonal relations coding equality and substitution relationsencoding variables. Modal logic as a fragment of first order logic ismade algebraic via Boolean modules.

6. Free Algebras

Given any system such as integer arithmetic or real arithmetic, we canwrite \(T\) for the set of all definite terms such as \(1 + (2/3)\)built from constants and constituting the definite language, and\(T[V]\) for the larger indefinite language permitting variables drawnfrom a set \(V\) in place of some of the constant symbols, with termssuch as \(x + (2/y)\). When \(V\) contains only a single variable\(“x”\), \(T[\{“x”\}]\) is usually abbreviatedto \(T[“x”]\) or just \(T[x\)] which is usuallyunambiguous. This convention extends to the algebra \(\Phi\) of termsof \(T\) together with its list of operation symbols viewed asoperations for combining terms; we write \(\Phi[V\)] and call it theterm algebra on \(V\).

This notion of term algebra is a purely syntactic one involving onlythe operation symbols, constants, and variables of some language. Theterms \(2 + 3\) and \(3 + 2\) are distinct; likewise \(x + y\) and \(y+ x\) are distinct terms. As such they can be considered concreteterms.

Now in a universe such as the integers certain concrete terms areequivalent in the sense that they always evaluate to the same elementof the universe regardless of the values of their variable, forexample \(x + y\) and \(y + x\). It is convenient to collectequivalent concrete terms into equivalence classes each of which is tobe thought of as an abstract term.

As a simple example of abstract terms consider linear polynomials ofthe form \(ax + by\) where \(a\) and \(b\) are nonnegative integers,for example \(7x + 3y\). The set of all such polynomials includes 0and is closed under polynomial addition, an associative andcommutative operation. This set together with the operation ofaddition and the zero polynomial therefore constitutes a commutativemonoid.

This monoid is an example of a free algebra, namely the freecommutative monoid on two generators \(x\) and \(y\). What makes itfree is that it satisfies no laws other than those of a commutativemonoid. It is not however a free monoid because it satisfies thecommutative law. The free monoid on two generators \(x\) and \(y\) isinstead the set of all finite strings over the two-letter alphabet\(\{x,y\}\).

When commutativity is introduced as a law, it identifies thepreviously distinct strings \(xy\) and \(yx\) as a single polynomial;more generally any two strings with the same number of \(x\)s and\(y\)s are identified.

Free monoids and free commutative monoids are examples of free\(C\)-algebras where \(C\) is a class of algebras. In these twoexamples the class \(C\) is respectively that of monoids andcommutative monoids.

A free \(C\)-algebra is an algebra that lives at the frontier ofsyntax and semantics. On the semantic side it is a member of \(C\). Onthe syntactic side its elements behave like terms subject to the lawsof \(C\), but no other laws expressible with its generators.Commutativity \(xy = yx\) is expressible with two generators and so afree monoid on two or more generators cannot be commutative, thoughthe free monoid on one generator, namely the set of all finite stringsover a one-letter alphabet does form a commutative monoid on onegenerator.

On the syntactic side, the free \(C\)-algebra \(B\) on a set \(X\)arises as a quotient of the term algebra formed from \(X\) (viewed asa set of variables) using the operation symbols and constants commonto the algebras of \(C\). The quotient identifies those terms thathave the same value for all algebras \(A\) of \(C\) and all valuationsassigning values in \(A\) to the variables of \(X\). This performsjust enough identifications to satisfy every law of \(C\) (therebymaking this quotient a \(C\)-algebra) while still retaining thesyntactic essence of the original term algebra in a sense made moreprecise by the following paragraph.

(Since the concept of a term algebra can seem a little circular inplaces, a more detailed account may clarify the concept. Given thelanguage of \(C\), meaning the operation symbols and constant symbolscommon to the algebras of \(C\), along with a set \(X\) of variables,we first form the underlying set of the algebra, and then interpretthe symbols of the language as operations on and values in that set.The set itself consists of the terms built in the usual way from thosevariables and constant symbols using the operation symbols; in thatsense these elements are syntactic. But now we change our point ofview by treating those elements as semantic, and we look to theconstant symbols and operation symbols of the language as syntacticentities needing to be interpreted in this semantic domain (albeit ofterms) in order to turn this set of terms into an algebra of terms. Weinterpret each constant symbol as itself. And we interpret each\(n\)-ary operation symbol \(f\) as the \(n\)-ary operation that takesany \(n\) terms \(t_1 , \ldots ,t_n\) as its \(n\) arguments andreturns the single term \(f(t_1 , \ldots ,t_n)\). Note that thisinterpretation of \(f\) onlyreturns a term, it does notactuallybuild it. All term building was completed when weproduced the underlying set of the algebra.)

From the semantic side, a \(C\)-algebra \(B\) together with a subset\(X\) of \(B\) thought of as variables is said to be a free\(C\)-algebra on \(X\), or is freely generated by \(X\), when, givenany \(C\)-algebra \(A\), any valuation in \(A\) of the variables in\(X\) (that is, any function \(f: X\rightarrow A\)) uniquely extendsto a homomorphism \(h: B\rightarrow A\). (We say that \(h:B\rightarrow A\) extends \(f: X\rightarrow A\) when the restriction of\(h\) to \(X\) is \(f\).)

As a convenient shorthand a free \(C\)-algebra on no generators canalso be called an initial \(C\)-algebra. An initial \(C\)-algebra hasexactly one homomorphism to every \(C\)-algebra.

Before proceeding to the examples it is worthwhile pointing out animportant basic property of free algebras as defined from the semanticside.

Two free algebras \(B, B'\) on respective generator sets \(X, Y\)having the same cardinality are isomorphic.

By way of proof, pick any bijection \(f: X\rightarrow Y\). This, itsinverse \(f': Y\rightarrow X\), and the two identity functions onrespectively \(X\) and \(Y\), form a system of four functions closedunder composition. Each of these functions is from a generator set toan algebra and therefore has a unique extension to a homomorphism.These four homomorphisms are also closed under composition. The onefrom \(B\) to itself extends the identity function on \(X\) andtherefore must be the identity homomorphism on \(B\) (since the latterexists and its restriction to \(X\) is the identity function on\(X)\). Likewise the homomorphism from \(G\) to \(G\) is an identityfunction. Hence the homomorphisms between \(B\) and \(G\) compose ineither order to identities, which makes them isomorphisms. But this iswhat it means for \(B\) and \(B'\) to be isomorphic.

This fact allows us to saythe free algebra on a given set,thinking of isomorphic algebras as being “morally” thesame. Were this not the case, our quotient construction would beincomplete as it produces a unique free algebra, whereas the abovedefinition of free algebra allows any algebra isomorphic to thatproduced by the quotient construction to be considered free. Since allfree algebras on \(X\) are isomorphic, the quotient construction is asgood as any, and is furthermore one way of proving that they exist. Italso establishes that the choice of set of variables is irrelevantexcept for its cardinality, as intuition would suggest.

6.1 Free monoids and groups

Take \(C\) to be the class of monoids. The term algebra determined bythe binary operation symbol and the constant symbol for identity canbe viewed as binary trees with variables and copies of the constantsymbol at the leaves. Identifying trees according to associativity hasthe effect of flattening the trees into words that ignore the order inwhich the operation was applied (without however reversing the orderof any arguments). This produces words over the alphabet \(X\)together with the identity. The identity laws then erase theidentities, except in the case of a word consisting only of theidentity symbol, which we take to be the empty word.

Thus the monoid of finite words over an alphabet \(X\) is the freemonoid on \(X\).

Another representation of the free monoid on \(n\) generators is as aninfinite tree, every vertex of which has \(n\) descendants, one foreach letter of the alphabet, with each edge labeled by thecorresponding letter. Each vertex \(v\) represents the word consistingof the letters encountered along the path from the root to \(v\). Theconcatenation of \(u\) and \(v\) is the vertex arrived at by takingthe subtree whose root is the vertex \(u\), noticing that this tree isisomorphic to the full tree, and locating \(v\) in this subtree asthough it were the full tree.

If we ignore the direction and labels of the edges in this tree we canstill identify the root: it is the only vertex with \(n\) edgesincident on it, all other vertices have \(n+1\), namely the oneincoming edge and the \(n\) outgoing ones.

The freecommutative monoid on a set is that monoid whosegenerators behave like letters just as for free monoids (in particularthey are still atoms), but which satisfy the additional law \(uv =vu\). We make further identifications,e.g. of“dog” and “dgo”. Order of letters in a word isnow immaterial, all that matters is how many copies there are of eachletter. This information can be represented as an \(n\)-tuple ofnatural numbers where \(n\) is the size of the alphabet. Thus the freecommutative monoid on \(n\) generators is \(N^n\), the algebra of\(n\)-tuples of natural numbers under addition.

It can also be obtained from the tree representation of the freemonoid by identifying vertices. Consider the case \(n = 2\) of twoletters. Since the identifications do not change word length, allidentifications are of vertices at the same depth from the root. Weperform all identifications simultaneously as follows. At every vertex\(v\), identify \(v_{01}\) and \(v_{10}\) and their subtrees. Whereasbefore there were \(2^n\) vertices at depth \(n\), now there are\(n+1\). Furthermore instead of a tree we have the upper rightquadrant of the plane, that is, \(N^2\), rotated 135 degreesclockwise, with every vertex \(v\) at the top of a diamond whose othervertices are \(v_0\) and \(v_1\) at the next level down, and theidentified pair \(v_{01} = v_{10}\) below both.

To form the free group on \(n\) generators, first form the free monoidon \(2n\) generators, with generators organized into complementarypairs each the inverse of the other, and then delete all adjacentcomplementary pairs from all words.

This view is not particularly insightful. The group counterpart of thetree representation does a better job of presenting a free group.Consider the free group on \(n = 2\) generators \(A\) and \(B\). Westart with the free monoid on 4 generators \(A, B, a, b\) where \(a\)is the inverse of \(A\) and \(b\) that of \(B\). Every vertex of thistree has 4 descendants. So the root has degree 4 and the remainingvertices have degree 5: every vertex except the root has one edgegoing in, say the generator \(a\), and four out. Consider any nonrootvertex \(v\). The effect of deleting adjacent complementary pairs isto identify the immediate ancestor of \(v\) with one of the fourdescendants of \(v\), namely the one that makes the path from theancestor to the descendant a complementary pair. For every nonrootvertex \(v\) these identifications reduce the degree of \(v\) from 5to 4. The root remains at degree 4.

So now we have an infinite graph every vertex of which has degree 4.Unlike the tree for the free monoid on 2 generators, where the root istopologically different from the other vertices, the tree for the freegroup on 2 generators is entirely homogeneous. Thus if we throw awaythe vertex labels and rely only on the edge labels to navigate, anyvertex can be taken as the identity of the group.

This homogeneity remains the case for the free abelian group on 2generators, whose vertices are still of degree 4. However theadditional identifications turns it from a tree (a graph with nocycles) to a grid whose vertices are the lattice points of the plane.That is, the free abelian group on 2 generators is \(Z^2\), and on\(n\) generators \(Z^n\). The edges are the line segments joiningadjacent lattice points.

6.2 Free rings

With no generators the free monoid, free group, and free ring are allthe one-element algebra consisting of just the additive identity 0. Aring with identity means having a multiplicative identity, that is, aword \(\varepsilon\). But this makes \(\varepsilon\) a generator forthe additive group of the ring, and the free abelian group on onegenerator is the integers. So the free ring with identity on nogenerators is the integers under addition and now multiplication.

The free ring on one generator \(x\) must include \(x^2 , x^3\), etc.by multiplication, but these can be added and subtracted resulting inpolynomials such as \(7x^3 -3x^2 +2x\) but without a constant term,with the exception of 0 itself. The distributivity law for rings meansthat a term such as \((7x+x^2 )(2x^3 +x)\) can be expanded as \(7x^2+x^3 +14x^4 +2x^5\). It should now be clear that these are justordinary polynomials with no constant term; in particular we aremissing the zero-degree polynomial 1 and so this ring has nomultiplicative identity. However it is a commutative ring even thoughwe did not specify this. The free ring with identity on one generatorintroduces 1 as the multiplicative identity and becomes the ordinaryone-variable polynomials since now we can form all the integers. Justas with monoids, the free ring with identity on two generators is notcommutative, the polynomials \(xy\) and \(yx\) being distinct. Thefreecommutative ring with identity on two generators howeverconsists of the ordinary two-variable polynomials over theintegers.

6.3 Free combinatorial structures

From the examples so far one might conclude that all free algebras onone or more generators are infinite. This is by no means always thecase; as counterexamples we may point to a number of classes: sets,pointed sets, bipointed sets, graphs, undirected graphs, Booleanalgebras, distributive lattices, etc. Each of these forms a locallyfinite variety as defined earlier.

A pointed set is an algebra with one constant, say \(c\). The freepointed set on \(x\) and \(y\) has three elements, \(x, y\), and\(c\). A bipointed set is an algebra with two constants \(c\) and\(d\), and the free bipointed set on \(x\) and \(y\) then has fourelements, \(x, y, c\), and \(d\).

Graphs, of the oriented kind arising in say automata theory wheremultiple edges may connect the same two vertices, can be organized asalgebras having two unary operations \(s\) and \(t\) satisfying\(s(s(x)) = t(s(x)) = s(x)\) and \(t(t(x)) = s(t(x)) = t(x)\). Thefree graph on one generator \(x\) has three elements, \(x, s(x)\), and\(t(x)\), constituting respectively an edge and its two endpoints orvertices. In this framework the vertices are the elementssatisfying \(s(x) = x\) (and hence \(t(x) = x\) since \(x = s(x) =t(s(x)) = t(x)\)); all other elements constitute edges. The free graphon \(n\) generators consists of \(n\) such edges, all independent.Other graphs arise by identifying elements. There is no pointidentifying an edge with either another edge or a vertex since thatsimply absorbs the first edge into the second entity. This leaves onlyvertices; identifying two vertices yields a single vertex common totwo edges, or to the same edge in the identification \(s(x) = t(x)\)creating a self-loop.

The term “oriented” is to be preferred to“directed” because a directed graph as understood incombinatorics is an oriented graph with the additional property thatif \(s(x) = s(y)\) and \(t(x) = t(y)\) then \(x = y\); that is, onlyone edge is permitted between two vertices in a given direction.

Unoriented graphs are defined as for graphs with an additional unaryoperation \(g\) satisfying \(g(g(x)) = x\) and \(s(g(x)) = t(x)\)(whence \(s(x) = s(g(g(x))) = t(g(x)))\). The free undirected graph on\(x\) consists of \(x, s(x), t(x)\), and \(g(x)\), with the pair \(x,g(x)\) constituting the two one-way lanes of a two-lane highwaybetween \(s(x) = t(g(x))\) and \(t(x) = s(g(x)\)). Identification ofelements of undirected graphs works as for their orientedcounterparts: it is only worth identifying vertices. However there isone interesting twist here: vertices can be of two kinds, thosesatisfying \(x = g(x)\) and those not. The latter kind of vertex isnow asymmetric: one direction of the bidirectional edge is identifiedwith its vertices while the other one forms an oriented loop in thesense that its other direction is a vertex. This phenomenon does notarise for undirected graphs defined as those satisfying “if\(s(x) = s(y)\) and \(t(x) = t(y)\) then \(x = y\).”

6.4 Free logical structures

Boolean algebras are traditionally defined axiomatically ascomplemented distributive lattices, which has the benefit of showingthat they form a variety, and furthermore a finitely axiomatizableone. However Boolean algebras are so fundamental in their own rightthat, rather than go to the trouble of defining lattice, distributive,and complemented just for this purpose, it is easier as well as moreinsightful to obtain them from the initial Boolean algebra. Itsuffices to define this as the two-element set \(\{0, 1\}\), theconstants (zeroary operations) 0 and 1, and the \(2^{2^2} = 16\)binary operations. A Boolean algebra is then any algebra with those 16operations and two constants satisfying the equations satisfied by theinitial Boolean algebra.

An almost-definitive property of the class of Boolean algebras is thattheir polynomials in the initial Boolean algebra are all theoperations on that algebra. The catch is that the inconsistent classconsisting of only the one-element or inconsistent algebra also hasthis property. This class is easily ruled out however by adding thatBoolean algebra is consistent. But just barely—adding any newequation to Boolean algebra (without introducing new operations)axiomatizes the inconsistent algebra.

Sheffer has shown that the constants and the 16 operations can begenerated as polynomials in just one constant, which can be 0 or 1,and one binary operation, which can be NAND, \(\neg(x\wedge y)\), orNOR, \(\neg(x\vee y)\). Any such sufficient set is called abasis. Along the same lines Stone has shown that conjunction,exclusive-or, and the constant 1 form a basis. The significance ofStone’s basis over Sheffer’s is that Boolean algebrasorganized with those operations satisfy all the axioms for acommutative ring with identity with conjunction as multiplication andexclusive-or as addition, as well as the law \(x^2 = 1\). Any ringsatisfying this last condition is called aBoolean ring.Boolean rings are equivalent to Boolean algebras in the sense thatthey have the same polynomials.

An atom of a Boolean algebra is an element \(x\) such that for all\(y, x\wedge y\) is either \(x\) or 0. An atomless Boolean algebra isone with no atoms.

There is exactly one Boolean algebra of cardinality every finite powerof 2, and it is isomorphic to the Boolean algebra of a power set\(2^X\) of that cardinality under the set operations of union,intersection, and complement relative to \(X\). Hence all finiteBoolean algebras have cardinality a power of 2. This situation changeswith infinite Boolean algebras; in particular countable Booleanalgebras exist. One such is the free Boolean algebra on countably manygenerators, which is the only countable atomless Boolean algebra. Thefinite and cofinite (complement of a finite set) subsets of the set\(N\) of natural numbers form a subalgebra of the powerset Booleanalgebra \(2^N\) not isomorphic to the free Boolean algebra, but it hasatoms, namely the singleton sets.

The free Boolean algebra \(F(n)\) on \(n\) generators consists of all\(2^2 n\) \(n\)-ary operations on the two-element Boolean algebra.Boolean algebras therefore form a locally finite variety.

The equational theory of distributive lattices is obtained from thatof Boolean algebras by selecting as its operations just the monotonebinary operations on the two-element algebra, omitting the constants.These are the operations with the property that if either argument ischanged from 0 to 1, the result does not change from 1 to 0. Adistributive lattice is any model of those Boolean equations betweenterms built solely with monotone binary operations. Hence everyBoolean algebra is a distributive lattice.

Distributive lattices can be arbitrarily “thin.” At theextreme, any chain (linear or total order, \(e.g\). the realsstandardly ordered) under the usual operations of max and min forms adistributive lattice. Since we have omitted the constants thisincludes the empty lattice, which we have not excluded here as analgebra. (Some authors disallow the empty set as an algebra but thisproscription spoils many good theorems without gaining any usefulones.) Hence there exist distributive lattices of every possiblecardinality.

Every finite-dimensional vector space is free, being generated by anychoice of basis. This extends to infinite-dimensional vector spacesprovided we accept the Axiom of Choice. Vector spaces over a finitefield therefore form a locally finite variety when scalarmultiplication is organized as one unary operation for each fieldelement.

6.5 Free algebras categorially

We now consider how free algebras are organized from the perspectiveof category theory. We defined the free algebra \(B\) generated by asubset \(X\) of \(B\) as having the property that for every algebra\(A\) and every valuation \(f: X\rightarrow A\), there exists a uniquehomomorphism \(h: B\rightarrow A\). Now every homomorphism \(h:B\rightarrow A\) necessarily arises in this way, since its restrictionto \(X\), as a function from \(X\) to \(A\), is a valuation.Furthermore every function \(f: X\rightarrow A\) arises as therestriction to \(X\) of its extension to a homomorphism. Hence we havea bijection between the functions from \(X\) to \(A\) and thehomomorphisms from \(B\) to \(A\).

Now the typing here is a little casual, so let us clean it up. Since\(X\) is a set while \(A\) is an algebra, \(f\) is better typed as\(f: X\rightarrow U(A)\) where \(U(A)\) denotes the underlying set of\(A\). And the relationship of \(X\) to \(B\) is better understoodwith the notation \(B = F(X)\) denoting the free algebra generated bythe set \(X\). So \(U\) maps algebras to sets while \(F\) maps sets toalgebras. \(F\) and \(U\) are not in general inverses of each other,but they are nonetheless related in a way we now make precise.

For any category \(\mathbf{C}\), the notation \(\mathbf{C}(A, B)\) isgenerally used to denote the set of all morphisms from object \(A\) toobject \(B\) in category \(\mathbf{C}\). And the set of all functionsfrom the set \(X\) to the set \(Y\) can be understood as theparticular case \(\mathbf{Set}(X, Y)\) of this convention where\(\mathbf{C}\) is taken to be the class \(\mathbf{Set}\) of all sets,which we can think of asdiscrete algebras, that is, algebraswith no structure. A class of algebras along with a specified set ofhomomorphisms between any two of its members is an instance of acategory. The members of the class are called theobjects of the category while the homomorphisms are calledthemorphisms.

The bijection we have just observed can now be stated as

Such a bijection is called anadjunction between\(\mathbf{Set}\) and \(\mathbf{C}\). Here \(F: \mathbf{Set}\rightarrow\mathbf{C}\) and \(U: \mathbf{C}\rightarrow \mathbf{Set}\) arerespectively the left and rightadjoints of this adjunction;we say that \(F\) is left adjoint to (or of) \(U\) and \(U\) rightadjoint to \(F\).

We have only described how \(F\) maps sets to algebras, and \(U\) mapsalgebras to sets. However \(F\) also maps functions to homomorphisms,mapping each function \(f\) to its unique extension as a homomorphism,while \(U\) maps homomorphisms to functions, namely the homomorphismitself as a function. Such maps between categories are instances offunctors.

In general a category \(C\) consists of objects \(a, b, c\) andmorphisms \(f: a\rightarrow b\), together with an associativecomposition law for “composable” morphisms \(f:b\rightarrow c\), \(g: a\rightarrow b\) yielding the morphism \(fg:a\rightarrow c\). Furthermore every object a has an identity element\(1_a : a\rightarrow a\) which whenever composable with a morphism\(f\) (on one side or the other) composes with it to yield \(f\). Afunctor \(F: C\rightarrow D\) maps objects of \(C\) to objects of\(D\) and morphisms of \(C\) to morphisms of \(D\), such that \(F(fg)= F(f)F(g)\) and \(F(1_a) = 1_{F(a)}\). That is, functors are“homomorphisms of categories,” preserving composition andidentities.

With no further qualification such a category is considered anabstract category. The categories we have been working withareconcrete in the sense that they come with a givenunderlying set orforgetful functor \(U: C\rightarrow\)Set.That is, algebras are based on sets, homomorphisms are certainfunctions between these sets, and \(U\) simply “forgets”the algebraic structure. Such forgetful functors arefaithfulin the sense that for any two morphisms \(f, g: a\rightarrow b\) of\(C\), if \(U(f) = U(g)\) then \(f = g,\) i.e. \(U\) does not identifydistinct homomorphisms. In general a concrete category is defined as acategory \(C\) together with a faithful forgetful functor \(U:C\rightarrow \textrm{Set}\).

Categories themselves admit a further generalization to 2-categoriesas algebras over two-dimensional graphs, with associative compositionof 1-cells generalized to the 2-associative pasting of 2-cells. Afurther simplification of the free-algebra machinery then obtains,namely via abstract adjunctions as the natural 2-dimensionalcounterpart of isomorphisms in a category, which in turn is thenatural 1-dimensional counterpart of equality of elements in a set,the 0-dimensional idea that two points can turn out to be one. Thisleads to a notion of abstract monad as simply the composition of anadjoint pair of 1-cells, one of which is the 1-cell abstracting thefunctor \(F\) that manufactures the free algebra \(F(V)\) from \(V\).Ordinary or concrete monads arise as the composition of functors asconcrete 1-cells of a 2-category of categories.

Bibliography

• Harold R. Jacobs,Elementary Algebra, 876pp, W.H.Freeman, 1979.
• Bartel Leendert van der Waerden,Moderne Algebra (2volumes), Springer, Vol. 1 1930, Vol. 2 1931.
• I.N. Herstein,Topics in Algebra, 2nd ed, 400pp, Wiley,1975.
• Saunders Mac Lane,Categories for the WorkingMathematician, Springer-Verlag, 1978.

Academic Tools

	How to cite this entry.
	Preview the PDF version of this entry at theFriends of the SEP Society.
	Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO).
	Enhanced bibliography for this entryatPhilPapers, with links to its database.

Other Internet Resources

• Many algebraic topics, at Mathworld, Wolfram Research.
• Linear algebra, at Answers.com

Related Entries

Boolean algebra: the mathematics of |category theory