Thursday, January 5, 2012

Classification of Algebraic Structures (Reference)

Below is an incomplete list of common algebraic structures together with a short definition. I've come to realize that I would've loved to have something like this when I was learning it all, so I figured I'd write one for others. I'll update this as I continue to learn. This list is by no means exhaustive, and I'm sure that others have probably done similar things elsewhere with greater success. This is simply partly for my own records and partly for those interested who might not otherwise have the motivation to find such a list on their own.

In order to define any mathematical objects of significance, the following definitions are required:

Set - An unordered collection of unique objects. This is arguably the foundational object for all of mathematics (although one can make a similar argument for categories - don't worry about that). Expressed with the notation
   {a, b, c}
to describe a set consisting of elements a,b,c. May contain finitely or infinitely many elements.

n-Tuple - An ordered collection of n objects, where n is generally finite. Although a rigorous set-theoretic definition exists, it is convenient to simply think of an n-tuple as a primitive object in its own right. Denoted
   (x1, x2, ..., xn)
for a tuple of n elements.

Ordered Pair - A 2-tuple. Naming convention can be extended to "ordered triple", "ordered quadruple", etc.

From here, things get somewhat convoluted, for there are at least two ways to build more complicated structures: One via Topology and one via Abstract Algebra (I suppose a third can arise through order theory). Since the algebraic approach is more accessible and easily described, I will start with these.

Magma - An ordered pair (X, ∙), where X is a set and ∙, referred to as multiplication, is a binary operation closed under X.

Semigroup - An magma in which the multiplication operation ∙ is associative.

Monoid - A semigroup in which there exists an identity element, which is denoted 1. For any element x in X:
   x∙1 = 1∙x = x

Group - A monoid in which every element x has a multiplicative inverse. For any element x in X there is an element x':
   x∙x' = x'∙x = 1

Abelian Group - A group in which the multiplication operation is commutative. In the case of an abelian group, we traditionally use an additive notation rather than a multiplicative one. Thus the group operation is referred to as "addition", the inverse of an element x is denoted (-x), and the identity element 1 is denoted 0. This notational change is in order to remain consistent with the notation of rings (below).

Rng - An ordered triple (X, +, ∙), where X is a set, (X, +) is an abelian group, and (X, ∙) is a semigroup. It is also required that both left and right multiplication distribute over addition for elements x,y,z:
   (x+y)z = xz + yz
   z(x+y) = zx + zy

Ring - A rng in which there also exists a multiplicative identity element (X is a monoid over multiplication). The ring can be thought of as a "space" in which some form of rudimentary arithmetic can be done. The notion of arithmetic might be considered to be fully developed in the setting of a field (see below).

Commutative Ring - A ring in which the multiplication operation is commutative.

Domain - A ring with no zero divisors: There do not exist nonzero elements a,b such that ab=0 (where, remember, 0 is the additive identity element).

Integral Domain - A domain which is also a commutative ring.

Unique Factorization Domain (UFD) - An integral domain in which every element can be decomposed into a product of prime elements ("prime", in this case, having a more general ring-theoretic definition) which is unique up to a permutation of factors and multiplication by unit elements.

Principle Ideal Domain (PID) - An integral domain in which every ideal is generated by a single element. Every PID is a UFD.

Skew Field - A ring in which every element has a multiplicative inverse.

Field - A commutative ring in which every element has a multiplicative inverse (alternatively, a commutative skew field). Every field is a PID. Intuitively, a field is the minimal algebraic structure in which basic arithmetic holds: We can add, subtract, multiply, and divide as we might expect.

R-Module over a Ring - An ordered quadruple (R, M, +, ∙) in which R is a ring, M is a set which is an abelian group with respect to + (addition) and ∙ (scalar multiplication) is a function which maps RxM into M. Scalar Multiplication must also satisfy the following axioms for all elements r,s in R and x,y in M:
   r(x+y) = rx ry
   (r+s)x = rx + sx
   r(sx) = (rs)x
   1x = x, where 1 is the multiplicative identity element of R
(Note: This is the definition of a so-called "left" module. A "right" module maps from MxR into M and has similar properties for left-multiplication. If R is a commutative ring, then these notions are identical.)

Vector Space - A module in which R is a field. In this case, the elements of M are referred to as vectors.

Algebra over a Ring - An R-module together with a bilinear operation, M-multiplication, which acts on the set M.

Algebra over a Field - An algebra over a ring  in which the ring R is a field.

Associative Algebra over a Field - An algebra over a field in which M-multiplication is associative.

At this point, further generalizations require taking a look at topological structures:

Topological Space - An ordered pair (X, T) in which X is a set and T is a collection of subsets of X. It is required that T contain the empty set, X itself, and be closed under arbitrary unions and finite intersections. Topological spaces roughly correspond to the geometric of "separability" between points in space. The subsets of X which belong to T are referred to as open sets and define the fundamental topological (and geometric) structure of the space. An open set which contains a point x is referred to as a neighborhood of X.

Kolmogorov Space (T0) - A topological space which has the property that for any two points a,b in X, either a or b has a neighborhood which does not contain the other point.

Frechet Space (T1) - A topological space which has the property that for any two points a,b in X, both a and b have neighborhoods which do not contain the other point.

Hausdorff Space (T2) - A topological space which has the property that for any two points a,b in X, a and b possess neighborhoods which are disjoint from one another.

Metric Space - An ordered pair (X, d) in which X is a set and a "distance function" d from X into the positive real numbers with the following properties for any elements x,y,z in X:
   - d(x,y) > 0 if x != y (Non-Negativity)
   - d(x,y) = 0 iff x = y
   - d(x,y) = d(y,x) (Symmetry)
   - d(x,z) <= d(x,y) + d(y,z) (Triangle Inequality)
The distance function allows for a geometric notion of distance to be computed between elements as one might expect. The distance function (also called a metric) induces a topology on X.

Complete Metric Space - A metric space in which every Cauchy sequence converges. Intuitively, all sequences of elements in the space which grow increasingly close together converge to a point which is indeed an element of the space.

At this point, the algebraic and topological notions come together.

Topological Vector Space - A vector space which also has a topology defined on it.

Normed Vector Space - A vector space, which is over some a subfield of the complex numbers, together with a function p which sends a vector into the positive real numbers and has the following properties for all a in the field F and vectors x,y:
   - p(ax) = |a|p(x)
   - p(x+y) <= p(x) + p(y) (Triangle Inequality)
   - p(x) = 0 iff x is the zero vector
The similarity with the definition of a metric is not accidental, as the norm induces a metric, and thus a topology, on the vector space.

Banach Space - A normed vector space which is also a complete metric space.

Inner Product Space - A vector space, which is over either the real or complex numbers, together with a binary function <∙,∙>, the inner product, which sends a pair of vectors into the positive real numbers and has the following properties for all a in the field F and vectors x,y,z:
   - <x,y> = <y,x>*, where * denotes the complex conjugate
   - <ax,y> = a<x,y>
   - <x,x> >= 0, where equality holds only if x = 0
The inner product induces a norm, and thus a metric and a topology, on the vector space. Intuitively, the inner product space extends the normed vector space by introducing enough structure that the notion of angle can be defined; indeed, any normed vector space whose norm satisfies the parallelogram law can be extended to be an inner product space.

Hilbert Space - An inner product space which is also a complete metric space. Note that every Hilbert Space is also a Banach Space.

That's all I've got for now...I'll update this on occasion and maybe put up a post to let anybody who cares know when I do. Let me know if there are any mistakes and I'll be sure to correct them.