Group (mathematics)

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Group_(mathematics) 

The manipulations of the Rubik's Cube form the Rubik's Cube group.

In mathematics, a group is a set and an operation that combines any two elements of the set to produce a third element of the set, in such a way that the operation is associative, an identity element exists and every element has an inverse. These three axioms hold for number systems and many other mathematical structures. For example, the integers together with the addition operation form a group. The concept of a group and the axioms that define it were elaborated for handling, in a unified way, essential structural properties of very different mathematical entities such as numbers, geometric shapes and polynomial roots. Because the concept of groups is ubiquitous in numerous areas both within and outside mathematics, some authors consider it as a central organizing principle of contemporary mathematics.

In geometry groups arise naturally in the study of symmetries and geometric transformations: The symmetries of an object form a group, called the symmetry group of the object, and the transformations of a given type form a general group. Lie groups appear in symmetry groups in geometry, and also in the Standard Model of particle physics. The Poincaré group is a Lie group consisting of the symmetries of spacetime in special relativity. Point groups describe symmetry in molecular chemistry.

The concept of a group arose in the study of polynomial equations, starting with Évariste Galois in the 1830s, who introduced the term group (French: groupe) for the symmetry group of the roots of an equation, now called a Galois group. After contributions from other fields such as number theory and geometry, the group notion was generalized and firmly established around 1870. Modern group theory—an active mathematical discipline—studies groups in their own right. To explore groups, mathematicians have devised various notions to break groups into smaller, better-understandable pieces, such as subgroups, quotient groups and simple groups. In addition to their abstract properties, group theorists also study the different ways in which a group can be expressed concretely, both from a point of view of representation theory (that is, through the representations of the group) and of computational group theory. A theory has been developed for finite groups, which culminated with the classification of finite simple groups, completed in 2004. Since the mid-1980s, geometric group theory, which studies finitely generated groups as geometric objects, has become an active area in group theory.

Definition and illustration

First example: the integers

One of the more familiar groups is the set of integers

$${\displaystyle \mathbb {Z} =\{\ldots ,-4,-3,-2,-1,0,1,2,3,4,\ldots \}}$$

together with addition. For any two integers ${\displaystyle a}$ and ${\displaystyle b}$, the sum ${\displaystyle a+b}$ is also an integer; this closure property says that ${\displaystyle +}$ is a binary operation on ${\displaystyle \mathbb {Z} }$. The following properties of integer addition serve as a model for the group axioms in the definition below.

• For all integers ${\displaystyle a}$, ${\displaystyle b}$ and ${\displaystyle c}$, one has ${\displaystyle (a+b)+c=a+(b+c)}$. Expressed in words, adding ${\displaystyle a}$ to ${\displaystyle b}$ first, and then adding the result to ${\displaystyle c}$ gives the same final result as adding ${\displaystyle a}$ to the sum of ${\displaystyle b}$ and ${\displaystyle c}$. This property is known as associativity.
• If ${\displaystyle a}$ is any integer, then ${\displaystyle 0+a=a}$ and ${\displaystyle a+0=a}$. Zero is called the identity element of addition because adding it to any integer returns the same integer.
• For every integer ${\displaystyle a}$, there is an integer ${\displaystyle b}$ such that ${\displaystyle a+b=0}$ and ${\displaystyle b+a=0}$. The integer ${\displaystyle b}$ is called the inverse element of the integer ${\displaystyle a}$ and is denoted ${\displaystyle -a}$.

The integers, together with the operation ${\displaystyle +}$, form a mathematical object belonging to a broad class sharing similar structural aspects. To appropriately understand these structures as a collective, the following definition is developed.

Definition

The axioms for a group are short and natural... Yet somehow hidden behind these axioms is the monster simple group, a huge and extraordinary mathematical object, which appears to rely on numerous bizarre coincidences to exist. The axioms for groups give no obvious hint that anything like this exists.

Richard Borcherds in Mathematicians: An Outer View of the Inner World

A group is a set ${\displaystyle G}$ together with a binary operation on ${\displaystyle G}$, here denoted "${\displaystyle \cdot }$", that combines any two elements ${\displaystyle a}$ and ${\displaystyle b}$ to form an element of ${\displaystyle G}$, denoted ${\displaystyle a\cdot b}$, such that the following three requirements, known as group axioms, are satisfied:

Associativity

For all ${\displaystyle a}$, ${\displaystyle b}$, ${\displaystyle c}$ in ${\displaystyle G}$, one has ${\displaystyle (a\cdot b)\cdot c=a\cdot (b\cdot c)}$.

Identity element

There exists an element ${\displaystyle e}$ in ${\displaystyle G}$ such that, for every ${\displaystyle a}$ in ${\displaystyle G}$, one has ${\displaystyle e\cdot a=a}$ and ${\displaystyle a\cdot e=a}$.

Such an element is unique (see below). It is called the identity element of the group.

Inverse element

For each ${\displaystyle a}$ in ${\displaystyle G}$, there exists an element ${\displaystyle b}$ in ${\displaystyle G}$ such that ${\displaystyle a\cdot b=e}$ and ${\displaystyle b\cdot a=e}$, where ${\displaystyle e}$ is the identity element.

For each ${\displaystyle a}$, the element ${\displaystyle b}$ is unique (see below); it is called the inverse of ${\displaystyle a}$ and is commonly denoted ${\displaystyle a^{-1}}$.

Notation and terminology

Formally, the group is the ordered pair of a set and a binary operation on this set that satisfies the group axioms. The set is called the underlying set of the group, and the operation is called the group operation or the group law.

A group and its underlying set are thus two different mathematical objects. To avoid cumbersome notation, it is common to abuse notation by using the same symbol to denote both. This reflects also an informal way of thinking: that the group is the same as the set except that it has been enriched by additional structure provided by the operation.

For example, consider the set of real numbers ${\displaystyle \mathbb {R} }$, which has the operations of addition ${\displaystyle a+b}$ and multiplication ${\displaystyle ab}$. Formally, ${\displaystyle \mathbb {R} }$ is a set, ${\displaystyle (\mathbb {R} ,+)}$ is a group, and ${\displaystyle (\mathbb {R} ,+,\cdot )}$ is a field. But it is common to write ${\displaystyle \mathbb {R} }$ to denote any of these three objects.

The additive group of the field ${\displaystyle \mathbb {R} }$ is the group whose underlying set is ${\displaystyle \mathbb {R} }$ and whose operation is addition. The multiplicative group of the field ${\displaystyle \mathbb {R} }$ is the group ${\displaystyle \mathbb {R} ^{\times }}$ whose underlying set is the set of nonzero real numbers ${\displaystyle \mathbb {R} \smallsetminus \{0\}}$ and whose operation is multiplication.

More generally, one speaks of an additive group whenever the group operation is notated as addition; in this case, the identity is typically denoted ${\displaystyle 0}$, and the inverse of an element ${\displaystyle x}$ is denoted ${\displaystyle -x}$. Similarly, one speaks of a multiplicative group whenever the group operation is notated as multiplication; in this case, the identity is typically denoted ${\displaystyle 1}$, and the inverse of an element ${\displaystyle x}$ is denoted ${\displaystyle x^{-1}}$. In a multiplicative group, the operation symbol is usually omitted entirely, so that the operation is denoted by juxtaposition, ${\displaystyle ab}$ instead of ${\displaystyle a\cdot b}$.

The definition of a group does not require that ${\displaystyle a\cdot b=b\cdot a}$ for all elements ${\displaystyle a}$ and ${\displaystyle b}$ in ${\displaystyle G}$. If this additional condition holds, then the operation is said to be commutative, and the group is called an abelian group. It is a common convention that for an abelian group either additive or multiplicative notation may be used, but for a nonabelian group only multiplicative notation is used.

Several other notations are commonly used for groups whose elements are not numbers. For a group whose elements are functions, the operation is often function composition ${\displaystyle f\circ g}$; then the identity may be denoted id. In the more specific cases of geometric transformation groups, symmetry groups, permutation groups, and automorphism groups, the symbol ${\displaystyle \circ }$ is often omitted, as for multiplicative groups. Many other variants of notation may be encountered.

Second example: a symmetry group

Two figures in the plane are congruent if one can be changed into the other using a combination of rotations, reflections, and translations. Any figure is congruent to itself. However, some figures are congruent to themselves in more than one way, and these extra congruences are called symmetries. A square has eight symmetries. These are:

The elements of the symmetry group of the square, ${\displaystyle \mathrm {D} _{4}}$. Vertices are identified by color or number.

${\displaystyle \mathrm {id} }$ (keeping it as it is)	${\displaystyle r_{1}}$ (rotation by 90° clockwise)	${\displaystyle r_{2}}$ (rotation by 180°)	${\displaystyle r_{3}}$ (rotation by 270° clockwise)
${\displaystyle f_{\mathrm {v} }}$ (vertical reflection)	${\displaystyle f_{\mathrm {h} }}$ (horizontal reflection)	${\displaystyle f_{\mathrm {d} }}$ (diagonal reflection)	${\displaystyle f_{\mathrm {c} }}$ (counter-diagonal reflection)

• the identity operation leaving everything unchanged, denoted id;
• rotations of the square around its center by 90°, 180°, and 270° clockwise, denoted by ${\displaystyle r_{1}}$, ${\displaystyle r_{2}}$ and ${\displaystyle r_{3}}$, respectively;
• reflections about the horizontal and vertical middle line (${\displaystyle f_{\mathrm {v} }}$ and ${\displaystyle f_{\mathrm {h} }}$), or through the two diagonals (${\displaystyle f_{\mathrm {d} }}$ and ${\displaystyle f_{\mathrm {c} }}$).

These symmetries are functions. Each sends a point in the square to the corresponding point under the symmetry. For example, ${\displaystyle r_{1}}$ sends a point to its rotation 90° clockwise around the square's center, and ${\displaystyle f_{\mathrm {h} }}$ sends a point to its reflection across the square's vertical middle line. Composing two of these symmetries gives another symmetry. These symmetries determine a group called the dihedral group of degree four, denoted ${\displaystyle \mathrm {D} _{4}}$. The underlying set of the group is the above set of symmetries, and the group operation is function composition. Two symmetries are combined by composing them as functions, that is, applying the first one to the square, and the second one to the result of the first application. The result of performing first ${\displaystyle a}$ and then ${\displaystyle b}$ is written symbolically from right to left as ${\displaystyle b\circ a}$ ("apply the symmetry ${\displaystyle b}$ after performing the symmetry ${\displaystyle a}$"). This is the usual notation for composition of functions.

The group table lists the results of all such compositions possible. For example, rotating by 270° clockwise (${\displaystyle r_{3}}$) and then reflecting horizontally (${\displaystyle f_{\mathrm {h} }}$) is the same as performing a reflection along the diagonal (${\displaystyle f_{\mathrm {d} }}$). Using the above symbols, highlighted in blue in the group table:

$${\displaystyle f_{\mathrm {h} }\circ r_{3}=f_{\mathrm {d} }.}$$

Group table of ${\displaystyle \mathrm {D} _{4}}$

