Structure (mathematical logic)

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Structure_(mathematical_logic)

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.

Universal algebra studies structures that generalize the algebraic structures such as groups, rings, fields and vector spaces. The term universal algebra is used for structures of first-order theories with no relation symbols. Model theory has a different scope that encompasses more arbitrary first-order theories, including foundational structures such as models of set theory.

From the model-theoretic point of view, structures are the objects used to define the semantics of first-order logic, cf. also Tarski's theory of truth or Tarskian semantics.

For a given theory in model theory, a structure is called a model if it satisfies all the sentences of that theory. Logicians sometimes refer to structures as "interpretations", whereas the term "interpretation" generally has a different (although related) meaning in model theory; see interpretation (model theory).

History

In the context of mathematical logic, the term "model" was first used in 1940 by the philosopher Willard Van Orman Quine, in a reference to mathematician Richard Dedekind (1831–1916), a pioneer in the development of set theory. The term "theory of models" was coined by Alfred Tarski, a member of the Lwów–Warsaw school, in 1954.

Since the 19th century, one main method for proving the consistency of a set of axioms has been to provide a model for it.

Definition

Formally, a structure can be defined as a triple ${\displaystyle \mathcal{A}=(A,\sigma ,I)}$ consisting of a domain ${\displaystyle A,}$ a signature ${\displaystyle \sigma ,}$ and an interpretation function ${\displaystyle I}$ that indicates how the signature is to be interpreted on the domain. To indicate that a structure has a particular signature ${\displaystyle \sigma }$ one can refer to it as a ${\displaystyle \sigma }$-structure.

Domain

Main article: Domain of discourse

The domain of a structure is an arbitrary set; it is also called the underlying set of the structure, its carrier (especially in universal algebra), its universe (especially in model theory, cf. universe), or its domain of discourse. In classical first-order logic, the definition of a structure prohibits the empty domain.

Sometimes the notation ${\displaystyle \mathrm{dom}(\mathcal{A})}$ or ${\displaystyle |\mathcal{A}|}$ is used for the domain of ${\displaystyle \mathcal{A},}$ but often no notational distinction is made between a structure and its domain (that is, the same symbol ${\displaystyle \mathcal{A}}$ refers both to the structure and its domain.)

Signature

Main article: Signature (logic)

The signature ${\displaystyle \sigma =(S,\mathrm{ar})}$ of a structure consists of:

• a set ${\displaystyle S}$ of function symbols and relation symbols, along with
• a function ${\displaystyle \mathrm{ar}:S\to {\mathbb{N}}_0}$ that ascribes to each symbol ${\displaystyle s}$ a natural number ${\displaystyle n=\mathrm{ar}(s).}$

The natural number ${\displaystyle n=\mathrm{ar}(s)}$ of a symbol ${\displaystyle s}$ is called the arity of ${\displaystyle s}$ because it is the arity of the interpretation of ${\displaystyle s.}$

Since the signatures that arise in algebra often contain only function symbols, a signature with no relation symbols is called an algebraic signature. A structure with such a signature is also called an algebra; this should not be confused with the notion of an algebra over a field.

Interpretation function

Main article: Interpretation (logic) § First-order logic

Not to be confused with an interpretation of a model in another model.

The interpretation function ${\displaystyle I}$ of ${\displaystyle \mathcal{A}}$ assigns functions and relations to the symbols of the signature. To each function symbol ${\displaystyle f}$ of arity ${\displaystyle n}$ is assigned an ${\displaystyle n}$-ary function ${\displaystyle f^{\mathcal{A}}=I(f)}$ on the domain. Each relation symbol ${\displaystyle R}$ of arity ${\displaystyle n}$ is assigned an ${\displaystyle n}$-ary relation ${\displaystyle R^{\mathcal{A}}=I(R)\subseteq A^{\mathrm{a}\mathrm{r}(\mathrm{R})}}$ on the domain. A nullary (${\displaystyle =0}$-ary) function symbol ${\displaystyle c}$ is called a constant symbol, because its interpretation ${\displaystyle I(c)}$ can be identified with a constant element of the domain.

When a structure (and hence an interpretation function) is given by context, no notational distinction is made between a symbol ${\displaystyle s}$ and its interpretation ${\displaystyle I(s).}$ For example, if ${\displaystyle f}$ is a binary function symbol of ${\displaystyle \mathcal{A},}$ one simply writes ${\displaystyle f:{\mathcal{A}}^2\to \mathcal{A}}$ rather than ${\displaystyle f^{\mathcal{A}}:|\mathcal{A}{|}^2\to |\mathcal{A}|.}$

Examples

The standard signature ${\displaystyle {\sigma }_f}$ for fields consists of two binary function symbols ${\displaystyle \mathbf{+}}$ and ${\displaystyle \times }$ where additional symbols can be derived, such as a unary function symbol ${\displaystyle \mathbf{-}}$ (uniquely determined by ${\displaystyle \mathbf{+}}$) and the two constant symbols ${\displaystyle \mathbf{0}}$ and ${\displaystyle \mathbf{1}}$ (uniquely determined by ${\displaystyle \mathbf{+}}$ and ${\displaystyle \times }$ respectively). Thus a structure (algebra) for this signature consists of a set of elements ${\displaystyle A}$ together with two binary functions, that can be enhanced with a unary function, and two distinguished elements; but there is no requirement that it satisfy any of the field axioms. The rational numbers ${\displaystyle \mathbb{Q},}$ the real numbers ${\displaystyle \mathbb{R}}$ and the complex numbers ${\displaystyle \mathbb{C},}$ like any other field, can be regarded as ${\displaystyle \sigma }$-structures in an obvious way: $${\displaystyle \begin{array}{rl}\mathcal{Q}& =(\mathbb{Q},{\sigma }_f,I_{\mathcal{Q}})\\ \mathcal{R}& =(\mathbb{R},{\sigma }_f,I_{\mathcal{R}})\\ \mathcal{C}& =(\mathbb{C},{\sigma }_f,I_{\mathcal{C}})\end{array}}$$

In all three cases we have the standard signature given by $${\displaystyle {\sigma }_f=(S_f,{\mathrm{ar}}_f)}$$ with ${\displaystyle S_f=\{+,\times ,-,0,1\}}$ and $${\displaystyle \begin{array}{rlrl}{\mathrm{ar}}_f& (+)& & =2,\\ {\mathrm{ar}}_f& (\times )& & =2,\\ {\mathrm{ar}}_f& (-)& & =1,\\ {\mathrm{ar}}_f& (0)& & =0,\\ {\mathrm{ar}}_f& (1)& & =0.\end{array}}$$

The interpretation function ${\displaystyle I_{\mathcal{Q}}}$ is:

${\displaystyle I_{\mathcal{Q}}(+):\mathbb{Q}\times \mathbb{Q}\to \mathbb{Q}}$ is addition of rational numbers,

${\displaystyle I_{\mathcal{Q}}(\times ):\mathbb{Q}\times \mathbb{Q}\to \mathbb{Q}}$ is multiplication of rational numbers,

${\displaystyle I_{\mathcal{Q}}(-):\mathbb{Q}\to \mathbb{Q}}$ is the function that takes each rational number ${\displaystyle x}$ to ${\displaystyle -x,}$ and

