- List of algebraic structures
In
universal algebra , a branch of puremathematics , analgebraic structure is a variety orquasivariety .Abstract algebra is primarily the study of algebraic structures and their properties. Someaxiom aticformal system s that are neither varieties nor quasivarieties, called "nonvarieties" below, are included among the algebraic structures by tradition. Other web lists of algebraic structures, organized more or less alphabetically, include [http://math.chapman.edu/cgi-bin/structures/ Jipsen] and [http://planetmath.org/browse/objects/ PlanetMath.] These lists mention many structures not included below, and may present more information about some structures than is presented here.Generalities
An algebraic structure consists of one or two sets closed under some operations, functions, and relations, satisfying a number of
axiom s, including none. This definition of an algebraic structure should not be taken as restrictive. Anything that satisfies the axioms defining a structure is an instance of that structure, regardless of how many other axioms that instance happens to satisfy. For example, all groups are alsosemigroup s and magmas.Structures are listed below in approximate order of increasing complexity as follows:
*Structures that are varieties precede those that are not;
*Simple structures built on one underlying set "S" precede composite structures built on two;
* If "A" and "B" are the two underlying sets making up a composite structure, that structure may include functions of the form "A"x"A"→"B" or "A"x"B"→"A".
*Structures are then ordered by the number and arities of the operations they contain. The heap, a group-like structure, is the only structure mentioned in this entry requiring an operation whosearity exceeds 2.If structure "B" is under structure "A" and more indented, then "A" is interpretable in "B", meaning that all
theorem s of "A" are theorems of "B". The converse is usually not the case.A structure is trivial if the
cardinality of "S" is less than 2, and is otherwise nontrivial.Varieties
Identities are equations formulated using only the operations the structure allows, and variables that are tacitly universally quantified over a set that is part of the definition of the structure. Hence identities contain no sentential
connective s, existentially quantified variables, orrelation s of any kind other than equality and the operations the structure allows.If the axioms defining an algebraic structure are all identities--or can be recast as identities--the structure is a variety (not to be confused with
algebraic variety in the sense ofalgebraic geometry ). Nonidentities can often be recast as identities. For example, any lattice inequality of the form α≤β can always be recast as the identity α∧β=α.An important result is that given any variety C and any underlying set "X", the
free object "F"("X")∈C exists.imple structures
No
binary operation .
* Set: a degenerate algebraic structure having no operations.
*Pointed set : "S" has one or more distinguished elements. While pointed sets are near-trivial, they lead todiscrete space s, which are not.
**Bipointed set : "S" has exactly two distinguished elements.
* Unary system: "S" and a singleunary operation over "S".
* Pointed unary system: a unary system with "S" a pointed set.Group-like structures
*All group-like structures feature a primary (and usually unique) binary or
ternary operation , which usually (i.e., forsemigroup s and hoops) associates. Thanks to associativity, brackets are not required to resolve the order of operation, and concatenation suffices to denote the operation. When associativity is not the case (quasigroup s, semiheaps, hoops, implication algebras), an embedded period indicates the grouping. Examples: "xy"."z", "x"."yz".
*For Steiner magmas,abelian group s,logic algebra s,semilattice s, equivalence algebras, and hoops, the primary binary operation also commutes.Commutativity may be added to any group-like structure for which it is not already the case.
* Group,logic algebra s, lattices, and loops feature aunary operation , denoted here by enclosure in parentheses.
*Formonoid s, loops, and sloops, "S" is apointed set .See magma for a:
*Diagram summarizing the connections among several of the better-known group-like structures;
* Description of the many properties that a magma may possess.One
binary operation .
* Magma or groupoid: "S" is closed under a singlebinary operation .
**Implication algebra : a magma satisfying "xy"."x"="x", "x"."yz"="y"."xz", and "xy"."y"="yx"."x".
**Steiner magma: Acommutative magma satisfying "x"."xy" = "y".
*** Squag: anidempotent Steiner magma.
*** Sloop: a Steiner magma with distinguished element 1, such that "xx" = 1.
**Rack: A magma satisfying the identity "xy.z" = "xz"."yz". Also, ∀"x","y" there exists a unique "z" such that "zx" = "y".
***Quandle : Anidempotent rack.
**Semigroup : anassociative magma.
***Equivalence algebra : a commutative semigroup satisfying "yyx"="x".
***Monoid : aunital semigroup.
****Boolean group : a monoid with "xx" =identity element .
**** Group: a monoid with aunary operation , inverse, giving rise to aninverse element equal to theidentity element . thus ("b")"ba"="a" holds in all groups.
*****Abelian group : acommutative group. The single axiom "yxz"("yz")="x" suffices. [ McCune, William (1993) "Single Axioms for Groups and Abelian Groups with Various Operations," "Journal of Automated Reasoning 10": 1-13.]
*****Group with operators : a group with a set of unary operations over "S", with each unary operation distributing over the group operation.
*****Algebraic group :
******Reductive group : analgebraic group such that theunipotent radical of the identity component of "S" istrivial .
****Logic algebra : a commutative monoid with aunary operation , complementation, satisfying "x"(1)=(1) and (("x"))="x". 1 and (1) are lattice bounds for "S".
*****MV-algebra : a logic algebra satisfying the axiom (("x")"y")"y" = (("y")"x")"x".
***** Boundary algebra: a logic algebra satisfying ("x")"x"=(1) and ("xy")"y" = ("x")"y", from which it can be proved that boundary algebra is adistributive lattice . "x"(1)=(1) and (("x"))="x", and "xx"="x" are now provable.
**Order algebra : anidempotent magma satisfying "yx"="xy"."x", "xy"="xy"."y", "x":"xy"."z"="x"."yz", and "xy"."z"."y"="xz"."y". Hence idempotence holds in the following wide sense. For any subformula "x" of formula "z": (i) all but one instance of "x" may be erased; (ii) "x" may be duplicated at will anywhere in "z".
*** Band: an associative order algebra, and anidempotent semigroup.
****Rectangular band : a band satisfying the axiom "xyz" = "xz".
****Normal band : a band satisfying the axiom "xyzx" = "xzyx".::The following two structures form a bridge connecting magmas and lattices:::*Semilattice : acommutative band. The binary operation is calledmeet orjoin .:::*Lattice : a semilattice with a unary operation, dualization, denoted ("x") and satisfying theabsorption law , "x"("xy") = ("x"("xy")) = "x". "xx" = "x" is now provable.Two
binary operation s.
* Hoop: a commutativemonoid with a secondbinary operation , denoted byinfix →, satisfying the axioms "x"→."y"→"z" = "xy".→"z", "x"→"x" = 1, and "x"→"y"."x" = "y"→"x"."y".Three
binary operation s.Quasigroups feature 3 binary operations because axiomatizing the
cancellation property by means of identities alone requires two binary operations in addition to the group operation.
*Quasigroup : a cancellative magma. Equivalently, ∀"x","y"∈"S", ∃"a","b"∈"S", such that "xa" = "y" and "bx" = "y".
** Loop: aunital quasigroup. Every element of "S" has, provably, a unique left and right inverse.
***Bol loop : A loop satisfying either "a"."b"."ac" = "a"."ba"."c" (left) or "ca"."b"."a" = "c"."ab"."a" (right).
****Moufang loop : a left and rightbol loop . More simply, a loop satisfying "zx"."yz" = "z"."xy"."z".
****Bruck loop: abol loop whose inverse satisfies ("ab") = ("a")("b").
***Group: an associative loop.One
ternary operation , heap product, denoted "xyz":*Semiheap: "S" is closed under heap product, which para-associates: "vwx.yz" = "v.wxy.z" = "vw.xyz".
**Idempotent semiheap: A semiheap satisfying "xxx" = "x".
***Generalized heap: An idempotent semiheap satisfying "yy.zzx" = "zz.yyz" and "xyy.zz" = "xzz.yy".
**Heap: A semiheap satisfying "yyx" = "xyy" = "x".
***Group: A heap with distinguished element 1. The group product of "x" and "y" is defined as "x"1"y", and the group inverse of "x" is defined as 1"x"1.Lattice-like structures
The
binary operations meet andjoin , which characterize all structures in this section, areidempotent , by assumption or proof. Latticoids are the only lattice-like structure that do not associate.One
binary operation , one ofmeet orjoin , denoted byconcatenation . The two structures below are also magmas; see the preceding section.
*Semilattice : thebinary operation commutes and associates.
**Lattice : a semilattice with a unary operation, dualization, denoted by enclosure. If "xy" denotes meet, ("xy") denotes join, and vice versa. The binary and unary operations interact via a form of theabsorption law , "x"("xy") = "x" = ("x"("xy")).Two
binary operations ,meet (infix ∧) andjoin (infix ∨). Byduality , interchanging all meets and joins preserves truth.N.B. Lattice has another mathematical meaning unrelated to this section, namely a
discrete subgroup of thereal vector space R"n" that spans R"n".
*Latticoid : meet and joincommute but do notassociate .
*Skew lattice : meet and join associate but do not commute.
*Lattice: acommutative skew lattice, anassociative latticoid, and both ameet andjoin semilattice . Meet and join interact via theabsorption law .
**Bounded lattice : a lattice with two distinguished elements, the greatest (1) and the least element (0), such that "x"∨1=1 and "x"∨0="x". Dualizing requires interchanging 0 and 1. A bounded lattice is apointed set .
**Involutive lattice : a lattice with a unary operation, denoted by postfix ', and satisfying "x" = "x" and ("x"∨"y")' = "x' "∧"y' ".
**Complemented lattice : a lattice with a unary operation, complementation, denoted by postfix ', such that "x"∧"x' " = 0 and 1=0'. 0 and 1 bound "S".
*** Ortholattice: a complemented lattice satisfying "x" = "x" and "x"∨"y"="y" ↔ "y' "∨"x' "= "x' " (complementation is order reversing).
****Orthomodular lattice : an ortholattice such that ("x" ≤ "y") → ("x" ∨ ("x"⊥ ∧ "y") = "y") holds.
***DeMorgan algebra : a complemented lattice satisfying "x" = "x" and ("x"∨"y")' = "x' "∧"y' ". Also a bounded involutive lattice.
**Modular lattice : a lattice satisfying the modular identity, "x"∨("y"∧("x"∨"z")) = ("x"∨"y")∧("x"∨"z").
***Arguesian lattice : a modular lattice satisfying the identity .
***Distributive lattice : a lattice in which each of meet and join distributes over the other. Distributive lattices are modular, but the converse need not hold.
**** Boolean algebra: a complemented distributive lattice. Either of meet or join can be defined in terms of the other and complementation.
*****Boolean algebra with operators : a Boolean algebra with one or more added operations, usually unary. Let a postfix * denote any added unary operation. Then 0* = 0 and ("x"∨"y")* = "x"*∨"y"*. More generally, all added operations (a) evaluate to 0 if any argument is 0, and (b) are join preserving, i.e., distribute over join.
******Modal algebra: a Boolean algebra with a single added operator, themodal operator .
*******Derivative algebra: a modal algebra whose added unary operation, thederivative operator , satisfies "x"**∨"x"*∨"x" = "x"*∨"x".
*******Interior algebra : a modal algebra whose added unary operation, theinterior operator , satisfies "x"*∨"x" = "x" and "x"** = "x"*. The dual is aclosure algebra .
********Monadic Boolean algebra : a closure algebra whose added unary operation, theexistential quantifier , denoted by prefix ∃, satisfies the axiom ∃(∃"x")' = (∃"x")'. The dual operator, ∀"x" := (∃"x' ")' is theuniversal quantifier .::::Two structures whose intended interpretation is first-order logic:::::*Polyadic algebra : amonadic Boolean algebra with a second unary operation, denoted by prefixed S. "I" is anindex set , "J","K"⊂"I". ∃ maps each "J" into thequantifier ∃("J"). S maps "I"→"I"transformation s into Booleanendomorphism s on "S". σ, τ range over possible transformations; δ is theidentity transformation . The axioms are: ∃(∅)"a"="a", ∃("J"∪"K") = ∃("J")∃("K"), S(δ)"a" = "a", S(σ)S(τ) = S(στ), S(σ)∃("J") = S(τ)∃("J") (∀"i"∈"I"-"J", such that σ"i"=τ"i"), and ∃("J")S(τ) = S(τ)∃(τ-1"J") (τinjective ). [Pp. 26-28, 251, ofPaul Halmos (1962) "Algebraic Logic". Chelsea.] ::::*Cylindric algebra : Boolean algebra augmented by cylindrification operations.Three binary operations::::*
Boolean semigroup : a Boolean algebra with an added binary operation that associates, distributes over join, and is annihilated by 0.::*Implicative lattice : a distributive lattice with a third binary operation, implication, that distributes left and right over each of meet and join.::*Brouwerian algebra : a distributive lattice with agreatest element and a third binary operation, denoted by infix " ' ", satisfying (("x"∧"y")≤"z")∧("y"≤"x")' "z".:::*Heyting algebra : a Brouwerian algebra with aleast element , whose third binary operation, now calledrelative pseudo-complement , satisfies the identities "x'x"=1, "x"("x'y") = "xy", "x' "("yz") = ("x'y")("x'z"), and ("xy")z" = ("x'z")("y'z"). Inpointless topology , a Heyting algebra is called a frame"'.Four or more binary operations:
*Residuated semilattice : a semilattice under meet or join, a monoid under product, and two further binary operations, residuation, satisfying the axioms .
**Action algebra : aresiduated semilattice that is also Kleene lattice. Hence combines a 〈∨, •, 1, ←, →〉 algebra with a 〈∨, 0, •, 1, *〉 algebra.
**Residuated lattice : a Brouwerian algebra with a least element and a fourth binary operation, denoted by infix ⊗, such that (⊗,1) is a commutativemonoid obeying the adjointness property (("x"≤"y")' "z") ↔ ("x"⊗"y"≤"z").
***Residuated Boolean algebra : aresiduated lattice whose lattice part is aBoolean algebra .
****Relation algebra : aresiduated Boolean algebra with an added unary operation, converse. "S", theCartesian square of some set, is amonoid under an added residuated binary operation, relative product, whose identity element is distinct from the Boolean bounds. The converse of a function is its inverse, and the relative product of two functions is their composition. Relative product distributes over join. Also aninterior algebra with converse as itsinterior operator .Lattice ordered structures
"S" includes distinguished elements and is closed under additional operations, so that the axioms for a
semigroup ,monoid , group, or a ring are satisfied.Ring-like structures
Two
binary operations , addition and multiplication. That multiplication has a 0 is either an axiom or a theorem.
*Shell:Multiplication has left/rightidentity element of 1, and azero element , 0, which is also the left/rightidentity element foraddition .
*Ringoid : multiplication distributes over addition.
**Nonassociative ring : a ringoid that is an abelian group under addition.
***Lie ring : a nonassociative ring whose multiplication anticommutes and satisfies theJacobi identity .
***Jordan ring : a nonassociative ring whose multiplication commutes and satisfies theJordan identity .
**Newman algebra: a ringoid that is also a shell. There is a unary operation,inverse , denoted by a postfix "'", such that x+x'=1 and xx'=0. The following are provable: inverse is unique, "x"="x", addition commutes and associates, and multiplication commutes and is idempotent.
**Semiring : a ringoid that is also a shell. Addition and multiplication associate, addition commutes.
*** Commutativesemiring : a semiring whose multiplication commutes.
** Rng: a ringoid that is anAbelian group under addition and 0, and a semigroup under multiplication.
*** Ring: a rng that is a monoid under multiplication and 1.
****Commutative ring : a ring with commutative multiplication.
*****Boolean ring : a commutative ring withidempotent multiplication,isomorphic to Boolean algebra.
****Differential ring: A ring with an addedunary operation , derivation, denoted by postfix ' and satisfying theproduct rule , ("xy")' = "x'y"+"xy"'.N.B. The above definitions of "rng", "ring", and "semiring" do not command universal assent:
*Some employ "ring" to denote what is here called arng , and call a ring in the above sense a "ring with identity";
*Some define a semiring as having no identity elements.Modules and algebras
Two sets, "R" and "S". Elements of "R" are scalars, denoted by Greek letters. Elements of "S" are denoted by Latin letters. For every ring "R", there is a corresponding variety of "R"-modules.
*
Monoid ring : "R" is aring and "S" is amonoid .
**Group ring : a monoid ring such that "S" is a group.
***Group algebra : a group ring whose group product commutes.
*Module: "S" is an abeliangroup with operators , each unary operator indexed by "R". The operators arescalar multiplication "R"x"S"→"S", which commutes, associates, isunital , and distributes over module and scalar addition. If only the pre(post)multiplication of module elements by scalars is defined, the result is a "left" ("right") "module".
*Comodule : the dual of a module.
**Vector space : A module such that "R" is a field.
**Algebra over a ring (also "R-algebra"): a module where "R" is acommutative ring . There is a second binary operation over "S", called multiplication and denoted by concatenation, which distributes over module addition and isbilinear : α("xy") = (α"x")"y" = "x"(α"y").
***Algebra over a field : An algebra over a ring whose "R" is a field.
****Associative algebra : an algebra over a field or ring, whose vector multiplication associates.
*****Coalgebra : the dual of a unital associative algebra.
*****Commutative algebra : an associative algebra whose vector multiplication commutes.
*****Incidence algebra : an associative algebra such that the elements of "S" are the functions "f" ["a,b"] : ["a,b"] →"R", where ["a,b"] is an arbitrary closed interval of a locally finiteposet . Vector multiplication is defined as aconvolution of functions.
****Jordan algebra : an algebra over a field whose vector multiplication commutes, may or may not associate, and satisfies theJordan identity .
****Lie algebra : an algebra over a field satisfying theJacobi identity . The vector multiplication, theLie bracket denoted ["u,v"] ,anticommute s, usually does not associate, and isnilpotent .
*****Kac-Moody algebra : a Lie algebra, usually infinite-dimensional, definable by generators and relations through ageneralized Cartan matrix .
******Generalized Kac-Moody algebra : a Kac-Moody algebra whosesimple root s may beimaginary .
******Affine Lie algebra : a Kac-Moody algebra whosegeneralized Cartan matrix ispositive semi-definite and has corank 1.Quasivarieties
A
quasivariety is a variety with one or more axioms that are quasiidentities. Let Greek letters be metavariables denoting identities. A quasiidentity then takes the form (α1∧,...,∧αn) → β.Magmas
Cancellative
*Semigroup: a semigroup satisfying the added axioms "xa"="ya"→"x"="y", and "bx"="by"→"x"="y".
*Monoid: aunital cancellative semigroup.Combinatory logic
The elements of "S" are
higher order function s, and concatenation denotes the binary operation offunction composition .
*BCI algebra : a magma with distinguished element 0, satisfying the identities ("xy.xz")"zy" = 0, ("x.xy")"y" = 0, "xx"=0, "xy"="yx"=0 → "x"="y", and "x"0 = 0 → "x"=0.
**BCK algebra : a BCI algebra satisfying the identity "x"0 = "x". "x"≤"y", defined as "xy"=0, induces apartial order with 0 as least element.
*Combinatory logic: Acombinator concatenate s upper case letters.Term s concatenate combinators and lower case letters. Concatenation is left and right cancellative. '=' is anequivalence relation over terms. The axioms are S"xyz" = "xz"."yz" and K"xy" = "x"; these implicitly define the primitive combinators S and K. The distinguished elements I and 1, defined as I=SK.K and 1=S.KI, have the provable properties I"x"="x" and 1"xy"="xy". Combinatory logic has the expressive power ofset theory . [Raymond Smullyan (1994) "Diagonalization and Self-Reference". Oxford Univ. Press: chpt. 18.]
**Extensional combinatory logic: Combinatory logic with the added quasiidentity ("Wx"="Vx")→("W"="V"), with "W", "V" containing no instance of "x".Graphs
One set, "V" a
finite set of vertices, and abinary relation "E"⊆"V"2, adjacency, consisting of edges. No operations.
*Directed graph : "E" isirreflexive .
**Directed acyclic graph : A directed graph with no path whose endpoints are the same element of "V".
**Graph: A directed graph such that "E" issymmetric . Dropping the requirement that "E" beirreflexive makes loops possible.
***Connected graph : A graph such that a path connects any two vertices.
****Tree: a connected graph with no cycles.
****Cycle graph : a connected graph consisting of a single cycle.
****Complete graph : a connected graph such that the path between any two vertices includes no other vertex. Hence for any two vertices "x" and "y", ("x","y") and ("y","x") are both elements of "E".
*****Tournament: A complete graph such that only one of ("x","y") and ("y","x") is an element of "E".Lattices
*
Semimodular lattice :
* Kleene lattice: a bounded distributive lattice with a unary involution, denoted by postfix ', satisfying the axioms (x∨y)' = x'∨y', x" = x, and (x∧x')∨(y∨y') = y∨y'.
*Semidistributive lattice : a lattice satisfying the axiom ("x"∧"y" = "x"∧"z")→("x"∧"y"="x"∧("y"∨"z")), and dually.Ring-like
*
Kleene algebra : a semiring withidempotent addition and a unary operation, theKleene star , denoted by postfix * and satisfying (1+x*x)x*=x*=(1+xx*)x*.Universal classes
*Quasitrivial
groupoid : amagma such that "xy" = "x" or "y".*
Integral domain : A commutative ring such that ("xy"=0)→(("x"=0)∨("y"=0)). Also a domain whose multiplication commutes.
*Integral relation algebra: arelation algebra such that ("xy"=0)→(("x"=0)∨("y"=0)).Partial order for nonlattices
If the
partial order relation ≤ is added to a structure other than a lattice, the result is a "partially ordered" structure. These are discussed in Birkhoff (1967: chpts. 13-15, 17) using a differing terminology. Examples include:
* Ordered magma,semigroup ,monoid , group, and vector space: In each case, "S" is partially ordered;
*Linearly ordered group andordered ring : "S" is linearly ordered;
**Archimedean group : alinearly ordered group for which theArchimedean property holds.
*Ordered field : a field whose "S" is totally ordered by '≤,' so that ("a"≤"b")→("a"+"c"≤"b"+"c") and (0≤"a","b")→ (0≤"ab").Nonvarieties
Nonvarieties cannot be
axiom atized solely with identities and quasiidentities. Many nonidentities are of three very simple kinds:
#The requirement that "S" (or "R" or "K") be a "nontrivial" ring, namely one such that "S"≠{0}, 0 being the additiveidentity element . The nearest thing to an identity implying "S"≠{0} is the nonidentity 0≠1, which requires that the additive and multiplicative identities be distinct.
#Axioms involving multiplication, holding for all members of "S" (or "R" or "K") except 0. In order for an algebraic structure to be a variety, the domain of each operation must be an entire underlying set; there can be nopartial operation s.
#"0 is not the successor of anything," included in nearly all arithmetics. Most of the classic results ofuniversal algebra do not hold for nonvarieties. For example, neither the free field over any set nor thedirect product ofintegral domain s exists. Nevertheless, nonvarieties often retain an undoubted algebraic flavor.There are whole classes of
axiom aticformal system s not included in this section, e.g.,logic s,topological space s, and this exclusion is in some sense arbitrary. Many of the nonvarieties below were included because of their intrinsic interest and importance, either by virtue of their foundational nature (Peano arithmetic ), ubiquity (thereal field ), or richness (e.g., fields,normed vector spaces ). Also, a great deal of theoretical physics can be recast using the nonvarieties calledmultilinear algebra s.No operations. Functions or relations may be present:
*Multiset : "S" is a multiset and N is the set ofnatural number s. There is a multifunction "m": "S"→N such that "m"("x") is themultiplicity of "x"∈"S".Arithmetics
If the name of a structure in this section includes the word "arithmetic," the structure features one or both of the
binary operation saddition andmultiplication . If both operations are included, the recursive identity defining multiplication usually links them. Arithmetics necessarily have infinite models.
*Cegielski arithmetic [Smorynski (1991).] : A commutativecancellative monoid under multiplication. 0 annihilates multiplication, and "xy"=1if and only if "x" and "y" are both 1. Other axioms and one axiom schema govern order,exponentiation ,divisibility , andprimality ; consult Smorynski. Adding thesuccessor function and its axioms as per Dedekind algebra render addition recursively definable, resulting in a system with the expressive power ofRobinson arithmetic .In the structures below, addition and multiplication, if present, arerecursive ly defined by means of aninjective operation called successor, denoted by prefix σ. 0 is the axiomaticidentity element for addition, and annihilates multiplication. Both axioms hold forsemiring s.
*Dedekind algebra [Potter (2004: 90).] , also called a "Peano algebra": A pointed unary system by virtue of 0, the unique element of "S" not included in the range of successor. Dedekind algebras are fragments of Skolem arithmetic.
** Dedekind-Peano structure: A Dedekind algebra with anaxiom schema ofinduction .
***Presburger arithmetic : A Dedekind-Peano structure withrecursive addition .Arithmetics above this line are decidable. Those below are incompletable.::*Robinson arithmetic : Presburger arithmetic withrecursive multiplication .:::*Peano arithmetic : Robinson arithmetic with anaxiom schema ofinduction . The semiring axioms for N (other than "x"+0="x" and "x"0=0, included in the recursive definitions of addition and multiplication) are now theorems. ::::*Heyting arithmetic : Peano arithmetic withintuitionist logic as the background logic.**
Primitive recursive arithmetic : A Dedekind algebra with recursively defined addition, multiplication, exponentiation, and otherprimitive recursive operations as desired. A rule of induction replaces theaxiom of induction . The background logic lacksquantification and thus is notfirst-order logic .
**Skolem arithmetic (Boolos and Jeffrey 2002: 73-76): Not an algebraic structure because there is no fixed set of operations of fixed adicity. Skolem arithmetic is a Dedekind algebra with projection functions, indexed by "n", whose arguments are functions and that return the "n"th argument of a function. Theidentity function is the projection function whose arguments are all unary operations. Composite operations of anyadicity , including addition and multiplication, may be constructed usingfunction composition andprimitive recursion . Mathematicalinduction becomes a theorem.
***Kalmar arithmetic: Skolem arithmetic with different primitive functions.The following arithmetics lack a connection between addition and multiplication. They are the simplest arithmetics capable of expressing all
primitive recursive function s.
*Baby Arithmetic [Machover, M., 1996. "Sets, Logic, and their Limitations". Cambridge Univ. Press: 10.9.] : Because there is nouniversal quantification , there are axiom schemes but no axioms. ["n"] denotes "n" consecutive applications of successor to 0. Addition and multiplication are defined by the schemes ["n"] + ["p"] = ["n"+"p"] and ["n"] ["p"] = ["np"] .
**"R" [Alfred Tarski ,Andrej Mostowski , andRaphael Robinson , 1953. "Undecidable Theories". North-Holland: 53.] : Baby arithmetic plus thebinary relation s "=" and "≤". These relations are governed by the schemes ["n"] = ["p"] ↔ "n"="p", ("x"≤ ["n"] )→("x"=0)∨,...,∨("x"= ["n"] ), and ("x"≤ ["n"] )∨( ["n"] ≤"x").Lattices that are not varieties
*Part algebra: a Boolean algebra with no least element 0, so that the complement of 1 is not defined.Two sets, Φ and "D".
*Information algebra : "D" is a lattice, and Φ is a commutativemonoid under combination, anidempotent operation. The operation of focussing, "f": Φx"D"→Φ satisfies the axiom "f"("f"(φ,"x"),"y")="f"(φ,"x"∧"y") and distributes over combination. Every element of Φ has an identity element in "D" under focussing.Field-like structures
Two
binary operation s, addition and multiplication. "S" is nontrivial, i.e., "S"≠{0}. "S"-0 is "S" with 0 removed.
* Domain: a ring whose solezero divisor is 0.
**Integral domain : acommutative ring , 0 ≠ 1, and having thezero-product property : ("x"≠0∧"y"≠0) → "xy"≠0. Hence there are nozero divisor s.
***Euclidean domain : anintegral domain with a function "f": "S"→N satisfying the division with remainder property.
*Division ring (also "skew field", "sfield"): a ring such that "S"-0 is a group under multiplication.
** Field: a division ring whose multiplication commutes. Recapitulating: addition and multiplication commute, associate, and areunital . "S" is closed under a two-sidedadditive inverse , "S"-0 under a two-sidedmultiplicative inverse . Multiplication has azero element and distributes over addition.
***Ordered field : a field whose "S" is totally ordered by '≤', so that ("a"≤"b")→("a"+"c"≤"b"+"c") and (0≤"a","b")→ (0≤"ab").
****Real closed field : an ordered real field such that for every element "x" of "S", there exists a "y" such that "x" = "y"2 or -"y"2. Allpolynomial equation s of odd degree and whose coefficients are elements of "S", have at least one root that in "S".
****Real field : aDedekind complete ordered field.
*****Differential field: A real field with an addedunary operation , derivation, denoted by postfix ' and satisfying theproduct rule , ("xy")' = "x'y" + "xy' ", and distributing overaddition , ("x"+"y")' = "x' "+ "y' ".
***Algebraically closed field : a field such that allpolynomial equation s whose coefficients are elements of "S" have all roots in "S".The following field-like structures are not varieties for reasons in addition to "S"≠{0}:
*Simple ring : a ring having no ideals other than 0 and "S".
**Weyl algebra :
*Artinian ring : a ring whose ideals satisfy thedescending chain condition .Vector spaces that are not varieties
The following composite structures are extensions of
vector space s that are not varieties. Two sets: "M" is a set of vectors and "R" is a set ofscalar s.Three binary operations.
*Normed vector space : a vector space with a norm, namely a function "M"→"R" that issymmetric ,linear , andpositive definite .
**Inner product space (also "Euclidian" vector space): a normed vector space such that "R" is thereal field , whose norm is the square root of theinner product , "M"×"M"→"R". Let "i","j", and "n" be positive integers such that 1≤"i","j"≤"n". Then "M" has anorthonormal basis such that "e"i•"e"j = 1 if "i"="j" and 0 otherwise. Seefree module .
**Unitary space: Differs from inner product spaces in that "R" is thecomplex field , and the inner product has a different name, the hermitian inner product, with different properties:conjugate symmetric,bilinear , andpositive definite . [Birkhoff and MacLane (1979: 369).]
*Graded vector space : a vector space such that the members of "M" have adirect sum decomposition. Seegraded algebra below.Structures that build on the notion of vector space:
*Matroid :
*Antimatroid :Multilinear algebras
Four
binary operation s. Two sets, "V" and "K":
# The members of "V" aremultivector s (including vectors), denoted by lower case Latin letters. "V" is anabelian group undermultivector addition, and amonoid underouter product . The outer product goes under various names, and is multilinear in principle but usuallybilinear . The outer product defines the multivectors recursively starting from the vectors. Thus the members of "V" have a "degree" (seegraded algebra below). Multivectors may have aninner product as well, denoted "u"•"v": "V"×"V"→"K", that issymmetric ,linear , andpositive definite ; seeinner product space above.
# The properties and notation of "K" are the same as those of "R" above, except that "K" may have -1 as a distinguished member. "K" is usually thereal field , as multilinear algebras are designed to describe physical phenomena withoutcomplex number s.
# Thescalar multiplication of scalars and multivectors, "V"×"K"→"V", has the same properties as module scalar multiplication.
*Symmetric algebra : aunital commutative algebra with vector multiplication.
*Universal enveloping algebra : Given aLie algebra "L" over "K", the "most general"unital associative "K"-algebra "A", such that the Lie algebra "AL" contains "L".
**Hopf algebra :
***Group Hopf algebra :
*Graded algebra : an associative algebra withunital outer product. The members of "V" have adirectram decomposition resulting in their having a "degree," with vectors having degree 1. If "u" and "v" have degree "i" and "j", respectively, the outer product of "u" and "v" is of degree "i+j". "V" also has a distinguished member 0 for each possible degree. Hence all members of "V" having the same degree form anAbelian group under addition.
**Tensor algebra : A graded algebra such that "V" includes all finite iterations of a binary operation over "V", called thetensor product . All multilinear algebras can be seen as special cases of tensor algebra.
***Exterior algebra (also "Grassmann algebra"): a graded algebra whoseanticommutative outer product, denoted by infix ∧, is called theexterior product . "V" has anorthonormal basis . "v"1 ∧ "v"2 ∧ ... ∧ "v"k = 0 if and only if "v"1, ..., "v"k arelinearly dependent . Multivectors also have aninner product .
****Clifford algebra : an exterior algebra with a symmetricbilinear form "Q": "V"×"V"→"K". The special case "Q"=0 yields an exterior algebra. The exterior product is written 〈"u","v"〉. Usually, 〈"e"i,"e"i〉 = -1 (usually) or 1 (otherwise).
****Geometric algebra : an exterior algebra whose exterior (called "geometric") product is denoted by concatenation. The geometric product of parallel multivectors commutes, that of orthogonal vectors anticommutes. The product of a scalar with a multivector commutes. "vv" yields a scalar.
*****Grassmann-Cayley algebra : a geometric algebra without an inner product.tructures with topologies or manifolds
These algebraic structures are not varieties, because the underlying set either has a
topology or is amanifold , characteristics that are not algebraic in nature. This added structure must be compatible in some sense, however, with the algebraic structure. The case of when the added structure ispartial order is discussed above, under varieties.Topology :
*Topological group : a group whose "S" has atopology ;
**Discrete group : a topological group whose topology is discrete. Also a 0-dimensionalLie group .
*Topological vector space : anormed vector space whose "R" has atopology .Manifold :
*Lie group : a group whose "S" has a smoothmanifold structure.Categories
A class "O" consisting of objects, and a class "M" consisting of
morphism s defined over "O". "O" and "M" may beproper class es. Let "x","y" be any two elements of "M". Then there exist:
*Two functions, "c", "d": "M"→"O". "d"("x") is the domain of "x", and "c"("x") is itscodomain .
*A binary partial operation over "M", called composition and denoted byconcatenation . "xy" is definediff "c"("x")="d"("y"). If "xy" is defined, "d"("xy") = "d"("x") and "c"("xy") = "c"("y").
Category: Composition associates (if defined), and "x" has left and right identity elements, the domain and codomain of "x", respectively, so that "d"("x")"x" = "x" = "xc"("x"). Letting φ stand for one of "c" or "d", and γ stand for the other, then φ(γ("x")) = γ("x"). If "O" has but one element, the associated category is amonoid .Examples
Recurring underlying sets: N=
natural numbers ; Z=integers ; Q=rational numbers ; R=real number s; C=complex number s.Arithmetics
*N is a pointed unary system, and the standard interpretation of
Peano arithmetic .
* A Dedekind algebra is a free S-algebra on zero generators of type 〈1,0〉. Freeness implies that no two terms are equal. Very general results from the theory of free algebras, e.g., definition by recursion, and uniqueness up to isomorphism, are now applicable. [Cohn, Paul, 1965. "Universal Algebra", chpt. VII.1.]
*A Dedekind-Peano structure is afree object with one generator.
*The universe ofsingleton s forms a Dedekind-Peano structure if {"x"} interprets the successor of "x", and thenull set interprets 0. [Lewis (1991).]Group-like structures
*Nonzero N under
addition is amagma .
* Z undersubtraction (−) is aquasigroup .
* Nonzero Q under division (÷) is aquasigroup .
* Z under addition (+) is anabelian group .
* Nonzero Q undermultiplication (×) is anabelian group .
*Everycyclic group "G" is abelian, because if "x", "y" are in "G", then "xy" = "a"m"a"n = "a"m+n = "a"n+m = "a"n"a"m = "yx". In particular, Z is an abelian group under addition, as are the integers modulo "n", Z/"n"Z.
* Every group is a loop, because "a"*"x" = "b"if and only if "x" = "a"−1*"b", and "y"*"a" = "b" if and only if "y" = "b"*"a"−1.
* Invertible 2x2 matrices form a group undermatrix multiplication .
*Thepermutation s preserving thepartition of a set induced by anequivalence relation form a group underfunction composition and inverse.
*MV-algebra s characterize multi-valued andfuzzy logic s.*The set of all functions "X"→"X", "X" any nonempty set, is a
monoid underfunction composition and theidentity function .
*Incategory theory , the set of allendomorphism s of object "X" in category "C" is amonoid under composition of morphisms and theidentity morphism .Also see
examples of groups ,list of small groups , andlist of finite simple groups .Lattices
* The following structures, if ordered by
set inclusion , all formmodular lattice s. The:
**Subgroup s of a group, normal or not;
**Subring s andideal s of a ring;
**Submodules of amodule and thesubspace s of avector space ;
**Equivalence relation s on any set;
**Sublattices of any lattice including theempty set .
* Theclosed set s of atopological space form a lattice under finite unions andintersection s. Theopen set s, ordered byinclusion , form a lattice under arbitrary unions.
*A Boolean algebra (BA) is also anortholattice , aBoolean ring , acommutative monoid , and a Newman algebra. The BA 2 is a boundary algebra. A BA would be anabelian group if the BA identity andinverse element s were identical.
* Anyfield of sets , and theconnective s offirst-order logic , are models of Boolean algebra. SeeLindenbaum-Tarski algebra .
* The connectives ofintuitionistic logic form a model ofHeyting algebra .
* Themodal logic s K, S4, S5, and wK4 are models of modal algebra,interior algebra ,monadic Boolean algebra , and derivative algebra, respectively.
* Anyfirst-order theory whose sentences can be written in such a way that thequantifier s do not nest more than three deep, can be recast as a model ofrelation algebra . Such models includePeano arithmetic and most axiomatic set theories, includingZFC , NBG, andNew Foundations .Ring-like structures
* N is a commutative
semiring under addition and multiplication.
* The set "R" [X] of allpolynomial s over some coefficient ring "R" is a ring.
* 2x2 matrices under matrix addition and multiplication form a ring.
* If "n" is a positive integer, then the set Z"n" = Z/nZ of integers modulo "n" (the additivecyclic group of order "n" ) forms a ring having "n" elements (seemodular arithmetic ).Field-like structures
* Z is an
integral domain under addition and multiplication.
* Each of Q, R, C, and the p-adic integers is a field under addition and multiplication.
*Q and R areordered field s, totally ordered by '≤'.
*R is the:
**OnlyDedekind complete ordered field , as the axioms for such a field arecategorical ;
**Real field grounding real andfunctional analysis ;
**Filed whose subfields include the algebraic, the computable, and thedefinable number s.
*C is analgebraically closed field .
*Some facts aboutfinite field s:
**There exists a complete classification thereof.
**Analgebraic number field innumber theory is afinite field extension of Q, that is, a field containing Q which has finite dimension as avector space over Q.
**If "q" > 1 is a power of aprime number , then there exists (up to isomorphism ) exactly onefinite field with "q" elements, usually denoted F"q", or in the case that "q" is itself prime, by Z/"q"Z. Such fields are calledGalois field s, whence the alternative notation GF("q"). All finite fields are isomorphic to some Galois field.
**Given someprime number "p", the set Z"p" = Z/"p"Z of integers modulo "p" is thefinite field with "p" elements: F"p" = {0, 1, ..., "p" − 1} where the operations are defined by performing the operation in Z, dividing by "p" and taking the remainder; seemodular arithmetic .Lie groups : Seetable of Lie groups andlist of simple Lie groups .ee also
*abstract algebra
*algebraic structure
*arity
*category theory
*free object
*operation (mathematics)
*signature
*universal algebra
*variety (universal algebra)
*list of abstract algebra topics
*list of first-order theories
*list of linear algebra topics
*list of mathematics lists Notes
References
*
Garrett Birkhoff , 1967. "Lattice Theory", 3rd ed, AMS Colloquium Publications Vol. 25. American Mathematical Society.
*--------, andSaunders MacLane , 1999 (1967). "Algebra", 2nd ed. New York: Chelsea.
*George Boolos andRichard Jeffrey , 1980. "Computability and Logic", 2nd ed. Cambridge Univ. Press.
*Dummit, David S., and Foote, Richard M., 2004. "Abstract Algebra", 3rd ed. John Wiley and Sons.
*Grätzer, George, 1978. "Universal Algebra", 2nd ed. Springer.
*David K. Lewis , 1991. "Part of Classes". Blackwell.
* Michel, Anthony N., and Herget, Charles J., 1993 (1981). "Applied Algebra and Functional Analysis". Dover.
*Potter, Michael, 2004. "Set Theory and its Philosophy", 2nd ed. Oxford Univ. Press.
*Smorynski, Craig, 1991. "Logical Number Theory I". Springer-Verlag.A monograph available free online:
* Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. " [http://www.thoralf.uwaterloo.ca/htdocs/ualg.html A Course in Universal Algebra.] " Springer-Verlag. ISBN 3-540-90578-2.External links
* Jipsen:
**Alphabetical [http://math.chapman.edu/cgi-bin/structures/ list] of algebra structures; includes many not mentioned here.
** [http://math.chapman.edu/cgi-bin/structures?Online_books_and_lecture_notes Online books and lecture notes.]
** [http://www1.chapman.edu/~jipsen/PCP/theoriesPO1.html Map] containing about 50 structures, some of which do not appear above. Likewise, most of the structures above are absent from this map.
* [http://planetmath.org/browse/objects/ PlanetMath] topic index.
*Hazewinkel, Michiel (2001) " [http://books.google.com/books?id=3ndQH4mTzWQC&dq Encyclopaedia of Mathematics.] " Springer-Verlag.
* [http://mathworld.wolfram.com/topics/Algebra.html Mathworld] page on abstract algebra.
*Stanford Encyclopedia of Philosophy : [http://plato.stanford.edu/entries/algebra/ Algebra] byVaughan Pratt .
Wikimedia Foundation. 2010.