- The following two structures form a bridge connecting
magmas and
lattices:
- 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.
-
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.
-
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.
- 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:
- Converse is an
involution and distributes over composition so that (A•B)
= B
•A
. Converse and composition each
distribute over join.
[7]
Others:
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:
Let there be two
classes:
- O whose elements are
objects, and
- M whose elements are
morphisms defined over O.
Let x and 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.
-
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.
-
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.
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(φ,x∧y) and distributes over combination. Every element of Φ has an identity element in D under focussing.
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.
- 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.
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.
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 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.
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]
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.
-
^ 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).