${\displaystyle I_{\mathcal{Q}}(0)\in \mathbb{Q}}$ is the number ${\displaystyle 0,}$ and

${\displaystyle I_{\mathcal{Q}}(1)\in \mathbb{Q}}$ is the number ${\displaystyle 1;}$

and ${\displaystyle I_{\mathcal{R}}}$ and ${\displaystyle I_{\mathcal{C}}}$ are similarly defined.

But the ring ${\displaystyle \mathbb{Z}}$ of integers, which is not a field, is also a ${\displaystyle {\sigma }_f}$-structure in the same way. In fact, there is no requirement that any of the field axioms hold in a ${\displaystyle {\sigma }_f}$-structure.

A signature for ordered fields needs an additional binary relation such as ${\displaystyle <}$ or ${\displaystyle \le ,}$ and therefore structures for such a signature are not algebras, even though they are of course algebraic structures in the usual, loose sense of the word.

The ordinary signature for set theory includes a single binary relation ${\displaystyle \in .}$ A structure for this signature consists of a set of elements and an interpretation of the ${\displaystyle \in }$ relation as a binary relation on these elements.

Induced substructures and closed subsets

${\displaystyle \mathcal{A}}$ is called an (induced) substructure of ${\displaystyle \mathcal{B}}$ if

• ${\displaystyle \mathcal{A}}$ and ${\displaystyle \mathcal{B}}$ have the same signature ${\displaystyle \sigma (\mathcal{A})=\sigma (\mathcal{B});}$
• the domain of ${\displaystyle \mathcal{A}}$ is contained in the domain of ${\displaystyle \mathcal{B}:}$ ${\displaystyle |\mathcal{A}|\subseteq |\mathcal{B}|;}$ and
• the interpretations of all function and relation symbols agree on ${\displaystyle |\mathcal{A}|.}$

The usual notation for this relation is ${\displaystyle \mathcal{A}\subseteq \mathcal{B}.}$

A subset ${\displaystyle B\subseteq |\mathcal{A}|}$ of the domain of a structure ${\displaystyle \mathcal{A}}$ is called closed if it is closed under the functions of ${\displaystyle \mathcal{A},}$ that is, if the following condition is satisfied: for every natural number ${\displaystyle n,}$ every ${\displaystyle n}$-ary function symbol ${\displaystyle f}$ (in the signature of ${\displaystyle \mathcal{A}}$) and all elements ${\displaystyle b_1,b_2,\dots ,b_n\in B,}$ the result of applying ${\displaystyle f}$ to the ${\displaystyle n}$-tuple ${\displaystyle b_1{b}_2\dots b_n}$ is again an element of ${\displaystyle B:}$ ${\displaystyle f(b_1,b_2,\dots ,b_n)\in B.}$

For every subset ${\displaystyle B\subseteq |\mathcal{A}|}$ there is a smallest closed subset of ${\displaystyle |\mathcal{A}|}$ that contains ${\displaystyle B.}$ It is called the closed subset generated by ${\displaystyle B,}$ or the hull of ${\displaystyle B,}$ and denoted by ${\displaystyle ⟨B⟩}$ or ${\displaystyle ⟨B{⟩}_{\mathcal{A}}}$. The operator ${\displaystyle ⟨⟩}$ is a finitary closure operator on the set of subsets of ${\displaystyle |\mathcal{A}|}$.

If ${\displaystyle \mathcal{A}=(A,\sigma ,I)}$ and ${\displaystyle B\subseteq A}$ is a closed subset, then ${\displaystyle (B,\sigma ,I^{\prime })}$ is an induced substructure of ${\displaystyle \mathcal{A},}$ where ${\displaystyle I^{\prime }}$ assigns to every symbol of σ the restriction to ${\displaystyle B}$ of its interpretation in ${\displaystyle \mathcal{A}.}$ Conversely, the domain of an induced substructure is a closed subset.

The closed subsets (or induced substructures) of a structure form a lattice. The meet of two subsets is their intersection. The join of two subsets is the closed subset generated by their union. Universal algebra studies the lattice of substructures of a structure in detail.

Examples

Let ${\displaystyle \sigma =\{+,\times ,-,0,1\}}$ be again the standard signature for fields. When regarded as ${\displaystyle \sigma }$-structures in the natural way, the rational numbers form a substructure of the real numbers, and the real numbers form a substructure of the complex numbers. The rational numbers are the smallest substructure of the real (or complex) numbers that also satisfies the field axioms.

The set of integers gives an even smaller substructure of the real numbers which is not a field. Indeed, the integers are the substructure of the real numbers generated by the empty set, using this signature. The notion in abstract algebra that corresponds to a substructure of a field, in this signature, is that of a subring, rather than that of a subfield.

The most obvious way to define a graph is a structure with a signature ${\displaystyle \sigma }$ consisting of a single binary relation symbol ${\displaystyle E.}$ The vertices of the graph form the domain of the structure, and for two vertices ${\displaystyle a}$ and ${\displaystyle b,}$ ${\displaystyle (a,b)\in \text{E}}$ means that ${\displaystyle a}$ and ${\displaystyle b}$ are connected by an edge. In this encoding, the notion of induced substructure is more restrictive than the notion of subgraph. For example, let ${\displaystyle G}$ be a graph consisting of two vertices connected by an edge, and let ${\displaystyle H}$ be the graph consisting of the same vertices but no edges. ${\displaystyle H}$ is a subgraph of ${\displaystyle G,}$ but not an induced substructure. The notion in graph theory that corresponds to induced substructures is that of induced subgraphs.

Homomorphisms and embeddings

See also: Universal algebra § Basic constructions

Homomorphisms

Given two structures ${\displaystyle \mathcal{A}}$ and ${\displaystyle \mathcal{B}}$ of the same signature σ, a (σ-)homomorphism from ${\displaystyle \mathcal{A}}$ to ${\displaystyle \mathcal{B}}$ is a map ${\displaystyle h:|\mathcal{A}|\to |\mathcal{B}|}$ that preserves the functions and relations. More precisely:

• For every n-ary function symbol f of σ and any elements ${\displaystyle a_1,a_2,\dots ,a_n\in |\mathcal{A}|}$, the following equation holds:

${\displaystyle h(f(a_1,a_2,\dots ,a_n))=f(h(a_1),h(a_2),\dots ,h(a_n))}$.

• For every n-ary relation symbol R of σ and any elements ${\displaystyle a_1,a_2,\dots ,a_n\in |\mathcal{A}|}$, the following implication holds:

${\displaystyle (a_1,a_2,\dots ,a_n)\in R^{\mathcal{A}}⟹(h(a_1),h(a_2),\dots ,h(a_n))\in R^{\mathcal{B}}}$

where ${\displaystyle R^{\mathcal{A}}}$, ${\displaystyle R^{\mathcal{B}}}$ is the interpretation of the relation symbol ${\displaystyle R}$ in the structure ${\displaystyle \mathcal{A}}$, ${\displaystyle \mathcal{B}}$ respectively.

A homomorphism h from ${\displaystyle \mathcal{A}}$ to ${\displaystyle \mathcal{B}}$ is typically denoted as ${\displaystyle h:\mathcal{A}\to \mathcal{B}}$, although technically the function h is between the domains ${\displaystyle |\mathcal{A}|}$, ${\displaystyle |\mathcal{B}|}$ of the two structures ${\displaystyle \mathcal{A}}$, ${\displaystyle \mathcal{B}}$.