${\displaystyle \circ }$	${\displaystyle \mathrm {id} }$	${\displaystyle r_{1}}$	${\displaystyle r_{2}}$	${\displaystyle r_{3}}$	${\displaystyle f_{\mathrm {v} }}$	${\displaystyle f_{\mathrm {h} }}$	${\displaystyle f_{\mathrm {d} }}$	${\displaystyle f_{\mathrm {c} }}$
${\displaystyle \mathrm {id} }$	${\displaystyle \mathrm {id} }$	${\displaystyle r_{1}}$	${\displaystyle r_{2}}$	${\displaystyle r_{3}}$	${\displaystyle f_{\mathrm {v} }}$	${\displaystyle f_{\mathrm {h} }}$	${\displaystyle f_{\mathrm {d} }}$	${\displaystyle f_{\mathrm {c} }}$
${\displaystyle r_{1}}$	${\displaystyle r_{1}}$	${\displaystyle r_{2}}$	${\displaystyle r_{3}}$	${\displaystyle \mathrm {id} }$	${\displaystyle f_{\mathrm {c} }}$	${\displaystyle f_{\mathrm {d} }}$	${\displaystyle f_{\mathrm {v} }}$	${\displaystyle f_{\mathrm {h} }}$
${\displaystyle r_{2}}$	${\displaystyle r_{2}}$	${\displaystyle r_{3}}$	${\displaystyle \mathrm {id} }$	${\displaystyle r_{1}}$	${\displaystyle f_{\mathrm {h} }}$	${\displaystyle f_{\mathrm {v} }}$	${\displaystyle f_{\mathrm {c} }}$	${\displaystyle f_{\mathrm {d} }}$
${\displaystyle r_{3}}$	${\displaystyle r_{3}}$	${\displaystyle \mathrm {id} }$	${\displaystyle r_{1}}$	${\displaystyle r_{2}}$	${\displaystyle f_{\mathrm {d} }}$	${\displaystyle f_{\mathrm {c} }}$	${\displaystyle f_{\mathrm {h} }}$	${\displaystyle f_{\mathrm {v} }}$
${\displaystyle f_{\mathrm {v} }}$	${\displaystyle f_{\mathrm {v} }}$	${\displaystyle f_{\mathrm {d} }}$	${\displaystyle f_{\mathrm {h} }}$	${\displaystyle f_{\mathrm {c} }}$	${\displaystyle \mathrm {id} }$	${\displaystyle r_{2}}$	${\displaystyle r_{1}}$	${\displaystyle r_{3}}$
${\displaystyle f_{\mathrm {h} }}$	${\displaystyle f_{\mathrm {h} }}$	${\displaystyle f_{\mathrm {c} }}$	${\displaystyle f_{\mathrm {v} }}$	${\displaystyle f_{\mathrm {d} }}$	${\displaystyle r_{2}}$	${\displaystyle \mathrm {id} }$	${\displaystyle r_{3}}$	${\displaystyle r_{1}}$
${\displaystyle f_{\mathrm {d} }}$	${\displaystyle f_{\mathrm {d} }}$	${\displaystyle f_{\mathrm {h} }}$	${\displaystyle f_{\mathrm {c} }}$	${\displaystyle f_{\mathrm {v} }}$	${\displaystyle r_{3}}$	${\displaystyle r_{1}}$	${\displaystyle \mathrm {id} }$	${\displaystyle r_{2}}$
${\displaystyle f_{\mathrm {c} }}$	${\displaystyle f_{\mathrm {c} }}$	${\displaystyle f_{\mathrm {v} }}$	${\displaystyle f_{\mathrm {d} }}$	${\displaystyle f_{\mathrm {h} }}$	${\displaystyle r_{1}}$	${\displaystyle r_{3}}$	${\displaystyle r_{2}}$	${\displaystyle \mathrm {id} }$
The elements ${\displaystyle \mathrm {id} }$, ${\displaystyle r_{1}}$, ${\displaystyle r_{2}}$, and ${\displaystyle r_{3}}$ form a subgroup whose group table is highlighted in   red (upper left region). A left and right coset of this subgroup are highlighted in   green (in the last row) and   yellow (last column), respectively. The result of the composition ${\displaystyle f_{\mathrm {h} }\circ r_{3}}$, the symmetry ${\displaystyle f_{\mathrm {d} }}$, is highlighted in   blue (below table center).

Given this set of symmetries and the described operation, the group axioms can be understood as follows.

Binary operation: Composition is a binary operation. That is, ${\displaystyle a\circ b}$ is a symmetry for any two symmetries ${\displaystyle a}$ and ${\displaystyle b}$. For example,

$${\displaystyle r_{3}\circ f_{\mathrm {h} }=f_{\mathrm {c} },}$$

that is, rotating 270° clockwise after reflecting horizontally equals reflecting along the counter-diagonal (${\displaystyle f_{\mathrm {c} }}$). Indeed, every other combination of two symmetries still gives a symmetry, as can be checked using the group table.

Associativity: The associativity axiom deals with composing more than two symmetries: Starting with three elements ${\displaystyle a}$, ${\displaystyle b}$ and ${\displaystyle c}$ of ${\displaystyle \mathrm {D} _{4}}$, there are two possible ways of using these three symmetries in this order to determine a symmetry of the square. One of these ways is to first compose ${\displaystyle a}$ and ${\displaystyle b}$ into a single symmetry, then to compose that symmetry with ${\displaystyle c}$. The other way is to first compose ${\displaystyle b}$ and ${\displaystyle c}$, then to compose the resulting symmetry with ${\displaystyle a}$. These two ways must give always the same result, that is,

$${\displaystyle (a\circ b)\circ c=a\circ (b\circ c),}$$

For example, ${\displaystyle (f_{\mathrm {d} }\circ f_{\mathrm {v} })\circ r_{2}=f_{\mathrm {d} }\circ (f_{\mathrm {v} }\circ r_{2})}$ can be checked using the group table:

$${\displaystyle {\begin{aligned}(f_{\mathrm {d} }\circ f_{\mathrm {v} })\circ r_{2}&=r_{3}\circ r_{2}=r_{1}\\f_{\mathrm {d} }\circ (f_{\mathrm {v} }\circ r_{2})&=f_{\mathrm {d} }\circ f_{\mathrm {h} }=r_{1}.\end{aligned}}}$$

Identity element: The identity element is ${\displaystyle \mathrm {id} }$, as it does not change any symmetry ${\displaystyle a}$ when composed with it either on the left or on the right.

Inverse element: Each symmetry has an inverse: ${\displaystyle \mathrm {id} }$, the reflections ${\displaystyle f_{\mathrm {h} }}$, ${\displaystyle f_{\mathrm {v} }}$, ${\displaystyle f_{\mathrm {d} }}$, ${\displaystyle f_{\mathrm {c} }}$ and the 180° rotation ${\displaystyle r_{2}}$ are their own inverse, because performing them twice brings the square back to its original orientation. The rotations ${\displaystyle r_{3}}$ and ${\displaystyle r_{1}}$ are each other's inverses, because rotating 90° and then rotation 270° (or vice versa) yields a rotation over 360° which leaves the square unchanged. This is easily verified on the table.

In contrast to the group of integers above, where the order of the operation is immaterial, it does matter in ${\displaystyle \mathrm {D} _{4}}$, as, for example, ${\displaystyle f_{\mathrm {h} }\circ r_{1}=f_{\mathrm {c} }}$ but ${\displaystyle r_{1}\circ f_{\mathrm {h} }=f_{\mathrm {d} }}$. In other words, ${\displaystyle \mathrm {D} _{4}}$ is not abelian.

History

Main article: History of group theory

The modern concept of an abstract group developed out of several fields of mathematics. The original motivation for group theory was the quest for solutions of polynomial equations of degree higher than 4. The 19th-century French mathematician Évariste Galois, extending prior work of Paolo Ruffini and Joseph-Louis Lagrange, gave a criterion for the solvability of a particular polynomial equation in terms of the symmetry group of its roots (solutions). The elements of such a Galois group correspond to certain permutations of the roots. At first, Galois's ideas were rejected by his contemporaries, and published only posthumously. More general permutation groups were investigated in particular by Augustin Louis Cauchy. Arthur Cayley's On the theory of groups, as depending on the symbolic equation ${\displaystyle \theta ^{n}=1}$ (1854) gives the first abstract definition of a finite group.

Geometry was a second field in which groups were used systematically, especially symmetry groups as part of Felix Klein's 1872 Erlangen program. After novel geometries such as hyperbolic and projective geometry had emerged, Klein used group theory to organize them in a more coherent way. Further advancing these ideas, Sophus Lie founded the study of Lie groups in 1884.

The third field contributing to group theory was number theory. Certain abelian group structures had been used implicitly in Carl Friedrich Gauss's number-theoretical work Disquisitiones Arithmeticae (1798), and more explicitly by Leopold Kronecker. In 1847, Ernst Kummer made early attempts to prove Fermat's Last Theorem by developing groups describing factorization into prime numbers.

The convergence of these various sources into a uniform theory of groups started with Camille Jordan's Traité des substitutions et des équations algébriques (1870). Walther von Dyck (1882) introduced the idea of specifying a group by means of generators and relations, and was also the first to give an axiomatic definition of an "abstract group", in the terminology of the time. As of the 20th century, groups gained wide recognition by the pioneering work of Ferdinand Georg Frobenius and William Burnside, who worked on representation theory of finite groups, Richard Brauer's modular representation theory and Issai Schur's papers. The theory of Lie groups, and more generally locally compact groups was studied by Hermann Weyl, Élie Cartan and many others. Its algebraic counterpart, the theory of algebraic groups, was first shaped by Claude Chevalley (from the late 1930s) and later by the work of Armand Borel and Jacques Tits.

The University of Chicago's 1960–61 Group Theory Year brought together group theorists such as Daniel Gorenstein, John G. Thompson and Walter Feit, laying the foundation of a collaboration that, with input from numerous other mathematicians, led to the classification of finite simple groups, with the final step taken by Aschbacher and Smith in 2004. This project exceeded previous mathematical endeavours by its sheer size, in both length of proof and number of researchers. Research concerning this classification proof is ongoing. Group theory remains a highly active mathematical branch, impacting many other fields, as the examples below illustrate.

Elementary consequences of the group axioms

Basic facts about all groups that can be obtained directly from the group axioms are commonly subsumed under elementary group theory. For example, repeated applications of the associativity axiom show that the unambiguity of

$${\displaystyle a\cdot b\cdot c=(a\cdot b)\cdot c=a\cdot (b\cdot c)}$$

generalizes to more than three factors. Because this implies that parentheses can be inserted anywhere within such a series of terms, parentheses are usually omitted.

Individual axioms may be "weakened" to assert only the existence of a left identity and left inverses. From these one-sided axioms, one can prove that the left identity is also a right identity and a left inverse is also a right inverse for the same element. Since they define exactly the same structures as groups, collectively the axioms are no weaker.

Uniqueness of identity element

The group axioms imply that the identity element is unique: If ${\displaystyle e}$ and ${\displaystyle f}$ are identity elements of a group, then ${\displaystyle e=e\cdot f=f}$. Therefore, it is customary to speak of the identity.

Uniqueness of inverses

The group axioms also imply that the inverse of each element is unique: If a group element ${\displaystyle a}$ has both ${\displaystyle b}$ and ${\displaystyle c}$ as inverses, then

${\displaystyle b}$	${\displaystyle {}={}}$	${\displaystyle b\cdot e}$		since ${\displaystyle e}$ is the identity element
	${\displaystyle {}={}}$	${\displaystyle b\cdot (a\cdot c)}$		since ${\displaystyle c}$ is an inverse of ${\displaystyle a}$, so ${\displaystyle e=a\cdot c}$
	${\displaystyle {}={}}$	${\displaystyle (b\cdot a)\cdot c}$		by associativity, which allows rearranging the parentheses
	${\displaystyle {}={}}$	${\displaystyle e\cdot c}$		since ${\displaystyle b}$ is an inverse of ${\displaystyle a}$, so ${\displaystyle b\cdot a=e}$
	${\displaystyle {}={}}$	${\displaystyle c}$		since ${\displaystyle e}$ is the identity element.

Therefore, it is customary to speak of the inverse of an element.

Division

Given elements ${\displaystyle a}$ and ${\displaystyle b}$ of a group ${\displaystyle G}$, there is a unique solution ${\displaystyle x}$ in ${\displaystyle G}$ to the equation ${\displaystyle a\cdot x=b}$, namely ${\displaystyle a^{-1}\cdot b}$. (One usually avoids using fraction notation ${\displaystyle {\tfrac {b}{a}}}$ unless ${\displaystyle G}$ is abelian, because of the ambiguity of whether it means ${\displaystyle a^{-1}\cdot b}$ or ${\displaystyle b\cdot a^{-1}}$.) It follows that for each ${\displaystyle a}$ in ${\displaystyle G}$, the function ${\displaystyle G\to G}$ that maps each ${\displaystyle x}$ to ${\displaystyle a\cdot x}$ is a bijection; it is called left multiplication by ${\displaystyle a}$ or left translation by ${\displaystyle a}$.

