User:Rschwieb/Cold storage
- Steiner magma: A commutative magma satisfying x.xy = y.
- Squag: an idempotent Steiner magma.[1]
- Sloop: a Steiner magma with distinguished element 1, such that xx = 1.
- Equivalential algebra: a magma satisfying xx.y=y, xy.z.z=xy, and xy.xzz.xzz=xy.[2]
- Implicational calculus: a magma satisfying xy.x=x, x.yz=y.xz, and xy.y=yx.x.[3]
- Equivalence algebra: an idempotent magma satisfying xy.x=x, x.yz=xy.xz, and xy.z.y.x = xz.y.x.[4]
- Semigroup: an associative magma.
- Equivalential calculus: a commutative semigroup satisfying yyx=x.[5]
- Boolean group: a monoid with xx = identity element.
- Reductive group: an algebraic group such that the unipotent radical of the identity component of S is trivial.
- Logic algebra: a commutative monoid with a unary operation, complementation, denoted by enclosure in parentheses, and 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 a distributive lattice. (0)=1, (1)=0, ((x))=x and xx=x are now provable.
- Boolean group: a monoid with xx = identity element.
- Equivalential calculus: a commutative semigroup satisfying yyx=x.[5]
- Order (algebra): an idempotent 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 an idempotent semigroup.
- Rectangular band: a band satisfying the axiom xyz = xz.
- Normal band: a band satisfying the axiom xyzx = xzyx.
- Band: an associative order algebra, and an idempotent semigroup.
- Steiner magma: A commutative magma satisfying x.xy = y.
- 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.
- Ring: a rng that is a monoid under multiplication and 1.
- Commutative ring: a ring with commutative multiplication.
- Boolean ring: a commutative ring with idempotent multiplication, isomorphic to Boolean algebra.
- Differential ring: A ring with an added unary operation, derivation, denoted by prefix ∂ and satisfying the product rule, ∂(xy) = ∂xy+x∂y.
- Commutative ring: a ring with commutative multiplication.
- Ring: a rng that is a monoid under multiplication and 1.
- 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.
- Involutive lattice: a lattice with a unary operation, denoted by postfix ', and satisfying x"=x and (x∨y)' = x' ∧y' .
- Relatively complemented lattice:
- Complemented lattice: a lattice with 0 and 1 such that for any x there is y with x ∨ y = 1 and x∧y = 0. Not definable by identities
- Lattice with choice of complement: a lattice with a unary operation, [complementation]], denoted by postfix ', such that x∧x' = 0 and 1=0'. 0 and 1 bound S -- as well as the dual conditions.
- Orthocomplemented lattice: a lattice with complementation 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.
- De Morgan algebra: a complemented lattice satisfying x" = x and (x∨y)' = x' ∧y' . Also a bounded involutive lattice.
- Orthocomplemented lattice: a lattice with complementation satisfying x" = x and x∨y=y ↔ y' ∨x' = x' (complementation is order reversing).
- Modular lattice: a lattice satisfying the modular identity, x∨(y∧(x∨z)) = (x∨y)∧(x∨z).
- Metric lattice: not definable by identities
- Projective lattice: not definable by identities
- 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, the modal operator.
- Derivative algebra: a modal algebra whose added unary operation, the derivative operator, satisfies x**∨x*∨x = x*∨x.
- Interior algebra: a modal algebra whose added unary operation, the interior operator, satisfies x*∨x = x and x** = x*. The dual is a closure algebra.
- Monadic Boolean algebra: a closure algebra whose added unary operation, the existential quantifier, denoted by prefix ∃, satisfies the axiom ∃(∃x)' = (∃x)'. The dual operator, ∀x := (∃x' )' is the universal quantifier.
- Modal algebra: a Boolean algebra with a single added operator, the modal operator.
- 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.
- Boolean algebra: a complemented distributive lattice. Either of meet or join can be defined in terms of the other and complementation.
- Three structures whose intended interpretations are first order logic:
- Polyadic algebra: a monadic Boolean algebra with a second unary operation, denoted by prefixed S. I is an index set, J,K⊂I. ∃ maps each J into the quantifier ∃(J). S maps I→I transformations into Boolean endomorphisms on S. σ, τ range over possible transformations; δ is the identity 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(τ)∃(τ-1J) (τ injective).[6]
- Relation algebra: S, the Cartesian square of some set, is a:
- Boolean algebra under join and complementation;
- Monoid under binary composition (infix •) and the identity element I such that 1=I '∨I;
- Residuated Boolean algebra by virtue of a second unary operation, converse (postfix ) and the axiom (A•(A•B)')∨B ' = B '.
- Converse is an involution and distributes over composition so that (A•B) = B•A. Converse and composition each distribute over join.[7]
- Cylindric algebra: Boolean algebra augmented by unary cylindrification operations.
- Three structures whose intended interpretations are first order logic:
Others:
- Coalgebra: the dual of a unital associative algebra.
- 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 finite poset. Vector multiplication is defined as a convolution of functions.
- Kac-Moody algebra: a Lie algebra, usually infinite-dimensional, definable by generators and relations through a generalized Cartan matrix.
- Generalized Kac-Moody algebra: a Kac-Moody algebra whose simple roots may be imaginary.
- Affine Lie algebra: a Kac-Moody algebra whose generalized Cartan matrix is positive semi-definite and has corank 1.
Structures with topologies or manifolds
[edit]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.
- Topological group: a group whose S has a topology;
- Discrete group: a topological group whose topology is discrete. Also a 0-dimensional Lie group.
- Topological vector space: a normed vector space whose R has a topology.
Categories
[edit]Let there be two classes:
Let x and 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 its codomain.
- A binary partial operation over M, called composition and denoted by concatenation. xy is defined iff 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 a monoid.
- Groupoid: Two equivalent definitions.
- Category theory: A small category in which every morphism is an isomorphism. Equivalently, a category such that every element x of M, x(a,b), has an inverse x(b,a); see diagram in section 2.2.
- Algebraic definition: A group whose product is a partial function. Group product associates in that if ab and bc are both defined, then ab.c=a.bc. (a)a and a(a) are always defined. Also, ab.(b) = a, and (a).ab = b.
Unclassified
[edit]- Incidence algebra: An associative algebra, defined for any locally finite poset and commutative ring with unity. Part of order theory.
- Group ring:
- Path algebra: related to a quiver and a directed graph.
- Categorical algebra: an associative algebra defined for any locally finite category and commutative ring with unity. Generalizes group algebra and incidence algebra, as the concept of category generalizes group and poset.
- 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: S is an abelian group under addition and 0, S-0 is an abelian group under multiplication and 1≠0, and multiplication distributes over addition. x0 = 0 is a theorem.
- Algebraically closed field: a field such that all polynomial equations whose coefficients are elements of S have all roots in S. This field is the complex numbers.
- 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 = y2 or -y2. All polynomial equations of odd degree and whose coefficients are elements of S, have at least one root that in S.
- Real field: a Dedekind complete ordered field.
- Differential field: A real field with an added unary operation, derivation, denoted by prefix ∂, distributing over addition, ∂(x+y) = ∂x+ ∂y, and satisfying the product rule, ∂(xy) = ∂xy + x∂y.
- Field: a division ring whose multiplication commutes. Recapitulating: S is an abelian group under addition and 0, S-0 is an abelian group under multiplication and 1≠0, and multiplication distributes over addition. x0 = 0 is a theorem.
Lattices that are not varieties
[edit]- 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 commutative monoid under combination, an idempotent operation. The operation of focussing, f: ΦxD→Φ 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.
Arithmetics
[edit]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.
- Cegielski arithmetic[8]: 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 an injective operation called successor, denoted by prefix σ. 0 is the axiomatic identity element for addition, and annihilates multiplication. Both axioms hold for semirings.
- Dedekind algebra[9], 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 an axiom schema of induction.
- Presburger arithmetic: A Dedekind-Peano structure with recursive addition.
- Dedekind-Peano structure: A Dedekind algebra with an axiom schema of induction.
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.
- Primitive recursive arithmetic: A Dedekind algebra with recursively defined addition, multiplication, exponentiation, and other primitive recursive operations as desired. A rule of induction replaces the axiom of induction. The background logic lacks quantification and thus is not first-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 nth argument of a function. The identity function is the projection function whose arguments are all unary operations. Composite operations of any adicity, including addition and multiplication, may be constructed using function composition and primitive recursion. Mathematical induction 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 functions.
- Baby Arithmetic[10]: 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[11]: 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).
Nonvarieties
[edit]Nonvarieties cannot be axiomatized 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 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.
- 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.
- "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.
Combinatory logic
[edit]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. x≤y, 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.[12]
- Extensional combinatory logic: Combinatory logic with the added quasiidentity (Wx=Vx)→(W=V), with W, V containing no instance of x.
Three binary operations.
- Normed vector space: a vector space with a norm, namely a function M→R that is symmetric, linear, and positive definite.
- Inner product space (also Euclidian vector space): a normed vector space such that R is the real field, whose norm is the square root of the inner product, M×M→R. Let i,j, and n be positive integers such that 1≤i,j≤n. Then M has an orthonormal basis such that ei•ej = 1 if i=j and 0 otherwise. See free module.
- Unitary space: Differs from inner product spaces in that R is the complex field, and the inner product has a different name, the hermitian inner product, with different properties: conjugate symmetric, bilinear, and positive definite.[13]
- Graded vector space: a vector space such that the members of M have a direct sum decomposition. See graded algebra below.
- 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. v1 ∧ v2 ∧ ... ∧ 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×V→K. 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.
- Grassmann-Cayley algebra: a geometric algebra without an inner product.
- 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. v1 ∧ v2 ∧ ... ∧ vk = 0 if and only if v1, ..., vk are linearly dependent. Multivectors also have an inner product.
- 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.
- ^ Wolfram, Steven (2002) A New Kind of Science, p. 1171.
- ^ Słomczyńska, Katarzyna (2008) "Free equivalential algebras", Annals of Pure and Applied Logic 155: 86-96
- ^ Wolfram, Steven (2002) A New Kind of Science, p. 803.
- ^ Jezek, J., and Ralph McKenzie (2001) "The Variety Generated by Equivalence Algebras," Algebra Universalis 45: 212, Prop. 1.1.
- ^ Wolfram, Steven (2002) A New Kind of Science, p. 803.
- ^ Pp. 26-28, 251, of Paul Halmos (1962) Algebraic Logic. Chelsea.
- ^ Givant, Steven, 2006, "The calculus of relations as a foundation for mathematics," Journal of Automated Reasoning 37: 277-322.
- ^ Smorynski (1991).
- ^ Potter (2004: 90).
- ^ Machover, M., 1996. Sets, Logic, and their Limitations. Cambridge Univ. Press: 10.9.
- ^ Alfred Tarski, Andrej Mostowski, and Raphael Robinson, 1953. Undecidable Theories. North-Holland: 53.
- ^ Raymond Smullyan (1994) Diagonalization and Self-Reference. Oxford Univ. Press: chpt. 18.
- ^ Birkhoff and MacLane (1979: 369).