For every signature σ there is a concrete category σ-Hom which has σ-structures as objects and σ-homomorphisms as morphisms.

A homomorphism ${\displaystyle h:\mathcal{A}\to \mathcal{B}}$ is sometimes called a strong homomorphism if the converse implication from above also holds. More precisely:

• For every n-ary relation symbol R of σ and any elements ${\displaystyle a_1,a_2,\dots ,a_n\in |\mathcal{A}|}$ such that ${\displaystyle (h(a_1),h(a_2),\dots ,h(a_n))\in R^{\mathcal{B}}}$, then there are ${\displaystyle a_1^{\prime },a_2^{\prime },\dots ,a_n^{\prime }\in |\mathcal{A}|}$ such that ${\displaystyle (a_1^{\prime },a_2^{\prime },\dots ,a_n^{\prime })\in R^{\mathcal{A}}}$ and ${\displaystyle h(a_1^{\prime })=h(a_1),h(a_2^{\prime })=h(a_2),\dots ,h(a_n^{\prime })=h(a_n).}$^[9]

The strong homomorphisms give rise to a subcategory of the category σ-Hom that was defined above.

Embeddings

A (σ-)homomorphism ${\displaystyle h:\mathcal{A}\to \mathcal{B}}$ is called a (σ-)embedding if it is injective and

• for every n-ary relation symbol R of σ and any elements ${\displaystyle a_1,a_2,\dots ,a_n}$, the following equivalence holds:

${\displaystyle (a_1,a_2,\dots ,a_n)\in R^{\mathcal{A}}⟺(h(a_1),h(a_2),\dots ,h(a_n))\in R^{\mathcal{B}}}$

(where ${\displaystyle R^{\mathcal{A}}}$, ${\displaystyle R^{\mathcal{B}}}$ is the interpretation of the relation symbol ${\displaystyle R}$ in the structure ${\displaystyle \mathcal{A}}$, ${\displaystyle \mathcal{B}}$ respectively).

Thus an embedding is the same thing as a strong homomorphism which is injective. The category σ-Emb of σ-structures and σ-embeddings is a concrete subcategory of σ-Hom.

Induced substructures correspond to subobjects in σ-Emb. If σ has only function symbols, σ-Emb is the subcategory of monomorphisms of σ-Hom. In this case induced substructures also correspond to subobjects in σ-Hom.

Example

As seen above, in the standard encoding of graphs as structures the induced substructures are precisely the induced subgraphs. However, a homomorphism between graphs is the same thing as a homomorphism between the two structures coding the graph. In the example of the previous section, even though the subgraph H of G is not induced, the identity map id: H → G is a homomorphism. This map is in fact a monomorphism in the category σ-Hom, and therefore H is a subobject of G which is not an induced substructure.

Homomorphism problem

The following problem is known as the homomorphism problem:

Given two finite structures ${\displaystyle \mathcal{A}}$ and ${\displaystyle \mathcal{B}}$ of a finite relational signature, find a homomorphism ${\displaystyle h:\mathcal{A}\to \mathcal{B}}$ or show that no such homomorphism exists.

Every constraint satisfaction problem (CSP) has a translation into the homomorphism problem. Therefore, the complexity of CSP can be studied using the methods of finite model theory.

Another application is in database theory, where a relational model of a database is essentially the same thing as a relational structure. It turns out that a conjunctive query on a database can be described by another structure in the same signature as the database model. A homomorphism from the relational model to the structure representing the query is the same thing as a solution to the query. This shows that the conjunctive query problem is also equivalent to the homomorphism problem.

Structures and first-order logic

See also: Model theory § First-order logic, and Model theory § Definability

Structures are sometimes referred to as "first-order structures". This is misleading, as nothing in their definition ties them to any specific logic, and in fact they are suitable as semantic objects both for very restricted fragments of first-order logic such as that used in universal algebra, and for second-order logic. In connection with first-order logic and model theory, structures are often called models, even when the question "models of what?" has no obvious answer.

Satisfaction relation

Each first-order structure ${\displaystyle \mathcal{M}=(M,\sigma ,I)}$ has a satisfaction relation ${\displaystyle \mathcal{M}\models \varphi }$ defined for all formulas ${\displaystyle \varphi }$ in the language consisting of the language of ${\displaystyle \mathcal{M}}$ together with a constant symbol for each element of ${\displaystyle M,}$ which is interpreted as that element. This relation is defined inductively using Tarski's T-schema.

A structure ${\displaystyle \mathcal{M}}$ is said to be a model of a theory ${\displaystyle T}$ if the language of ${\displaystyle \mathcal{M}}$ is the same as the language of ${\displaystyle T}$ and every sentence in ${\displaystyle T}$ is satisfied by ${\displaystyle \mathcal{M}.}$ Thus, for example, a "ring" is a structure for the language of rings that satisfies each of the ring axioms, and a model of ZFC set theory is a structure in the language of set theory that satisfies each of the ZFC axioms.

Definable relations

An ${\displaystyle n}$-ary relation ${\displaystyle R}$ on the universe (i.e. domain) ${\displaystyle M}$ of the structure ${\displaystyle \mathcal{M}}$ is said to be definable (or explicitly definable cf. Beth definability, or ${\displaystyle \mathrm{\varnothing }}$-definable, or definable with parameters from ${\displaystyle \mathrm{\varnothing }}$ cf. below) if there is a formula ${\displaystyle \phi (x_1,\dots ,x_n)}$ such that $${\displaystyle R=\{(a_1,\dots ,a_n)\in M^n:\mathcal{M}\models \phi (a_1,\dots ,a_n)\}.}$$ In other words, ${\displaystyle R}$ is definable if and only if there is a formula ${\displaystyle \phi }$ such that $${\displaystyle (a_1,\dots ,a_n)\in R\iff \mathcal{M}\models \phi (a_1,\dots ,a_n)}$$ is correct.

An important special case is the definability of specific elements. An element ${\displaystyle m}$ of ${\displaystyle M}$ is definable in ${\displaystyle \mathcal{M}}$ if and only if there is a formula ${\displaystyle \phi (x)}$ such that $${\displaystyle \mathcal{M}\models \mathrm{\forall }x(x=m\leftrightarrow \phi (x)).}$$

Definability with parameters

A relation ${\displaystyle R}$ is said to be definable with parameters (or ${\displaystyle |\mathcal{M}|}$-definable) if there is a formula ${\displaystyle \phi }$ with parameters from ${\displaystyle \mathcal{M}}$ such that ${\displaystyle R}$ is definable using ${\displaystyle \phi .}$ Every element of a structure is definable using the element itself as a parameter.

Some authors use definable to mean definable without parameters, while other authors mean definable with parameters. Broadly speaking, the convention that definable means definable without parameters is more common amongst set theorists, while the opposite convention is more common amongst model theorists.

Implicit definability

Recall from above that an ${\displaystyle n}$-ary relation ${\displaystyle R}$ on the universe ${\displaystyle M}$ of ${\displaystyle \mathcal{M}}$ is explicitly definable if there is a formula ${\displaystyle \phi (x_1,\dots ,x_n)}$ such that $${\displaystyle R=\{(a_1,\dots ,a_n)\in M^n:\mathcal{M}\models \phi (a_1,\dots ,a_n)\}.}$$

Here the formula ${\displaystyle \phi }$ used to define a relation ${\displaystyle R}$ must be over the signature of ${\displaystyle \mathcal{M}}$ and so ${\displaystyle \phi }$ may not mention ${\displaystyle R}$ itself, since ${\displaystyle R}$ is not in the signature of ${\displaystyle \mathcal{M}.}$ If there is a formula ${\displaystyle \phi }$ in the extended language containing the language of ${\displaystyle \mathcal{M}}$ and a new symbol ${\displaystyle R,}$ and the relation ${\displaystyle R}$ is the only relation on ${\displaystyle \mathcal{M}}$ such that ${\displaystyle \mathcal{M}\models \phi ,}$ then ${\displaystyle R}$ is said to be implicitly definable over ${\displaystyle \mathcal{M}.}$

By Beth's theorem, every implicitly definable relation is explicitly definable.

Many-sorted structures

Structures as defined above are sometimes called one-sorted structures to distinguish them from the more general many-sorted structures. A many-sorted structure can have an arbitrary number of domains. The sorts are part of the signature, and they play the role of names for the different domains. Many-sorted signatures also prescribe which sorts the functions and relations of a many-sorted structure are defined on. Therefore, the arities of function symbols or relation symbols must be more complicated objects such as tuples of sorts rather than natural numbers.

Vector spaces, for example, can be regarded as two-sorted structures in the following way. The two-sorted signature of vector spaces consists of two sorts V (for vectors) and S (for scalars) and the following function symbols:

+S and ×S of arity (S, S; S). −S of arity (S; S). 0S and 1S of arity (S).

+V of arity (V, V; V). −V of arity (V; V). 0V of arity (V).

× of arity (S, V; V).

If V is a vector space over a field F, the corresponding two-sorted structure ${\displaystyle \mathcal{V}}$ consists of the vector domain ${\displaystyle |\mathcal{V}{|}_V=V}$, the scalar domain ${\displaystyle |\mathcal{V}{|}_S=F}$, and the obvious functions, such as the vector zero ${\displaystyle 0_V^{\mathcal{V}}=0\in |\mathcal{V}{|}_V}$, the scalar zero ${\displaystyle 0_S^{\mathcal{V}}=0\in |\mathcal{V}{|}_S}$, or scalar multiplication ${\displaystyle {\times }^{\mathcal{V}}:|\mathcal{V}{|}_S\times |\mathcal{V}{|}_V\to |\mathcal{V}{|}_V}$.

Many-sorted structures are often used as a convenient tool even when they could be avoided with a little effort. But they are rarely defined in a rigorous way, because it is straightforward and tedious (hence unrewarding) to carry out the generalization explicitly.

In most mathematical endeavours, not much attention is paid to the sorts. A many-sorted logic however naturally leads to a type theory. As Bart Jacobs puts it: "A logic is always a logic over a type theory." This emphasis in turn leads to categorical logic because a logic over a type theory categorically corresponds to one ("total") category, capturing the logic, being fibred over another ("base") category, capturing the type theory.

Other generalizations

Partial algebras

Both universal algebra and model theory study classes of (structures or) algebras that are defined by a signature and a set of axioms. In the case of model theory these axioms have the form of first-order sentences. The formalism of universal algebra is much more restrictive; essentially it only allows first-order sentences that have the form of universally quantified equations between terms, e.g. ${\displaystyle \mathrm{\forall }}$ x ${\displaystyle \mathrm{\forall }}$y (x + y = y + x). One consequence is that the choice of a signature is more significant in universal algebra than it is in model theory. For example, the class of groups, in the signature consisting of the binary function symbol × and the constant symbol 1, is an elementary class, but it is not a variety. Universal algebra solves this problem by adding a unary function symbol ⁻¹.

In the case of fields this strategy works only for addition. For multiplication it fails because 0 does not have a multiplicative inverse. An ad hoc attempt to deal with this would be to define 0⁻¹ = 0. (This attempt fails, essentially because with this definition 0 × 0⁻¹ = 1 is not true.) Therefore, one is naturally led to allow partial functions, i.e., functions that are defined only on a subset of their domain. However, there are several obvious ways to generalize notions such as substructure, homomorphism and identity.

Structures for typed languages

In type theory, there are many sorts of variables, each of which has a type. Types are inductively defined; given two types δ and σ there is also a type σ → δ that represents functions from objects of type σ to objects of type δ. A structure for a typed language (in the ordinary first-order semantics) must include a separate set of objects of each type, and for a function type the structure must have complete information about the function represented by each object of that type.

Higher-order languages

Main article: Second-order logic

There is more than one possible semantics for higher-order logic, as discussed in the article on second-order logic. When using full higher-order semantics, a structure need only have a universe for objects of type 0, and the T-schema is extended so that a quantifier over a higher-order type is satisfied by the model if and only if it is disquotationally true. When using first-order semantics, an additional sort is added for each higher-order type, as in the case of a many sorted first order language.

Structures that are proper classes

In the study of set theory and category theory, it is sometimes useful to consider structures in which the domain of discourse is a proper class instead of a set. These structures are sometimes called class models to distinguish them from the "set models" discussed above. When the domain is a proper class, each function and relation symbol may also be represented by a proper class.

In Bertrand Russell's Principia Mathematica, structures were also allowed to have a proper class as their domain.

Social group

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Social_group

Individuals in groups are connected to each other by social relationships.

In the social sciences, a social group is defined as two or more people who interact with one another, share similar characteristics, and collectively have a sense of unity. Regardless, social groups come in a myriad of sizes and varieties. For example, a society can be viewed as a large social group. The system of behaviors and psychological processes occurring within a social group or between social groups is known as group dynamics.

Definition

Social cohesion approach

A social group exhibits some degree of social cohesion and is more than a simple collection or aggregate of individuals, such as people waiting at a bus stop, or people waiting in a line. Characteristics shared by members of a group may include interests, values, representations, ethnic or social background, and kinship ties. Kinship ties being a social bond based on common ancestry, marriage or adoption. In a similar vein, some researchers consider the defining characteristic of a group as social interaction. According to Dunbar's number, on average, people cannot maintain stable social relationships with more than 150 individuals.

Social psychologist Muzafer Sherif proposed to define a social unit as a number of individuals interacting with each other with respect to:

1. Common motives and goals
2. An accepted division of labor, i.e. roles
3. Established status (social rank, dominance) relationships
4. Accepted norms and values with reference to matters relevant to the group
5. Development of accepted sanctions (praise and punishment) if and when norms were respected or violated

This definition succeeds in providing the researcher with the tools required to answer three important questions:

1. "How is a group formed?"
2. "How does a group function?"
3. "How does one describe those social interactions that occur on the way to forming a group?"

Significance of that definition

The attention of those who use, participate in, or study groups has focused on functioning groups, on larger organizations, or on the decisions made in these organizations. Much less attention has been paid to the more ubiquitous and universal social behaviors that do not clearly demonstrate one or more of the five necessary elements described by Sherif.

