User:Rschwieb/Cold storage

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The following two structures form a bridge connecting magmas and lattices:

Three structures whose intended interpretations are first order logic:
Converse is an involution and distributes over composition so that (AB) = BA. Converse and composition each distribute over join.[7]


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.




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.


Lattices that are not varieties[edit]

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.


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.

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

  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.

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. 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.[12]

Three binary operations.

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