Similarly, given ${\displaystyle a}$ and ${\displaystyle b}$, the unique solution to ${\displaystyle x\cdot a=b}$ is ${\displaystyle b\cdot a^{-1}}$. For each ${\displaystyle a}$, the function ${\displaystyle G\to G}$ that maps each ${\displaystyle x}$ to ${\displaystyle x\cdot a}$ is a bijection called right multiplication by ${\displaystyle a}$ or right translation by ${\displaystyle a}$.

Basic concepts

The following sections use mathematical symbols such as ${\displaystyle X=\{x,y,z\}}$ to denote a set ${\displaystyle X}$ containing elements ${\displaystyle x,y,}$ and ${\displaystyle z}$, or ${\displaystyle x\in X}$ to state that ${\displaystyle x}$ is an element of ${\displaystyle X.}$ The notation ${\displaystyle f:X\to Y}$ means ${\displaystyle f}$ is a function associating to every element of ${\displaystyle X}$ an element of ${\displaystyle Y.}$

When studying sets, one uses concepts such as subset, function, and quotient by an equivalence relation. When studying groups, one uses instead subgroups, homomorphisms, and quotient groups. These are the analogues that take the group structure into account.

Group homomorphisms

Main article: Group homomorphism

Group homomorphisms are functions that respect group structure; they may be used to relate two groups. A homomorphism from a group ${\displaystyle (G,\cdot )}$ to a group ${\displaystyle (H,*)}$ is a function ${\displaystyle \varphi :G\to H}$ such that

${\displaystyle \varphi (a\cdot b)=\varphi (a)*\varphi (b)}$ for all elements ${\displaystyle a}$ and ${\displaystyle b}$ in ${\displaystyle G}$.

It would be natural to require also that ${\displaystyle \varphi }$ respect identities, ${\displaystyle \varphi (1_{G})=1_{H}}$, and inverses, ${\displaystyle \varphi (a^{-1})=\varphi (a)^{-1}}$ for all ${\displaystyle a}$ in ${\displaystyle G}$. However, these additional requirements need not be included in the definition of homomorphisms, because they are already implied by the requirement of respecting the group operation.

The identity homomorphism of a group ${\displaystyle G}$ is the homomorphism ${\displaystyle \iota _{G}:G\to G}$ that maps each element of ${\displaystyle G}$ to itself. An inverse homomorphism of a homomorphism ${\displaystyle \varphi :G\to H}$ is a homomorphism ${\displaystyle \psi :H\to G}$ such that ${\displaystyle \psi \circ \varphi =\iota _{G}}$ and ${\displaystyle \varphi \circ \psi =\iota _{H}}$, that is, such that ${\displaystyle \psi {\bigl (}\varphi (g){\bigr )}=g}$ for all ${\displaystyle g}$ in ${\displaystyle G}$ and such that ${\displaystyle \varphi {\bigl (}\psi (h){\bigr )}=h}$ for all ${\displaystyle h}$ in ${\displaystyle H}$. An isomorphism is a homomorphism that has an inverse homomorphism; equivalently, it is a bijective homomorphism. Groups ${\displaystyle G}$ and ${\displaystyle H}$ are called isomorphic if there exists an isomorphism ${\displaystyle \varphi :G\to H}$. In this case, ${\displaystyle H}$ can be obtained from ${\displaystyle G}$ simply by renaming its elements according to the function ${\displaystyle \varphi }$; then any statement true for ${\displaystyle G}$ is true for ${\displaystyle H}$, provided that any specific elements mentioned in the statement are also renamed.

The collection of all groups, together with the homomorphisms between them, form a category, the category of groups.

Subgroups

Main article: Subgroup

Informally, a subgroup is a group ${\displaystyle H}$ contained within a bigger one, ${\displaystyle G}$: it has a subset of the elements of ${\displaystyle G}$, with the same operation. Concretely, this means that the identity element of ${\displaystyle G}$ must be contained in ${\displaystyle H}$, and whenever ${\displaystyle h_{1}}$ and ${\displaystyle h_{2}}$ are both in ${\displaystyle H}$, then so are ${\displaystyle h_{1}\cdot h_{2}}$ and ${\displaystyle h_{1}^{-1}}$, so the elements of ${\displaystyle H}$, equipped with the group operation on ${\displaystyle G}$ restricted to ${\displaystyle H}$, indeed form a group. In this case, the inclusion map ${\displaystyle H\to G}$ is a homomorphism.

In the example of symmetries of a square, the identity and the rotations constitute a subgroup ${\displaystyle R=\{\mathrm {id} ,r_{1},r_{2},r_{3}\}}$, highlighted in red in the group table of the example: any two rotations composed are still a rotation, and a rotation can be undone by (i.e., is inverse to) the complementary rotations 270° for 90°, 180° for 180°, and 90° for 270°. The subgroup test provides a necessary and sufficient condition for a nonempty subset H of a group G to be a subgroup: it is sufficient to check that ${\displaystyle g^{-1}\cdot h\in H}$ for all elements ${\displaystyle g}$ and ${\displaystyle h}$ in ${\displaystyle H}$. Knowing a group's subgroups is important in understanding the group as a whole.

Given any subset ${\displaystyle S}$ of a group ${\displaystyle G}$, the subgroup generated by ${\displaystyle S}$ consists of all products of elements of ${\displaystyle S}$ and their inverses. It is the smallest subgroup of ${\displaystyle G}$ containing ${\displaystyle S}$. In the example of symmetries of a square, the subgroup generated by ${\displaystyle r_{2}}$ and ${\displaystyle f_{\mathrm {v} }}$ consists of these two elements, the identity element ${\displaystyle \mathrm {id} }$, and the element ${\displaystyle f_{\mathrm {h} }=f_{\mathrm {v} }\cdot r_{2}}$. Again, this is a subgroup, because combining any two of these four elements or their inverses (which are, in this particular case, these same elements) yields an element of this subgroup.

An injective homomorphism ${\displaystyle \phi \colon G'\to G}$ factors canonically as an isomorphism followed by an inclusion, ${\displaystyle G'\;{\stackrel {\sim }{\to }}\;H\hookrightarrow G}$ for some subgroup H of G. Injective homomorphisms are the monomorphisms in the category of groups.

Cosets

Main article: Coset

In many situations it is desirable to consider two group elements the same if they differ by an element of a given subgroup. For example, in the symmetry group of a square, once any reflection is performed, rotations alone cannot return the square to its original position, so one can think of the reflected positions of the square as all being equivalent to each other, and as inequivalent to the unreflected positions; the rotation operations are irrelevant to the question whether a reflection has been performed. Cosets are used to formalize this insight: a subgroup ${\displaystyle H}$ determines left and right cosets, which can be thought of as translations of ${\displaystyle H}$ by an arbitrary group element ${\displaystyle g}$. In symbolic terms, the left and right cosets of ${\displaystyle H}$, containing an element ${\displaystyle g}$, are

${\displaystyle gH=\{g\cdot h\mid h\in H\}}$ and ${\displaystyle Hg=\{h\cdot g\mid h\in H\}}$, respectively.

The left cosets of any subgroup ${\displaystyle H}$ form a partition of ${\displaystyle G}$; that is, the union of all left cosets is equal to ${\displaystyle G}$ and two left cosets are either equal or have an empty intersection. The first case ${\displaystyle g_{1}H=g_{2}H}$ happens precisely when ${\displaystyle g_{1}^{-1}\cdot g_{2}\in H}$, i.e., when the two elements differ by an element of ${\displaystyle H}$. Similar considerations apply to the right cosets of ${\displaystyle H}$. The left cosets of ${\displaystyle H}$ may or may not be the same as its right cosets. If they are (that is, if all ${\displaystyle g}$ in ${\displaystyle G}$ satisfy ${\displaystyle gH=Hg}$), then ${\displaystyle H}$ is said to be a normal subgroup.

In ${\displaystyle \mathrm {D} _{4}}$, the group of symmetries of a square, with its subgroup ${\displaystyle R}$ of rotations, the left cosets ${\displaystyle gR}$ are either equal to ${\displaystyle R}$, if ${\displaystyle g}$ is an element of ${\displaystyle R}$ itself, or otherwise equal to ${\displaystyle U=f_{\mathrm {c} }R=\{f_{\mathrm {c} },f_{\mathrm {d} },f_{\mathrm {v} },f_{\mathrm {h} }\}}$ (highlighted in green in the group table of ${\displaystyle \mathrm {D} _{4}}$). The subgroup ${\displaystyle R}$ is normal, because ${\displaystyle f_{\mathrm {c} }R=U=Rf_{\mathrm {c} }}$ and similarly for the other elements of the group. (In fact, in the case of ${\displaystyle \mathrm {D} _{4}}$, the cosets generated by reflections are all equal: ${\displaystyle f_{\mathrm {h} }R=f_{\mathrm {v} }R=f_{\mathrm {d} }R=f_{\mathrm {c} }R}$.)

Quotient groups

Main article: Quotient group

Suppose that ${\displaystyle N}$ is a normal subgroup of a group ${\displaystyle G}$, and

$${\displaystyle G/N=\{gN\mid g\in G\}}$$

denotes its set of cosets. Then there is a unique group law on ${\displaystyle G/N}$ for which the map ${\displaystyle G\to G/N}$ sending each element ${\displaystyle g}$ to ${\displaystyle gN}$ is a homomorphism. Explicitly, the product of two cosets ${\displaystyle gN}$ and ${\displaystyle hN}$ is ${\displaystyle (gh)N}$, the coset ${\displaystyle eN=N}$ serves as the identity of ${\displaystyle G/N}$, and the inverse of ${\displaystyle gN}$ in the quotient group is ${\displaystyle (gN)^{-1}=\left(g^{-1}\right)N}$. The group ${\displaystyle G/N}$, read as "${\displaystyle G}$ modulo ${\displaystyle N}$", is called a quotient group or factor group. The quotient group can alternatively be characterized by a universal property.

Group table of the quotient group ${\displaystyle \mathrm {D} _{4}/R}$

${\displaystyle \cdot }$	${\displaystyle R}$	${\displaystyle U}$
${\displaystyle R}$	${\displaystyle R}$	${\displaystyle U}$
${\displaystyle U}$	${\displaystyle U}$	${\displaystyle R}$

The elements of the quotient group ${\displaystyle \mathrm {D} _{4}/R}$ are ${\displaystyle R}$ and ${\displaystyle U=f_{\mathrm {v} }R}$. The group operation on the quotient is shown in the table. For example, ${\displaystyle U\cdot U=f_{\mathrm {v} }R\cdot f_{\mathrm {v} }R=(f_{\mathrm {v} }\cdot f_{\mathrm {v} })R=R}$. Both the subgroup ${\displaystyle R=\{\mathrm {id} ,r_{1},r_{2},r_{3}\}}$ and the quotient ${\displaystyle \mathrm {D} _{4}/R}$ are abelian, but ${\displaystyle \mathrm {D} _{4}}$ is not. Sometimes a group can be reconstructed from a subgroup and quotient (plus some additional data), by the semidirect product construction; ${\displaystyle \mathrm {D} _{4}}$ is an example.

The first isomorphism theorem implies that any surjective homomorphism ${\displaystyle \phi \colon G\to H}$ factors canonically as a quotient homomorphism followed by an isomorphism: ${\displaystyle G\to G/\ker \phi \;{\stackrel {\sim }{\to }}\;H}$. Surjective homomorphisms are the epimorphisms in the category of groups.

Presentations

Main article: Presentation of a group

Every group is isomorphic to a quotient of a free group, in many ways.

For example, the dihedral group ${\displaystyle \mathrm {D} _{4}}$ is generated by the right rotation ${\displaystyle r_{1}}$ and the reflection ${\displaystyle f_{\mathrm {v} }}$ in a vertical line (every element of ${\displaystyle \mathrm {D} _{4}}$ is a finite product of copies of these and their inverses). Hence there is a surjective homomorphism φ from the free group ${\displaystyle \langle r,f\rangle }$ on two generators to ${\displaystyle \mathrm {D} _{4}}$ sending ${\displaystyle r}$ to ${\displaystyle r_{1}}$ and ${\displaystyle f}$ to ${\displaystyle f_{1}}$. Elements in ${\displaystyle \ker \phi }$ are called relations; examples include ${\displaystyle r^{4},r^{2},(r\cdot f)^{2}}$. In fact, it turns out that ${\displaystyle \ker \phi }$ is the smallest normal subgroup of ${\displaystyle \langle r,f\rangle }$ containing these three elements; in other words, all relations are consequences of these three. The quotient of the free group by this normal subgroup is denoted ${\displaystyle \langle r,f\mid r^{4}=f^{2}=(r\cdot f)^{2}=1\rangle }$. This is called a presentation of ${\displaystyle \mathrm {D} _{4}}$ by generators and relations, because the first isomorphism theorem for φ yields an isomorphism ${\displaystyle \langle r,f\mid r^{4}=f^{2}=(r\cdot f)^{2}=1\rangle \to \mathrm {D} _{4}}$.

A presentation of a group can be used to construct the Cayley graph, a graphical depiction of a discrete group.

Examples and applications

Main article: Examples of groups

 

A periodic wallpaper pattern gives rise to a wallpaper group.

 

The fundamental group of a plane minus a point (bold) consists of loops around the missing point. This group is isomorphic to the integers.

Examples and applications of groups abound. A starting point is the group ${\displaystyle \mathbb {Z} }$ of integers with addition as group operation, introduced above. If instead of addition multiplication is considered, one obtains multiplicative groups. These groups are predecessors of important constructions in abstract algebra.

Groups are also applied in many other mathematical areas. Mathematical objects are often examined by associating groups to them and studying the properties of the corresponding groups. For example, Henri Poincaré founded what is now called algebraic topology by introducing the fundamental group. By means of this connection, topological properties such as proximity and continuity translate into properties of groups. For example, elements of the fundamental group are represented by loops. The second image shows some loops in a plane minus a point. The blue loop is considered null-homotopic (and thus irrelevant), because it can be continuously shrunk to a point. The presence of the hole prevents the orange loop from being shrunk to a point. The fundamental group of the plane with a point deleted turns out to be infinite cyclic, generated by the orange loop (or any other loop winding once around the hole). This way, the fundamental group detects the hole.

In more recent applications, the influence has also been reversed to motivate geometric constructions by a group-theoretical background. In a similar vein, geometric group theory employs geometric concepts, for example in the study of hyperbolic groups. Further branches crucially applying groups include algebraic geometry and number theory.

In addition to the above theoretical applications, many practical applications of groups exist. Cryptography relies on the combination of the abstract group theory approach together with algorithmical knowledge obtained in computational group theory, in particular when implemented for finite groups. Applications of group theory are not restricted to mathematics; sciences such as physics, chemistry and computer science benefit from the concept.

Numbers

Many number systems, such as the integers and the rationals, enjoy a naturally given group structure. In some cases, such as with the rationals, both addition and multiplication operations give rise to group structures. Such number systems are predecessors to more general algebraic structures known as rings and fields. Further abstract algebraic concepts such as modules, vector spaces and algebras also form groups.

Integers

The group of integers ${\displaystyle \mathbb {Z} }$ under addition, denoted ${\displaystyle \left(\mathbb {Z} ,+\right)}$, has been described above. The integers, with the operation of multiplication instead of addition, ${\displaystyle \left(\mathbb {Z} ,\cdot \right)}$ do not form a group. The associativity and identity axioms are satisfied, but inverses do not exist: for example, ${\displaystyle a=2}$ is an integer, but the only solution to the equation ${\displaystyle a\cdot b=1}$ in this case is ${\displaystyle b={\tfrac {1}{2}}}$, which is a rational number, but not an integer. Hence not every element of ${\displaystyle \mathbb {Z} }$ has a (multiplicative) inverse.

Rationals

The desire for the existence of multiplicative inverses suggests considering fractions

$${\displaystyle {\frac {a}{b}}.}$$

Fractions of integers (with ${\displaystyle b}$ nonzero) are known as rational numbers. The set of all such irreducible fractions is commonly denoted ${\displaystyle \mathbb {Q} }$. There is still a minor obstacle for ${\displaystyle \left(\mathbb {Q} ,\cdot \right)}$, the rationals with multiplication, being a group: because zero does not have a multiplicative inverse (i.e., there is no ${\displaystyle x}$ such that ${\displaystyle x\cdot 0=1}$), ${\displaystyle \left(\mathbb {Q} ,\cdot \right)}$ is still not a group.

However, the set of all nonzero rational numbers ${\displaystyle \mathbb {Q} \smallsetminus \left\{0\right\}=\left\{q\in \mathbb {Q} \mid q\neq 0\right\}}$ does form an abelian group under multiplication, also denoted ${\displaystyle \mathbb {Q} ^{\times }}$. Associativity and identity element axioms follow from the properties of integers. The closure requirement still holds true after removing zero, because the product of two nonzero rationals is never zero. Finally, the inverse of ${\displaystyle a/b}$ is ${\displaystyle b/a}$, therefore the axiom of the inverse element is satisfied.

The rational numbers (including zero) also form a group under addition. Intertwining addition and multiplication operations yields more complicated structures called rings and – if division by other than zero is possible, such as in ${\displaystyle \mathbb {Q} }$ – fields, which occupy a central position in abstract algebra. Group theoretic arguments therefore underlie parts of the theory of those entities.

Modular arithmetic

Main article: Modular arithmetic

 

The hours on a clock form a group that uses addition modulo 12. Here, 9 + 4 ≡ 1.

Modular arithmetic for a modulus ${\displaystyle n}$ defines any two elements ${\displaystyle a}$ and ${\displaystyle b}$ that differ by a multiple of ${\displaystyle n}$ to be equivalent, denoted by ${\displaystyle a\equiv b{\pmod {n}}}$. Every integer is equivalent to one of the integers from ${\displaystyle 0}$ to ${\displaystyle n-1}$, and the operations of modular arithmetic modify normal arithmetic by replacing the result of any operation by its equivalent representative. Modular addition, defined in this way for the integers from ${\displaystyle 0}$ to ${\displaystyle n-1}$, forms a group, denoted as ${\displaystyle \mathrm {Z} _{n}}$ or ${\displaystyle (\mathbb {Z} /n\mathbb {Z} ,+)}$, with ${\displaystyle 0}$ as the identity element and ${\displaystyle n-a}$ as the inverse element of ${\displaystyle a}$.

A familiar example is addition of hours on the face of a clock, where 12 rather than 0 is chosen as the representative of the identity. If the hour hand is on ${\displaystyle 9}$ and is advanced ${\displaystyle 4}$ hours, it ends up on ${\displaystyle 1}$, as shown in the illustration. This is expressed by saying that ${\displaystyle 9+4}$ is congruent to ${\displaystyle 1}$ "modulo ${\displaystyle 12}$" or, in symbols,

$${\displaystyle 9+4\equiv 1{\pmod {12}}.}$$

For any prime number ${\displaystyle p}$, there is also the multiplicative group of integers modulo ${\displaystyle p}$. Its elements can be represented by ${\displaystyle 1}$ to ${\displaystyle p-1}$. The group operation, multiplication modulo ${\displaystyle p}$, replaces the usual product by its representative, the remainder of division by ${\displaystyle p}$. For example, for ${\displaystyle p=5}$, the four group elements can be represented by ${\displaystyle 1,2,3,4}$. In this group, ${\displaystyle 4\cdot 4\equiv 1{\bmod {5}}}$, because the usual product ${\displaystyle 16}$ is equivalent to ${\displaystyle 1}$: when divided by ${\displaystyle 5}$ it yields a remainder of ${\displaystyle 1}$. The primality of ${\displaystyle p}$ ensures that the usual product of two representatives is not divisible by ${\displaystyle p}$, and therefore that the modular product is nonzero. The identity element is represented by ${\displaystyle 1}$, and associativity follows from the corresponding property of the integers. Finally, the inverse element axiom requires that given an integer ${\displaystyle a}$ not divisible by ${\displaystyle p}$, there exists an integer ${\displaystyle b}$ such that

$${\displaystyle a\cdot b\equiv 1{\pmod {p}},}$$

that is, such that ${\displaystyle p}$ evenly divides ${\displaystyle a\cdot b-1}$. The inverse ${\displaystyle b}$ can be found by using Bézout's identity and the fact that the greatest common divisor ${\displaystyle \gcd(a,p)}$ equals ${\displaystyle 1}$. In the case ${\displaystyle p=5}$ above, the inverse of the element represented by ${\displaystyle 4}$ is that represented by ${\displaystyle 4}$, and the inverse of the element represented by ${\displaystyle 3}$ is represented by ${\displaystyle 2}$, as ${\displaystyle 3\cdot 2=6\equiv 1{\bmod {5}}}$. Hence all group axioms are fulfilled. This example is similar to ${\displaystyle \left(\mathbb {Q} \smallsetminus \left\{0\right\},\cdot \right)}$ above: it consists of exactly those elements in the ring ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ that have a multiplicative inverse. These groups, denoted ${\displaystyle \mathbb {F} _{p}^{\times }}$, are crucial to public-key cryptography.

Cyclic groups

Main article: Cyclic group

 

The 6th complex roots of unity form a cyclic group. ${\displaystyle z}$ is a primitive element, but ${\displaystyle z^{2}}$ is not, because the odd powers of ${\displaystyle z}$ are not a power of ${\displaystyle z^{2}}$.

A cyclic group is a group all of whose elements are powers of a particular element ${\displaystyle a}$. In multiplicative notation, the elements of the group are

$${\displaystyle \dots ,a^{-3},a^{-2},a^{-1},a^{0},a,a^{2},a^{3},\dots ,}$$

where ${\displaystyle a^{2}}$ means ${\displaystyle a\cdot a}$, ${\displaystyle a^{-3}}$ stands for ${\displaystyle a^{-1}\cdot a^{-1}\cdot a^{-1}=(a\cdot a\cdot a)^{-1}}$, etc. Such an element ${\displaystyle a}$ is called a generator or a primitive element of the group. In additive notation, the requirement for an element to be primitive is that each element of the group can be written as

$${\displaystyle \dots ,(-a)+(-a),-a,0,a,a+a,\dots .}$$

In the groups ${\displaystyle (\mathbb {Z} /n\mathbb {Z} ,+)}$ introduced above, the element ${\displaystyle 1}$ is primitive, so these groups are cyclic. Indeed, each element is expressible as a sum all of whose terms are ${\displaystyle 1}$. Any cyclic group with ${\displaystyle n}$ elements is isomorphic to this group. A second example for cyclic groups is the group of ${\displaystyle n}$th complex roots of unity, given by complex numbers ${\displaystyle z}$ satisfying ${\displaystyle z^{n}=1}$. These numbers can be visualized as the vertices on a regular ${\displaystyle n}$-gon, as shown in blue in the image for ${\displaystyle n=6}$. The group operation is multiplication of complex numbers. In the picture, multiplying with ${\displaystyle z}$ corresponds to a counter-clockwise rotation by 60°. From field theory, the group ${\displaystyle \mathbb {F} _{p}^{\times }}$ is cyclic for prime ${\displaystyle p}$: for example, if ${\displaystyle p=5}$, ${\displaystyle 3}$ is a generator since ${\displaystyle 3^{1}=3}$, ${\displaystyle 3^{2}=9\equiv 4}$, ${\displaystyle 3^{3}\equiv 2}$, and ${\displaystyle 3^{4}\equiv 1}$.

Some cyclic groups have an infinite number of elements. In these groups, for every non-zero element ${\displaystyle a}$, all the powers of ${\displaystyle a}$ are distinct; despite the name "cyclic group", the powers of the elements do not cycle. An infinite cyclic group is isomorphic to ${\displaystyle (\mathbb {Z} ,+)}$, the group of integers under addition introduced above. As these two prototypes are both abelian, so are all cyclic groups.

The study of finitely generated abelian groups is quite mature, including the fundamental theorem of finitely generated abelian groups; and reflecting this state of affairs, many group-related notions, such as center and commutator, describe the extent to which a given group is not abelian.

Symmetry groups

Main article: Symmetry group

See also: Molecular symmetry, Space group, Point group, and Symmetry in physics

 

The (2,3,7) triangle group, a hyperbolic reflection group, acts on this tiling of the hyperbolic plane

Symmetry groups are groups consisting of symmetries of given mathematical objects, principally geometric entities, such as the symmetry group of the square given as an introductory example above, although they also arise in algebra such as the symmetries among the roots of polynomial equations dealt with in Galois theory (see below). Conceptually, group theory can be thought of as the study of symmetry. Symmetries in mathematics greatly simplify the study of geometrical or analytical objects. A group is said to act on another mathematical object X if every group element can be associated to some operation on X and the composition of these operations follows the group law. For example, an element of the (2,3,7) triangle group acts on a triangular tiling of the hyperbolic plane by permuting the triangles. By a group action, the group pattern is connected to the structure of the object being acted on.

In chemical fields, such as crystallography, space groups and point groups describe molecular symmetries and crystal symmetries. These symmetries underlie the chemical and physical behavior of these systems, and group theory enables simplification of quantum mechanical analysis of these properties. For example, group theory is used to show that optical transitions between certain quantum levels cannot occur simply because of the symmetry of the states involved.

Group theory helps predict the changes in physical properties that occur when a material undergoes a phase transition, for example, from a cubic to a tetrahedral crystalline form. An example is ferroelectric materials, where the change from a paraelectric to a ferroelectric state occurs at the Curie temperature and is related to a change from the high-symmetry paraelectric state to the lower symmetry ferroelectric state, accompanied by a so-called soft phonon mode, a vibrational lattice mode that goes to zero frequency at the transition.

Such spontaneous symmetry breaking has found further application in elementary particle physics, where its occurrence is related to the appearance of Goldstone bosons.

Buckminsterfullerene displays icosahedral symmetry	Ammonia, NH3. Its symmetry group is of order 6, generated by a 120° rotation and a reflection.	Cubane C8H8 features octahedral symmetry.	The tetrachloroplatinate(II) ion, [PtCl4]2- exhibits square-planar geometry

Finite symmetry groups such as the Mathieu groups are used in coding theory, which is in turn applied in error correction of transmitted data, and in CD players. Another application is differential Galois theory, which characterizes functions having antiderivatives of a prescribed form, giving group-theoretic criteria for when solutions of certain differential equations are well-behaved. Geometric properties that remain stable under group actions are investigated in (geometric) invariant theory.

General linear group and representation theory

Main articles: General linear group, Representation theory, and Character theory

 

Two vectors (the left illustration) multiplied by matrices (the middle and right illustrations). The middle illustration represents a clockwise rotation by 90°, while the right-most one stretches the ${\displaystyle x}$-coordinate by factor 2.

Matrix groups consist of matrices together with matrix multiplication. The general linear group ${\displaystyle \mathrm {GL} (n,\mathbb {R} )}$ consists of all invertible ${\displaystyle n}$-by-${\displaystyle n}$ matrices with real entries. Its subgroups are referred to as matrix groups or linear groups. The dihedral group example mentioned above can be viewed as a (very small) matrix group. Another important matrix group is the special orthogonal group ${\displaystyle \mathrm {SO} (n)}$. It describes all possible rotations in ${\displaystyle n}$ dimensions. Rotation matrices in this group are used in computer graphics.

Representation theory is both an application of the group concept and important for a deeper understanding of groups. It studies the group by its group actions on other spaces. A broad class of group representations are linear representations in which the group acts on a vector space, such as the three-dimensional Euclidean space ${\displaystyle \mathbb {R} ^{3}}$. A representation of a group ${\displaystyle G}$ on an ${\displaystyle n}$-dimensional real vector space is simply a group homomorphism ${\displaystyle \rho :G\to \mathrm {GL} (n,\mathbb {R} )}$ from the group to the general linear group. This way, the group operation, which may be abstractly given, translates to the multiplication of matrices making it accessible to explicit computations.

A group action gives further means to study the object being acted on. On the other hand, it also yields information about the group. Group representations are an organizing principle in the theory of finite groups, Lie groups, algebraic groups and topological groups, especially (locally) compact groups.

Galois groups

Main article: Galois group

Galois groups were developed to help solve polynomial equations by capturing their symmetry features. For example, the solutions of the quadratic equation ${\displaystyle ax^{2}+bx+c=0}$ are given by

$${\displaystyle x={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}.}$$

Each solution can be obtained by replacing the ${\displaystyle \pm }$ sign by ${\displaystyle +}$ or ${\displaystyle -}$; analogous formulae are known for cubic and quartic equations, but do not exist in general for degree 5 and higher. In the quadratic formula, changing the sign (permuting the resulting two solutions) can be viewed as a (very simple) group operation. Analogous Galois groups act on the solutions of higher-degree polynomials and are closely related to the existence of formulas for their solution. Abstract properties of these groups (in particular their solvability) give a criterion for the ability to express the solutions of these polynomials using solely addition, multiplication, and roots similar to the formula above.

Modern Galois theory generalizes the above type of Galois groups by shifting to field theory and considering field extensions formed as the splitting field of a polynomial. This theory establishes—via the fundamental theorem of Galois theory—a precise relationship between fields and groups, underlining once again the ubiquity of groups in mathematics.

Finite groups

Main article: Finite group

A group is called finite if it has a finite number of elements. The number of elements is called the order of the group. An important class is the symmetric groups ${\displaystyle \mathrm {S} _{N}}$, the groups of permutations of ${\displaystyle N}$ objects. For example, the symmetric group on 3 letters ${\displaystyle \mathrm {S} _{3}}$ is the group of all possible reorderings of the objects. The three letters ABC can be reordered into ABC, ACB, BAC, BCA, CAB, CBA, forming in total 6 (factorial of 3) elements. The group operation is composition of these reorderings, and the identity element is the reordering operation that leaves the order unchanged. This class is fundamental insofar as any finite group can be expressed as a subgroup of a symmetric group ${\displaystyle \mathrm {S} _{N}}$ for a suitable integer ${\displaystyle N}$, according to Cayley's theorem. Parallel to the group of symmetries of the square above, ${\displaystyle \mathrm {S} _{3}}$ can also be interpreted as the group of symmetries of an equilateral triangle.

The order of an element ${\displaystyle a}$ in a group ${\displaystyle G}$ is the least positive integer ${\displaystyle n}$ such that ${\displaystyle a^{n}=e}$, where ${\displaystyle a^{n}}$ represents

$${\displaystyle \underbrace {a\cdots a} _{n{\text{ factors}}},}$$

that is, application of the operation "${\displaystyle \cdot }$" to ${\displaystyle n}$ copies of ${\displaystyle a}$. (If "${\displaystyle \cdot }$" represents multiplication, then ${\displaystyle a^{n}}$ corresponds to the ${\displaystyle n}$th power of ${\displaystyle a}$.) In infinite groups, such an ${\displaystyle n}$ may not exist, in which case the order of ${\displaystyle a}$ is said to be infinity. The order of an element equals the order of the cyclic subgroup generated by this element.

More sophisticated counting techniques, for example, counting cosets, yield more precise statements about finite groups: Lagrange's Theorem states that for a finite group ${\displaystyle G}$ the order of any finite subgroup ${\displaystyle H}$ divides the order of ${\displaystyle G}$. The Sylow theorems give a partial converse.

The dihedral group ${\displaystyle \mathrm {D} _{4}}$ of symmetries of a square is a finite group of order 8. In this group, the order of ${\displaystyle r_{1}}$ is 4, as is the order of the subgroup ${\displaystyle R}$ that this element generates. The order of the reflection elements ${\displaystyle f_{\mathrm {v} }}$ etc. is 2. Both orders divide 8, as predicted by Lagrange's theorem. The groups ${\displaystyle \mathbb {F} _{p}^{\times }}$ of multiplication modulo a prime ${\displaystyle p}$ have order ${\displaystyle p-1}$.

Finite abelian groups

Any finite abelian group is isomorphic to a product of finite cyclic groups; this statement is part of the fundamental theorem of finitely generated abelian groups.

Any group of prime order ${\displaystyle p}$ is isomorphic to the cyclic group ${\displaystyle \mathrm {Z} _{p}}$ (a consequence of Lagrange's theorem). Any group of order ${\displaystyle p^{2}}$ is abelian, isomorphic to ${\displaystyle \mathrm {Z} _{p^{2}}}$ or ${\displaystyle \mathrm {Z} _{p}\times \mathrm {Z} _{p}}$. But there exist nonabelian groups of order ${\displaystyle p^{3}}$; the dihedral group ${\displaystyle \mathrm {D} _{4}}$ of order ${\displaystyle 2^{3}}$ above is an example.

Simple groups

When a group ${\displaystyle G}$ has a normal subgroup ${\displaystyle N}$ other than ${\displaystyle \{1\}}$ and ${\displaystyle G}$ itself, questions about ${\displaystyle G}$ can sometimes be reduced to questions about ${\displaystyle N}$ and ${\displaystyle G/N}$. A nontrivial group is called simple if it has no such normal subgroup. Finite simple groups are to finite groups as prime numbers are to positive integers: they serve as building blocks, in a sense made precise by the Jordan–Hölder theorem.

Classification of finite simple groups

Main article: Classification of finite simple groups

Computer algebra systems have been used to list all groups of order up to 2000. But classifying all finite groups is a problem considered too hard to be solved.

The classification of all finite simple groups was a major achievement in contemporary group theory. There are several infinite families of such groups, as well as 26 "sporadic groups" that do not belong to any of the families. The largest sporadic group is called the monster group. The monstrous moonshine conjectures, proved by Richard Borcherds, relate the monster group to certain modular functions.

The gap between the classification of simple groups and the classification of all groups lies in the extension problem.

Groups with additional structure

An equivalent definition of group consists of replacing the "there exist" part of the group axioms by operations whose result is the element that must exist. So, a group is a set ${\displaystyle G}$ equipped with a binary operation ${\displaystyle G\times G\rightarrow G}$ (the group operation), a unary operation ${\displaystyle G\rightarrow G}$ (which provides the inverse) and a nullary operation, which has no operand and results in the identity element. Otherwise, the group axioms are exactly the same. This variant of the definition avoids existential quantifiers and is used in computing with groups and for computer-aided proofs.

This way of defining groups lends itself to generalizations such as the notion of group object in a category. Briefly, this is an object with morphisms that mimic the group axioms.

Topological groups

The unit circle in the complex plane under complex multiplication is a Lie group and, therefore, a topological group. It is topological since complex multiplication and division are continuous. It is a manifold and thus a Lie group, because every small piece, such as the red arc in the figure, looks like a part of the real line (shown at the bottom).

 

Main article: Topological group

Some topological spaces may be endowed with a group law. In order for the group law and the topology to interweave well, the group operations must be continuous functions; informally, ${\displaystyle g\cdot h}$ and ${\displaystyle g^{-1}}$ must not vary wildly if ${\displaystyle g}$ and ${\displaystyle h}$ vary only a little. Such groups are called topological groups, and they are the group objects in the category of topological spaces. The most basic examples are the group of real numbers under addition and the group of nonzero real numbers under multiplication. Similar examples can be formed from any other topological field, such as the field of complex numbers or the field of p-adic numbers. These examples are locally compact, so they have Haar measures and can be studied via harmonic analysis. Other locally compact topological groups include the group of points of an algebraic group over a local field or adele ring; these are basic to number theory Galois groups of infinite algebraic field extensions are equipped with the Krull topology, which plays a role in infinite Galois theory. A generalization used in algebraic geometry is the étale fundamental group.

Lie groups

Main article: Lie group

A Lie group is a group that also has the structure of a differentiable manifold; informally, this means that it looks locally like a Euclidean space of some fixed dimension. Again, the definition requires the additional structure, here the manifold structure, to be compatible: the multiplication and inverse maps are required to be smooth.

A standard example is the general linear group introduced above: it is an open subset of the space of all ${\displaystyle n}$-by-${\displaystyle n}$ matrices, because it is given by the inequality

$${\displaystyle \det(A)\neq 0,}$$

where ${\displaystyle A}$ denotes an ${\displaystyle n}$-by-${\displaystyle n}$ matrix.

Lie groups are of fundamental importance in modern physics: Noether's theorem links continuous symmetries to conserved quantities. Rotation, as well as translations in space and time, are basic symmetries of the laws of mechanics. They can, for instance, be used to construct simple models—imposing, say, axial symmetry on a situation will typically lead to significant simplification in the equations one needs to solve to provide a physical description. Another example is the group of Lorentz transformations, which relate measurements of time and velocity of two observers in motion relative to each other. They can be deduced in a purely group-theoretical way, by expressing the transformations as a rotational symmetry of Minkowski space. The latter serves—in the absence of significant gravitation—as a model of spacetime in special relativity. The full symmetry group of Minkowski space, i.e., including translations, is known as the Poincaré group. By the above, it plays a pivotal role in special relativity and, by implication, for quantum field theories. Symmetries that vary with location are central to the modern description of physical interactions with the help of gauge theory. An important example of a gauge theory is the Standard Model, which describes three of the four known fundamental forces and classifies all known elementary particles.

Generalizations

Group-like structures
	Totality	Associativity	Identity	Division	Commutativity
Semigroupoid	Unneeded	Required	Unneeded	Unneeded	Unneeded
Small category	Unneeded	Required	Required	Unneeded	Unneeded
Groupoid	Unneeded	Required	Required	Required	Unneeded
Magma	Required	Unneeded	Unneeded	Unneeded	Unneeded
Quasigroup	Required	Unneeded	Unneeded	Required	Unneeded
Unital magma	Required	Unneeded	Required	Unneeded	Unneeded
Semigroup	Required	Required	Unneeded	Unneeded	Unneeded
Loop	Required	Unneeded	Required	Required	Unneeded
Monoid	Required	Required	Required	Unneeded	Unneeded
Group	Required	Required	Required	Required	Unneeded
Commutative monoid	Required	Required	Required	Unneeded	Required
Abelian group	Required	Required	Required	Required	Required
^α The closure axiom, used by many sources and defined differently, is equivalent.

In abstract algebra, more general structures are defined by relaxing some of the axioms defining a group. For example, if the requirement that every element has an inverse is eliminated, the resulting algebraic structure is called a monoid. The natural numbers ${\displaystyle \mathbb {N} }$ (including zero) under addition form a monoid, as do the nonzero integers under multiplication ${\displaystyle (\mathbb {Z} \smallsetminus \{0\},\cdot )}$, see above. There is a general method to formally add inverses to elements to any (abelian) monoid, much the same way as ${\displaystyle (\mathbb {Q} \smallsetminus \{0\},\cdot )}$ is derived from ${\displaystyle (\mathbb {Z} \smallsetminus \{0\},\cdot )}$, known as the Grothendieck group. Groupoids are similar to groups except that the composition ${\displaystyle a\cdot b}$ need not be defined for all ${\displaystyle a}$ and ${\displaystyle b}$. They arise in the study of more complicated forms of symmetry, often in topological and analytical structures, such as the fundamental groupoid or stacks. Finally, it is possible to generalize any of these concepts by replacing the binary operation with an arbitrary n-ary one (i.e., an operation taking n arguments). With the proper generalization of the group axioms this gives rise to an n-ary group. The table gives a list of several structures generalizing groups.

Cognitive distortion

From Wikipedia, the free encyclopedia

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

A cognitive distortion is an exaggerated or irrational thought pattern involved in the onset or perpetuation of psychopathological states, such as depression and anxiety.

Cognitive distortions are thoughts that cause individuals to perceive reality inaccurately. According to Aaron Beck's cognitive model, a negative outlook on reality, sometimes called negative schemas (or schemata), is a factor in symptoms of emotional dysfunction and poorer subjective well-being. Specifically, negative thinking patterns reinforce negative emotions and thoughts. During difficult circumstances, these distorted thoughts can contribute to an overall negative outlook on the world and a depressive or anxious mental state. According to hopelessness theory and Beck's theory, the meaning or interpretation that people give to their experience importantly influences whether they will become depressed and whether they will experience severe, repeated, or long-duration episodes of depression.

Challenging and changing cognitive distortions is a key element of cognitive behavioral therapy (CBT).

Definition

Cognitive comes from the Medieval Latin cognitīvus, equivalent to Latin cognit(us), 'known'. Distortion means the act of twisting or altering something out of its true, natural, or original state.

History

In 1957, American psychologist Albert Ellis, though he did not know it yet, would aid cognitive therapy in correcting cognitive distortions and indirectly helping David D. Burns in writing The Feeling Good Handbook. Ellis created what he called the ABC Technique of rational beliefs. The ABC stands for the activating event, beliefs that are irrational, and the consequences that come from the belief. Ellis wanted to prove that the activating event is not what caused the emotional behavior or the consequences, but the beliefs and how the person irrationally perceive the events that aids the consequences. With this model, Ellis attempted to use rational emotive behavior therapy (REBT) with his patients, in order to help them "reframe" or reinterpret the experience in a more rational manner. In this model Ellis explains it all for his clients, while Beck helps his clients figure this out on their own. Beck first started to notice these automatic distorted thought processes when practicing psychoanalysis, while his patients followed the rule of saying anything that comes to mind. Aaron realized that his patients had irrational fears, thoughts, and perceptions that were automatic. Beck began noticing his automatic thought processes that he knew his patients had but did not report. Most of the time the thoughts were biased against themselves and very erroneous.

Beck believed that the negative schemas developed and manifested themselves in the perspective and behavior. The distorted thought processes lead to focusing on degrading the self, amplifying minor external setbacks, experiencing other's harmless comments as ill-intended, while simultaneously seeing self as inferior. Inevitably cognitions are reflected in their behavior with a reduced desire to care for oneself, to seek pleasure, and give up. These exaggerated perceptions, due to cognition, feel real and accurate because the schemas, after being reinforced through the behavior, tend to become automatic and do not allow time for reflection. This cycle is also known as Beck's cognitive triad, focused on the theory that the person's negative schema applied to the self, the future, and the environment.

In 1972, psychiatrist, psychoanalyst, and cognitive therapy scholar Aaron T. Beck published Depression: Causes and Treatment. He was dissatisfied with the conventional Freudian treatment of depression, because there was no empirical evidence for the success of Freudian psychoanalysis. Beck's book provided a comprehensive and empirically-supported theoretical model for depression—its potential causes, symptoms, and treatments. In Chapter 2, titled "Symptomatology of Depression", he described "cognitive manifestations" of depression, including low self-evaluation, negative expectations, self-blame and self-criticism, indecisiveness, and distortion of the body image.

Beck's student David D. Burns continued research on the topic. In his book Feeling Good: The New Mood Therapy, Burns described personal and professional anecdotes related to cognitive distortions and their elimination. When Burns published Feeling Good: The New Mood Therapy, it made Beck's approach to distorted thinking widely known and popularized. Burns sold over four million copies of the book in the United States alone. It was a book commonly "prescribed" for patients who have cognitive distortions that have led to depression. Beck approved of the book, saying that it would help others alter their depressed moods by simplifying the extensive study and research that had taken place since shortly after Beck had started as a student and practitioner of psychoanalytic psychiatry. Nine years later, The Feeling Good Handbook was published, which was also built on Beck's work and includes a list of ten specific cognitive distortions that will be discussed throughout this article.

Main types

Examples of some common cognitive distortions seen in depressed and anxious individuals. People may be taught how to identify and alter these distortions as part of cognitive behavioural therapy.

John C. Gibbs and Granville Bud Potter propose four categories for cognitive distortions: self-centered, blaming others, minimizing-mislabeling, and assuming the worst. The cognitive distortions listed below are categories of automatic thinking, and are to be distinguished from logical fallacies.

All-or-nothing thinking

Main article: Splitting (psychology)

The "all-or-nothing thinking distortion" is also referred to as "splitting", "black-and-white thinking", and "polarized thinking." Someone with the all-or-nothing thinking distortion looks at life in black and white categories. Either they are a success or a failure; either they are good or bad; there is no in-between. According to one article, "Because there is always someone who is willing to criticize, this tends to collapse into a tendency for polarized people to view themselves as a total failure. Polarized thinkers have difficulty with the notion of being 'good enough' or a partial success."

• Example (from The Feeling Good Handbook): A woman eats a spoonful of ice cream. She thinks she is a complete failure for breaking her diet. She becomes so depressed that she ends up eating the whole quart of ice cream.

This example captures the polarized nature of this distortion—the person believes they are totally inadequate if they fall short of perfection. In order to combat this distortion, Burns suggests thinking of the world in terms of shades of gray. Rather than viewing herself as a complete failure for eating a spoonful of ice cream, the woman in the example could still recognize her overall effort to diet as at least a partial success.

This distortion is commonly found in perfectionists.

Jumping to conclusions

Main article: Jumping to conclusions

Reaching preliminary conclusions (usually negative) with little (if any) evidence. Three specific subtypes are identified:

Mind reading

Inferring a person's possible or probable (usually negative) thoughts from their behavior and nonverbal communication; taking precautions against the worst suspected case without asking the person.

• Example 1: A student assumes that the readers of their paper have already made up their minds concerning its topic, and, therefore, writing the paper is a pointless exercise.
• Example 2: Kevin assumes that because he sits alone at lunch, everyone else must think he is a loser. (This can encourage self-fulfilling prophecy; Kevin may not initiate social contact because of his fear that those around him already perceive him negatively).

Fortune-telling

Predicting outcomes (usually negative) of events.

• Example: A depressed person tells themselves they will never improve; they will continue to be depressed for their whole life.

One way to combat this distortion is to ask, "If this is true, does it say more about me or them?"

Labeling

Labeling occurs when someone overgeneralizes characteristics of other people. For example, someone might use an unfavorable term to describe a complex person or event.

Emotional reasoning

Main article: Emotional reasoning

In the emotional reasoning distortion, it is assumed that feelings expose the true nature of things and experience reality as a reflection of emotionally linked thoughts; something is believed true solely based on a feeling.

• Examples: "I feel stupid, therefore I must be stupid". Feeling fear of flying in planes, and then concluding that planes must be a dangerous way to travel. Feeling overwhelmed by the prospect of cleaning one's house, therefore concluding that it's hopeless to even start cleaning.

Should/shouldn't and must/mustn't statements

Making "must" or "should" statements was included by Albert Ellis in his rational emotive behavior therapy (REBT), an early form of CBT; he termed it "musturbation". Michael C. Graham called it "expecting the world to be different than it is". It can be seen as demanding particular achievements or behaviors regardless of the realistic circumstances of the situation.

• Example: After a performance, a concert pianist believes he or she should not have made so many mistakes.
• In Feeling Good: The New Mood Therapy, David Burns clearly distinguished between pathological "should statements", moral imperatives, and social norms.

A related cognitive distortion, also present in Ellis' REBT, is a tendency to "awfulize"; to say a future scenario will be awful, rather than to realistically appraise the various negative and positive characteristics of that scenario. According to Burns, "must" and "should" statements are negative because they cause the person to feel guilty and upset at themselves. Some people also direct this distortion at other people, which can cause feelings of anger and frustration when that other person does not do what they should have done. He also mentions how this type of thinking can lead to rebellious thoughts. In other words, trying to whip oneself into doing something with "shoulds" may cause one to desire just the opposite.

Gratitude traps

Main article: Gratitude trap

A gratitude trap is a type of cognitive distortion that typically arises from misunderstandings regarding the nature or practice of gratitude. The term can refer to one of two related but distinct thought patterns:

• A self-oriented thought process involving feelings of guilt, shame, or frustration related to one's expectations of how things "should" be
• An "elusive ugliness in many relationships, a deceptive 'kindness,' the main purpose of which is to make others feel indebted", as defined by psychologist Ellen Kenner

Blaming others

Personalization and blaming

Main article: Blame

Personalization is assigning personal blame disproportionate to the level of control a person realistically has in a given situation.

• Example 1: A foster child assumes that he/she has not been adopted because he/she is not "loveable enough".
• Example 2: A child has bad grades. His/her mother believes it is because she is not a good enough parent.

Blaming is the opposite of personalization. In the blaming distortion, the disproportionate level of blame is placed upon other people, rather than oneself. In this way, the person avoids taking personal responsibility, making way for a "victim mentality".

• Example: Placing blame for marital problems entirely on one's spouse.

Always being right

In this cognitive distortion, being wrong is unthinkable. This distortion is characterized by actively trying to prove one's actions or thoughts to be correct, and sometimes prioritizing self-interest over the feelings of another person. In this cognitive distortion, the facts that oneself has about their surroundings are always right while other people's opinions and perspectives are wrongly seen.

Fallacy of change

Relying on social control to obtain cooperative actions from another person. The underlying assumption of this thinking style is that one's happiness depends on the actions of others. The fallacy of change also assumes that other people should change to suit one's own interests automatically and/or that it is fair to pressure them to change. It may be present in most abusive relationships in which partners' "visions" of each other are tied into the belief that happiness, love, trust, and perfection would just occur once they or the other person change aspects of their beings.

Minimizing-mislabeling

Magnification and minimization

Main articles: Exaggeration and Minimisation (psychology)

Giving proportionally greater weight to a perceived failure, weakness or threat, or lesser weight to a perceived success, strength or opportunity, so that the weight differs from that assigned by others, such as "making a mountain out of a molehill". In depressed clients, often the positive characteristics of other people are exaggerated and their negative characteristics are understated.

• Catastrophizing – Giving greater weight to the worst possible outcome, however unlikely, or experiencing a situation as unbearable or impossible when it is just uncomfortable.

Labeling and mislabeling

Main article: Labeling theory

A form of overgeneralization; attributing a person's actions to their character instead of to an attribute. Rather than assuming the behaviour to be accidental or otherwise extrinsic, one assigns a label to someone or something that is based on the inferred character of that person or thing.

Assuming the worst

Overgeneralizing

Someone who overgeneralizes makes faulty generalizations from insufficient evidence. Such as seeing a "single negative event" as a "never-ending pattern of defeat", and as such drawing a very broad conclusion from a single incident or a single piece of evidence. Even if something bad happens only once, it is expected to happen over and over again.

• Example 1: A young woman is asked out on a first date, but not a second one. She is distraught as she tells her friend, "This always happens to me! I'll never find love!"
• Example 2: A woman is lonely and often spends most of her time at home. Her friends sometimes ask her to dinner and to meet new people. She feels it is useless to even try. No one really could like her. And anyway, all people are the same; petty and selfish.

One suggestion to combat this distortion is to "examine the evidence" by performing an accurate analysis of one's situation. This aids in avoiding exaggerating one's circumstances.

Disqualifying the positive

Disqualifying the positive refers to rejecting positive experiences by insisting they "don't count" for some reason or other. Negative belief is maintained despite contradiction by everyday experiences. Disqualifying the positive may be the most common fallacy in the cognitive distortion range; it is often analyzed with "always being right", a type of distortion where a person is in an all-or-nothing self-judgment. People in this situation show signs of depression. Examples include:

• "I will never be as good as Jane"
• "Anyone could have done as well"
• "They are just congratulating me to be nice"

Mental filtering

Main article: Selective abstraction

Filtering distortions occur when an individual dwells only on the negative details of a situation and filters out the positive aspects.

• Example: Andy gets mostly compliments and positive feedback about a presentation he has done at work, but he also has received a small piece of criticism. For several days following his presentation, Andy dwells on this one negative reaction, forgetting all of the positive reactions that he had also been given.

The Feeling Good Handbook notes that filtering is like a "drop of ink that discolors a beaker of water". One suggestion to combat filtering is a cost–benefit analysis. A person with this distortion may find it helpful to sit down and assess whether filtering out the positive and focusing on the negative is helping or hurting them in the long run.

Conceptualization

In a series of publications, philosopher Paul Franceschi has proposed a unified conceptual framework for cognitive distortions designed to clarify their relationships and define new ones. This conceptual framework is based on three notions: (i) the reference class (a set of phenomena or objects, e.g. events in the patient's life); (ii) dualities (positive/negative, qualitative/quantitative, ...); (iii) the taxon system (degrees allowing to attribute properties according to a given duality to the elements of a reference class). In this model, "dichotomous reasoning", "minimization", "maximization" and "arbitrary focus" constitute general cognitive distortions (applying to any duality), whereas "disqualification of the positive" and "catastrophism" are specific cognitive distortions, applying to the positive/negative duality. This conceptual framework posits two additional cognitive distortion classifications: the "omission of the neutral" and the "requalification in the other pole".

Cognitive restructuring

Cognitive restructuring (CR) is a popular form of therapy used to identify and reject maladaptive cognitive distortions, and is typically used with individuals diagnosed with depression. In CR, the therapist and client first examine a stressful event or situation reported by the client. For example, a depressed male college student who experiences difficulty in dating might believe that his "worthlessness" causes women to reject him. Together, therapist and client might then create a more realistic cognition, e.g., "It is within my control to ask girls on dates. However, even though there are some things I can do to influence their decisions, whether or not they say yes is largely out of my control. Thus, I am not responsible if they decline my invitation." CR therapies are designed to eliminate "automatic thoughts" that include clients' dysfunctional or negative views. According to Beck, doing so reduces feelings of worthlessness, anxiety, and anhedonia that are symptomatic of several forms of mental illness. CR is the main component of Beck's and Burns's CBT.

Narcissistic defense

Main article: Narcissistic defences

Those diagnosed with narcissistic personality disorder tend, unrealistically, to view themselves as superior, overemphasizing their strengths and understating their weaknesses. Narcissists use exaggeration and minimization this way to shield themselves against psychological pain.

Decatastrophizing

Main article: Decatastrophizing

In cognitive therapy, decatastrophizing or decatastrophization is a cognitive restructuring technique that may be used to treat cognitive distortions, such as magnification and catastrophizing, commonly seen in psychological disorders like anxiety and psychosis. Major features of these disorders are the subjective report of being overwhelmed by life circumstances and the incapability of affecting them.

The goal of CR is to help the client change their perceptions to render the felt experience as less significant.

Criticism

Main article: Cognitive behavioral therapy § Criticisms

Common criticisms of the diagnosis of cognitive distortion relate to epistemology and the theoretical basis. If the perceptions of the patient differ from those of the therapist, it may not be because of intellectual malfunctions but because the patient has different experiences. In some cases, depressed subjects appear to be "sadder but wiser".

Lateral computing

From Wikipedia, the free encyclopedia

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

Lateral computing is a lateral thinking approach to solving computing problems. Lateral thinking has been made popular by Edward de Bono. This thinking technique is applied to generate creative ideas and solve problems. Similarly, by applying lateral-computing techniques to a problem, it can become much easier to arrive at a computationally inexpensive, easy to implement, efficient, innovative or unconventional solution.

The traditional or conventional approach to solving computing problems is to either build mathematical models or have an IF- THEN -ELSE structure. For example, a brute-force search is used in many chess engines, but this approach is computationally expensive and sometimes may arrive at poor solutions. It is for problems like this that lateral computing can be useful to form a better solution.

A simple problem of truck backup can be used for illustrating lateral-computing. This is one of the difficult tasks for traditional computing techniques, and has been efficiently solved by the use of fuzzy logic (which is a lateral computing technique). Lateral-computing sometimes arrives at a novel solution for particular computing problem by using the model of how living beings, such as how humans, ants, and honeybees, solve a problem; how pure crystals are formed by annealing, or evolution of living beings or quantum mechanics etc.

From lateral-thinking to lateral-computing

Lateral thinking is technique for creative thinking for solving problems. The brain as center of thinking has a self-organizing information system. It tends to create patterns and traditional thinking process uses them to solve problems. The lateral thinking technique proposes to escape from this patterning to arrive at better solutions through new ideas. Provocative use of information processing is the basic underlying principle of lateral thinking,

The provocative operator (PO) is something which characterizes lateral thinking. Its function is to generate new ideas by provocation and providing escape route from old ideas. It creates a provisional arrangement of information.

Water logic is contrast to traditional or rock logic. Water logic has boundaries which depends on circumstances and conditions while rock logic has hard boundaries. Water logic, in someways, resembles fuzzy logic.

Transition to lateral-computing

Lateral computing does a provocative use of information processing similar to lateral-thinking. This is explained with the use of evolutionary computing which is a very useful lateral-computing technique. The evolution proceeds by change and selection. While random mutation provides change, the selection is through survival of the fittest. The random mutation works as a provocative information processing and provides a new avenue for generating better solutions for the computing problem. The term "Lateral Computing" was first proposed by Prof CR SUTHIKSHN Kumar and First World Congress on Lateral Computing WCLC 2004 was organized with international participants during December 2004.

Lateral computing takes the analogies from real-world examples such as:

• How slow cooling of the hot gaseous state results in pure crystals (Annealing)
• How the neural networks in the brain solve such problems as face and speech recognition
• How simple insects such as ants and honeybees solve some sophisticated problems
• How evolution of human beings from molecular life forms are mimicked by evolutionary computing
• How living organisms defend themselves against diseases and heal their wounds
• How electricity is distributed by grids

Differentiating factors of "lateral computing":

• Does not directly approach the problem through mathematical means.
• Uses indirect models or looks for analogies to solve the problem.
• Radically different from what is in vogue, such as using "photons" for computing in optical computing. This is rare as most conventional computers use electrons to carry signals.
• Sometimes the Lateral Computing techniques are surprisingly simple and deliver high performance solutions to very complex problems.
• Some of the techniques in lateral computing use "unexplained jumps". These jumps may not look logical. The example is the use of "Mutation" operator in genetic algorithms.

Convention – lateral

It is very hard to draw a clear boundary between conventional and lateral computing. Over a period of time, some unconventional computing techniques become integral part of mainstream computing. So there will always be an overlap between conventional and lateral computing. It will be tough task classifying a computing technique as a conventional or lateral computing technique as shown in the figure. The boundaries are fuzzy and one may approach with fuzzy sets.

Formal definition

Lateral computing is a fuzzy set of all computing techniques which use unconventional computing approach. Hence Lateral computing includes those techniques which use semi-conventional or hybrid computing. The degree of membership for lateral computing techniques is greater than 0 in the fuzzy set of unconventional computing techniques.

The following brings out some important differentiators for lateral computing.

Conventional computing

• The problem and technique are directly correlated.
• Treats the problem with rigorous mathematical analysis.
• Creates mathematical models.
• The computing technique can be analyzed mathematically.

Lateral computing

• The problem may hardly have any relation to the computing technique used
• Approaches problems by analogies such as human information processing model, annealing, etc.
• Sometimes the computing technique cannot be mathematically analyzed.

Lateral computing and parallel computing

Parallel computing focuses on improving the performance of the computers/algorithms through the use of several computing elements (such as processing elements). The computing speed is improved by using several computing elements. Parallel computing is an extension of conventional sequential computing. However, in lateral computing, the problem is solved using unconventional information processing whether using a sequential or parallel computing.

A review of lateral-computing techniques

There are several computing techniques which fit the Lateral computing paradigm. Here is a brief description of some of the Lateral Computing techniques:

Swarm intelligence

Swarm intelligence (SI) is the property of a system whereby the collective behaviors of (unsophisticated) agents, interacting locally with their environment, cause coherent functional global patterns to emerge. SI provides a basis with which it is possible to explore collective (or distributed) problem solving without centralized control or the provision of a global model.

One interesting swarm intelligent technique is the Ant Colony algorithm:

• Ants are behaviorally unsophisticated; collectively they perform complex tasks. Ants have highly developed sophisticated sign-based communication.
• Ants communicate using pheromones; trails are laid that can be followed by other ants.
• Routing Problem Ants drop different pheromones used to compute the "shortest" path from source to destination(s).

Agent-based systems

Agents are encapsulated computer systems that are situated in some environment and are capable of flexible, autonomous action in that environment in order to meet their design objectives. Agents are considered to be autonomous (independent, not-controllable), reactive (responding to events), pro-active (initiating actions of their own volition), and social (communicative). Agents vary in their abilities: they can be static or mobile, or may or may not be intelligent. Each agent may have its own task and/or role. Agents, and multi-agent systems, are used as a metaphor to model complex distributed processes. Such agents invariably need to interact with one another in order to manage their inter-dependencies. These interactions involve agents cooperating, negotiating and coordinating with one another.

Agent-based systems are computer programs that try to simulate various complex phenomena via virtual "agents" that represent the components of a business system. The behaviors of these agents are programmed with rules that realistically depict how business is conducted. As widely varied individual agents interact in the model, the simulation shows how their collective behaviors govern the performance of the entire system - for instance, the emergence of a successful product or an optimal schedule. These simulations are powerful strategic tools for "what-if" scenario analysis: as managers change agent characteristics or "rules," the impact of the change can be easily seen in the model output

Grid computing

By analogy, a computational grid is a hardware and software infrastructure that provides dependable, consistent, pervasive, and inexpensive access to high-end computational capabilities. The applications of grid computing are in:

• Chip design, cryptographic problems, medical instrumentation, and supercomputing.
• Distributed supercomputing applications use grids to aggregate substantial computational resources in order to tackle problems that cannot be solved on a single system.

Autonomic computing

Main article: Autonomic computing

The autonomic nervous system governs our heart rate and body temperature, thus freeing our conscious brain from the burden of dealing with these and many other low-level, yet vital, functions. The essence of autonomic computing is self-management, the intent of which is to free system administrators from the details of system operation and maintenance.

Four aspects of autonomic computing are:

• Self-configuration
• Self-optimization
• Self-healing
• Self-protection

This is a grand challenge promoted by IBM.

Optical computing

Optical computing is to use photons rather than conventional electrons for computing. There are quite a few instances of optical computers and successful use of them. The conventional logic gates use semiconductors, which use electrons for transporting the signals. In case of optical computers, the photons in a light beam are used to do computation.

There are numerous advantages of using optical devices for computing such as immunity to electromagnetic interference, large bandwidth, etc.

DNA computing

DNA computing uses strands of DNA to encode the instance of the problem and to manipulate them using techniques commonly available in any molecular biology laboratory in order to simulate operations that select the solution of the problem if it exists.

Since the DNA molecule is also a code, but is instead made up of a sequence of four bases that pair up in a predictable manner, many scientists have thought about the possibility of creating a molecular computer. These computers rely on the much faster reactions of DNA nucleotides binding with their complements, a brute force method that holds enormous potential for creating a new generation of computers that would be 100 billion times faster than today's fastest PC. DNA computing has been heralded as the "first example of true nanotechnology", and even the "start of a new era", which forges an unprecedented link between computer science and life science.

Example applications of DNA computing are in solution for the Hamiltonian path problem which is a known NP complete one. The number of required lab operations using DNA grows linearly with the number of vertices of the graph. Molecular algorithms have been reported that solves the cryptographic problem in a polynomial number of steps. As known, factoring large numbers is a relevant problem in many cryptographic applications.

Quantum computing

In a quantum computer, the fundamental unit of information (called a quantum bit or qubit), is not binary but rather more quaternary in nature. This qubit property arises as a direct consequence of its adherence to the laws of quantum mechanics, which differ radically from the laws of classical physics. A qubit can exist not only in a state corresponding to the logical state 0 or 1 as in a classical bit, but also in states corresponding to a blend or quantum superposition of these classical states. In other words, a qubit can exist as a zero, a one, or simultaneously as both 0 and 1, with a numerical coefficient representing the probability for each state. A quantum computer manipulates qubits by executing a series of quantum gates, each a unitary transformation acting on a single qubit or pair of qubits. In applying these gates in succession, a quantum computer can perform a complicated unitary transformation to a set of qubits in some initial state.

Reconfigurable computing

Field-programmable gate arrays (FPGA) are making it possible to build truly reconfigurable computers. The computer architecture is transformed by on the fly reconfiguration of the FPGA circuitry. The optimal matching between architecture and algorithm improves the performance of the reconfigurable computer. The key feature is hardware performance and software flexibility.

For several applications such as fingerprint matching, DNA sequence comparison, etc., reconfigurable computers have been shown to perform several orders of magnitude better than conventional computers.

Simulated annealing

The Simulated annealing algorithm is designed by looking at how the pure crystals form from a heated gaseous state while the system is cooled slowly. The computing problem is redesigned as a simulated annealing exercise and the solutions are arrived at. The working principle of simulated annealing is borrowed from metallurgy: a piece of metal is heated (the atoms are given thermal agitation), and then the metal is left to cool slowly. The slow and regular cooling of the metal allows the atoms to slide progressively their most stable ("minimal energy") positions. (Rapid cooling would have "frozen" them in whatever position they happened to be at that time.) The resulting structure of the metal is stronger and more stable. By simulating the process of annealing inside a computer program, it is possible to find answers to difficult and very complex problems. Instead of minimizing the energy of a block of metal or maximizing its strength, the program minimizes or maximizes some objective relevant to the problem at hand.

Soft computing

One of the main components of "Lateral-computing" is soft computing which approaches problems with human information processing model. The Soft Computing technique comprises Fuzzy logic, neuro-computing, evolutionary-computing, machine learning and probabilistic-chaotic computing.

Neuro computing

Instead of solving a problem by creating a non-linear equation model of it, the biological neural network analogy is used for solving the problem. The neural network is trained like a human brain to solve a given problem. This approach has become highly successful in solving some of the pattern recognition problems.

Evolutionary computing

The genetic algorithm (GA) resembles the natural evolution to provide a universal optimization. Genetic algorithms start with a population of chromosomes which represent the various solutions. The solutions are evaluated using a fitness function and a selection process determines which solutions are to be used for competition process. These algorithms are highly successful in solving search and optimization problems. The new solutions are created using evolutionary principles such as mutation and crossover.

Fuzzy logic

Fuzzy logic is based on the fuzzy sets concepts proposed by Lotfi Zadeh. The degree of membership concept is central to fuzzy sets. The fuzzy sets differ from crisp sets since they allow an element to belong to a set to a degree (degree of membership). This approach finds good applications for control problems. The Fuzzy logic has found enormous applications and has already found a big market presence in consumer electronics such as washing machines, microwaves, mobile phones, Televisions, Camcoders etc.

Probabilistic/chaotic computing

Probabilistic computing engines, e.g. use of probabilistic graphical model such as Bayesian network. Such computational techniques are referred to as randomization, yielding probabilistic algorithms. When interpreted as a physical phenomenon through classical statistical thermodynamics, such techniques lead to energy savings that are proportional to the probability p with which each primitive computational step is guaranteed to be correct (or equivalently to the probability of error, (1–p). Chaotic Computing is based on the chaos theory.

Fractals

Fractal Computing are objects displaying self-similarity at different scales. Fractals generation involves small iterative algorithms. The fractals have dimensions greater than their topological dimensions. The length of the fractal is infinite and size of it cannot be measured. It is described by an iterative algorithm unlike a Euclidean shape which is given by a simple formula. There are several types of fractals and Mandelbrot sets are very popular.

Fractals have found applications in image processing, image compression music generation, computer games etc. Mandelbrot set is a fractal named after its creator. Unlike the other fractals, even though the Mandelbrot set is self-similar at magnified scales, the small scale details are not identical to the whole. I.e., the Mandelbrot set is infinitely complex. But the process of generating it is based on an extremely simple equation. The Mandelbrot set M is a collection of complex numbers. The numbers Z which belong to M are computed by iteratively testing the Mandelbrot equation. C is a constant. If the equation converges for chosen Z, then Z belongs to M. Mandelbrot equation:

Randomized algorithm

A Randomized algorithm makes arbitrary choices during its execution. This allows a savings in execution time at the beginning of a program. The disadvantage of this method is the possibility that an incorrect solution will occur. A well-designed randomized algorithm will have a very high probability of returning a correct answer. The two categories of randomized algorithms are:

• Monte Carlo algorithm
• Las Vegas algorithm

Consider an algorithm to find the k^th element of an array. A deterministic approach would be to choose a pivot element near the median of the list and partition the list around that element. The randomized approach to this problem would be to choose a pivot at random, thus saving time at the beginning of the process. Like approximation algorithms, they can be used to more quickly solve tough NP-complete problems. An advantage over the approximation algorithms, however, is that a randomized algorithm will eventually yield an exact answer if executed enough times

Machine learning

Human beings/animals learn new skills, languages/concepts. Similarly, machine learning algorithms provide capability to generalize from training data. There are two classes of Machine Learning (ML):

• Supervised ML
• Unsupervised ML

One of the well known machine learning technique is Back Propagation Algorithm. This mimics how humans learn from examples. The training patterns are repeatedly presented to the network. The error is back propagated and the network weights are adjusted using gradient descent. The network converges through several hundreds of iterative computations.

Support vector machines

This is another class of highly successful machine learning techniques successfully applied to tasks such as text classification, speaker recognition, image recognition etc.

Example applications

There are several successful applications of lateral-computing techniques. Here is a small set of applications that illustrates lateral computing:

• Bubble sorting: Here the computing problem of sorting is approached with an analogy of bubbles rising in water. This is by treating the numbers as bubbles and floating them to their natural position.
• Truck backup problem: This is an interesting problem of reversing a truck and parking it at a particular location. The traditional computing techniques have found it difficult to solve this problem. This has been successfully solved by Fuzzy system.
• Balancing an inverted pendulum: This problem involves balancing and inverted pendulum. This problem has been efficiently solved by neural networks and fuzzy systems.
• Smart volume control for mobile phones: The volume control in mobile phones depend on the background noise levels, noise classes, hearing profile of the user and other parameters. The measurement on noise level and loudness level involve imprecision and subjective measures. The authors have demonstrated the successful use of fuzzy logic system for volume control in mobile handsets.
• Optimization using genetic algorithms and simulated annealing: The problems such as traveling salesman problem have been shown to be NP complete problems. Such problems are solved using algorithms which benefit by heuristics. Some of the applications are in VLSI routing, partitioning etc. Genetic algorithms and Simulated annealing have been successful in solving such optimization problems.
• Programming The Unprogrammable (PTU) involving the automatic creation of computer programs for unconventional computing devices such as cellular automata, multi-agent systems, parallel systems, field-programmable gate arrays, field-programmable analog arrays, ant colonies, swarm intelligence, distributed systems, and the like.

Summary

Above is a review of lateral-computing techniques. Lateral-computing is based on the lateral-thinking approach and applies unconventional techniques to solve computing problems. While, most of the problems are solved in conventional techniques, there are problems which require lateral-computing. Lateral-computing provides advantage of computational efficiency, low cost of implementation, better solutions when compared to conventional computing for several problems. The lateral-computing successfully tackles a class of problems by exploiting tolerance for imprecision, uncertainty and partial truth to achieve tractability, robustness and low solution cost. Lateral-computing techniques which use the human like information processing models have been classified as "Soft Computing" in literature.

Lateral-computing is valuable while solving numerous computing problems whose mathematical models are unavailable. They provide a way of developing innovative solutions resulting in smart systems with Very High Machine IQ (VHMIQ). This article has traced the transition from lateral-thinking to lateral-computing. Then several lateral-computing techniques have been described followed by their applications. Lateral-computing is for building new generation artificial intelligence based on unconventional processing.