Some of the earliest efforts to understand these social units have been the extensive descriptions of urban street gangs in the 1920s and 1930s, continuing through the 1950s, which understood them to be largely reactions to the established authority. The primary goal of gang members was to defend gang territory, and to define and maintain the dominance structure within the gang. There remains in the popular media and urban law enforcement agencies an avid interest in gangs, reflected in daily headlines which emphasize the criminal aspects of gang behavior. However, these studies and the continued interest have not improved the capacity to influence gang behavior or to reduce gang related violence.

The relevant literature on animal social behaviors, such as work on territory and dominance, has been available since the 1950s. Also, they have been largely neglected by policy makers, sociologists and anthropologists. Indeed, vast literature on organization, property, law enforcement, ownership, religion, warfare, values, conflict resolution, authority, rights, and families have grown and evolved without any reference to any analogous social behaviors in animals. This disconnect may be the result of the belief that social behavior in humankind is radically different from the social behavior in animals because of the human capacity for language use and rationality. Of course, while this is true, it is equally likely that the study of the social (group) behaviors of other animals might shed light on the evolutionary roots of social behavior in people.

Territorial and dominance behaviors in humans are so universal and commonplace that they are simply taken for granted (though sometimes admired, as in home ownership, or deplored, as in violence). But these social behaviors and interactions between human individuals play a special role in the study of groups: they are necessarily prior to the formation of groups. The psychological internalization of territorial and dominance experiences in conscious and unconscious memory are established through the formation of social identity, personal identity, body concept, or self concept. An adequately functioning individual identity is necessary before an individual can function in a division of labor (role), and hence, within a cohesive group. Coming to understand territorial and dominance behaviors may thus help to clarify the development, functioning, and productivity of groups.

Social identification approach

Explicitly contrasted against a social cohesion based definition for social groups is the social identity perspective, which draws on insights made in social identity theory. Here, rather than defining a social group based on expressions of cohesive social relationships between individuals, the social identity model assumes that "psychological group membership has primarily a perceptual or cognitive basis." It posits that the necessary and sufficient condition for individuals to act as group members is "awareness of a common category membership" and that a social group can be "usefully conceptualized as a number of individuals who have internalized the same social category membership as a component of their self concept." Stated otherwise, while the social cohesion approach expects group members to ask "who am I attracted to?", the social identity perspective expects group members to simply ask "who am I?"

Empirical support for the social identity perspective on groups was initially drawn from work using the minimal group paradigm. For example, it has been shown that the mere act of allocating individuals to explicitly random categories is sufficient to lead individuals to act in an ingroup favouring fashion (even where no individual self-interest is possible). Also problematic for the social cohesion account is recent research showing that seemingly meaningless categorization can be an antecedent of perceptions of interdependence with fellow category members.

While the roots of this approach to social groups had its foundations in social identity theory, more concerted exploration of these ideas occurred later in the form of self-categorization theory. Whereas social identity theory was directed initially at the explanation of intergroup conflict in the absence of any conflict of interests, self-categorization theory was developed to explain how individuals come to perceive themselves as members of a group in the first place, and how this self-grouping process underlies and determines all problems subsequent aspects of group behaviour.

Defining characteristics

In his text, Group Dynamics, Forsyth (2010) discuses several common characteristics of groups that can help to define them.

Interaction

Main article: Social interaction

This group component varies greatly, including verbal or non-verbal communication, social loafing, networking, forming bonds, etc. Research by Bales (cite, 1950, 1999) determine that there are two main types of interactions; relationship interactions and task interactions.

1. Relationship interactions: "actions performed by group members that relate to or influence the emotional and interpersonal bonds within the group, including both positive actions (social support, consideration) and negative actions (criticism, conflict)."
2. Task interactions: "actions performed by group members that pertain to the group's projects, tasks, and goals." This involve members organizing themselves and utilizing their skills and resources to achieve something.

Goals

Most groups have a reason for their existence, be it increasing the education and knowledge, receiving emotional support, or experiencing spirituality or religion. Groups can facilitate the achievement of these goals. The circumplex model of group tasks by Joseph McGrath organizes group related tasks and goals. Groups may focus on several of these goals, or one area at a time. The model divides group goals into four main types, which are further sub-categorized

1. Generating: coming up with ideas and plans to reach goals
   • Planning Tasks
   • Creativity Tasks
2. Choosing: Selecting a solution.
   • Intellective Tasks
   • Decision-making Tasks
3. Negotiating: Arranging a solution to a problem.
   • Cognitive Conflict Tasks
   • Mixed Motive Task
4. Executing: Act of carrying out a task.
   • Contests/Battles/Competitive Tasks
   • Performance/Psychomotor Tasks

Interdependence in relation

“The state of being dependent, to some degree, on other people, as when one's outcomes, actions, thoughts, feelings, and experiences are determined in whole or part by others." Some groups are more interdependent than others. For example, a sports team would have a relatively high level of interdependence as compared to a group of people watching a movie at the movie theater. Also, interdependence may be mutual (flowing back and forth between members) or more linear/unilateral. For example, some group members may be more dependent on their boss than the boss is on each of the individuals.

Structure

Group structure involves the emergence or regularities, norms, roles and relations that form within a group over time. Roles involve the expected performance and conduct of people within the group depending on their status or position within the group. Norms are the ideas adopted by the group pertaining to acceptable and unacceptable conduct by members. Group structure is a very important part of a group. If people fail to meet their expectations within to groups, and fulfil their roles, they may not accept the group, or be accepted by other group members.

Unity

When viewed holistically, a group is greater than the sum of its individual parts. When people speak of groups, they speak of the group as a whole, or an entity, rather than speaking of it in terms of individuals. For example, it would be said that "The band played beautifully." Several factors play a part in this image of unity, including group cohesiveness, and entitativity (appearance of cohesion by outsiders).

Types

Main article: Types of social groups

Donelson R. Forsyth distinguishes four main types of groups: primary groups, social groups, collectives, and categories.

Primary groups

Primary groups are small, long-term groups characterized by high amounts of cohesiveness, of member-identification, of face-to-face interaction, and of solidarity. Such groups may act as the principal source of socialization for individuals as primary groups may shape an individual's attitudes, values, and social orientation.

Three sub-groups of primary groups are:

1. kin (relatives)
2. close friends
3. neighbours

Social groups

Social groups are also small groups but are of moderate duration. These groups often form due to a common goal. In this type of group, it is possible for outgroup members (i.e., social categories of which one is not a member) to become ingroup members (i.e., social categories of which one is a member) with reasonable ease. Social groups, such as study-groups or coworkers, interact moderately over a prolonged period of time.

Collectives

In contrast, spontaneous collectives, such as bystanders or audiences of various sizes, exist only for a very brief period of time and it is very easy to become an ingroup member from an outgroup member and vice versa. Collectives may display similar actions and outlooks.

Categories

Categories consist of individuals that are similar to one another in a certain way; members of this group can be permanent ingroup members or temporary ingroup members. Examples of categories include groups with the same ethnicity, gender, religion, or nationality. This group is generally the largest type of group.

Health

The social groups people are involved with in the workplace directly affect their health. No matter where they work or what the occupation is, feeling a sense of belonging in a peer group is a key to overall success. Part of this is the responsibility of the leader (manager, supervisor, etc.). If the leader helps everyone feel a sense of belonging within the group, it can help boost morale and productivity. According to Dr. Niklas Steffens "Social identification contributes to both psychological and physiological health, but the health benefits are stronger for psychological health".

The social relationships people have can be linked to different health conditions. Lower quantity or quality social relationships have been connected to issues such as: development of cardiovascular disease, recurrent myocardial infarction, atherosclerosis, autonomic dysregulation, high blood pressure, cancer and delayed cancer recovery, and slower wound healing as well as inflammatory biomarkers and impaired immune function, factors associated with adverse health outcomes and mortality. The social relationship of marriage is the most studied of all, the marital history over the course of one's life can form differing health outcomes such as cardiovascular disease, chronic conditions, mobility limitations, self-rated health, and depressive symptoms. Social connectedness also plays a large part in overcoming certain conditions such as drug, alcohol, or substance abuse. With these types of issues, a person's peer group play a big role in helping them stay sober. Conditions do not need to be life-threatening, one's social group can help deal with work anxiety as well. When people are more socially connected have access to more support.

Some of the health issues people have may also stem from their uncertainty about just where they stand among their colleagues. It has been shown that being well socially connected has a significant impact on a person as they age, according to a 10-year study by the MacArthur Foundation, which was published in the book 'Successful Aging' the support, love, and care we feel through our social connections can help to counteract some of the health-related negatives of aging. Older people who were more active in social circles tended to be better off health-wise.

Group membership and recruitment

Social groups tend to form based on certain principles of attraction, that draw individuals to affiliate with each other, eventually forming a group.

• The Proximity Principle – the tendency for individuals to develop relationships and form groups with those they are (often physically) close to. This is often referred to as ‘familiarity breeds liking’, or that we prefer things/people that we are familiar with
• The Similarity Principle – the tendency for individuals to affiliate with or prefer individuals who share their attitudes, values, demographic characteristics, etc.
• The Complementarity Principle – the tendency for individuals to like other individuals who are dissimilar from themselves, but in a complementary manner. E.g. leaders will attract those who like being led, and those who like being led will attract leaders
• The Reciprocity Principle – the tendency for liking to be mutual. For example, if A likes B, B is inclined to like A. Conversely, if A dislikes B, B will probably not like A (negative reciprocity)
• The Elaboration Principle – the tendency for groups to complexify over time by adding new members through their relationships with existing group members. In more formal or structured groups, prospective members may need a reference from a current group member before they can join.

Other factors also influence the formation of a group. Extroverts may seek out groups more, as they find larger and more frequent interpersonal interactions stimulating and enjoyable (more than introverts). Similarly, groups may seek out extroverts more than introverts, perhaps because they find they connect with extroverts more readily. Those higher in relationality (attentiveness to their relations with other people) are also likelier to seek out and prize group membership. Relationality has also been associated with extroversion and agreeableness. Similarly, those with a high need for affiliation are more drawn to join groups, spend more time with groups and accept other group members more readily.

Previous experiences with groups (good and bad) inform people's decisions to join prospective groups. Individuals will compare the rewards of the group (e.g. belonging, emotional support, informational support, instrumental support, spiritual support; see Uchino, 2004 for an overview) against potential costs (e.g. time, emotional energy). Those with negative or 'mixed' experiences with previous groups will likely be more deliberate in their assessment of potential groups to join, and with which groups they choose to join. (For more, see Minimax Principal, as part of Social Exchange Theory)

Once a group has begun to form, it can increase membership through a few ways. If the group is an open group, where membership boundaries are relatively permeable, group members can enter and leave the group as they see fit (often via at least one of the aforementioned Principles of Attraction). A closed group  on the other hand, where membership boundaries are more rigid and closed, often engages in deliberate and/or explicit recruitment and socialization of new members.

If a group is highly cohesive, it will likely engage in processes that contribute to cohesion levels, especially when recruiting new members, who can add to a group's cohesion, or destabilize it. Classic examples of groups with high cohesion are fraternities, sororities, gangs, and cults, which are all noted for their recruitment process, especially their initiation or hazing. In all groups, formal and informal initiations add to a group's cohesion and strengthens the bond between the individual and group by demonstrating the exclusiveness of group membership as well as the recruit's dedication to the group. Initiations tend to be more formal in more cohesive groups. Initiation is also important for recruitment because it can mitigate any cognitive dissonance in potential group members.

In some instances, such as cults, recruitment can also be referred to as conversion. Kelman's Theory of Conversion identifies 3 stages of conversion: compliance (individual will comply or accept group's views, but not necessarily agree with them), identification (member begins to mimic group's actions, values, characteristics, etc.) and internalization (group beliefs and demands become congruent with member's personal beliefs, goals and values). This outlines the process of how new members can become deeply connected to the group.

Development

If one brings a small collection of strangers together in a restricted space and environment, provides a common goal and maybe a few ground rules, then a highly probable course of events will follow. Interaction between individuals is the basic requirement. At first, individuals will differentially interact in sets of twos or threes while seeking to interact with those with whom they share something in common: i.e., interests, skills, and cultural background. Relationships will develop some stability in these small sets, in that individuals may temporarily change from one set to another, but will return to the same pairs or trios rather consistently and resist change. Particular twosomes and threesomes will stake out their special spots within the overall space.

Again depending on the common goal, eventually twosomes and threesomes will integrate into larger sets of six or eight, with corresponding revisions of territory, dominance-ranking, and further differentiation of roles. All of this seldom takes place without some conflict or disagreement: for example, fighting over the distribution of resources, the choices of means and different subgoals, the development of what are appropriate norms, rewards and punishments. Some of these conflicts will be territorial in nature: i.e., jealousy over roles, or locations, or favored relationships. But most will be involved with struggles for status, ranging from mild protests to serious verbal conflicts and even dangerous violence.

By analogy to animal behavior, sociologists may term these behaviors territorial behaviors and dominance behaviors. Depending on the pressure of the common goal and on the various skills of individuals, differentiations of leadership, dominance, or authority will develop. Once these relationships solidify, with their defined roles, norms, and sanctions, a productive group will have been established.

Aggression is the mark of unsettled dominance order. Productive group cooperation requires that both dominance order and territorial arrangements (identity, self-concept) be settled with respect to the common goal and within the particular group. Some individuals may withdraw from interaction or be excluded from the developing group. Depending on the number of individuals in the original collection of strangers, and the number of "hangers-on" that are tolerated, one or more competing groups of ten or less may form, and the competition for territory and dominance will then also be manifested in the inter group transactions.

Dispersal and transformation

Two or more people in interacting situations will over time develop stable territorial relationships. As described above, these may or may not develop into groups. But stable groups can also break up in to several sets of territorial relationships. There are numerous reasons for stable groups to "malfunction" or to disperse, but essentially this is because of loss of compliance with one or more elements of the definition of group provided by Sherif. The two most common causes of a malfunctioning group are the addition of too many individuals, and the failure of the leader to enforce a common purpose, though malfunctions may occur due to a failure of any of the other elements (i.e., confusions status or of norms).

In a society, there is a need for more people to participate in cooperative endeavors than can be accommodated by a few separate groups. The military has been the best example as to how this is done in its hierarchical array of squads, platoons, companies, battalions, regiments, and divisions. Private companies, corporations, government agencies, clubs, and so on have all developed comparable (if less formal and standardized) systems when the number of members or employees exceeds the number that can be accommodated in an effective group. Not all larger social structures require the cohesion that may be found in the small group. For example, the neighborhood, the country club, or the megachurch are basically territorial organizations who support large social purposes. Any such large organizations may need only islands of cohesive leadership.

For a functioning group to attempt to add new members in a casual way is a certain prescription for failure, loss of efficiency, or disorganization. The number of functioning members in a group can be reasonably flexible between five and ten, and a long-standing cohesive group may be able to tolerate a few hangers on. The key concept is that the value and success of a group is obtained by each member maintaining a distinct, functioning identity in the minds of each of the members. The cognitive limit to this span of attention in individuals is often set at seven. Rapid shifting of attention can push the limit to about ten. After ten, subgroups will inevitably start to form with the attendant loss of purpose, dominance-order, and individuality, with confusion of roles and rules. The standard classroom with twenty to forty pupils and one teacher offers a rueful example of one supposed leader juggling a number of subgroups.

Weakening of the common purpose once a group is well established can be attributed to: adding new members; unsettled conflicts of identities (i.e., territorial problems in individuals); weakening of a settled dominance-order; and weakening or failure of the leader to tend to the group. The actual loss of a leader is frequently fatal to a group, unless there was lengthy preparation for the transition. The loss of the leader tends to dissolve all dominance relationships, as well as weakening dedication to common purpose, differentiation of roles, and maintenance of norms. The most common symptoms of a troubled group are loss of efficiency, diminished participation, or weakening of purpose, as well as an increase in verbal aggression. Often, if a strong common purpose is still present, a simple reorganization with a new leader and a few new members will be sufficient to re-establish the group, which is somewhat easier than forming an entirely new group. This is the most common factor.

Algebraic structure

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Algebraic_structure 

In mathematics, an algebraic structure or algebraic system consists of a nonempty set A (called the underlying set, carrier set or domain), a collection of operations on A (typically binary operations such as addition and multiplication), and a finite set of identities (known as axioms) that these operations must satisfy.

An algebraic structure may be based on other algebraic structures with operations and axioms involving several structures. For instance, a vector space involves a second structure called a field, and an operation called scalar multiplication between elements of the field (called scalars), and elements of the vector space (called vectors).

Abstract algebra is the name that is commonly given to the study of algebraic structures. The general theory of algebraic structures has been formalized in universal algebra. Category theory is another formalization that includes other mathematical structures and functions between structures of the same type (homomorphisms).

In universal algebra, an algebraic structure is called an algebra; this term may be ambiguous, since, in other contexts, an algebra is an algebraic structure that is a vector space over a field or a module over a commutative ring.

The collection of all structures of a given type (same operations and same laws) is called a variety in universal algebra; this term is also used with a completely different meaning in algebraic geometry, as an abbreviation of algebraic variety. In category theory, the collection of all structures of a given type and homomorphisms between them form a concrete category.

Introduction

Addition and multiplication are prototypical examples of operations that combine two elements of a set to produce a third element of the same set. These operations obey several algebraic laws. For example, a + (b + c) = (a + b) + c and a(bc) = (ab)c are associative laws, and a + b = b + a and ab = ba are commutative laws. Many systems studied by mathematicians have operations that obey some, but not necessarily all, of the laws of ordinary arithmetic. For example, the possible moves of an object in three-dimensional space can be combined by performing a first move of the object, and then a second move from its new position. Such moves, formally called rigid motions, obey the associative law, but fail to satisfy the commutative law.

Sets with one or more operations that obey specific laws are called algebraic structures. When a new problem involves the same laws as such an algebraic structure, all the results that have been proved using only the laws of the structure can be directly applied to the new problem.

In full generality, algebraic structures may involve an arbitrary collection of operations, including operations that combine more than two elements (higher arity operations) and operations that take only one argument (unary operations) or even zero arguments (nullary operations). The examples listed below are by no means a complete list, but include the most common structures taught in undergraduate courses.

Common axioms

Equational axioms

An axiom of an algebraic structure often has the form of an identity, that is, an equation such that the two sides of the equals sign are expressions that involve operations of the algebraic structure and variables. If the variables in the identity are replaced by arbitrary elements of the algebraic structure, the equality must remain true. Here are some common examples.

Commutativity

An operation ${\displaystyle \ast }$ is commutative if $${\displaystyle x\ast y=y\ast x}$$ for every x and y in the algebraic structure.

Associativity

An operation ${\displaystyle \ast }$ is associative if $${\displaystyle (x\ast y)\ast z=x\ast (y\ast z)}$$ for every x, y and z in the algebraic structure.

Left distributivity

An operation ${\displaystyle \ast }$ is left-distributive with respect to another operation ${\displaystyle +}$ if $${\displaystyle x\ast (y+z)=(x\ast y)+(x\ast z)}$$ for every x, y and z in the algebraic structure (the second operation is denoted here as ${\displaystyle +}$, because the second operation is addition in many common examples).

Right distributivity

An operation ${\displaystyle \ast }$ is right-distributive with respect to another operation ${\displaystyle +}$ if $${\displaystyle (y+z)\ast x=(y\ast x)+(z\ast x)}$$ for every x, y and z in the algebraic structure.

Distributivity

An operation ${\displaystyle \ast }$ is distributive with respect to another operation ${\displaystyle +}$ if it is both left-distributive and right-distributive. If the operation ${\displaystyle \ast }$ is commutative, left and right distributivity are both equivalent to distributivity.

Existential axioms

Some common axioms contain an existential clause. In general, such a clause can be avoided by introducing further operations, and replacing the existential clause by an identity involving the new operation. More precisely, let us consider an axiom of the form "for all X there is y such that ${\displaystyle f(X,y)=g(X,y)}$", where X is a k-tuple of variables. Choosing a specific value of y for each value of X defines a function ${\displaystyle \phi :X\mapsto y,}$ which can be viewed as an operation of arity k, and the axiom becomes the identity ${\displaystyle f(X,\phi (X))=g(X,\phi (X)).}$

The introduction of such auxiliary operation complicates slightly the statement of an axiom, but has some advantages. Given a specific algebraic structure, the proof that an existential axiom is satisfied consists generally of the definition of the auxiliary function, completed with straightforward verifications. Also, when computing in an algebraic structure, one generally uses explicitly the auxiliary operations. For example, in the case of numbers, the additive inverse is provided by the unary minus operation ${\displaystyle x\mapsto -x.}$

Also, in universal algebra, a variety is a class of algebraic structures that share the same operations, and the same axioms, with the condition that all axioms are identities. What precedes shows that existential axioms of the above form are accepted in the definition of a variety.

Here are some of the most common existential axioms.

Identity element

A binary operation ${\displaystyle \ast }$ has an identity element if there is an element e such that $${\displaystyle x\ast e=x\text{and}e\ast x=x}$$ for all x in the structure. Here, the auxiliary operation is the operation of arity zero that has e as its result.

Inverse element

Given a binary operation ${\displaystyle \ast }$ that has an identity element e, an element x is invertible if it has an inverse element, that is, if there exists an element ${\displaystyle \mathrm{inv}(x)}$ such that $${\displaystyle \mathrm{inv}(x)\ast x=e\text{and}x\ast \mathrm{inv}(x)=e.}$$For example, a group is an algebraic structure with a binary operation that is associative, has an identity element, and for which all elements are invertible.

Non-equational axioms

The axioms of an algebraic structure can be any first-order formula, that is a formula involving logical connectives (such as "and", "or" and "not"), and logical quantifiers (${\displaystyle \mathrm{\forall },\mathrm{\exists }}$) that apply to elements (not to subsets) of the structure.

Such a typical axiom is inversion in fields. This axiom cannot be reduced to axioms of preceding types. (it follows that fields do not form a variety in the sense of universal algebra.) It can be stated: "Every nonzero element of a field is invertible;" or, equivalently: the structure has a unary operation inv such that

${\displaystyle \mathrm{\forall }x,x=0\text{or}x\cdot \mathrm{inv}(x)=1.}$

The operation inv can be viewed either as a partial operation that is not defined for x = 0; or as an ordinary function whose value at 0 is arbitrary and must not be used.

Common algebraic structures

Main article: Outline of algebraic structures § Types of algebraic structures

One set with operations

Simple structures: no binary operation:

• Set: a degenerate algebraic structure S having no operations.

Group-like structures: one binary operation. The binary operation can be indicated by any symbol, or with no symbol (juxtaposition) as is done for ordinary multiplication of real numbers.

• Group: a monoid with a unary operation (inverse), giving rise to inverse elements.
• Abelian group: a group whose binary operation is commutative.

Ring-like structures or Ringoids: two binary operations, often called addition and multiplication, with multiplication distributing over addition.

• Ring: a semiring whose additive monoid is an abelian group.
• Division ring: a nontrivial ring in which division by nonzero elements is defined.
• Commutative ring: a ring in which the multiplication operation is commutative.
• Field: a commutative division ring (i.e. a commutative ring which contains a multiplicative inverse for every nonzero element).

Lattice structures: two or more binary operations, including operations called meet and join, connected by the absorption law.

• Complete lattice: a lattice in which arbitrary meet and joins exist.
• Bounded lattice: a lattice with a greatest element and least element.
• Distributive lattice: a lattice in which each of meet and join distributes over the other. A power set under union and intersection forms a distributive lattice.
• Boolean algebra: a complemented distributive lattice. Either of meet or join can be defined in terms of the other and complementation.

Two sets with operations

• Module: an abelian group M and a ring R acting as operators on M. The members of R are sometimes called scalars, and the binary operation of scalar multiplication is a function R × M → M, which satisfies several axioms. Counting the ring operations these systems have at least three operations.
• Vector space: a module where the ring R is a field or, in some contexts, a division ring.

• Algebra over a field: a module over a field, which also carries a multiplication operation that is compatible with the module structure. This includes distributivity over addition and linearity with respect to multiplication.
• Inner product space: a field F and vector space V with a definite bilinear form V × V → F.

Hybrid structures

Algebraic structures can also coexist with added structure of non-algebraic nature, such as partial order or a topology. The added structure must be compatible, in some sense, with the algebraic structure.

• Topological group: a group with a topology compatible with the group operation.
• Lie group: a topological group with a compatible smooth manifold structure.
• Ordered groups, ordered rings and ordered fields: each type of structure with a compatible partial order.
• Archimedean group: a linearly ordered group for which the Archimedean property holds.
• Topological vector space: a vector space whose M has a compatible topology.
• Normed vector space: a vector space with a compatible norm. If such a space is complete (as a metric space) then it is called a Banach space.
• Hilbert space: an inner product space over the real or complex numbers whose inner product gives rise to a Banach space structure.
• Vertex operator algebra
• Von Neumann algebra: a *-algebra of operators on a Hilbert space equipped with the weak operator topology.

Universal algebra

Main article: Universal algebra

Algebraic structures are defined through different configurations of axioms. Universal algebra abstractly studies such objects. One major dichotomy is between structures that are axiomatized entirely by identities and structures that are not. If all axioms defining a class of algebras are identities, then this class is a variety (not to be confused with algebraic varieties of algebraic geometry).

Identities are equations formulated using only the operations the structure allows, and variables that are tacitly universally quantified over the relevant universe. Identities contain no connectives, existentially quantified variables, or relations of any kind other than the allowed operations. The study of varieties is an important part of universal algebra. An algebraic structure in a variety may be understood as the quotient algebra of term algebra (also called "absolutely free algebra") divided by the equivalence relations generated by a set of identities. So, a collection of functions with given signatures generate a free algebra, the term algebra T. Given a set of equational identities (the axioms), one may consider their symmetric, transitive closure E. The quotient algebra T/E is then the algebraic structure or variety. Thus, for example, groups have a signature containing two operators: the multiplication operator m, taking two arguments, and the inverse operator i, taking one argument, and the identity element e, a constant, which may be considered an operator that takes zero arguments. Given a (countable) set of variables x, y, z, etc. the term algebra is the collection of all possible terms involving m, i, e and the variables; so for example, m(i(x), m(x, m(y,e))) would be an element of the term algebra. One of the axioms defining a group is the identity m(x, i(x)) = e; another is m(x,e) = x. The axioms can be represented as trees. These equations induce equivalence classes on the free algebra; the quotient algebra then has the algebraic structure of a group.

Some structures do not form varieties, because either:

1. It is necessary that 0 ≠ 1, 0 being the additive identity element and 1 being a multiplicative identity element, but this is a nonidentity;
2. Structures such as fields have some axioms that hold only for nonzero members of S. For an algebraic structure to be a variety, its operations must be defined for all members of S; there can be no partial operations.

Structures whose axioms unavoidably include nonidentities are among the most important ones in mathematics, e.g., fields and division rings. Structures with nonidentities present challenges that varieties do not. For example, the direct product of two fields is not a field, because ${\displaystyle (1,0)\cdot (0,1)=(0,0)}$, but fields do not have zero divisors.

Category theory

Category theory is another tool for studying algebraic structures (see, for example, Mac Lane 1998). A category is a collection of objects with associated morphisms. Every algebraic structure has its own notion of homomorphism, namely any function compatible with the operation(s) defining the structure. In this way, every algebraic structure gives rise to a category. For example, the category of groups has all groups as objects and all group homomorphisms as morphisms. This concrete category may be seen as a category of sets with added category-theoretic structure. Likewise, the category of topological groups (whose morphisms are the continuous group homomorphisms) is a category of topological spaces with extra structure. A forgetful functor between categories of algebraic structures "forgets" a part of a structure.

There are various concepts in category theory that try to capture the algebraic character of a context, for instance

• algebraic category
• essentially algebraic category
• presentable category
• locally presentable category
• monadic functors and categories
• universal property.

Different meanings of "structure"

In a slight abuse of notation, the word "structure" can also refer to just the operations on a structure, instead of the underlying set itself. For example, the sentence, "We have defined a ring structure on the set ${\displaystyle A}$", means that we have defined ring operations on the set ${\displaystyle A}$. For another example, the group ${\displaystyle (\mathbb{Z},+)}$ can be seen as a set ${\displaystyle \mathbb{Z}}$ that is equipped with an algebraic structure, namely the operation ${\displaystyle +}$.