Jump to content

Outline of algebraic structures: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
→‎Lattices: add arguesian lattice
→‎Simple structures: bipointed sets
Line 20: Line 20:
'''No''' [[binary operation]].
'''No''' [[binary operation]].
* [[Set]]: a degenerate algebraic structure having no operations.
* [[Set]]: a degenerate algebraic structure having no operations.
* [[Pointed set]]: ''S'' has one or more distinguished elements, often 0, 1, or both. While pointed sets are near-trivial, they lead to [[discrete space]]s, which are not.
* [[Pointed set]]: ''S'' has one or more distinguished elements. While pointed sets are near-trivial, they lead to [[discrete space]]s, which are not.
**[[Bipointed set]]: ''S'' has exactly two distinguished elements.
* Unary system: ''S'' and a single [[unary operation]] over ''S''.
* Unary system: ''S'' and a single [[unary operation]] over ''S''.
* Pointed unary system: a unary system with ''S'' a pointed set.
* Pointed unary system: a unary system with ''S'' a pointed set.

Revision as of 08:50, 25 October 2007

In universal algebra, a branch of pure mathematics, an algebraic structure consists of a set closed under one or more operations, satisfying a number of axioms, including none. Abstract algebra is primarily the study of algebraic structures and their properties. 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.

Other web lists of algebraic structures, organized alphabetically, include Jipsen and PlanetMath. These resources mention many structures not included below, and include more information about each structure than is presented here. This entry is more revealing of the hierarchical connections among algebraic structures than are Jipsen and PlanetMath.

Generalities

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 set, the universe S, precede composite ones built on two;
  • If A and B are two 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. No structure mentioned in this entry requires an operation whose arity exceeds 2.

If structure B is under structure A and more indented, then all theorems of A are theorems of B; the converse usually does not hold.

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). A simple example of how a nonidentity can be recast as an identity: the Boolean inequality α≤β can always be recast as the Boolean identity αβ=α.

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

One binary operation, denoted by concatenation. 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.

For monoids, loops, sloops, and combinatory algebras, S is a pointed set.

Two binary operations.

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

Three binary operations. Quasigroups are listed here, despite their having 3 binary operations, because they are (nonassociative) magmas. Quasigroups feature 3 binary operations only because establishing the quasigroup cancellation property by means of identities alone requires two binary operations in addition to the group operation.

Lattices

Two binary operations, meet (infix ∧)and join (infix ∨), that can be proved idempotent, and are connected by the absorption law. Interchanging all meets and joins preserves truth; this is the duality principle.

N.B. "Lattice" has another meaning unrelated to this section, namely a discrete subgroup of the real vector space Rn that spans Rn. See lattice (group).

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.

Four binary operations:

  • Residuated lattice: a Brouwerian algebra with a least element and a fourth binary operation, denoted by infix ⊗, such that (⊗,1) is a commutative monoid obeying the adjointness property ((xy)' z) ↔ (xyz).

Ring-like structures

Two binary operations, addition and multiplication. That multiplication has a 0 is either an axiom or a theorem.

  • Shell: addition and multiplication have respective identity elements 0 and 1.
  • Ringoid: multiplication distributes over addition..
    • Nonassociative ring: a ringoid that is an abelian group under addition.
    • 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.
      • Commutative semiring: a semiring whose multiplication commutes.
    • Rng: a ringoid that is an Abelian group under addition and 0, and a semigroup under multiplication.

N.B. These definitions do not command universal assent:

  • Some employ "ring" to denote what is here called a rng, and refer to a ring in the above sense as 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.

Partial order for nonlattices

Structures other than lattices can be applied to a partially ordered underlying set, resulting in another variety. These structures are discussed in Birkhoff (1967: chpts. 13-15, 17) using a differing terminology. Birkhoff also distinguishes partially ordered structures from the corresponding lattice-ordered ones.

Structures that are not varieties

The structures in this section are not varieties because they cannot be axiomatized with identities alone. Most of the 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.

Many mathematical structures of fundamental importance by virtue of their foundational nature (e.g., Peano arithmetic, the real field), or their richness (e.g., fields, normed vector spaces), are not varieties. Moreover, much of theoretical physics can be recast using multilinear algebras. Although structures with nonidentities retain an undoubted algebraic flavor, they suffer from defects varieties do not share. For example, neither the product of integral domains nor a free field over any set exists.

Arithmetics

One or both of the binary operations addition and multiplication. If both operations are included, the recursive identity defining multiplication links them. Arithmetics necessarily have infinite models.

  • Cegielski arithmetic (Smorynski 1991): A commutative cancellative monoid under multiplication. 0 annihilates multiplication, and xy=1 if and only if x and y are both 1. Other axioms and one axiom schema govern order, exponentiation, divisibility, and primality; consult Smorynski. Adding the successor function and its axioms as per Dedekind algebra render addition recursively definable, resulting in a system with the expressive power of Robinson arithmetic.

In the structures below, addition and multiplication, if present, are recursively defined by means of 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.

  • 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.

Lattices that are not varieties

Field-like structures

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

The following 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.

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.
  • Symmetric algebra: a unital commutative algebra with vector multiplication.
  • 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.
  • Graded algebra: an associative algebra with unital outer product. The members of V have a direct sum 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

Algebraic structures whose underlying set has either a topological or manifold structure are not varieties, because the added structure is not algebraic. The added structure must be compatible in some sense, however, with the algebraic structure. The case of when the underlying set is partially ordered is discussed above, under varieties.

Topology:

Manifold:

Examples

Some recurring universes: N=natural numbers; Z=integers; Q=rational numbers; R=real numbers; C=complex numbers.

Arithmetics

Group-like structures

Boolean algebras (BA) are primarily viewed as Boolean (complemented distributive) lattices. They are also ortholattices, rings, commutative monoids, and Newman algebras, and would be abelian groups if the BA identity and inverse elements were identical.

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

See also

Notes

  1. ^ McCune, William (1993) "Single Axioms for Groups and Abelian Groups with Various Operations," Journal of Automated Reasoning 10: 1-13.
  2. ^ Birkhoff and MacLane (1979: 369).

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: