Related Searches

List_of_algebraic_structures

List of algebraic structures

In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems 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 Jipsen and 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 axioms, 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 also semigroups 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 AxAB or AxBA.
  • 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 whose arity exceeds 2.

If structure B is under structure A and more indented, then A is interpretable in B, meaning that all theorems 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 connectives, existentially quantified variables, or relations 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 of algebraic 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.

Simple 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 to discrete spaces, which are not.
  • Unary system: S and a single unary operation over S.
  • Pointed unary system: a unary system with S a pointed set.

Group-like structures

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.

The following two structures form a bridge connecting magmas and lattices:
* Semilattice: a commutative band. The binary operation is called meet or join.
*Lattice: a semilattice with a unary operation, dualization, denoted (x) and satisfying the absorption law, x(xy) = (x(xy)) = x. xx = x is now provable.

Two binary operations.

  • Hoop: a commutative monoid with a second binary operation, denoted by infix →, satisfying the axioms x→.yz = xy.→z, xx = 1, and xy.x = yx.y.

Three binary operations.

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.

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 x1y, and the group inverse of x is defined as 1x1.

Lattice-like structures

The binary operations meet and join, which characterize all structures in this section, are idempotent, by assumption or proof. Latticoids are the only lattice-like structure that do not associate.

One binary operation, one of meet or join, denoted by concatenation. The two structures below are also magmas; see the preceding section.

  • Semilattice: the binary 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 the absorption law, x(xy) = x = (x(xy)).

Two binary operations, meet (infix ∧) and join (infix ∨). By duality, interchanging all meets and joins preserves truth.

N.B. Lattice has another mathematical meaning unrelated to this section, namely a discrete subgroup of the real vector space Rn that spans Rn.

Two structures whose intended interpretation is first-order logic:
*Polyadic algebra: a monadic Boolean algebra with a second unary operation, denoted by prefixed S. I is an index set, J,KI. ∃ maps each J into the quantifier ∃(J). S maps II transformations into Boolean endomorphisms on S. σ, τ range over possible transformations; δ is the identity transformation. The axioms are: ∃(∅)a=a, ∃(JK) = ∃(J)∃(K), S(δ)a = a, S(σ)S(τ) = S(στ), S(σ)∃(J) = S(τ)∃(J) (∀iI-J, such that σii), and ∃(J)S(τ) = S(τ)∃(τ-1J) (τ injective).
*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 a greatest element and a third binary operation, denoted by infix " ' ", satisfying ((xy)≤z)∧(yx)' z.
*Heyting algebra: a Brouwerian algebra with a least element, whose third binary operation, now called relative 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). In pointless topology, a Heyting algebra is called a frame'.

Four or more binary operations:

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.

N.B. The above definitions of rng, ring, and semiring do not command universal assent:

  • Some employ "ring" to denote what is here called a rng, 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.

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=yax=y, and bx=byx=y.
  • Monoid: a unital cancellative semigroup.

Combinatory logic

The elements of S are higher order functions, and concatenation denotes the binary operation of function 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 x0 = 0 → x=0.
    • BCK algebra: a BCI algebra satisfying the identity x0 = x. xy, defined as xy=0, induces a partial order with 0 as least element.
  • Combinatory logic: A combinator concatenates upper case letters. Terms concatenate combinators and lower case letters. Concatenation is left and right cancellative. '=' is an equivalence relation over terms. The axioms are Sxyz = xz.yz and Kxy = 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 Ix=x and 1xy=xy. Combinatory logic has the expressive power of set theory.

Graphs

One set, V a finite set of vertices, and a binary relation EV2, adjacency, consisting of edges. No operations.

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 (xy = xz)→(xy=x∧(yz)), and dually.

Ring-like

Universal classes

  • Quasitrivial groupoid: a magma 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: a relation 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:

Nonvarieties

Nonvarieties cannot be axiomatized solely with identities and quasiidentities. Many nonidentities are of three very simple kinds:

  1. The requirement that S (or R or K) be a "nontrivial" ring, namely one such that S≠{0}, 0 being the additive identity 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.
  2. 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 no partial operations.
  3. "0 is not the successor of anything," included in nearly all arithmetics.

Most of the classic results of universal algebra do not hold for nonvarieties. For example, neither the free field over any set nor the direct product of integral domains exists. Nevertheless, nonvarieties often retain an undoubted algebraic flavor.

There are whole classes of axiomatic formal systems not included in this section, e.g., logics, topological spaces, 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 (the real field), or richness (e.g., fields, normed vector spaces). Also, a great deal of theoretical physics can be recast using the nonvarieties called multilinear algebras.

No operations. Functions or relations may be present:

Arithmetics

If the name of a structure in this section includes the word "arithmetic," the structure features one or both of the binary operations addition and multiplication. If both operations are included, the recursive identity defining multiplication usually links them. Arithmetics necessarily have infinite models.

In the structures below, addition and multiplication, if present, are recursively defined by means of an injective operation called successor, denoted by prefix σ. 0 is the axiomatic identity element for addition, and annihilates multiplication. Both axioms hold for semirings.

Arithmetics above this line are decidable. Those below are incompletable.

*Robinson arithmetic: Presburger arithmetic with recursive multiplication.
* Peano arithmetic: Robinson arithmetic with an axiom schema of induction. The semiring axioms for N (other than x+0=x and x0=0, included in the recursive definitions of addition and multiplication) are now theorems.
*Heyting arithmetic: Peano arithmetic with intuitionist logic as the background logic.

The following arithmetics lack a connection between addition and multiplication. They are the simplest arithmetics capable of expressing all primitive recursive functions.

  • Baby Arithmetic: Because there is no universal 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: Baby arithmetic plus the binary relations "=" 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

Two sets, Φ and D.

  • Information algebra: D is a lattice, and Φ is a commutative monoid under combination, an idempotent operation. The operation of focussing, f: ΦxD→Φ satisfies the axiom f(f(φ,x),y)=f(φ,xy) and distributes over combination. Every element of Φ has an identity element in D under focussing.

Field-like structures

Two binary operations, addition and multiplication. S is nontrivial, i.e., S≠{0}. S-0 is S with 0 removed.

The following field-like structures are not varieties for reasons in addition to S≠{0}:

Vector spaces that are not varieties

The following composite structures are extensions of vector spaces that are not varieties. Two sets: M is a set of vectors and R is a set of scalars.

Three binary operations.

Structures that build on the notion of vector space:

Multilinear algebras

Four binary operations. Two sets, V and K:

  1. The members of V are multivectors (including vectors), denoted by lower case Latin letters. V is an abelian group under multivector addition, and a monoid under outer product. The outer product goes under various names, and is multilinear in principle but usually bilinear. The outer product defines the multivectors recursively starting from the vectors. Thus the members of V have a "degree" (see graded algebra below). Multivectors may have an inner product as well, denoted uv: V×VK, that is symmetric, linear, and positive definite; see inner product space above.
  2. 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 the real field, as multilinear algebras are designed to describe physical phenomena without complex numbers.
  3. The scalar multiplication of scalars and multivectors, V×KV, has the same properties as module scalar multiplication.
  4. Symmetric algebra: a unital commutative algebra with vector multiplication.
  5. Universal enveloping algebra: Given a Lie algebra L over K, the "most general" unital associative K-algebra A, such that the Lie algebra AL contains L.
  6. Graded algebra: an associative algebra with unital outer product. The members of V have a directram 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 an Abelian group under addition.
    • Tensor algebra: A graded algebra such that V includes all finite iterations of a binary operation over V, called the tensor product. All multilinear algebras can be seen as special cases of tensor algebra.
      • Exterior algebra (also Grassmann algebra): a graded algebra whose anticommutative outer product, denoted by infix ∧, is called the exterior product. V has an orthonormal basis. v1v2 ∧ ... ∧ vk = 0 if and only if v1, ..., vk are linearly dependent. Multivectors also have an inner product.
        • Clifford algebra: an exterior algebra with a symmetric bilinear form Q: V×VK. The special case Q=0 yields an exterior algebra. The exterior product is written 〈u,v〉. Usually, 〈ei,ei〉 = -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.

Structures with topologies or manifolds

These algebraic structures are not varieties, because the underlying set either has a topology or is a manifold, 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 is partial order is discussed above, under varieties.

Topology:

Manifold:

Categories

A class O consisting of objects, and a class M consisting of morphisms defined over O. O and M may be proper classes. Let x,y be any two elements of M. Then there exist:

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 a monoid.

Examples

Recurring underlying sets: N=natural numbers; Z=integers; Q=rational numbers; R=real numbers; C=complex numbers.

Arithmetics

Group-like structures

Also see examples of groups, list of small groups, and list of finite simple groups.

Lattices

Ring-like structures

  • N is a commutative semiring under addition and multiplication.
  • The set R[X] of all polynomials 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 Zn = Z/nZ of integers modulo n (the additive cyclic group of order n ) forms a ring having n elements (see modular arithmetic).

Field-like structures

Lie groups: See table of Lie groups and list of simple Lie groups.

See also

Notes

References

  • Garrett Birkhoff, 1967. Lattice Theory, 3rd ed, AMS Colloquium Publications Vol. 25. American Mathematical Society.
  • --------, and Saunders MacLane, 1999 (1967). Algebra, 2nd ed. New York: Chelsea.
  • George Boolos and Richard 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:

External links

Search another word or see List_of_algebraic_structureson Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature