Semigroup with two elements

Last updated

In mathematics, a semigroup with two elements is a semigroup for which the cardinality of the underlying set is two. There are exactly five nonisomorphic semigroups having two elements:

Contents

The semigroups LO2 and RO2 are antiisomorphic. O2, ({0,1}, ∧) and (Z2, +2) are commutative, and LO2 and RO2 are noncommutative. LO2, RO2 and ({0,1}, ∧) are bands.

Determination of semigroups with two elements

Choosing the set A = { 1, 2 } as the underlying set having two elements, sixteen binary operations can be defined in A. These operations are shown in the table below. In the table, a matrix of the form

 x  y 
 z  t 

indicates a binary operation on A having the following Cayley table.

 1  2 
 1  x  y 
 2  z  t 
List of binary operations in { 1, 2 }
  1   1 
  1   1 
  1   1 
  1   2 
  1   1 
  2   1 
  1   1 
  2   2 
 Null semigroup O2   ≡ Semigroup({0,1}, )  2·(1·2) = 2, (2·1)·2 = 1  Left zero semigroup LO2 
  1   2 
  1   1 
  1   2 
  1   2 
  1   2 
  2   1 
  1   2 
  2   2 
 2·(1·2) = 1, (2·1)·2 = 2  Right zero semigroup RO2   ≡ Group(Z2, ·2)   ≡ Semigroup({0,1}, )
  2   1 
  1   1 
  2   1 
  1   2 
  2   1 
  2   1 
  2   1 
  2   2 
 1·(1·2) = 2, (1·1)·2 = 1   ≡ Group(Z2, +2)  1·(1·1) = 1, (1·1)·1 = 2  1·(2·1) = 1, (1·2)·1 = 2 
  2   2 
  1   1 
  2   2 
  1   2 
  2   2 
  2   1 
  2   2 
  2   2 
 1·(1·1) = 2, (1·1)·1 = 1  1·(2·1) = 2, (1·2)·1 = 1  1·(1·2) = 2, (1·1)·2 = 1  Null semigroup O2 

In this table:

The two-element semigroup ({0,1}, ∧)

The Cayley table for the semigroup ({0,1}, ) is given below:

  0  1 
 0   0   0 
 1   0   1 

This is the simplest non-trivial example of a semigroup that is not a group. This semigroup has an identity element, 1, making it a monoid. It is also commutative. It is not a group because the element 0 does not have an inverse, and is not even a cancellative semigroup because we cannot cancel the 0 in the equation 1·0 = 0·0.

This semigroup arises in various contexts. For instance, if we choose 1 to be the truth value "true" and 0 to be the truth value "false" and the operation to be the logical connective "and", we obtain this semigroup in logic. It is isomorphic to the monoid {0,1} under multiplication. It is also isomorphic to the semigroup

under matrix multiplication.

The two-element semigroup (Z2, +2)

The Cayley table for the semigroup (Z2, +2) is given below:

+2 0  1 
 0   0   1 
 1   1   0 

This group is isomorphic to the cyclic group Z2 and the symmetric group S2.

Semigroups of order 3

Let A be the three-element set {1, 2, 3}. Altogether, a total of 39 = 19683 different binary operations can be defined on A. 113 of the 19683 binary operations determine 24 nonisomorphic semigroups, or 18 non-equivalent semigroups (with equivalence being isomorphism or anti-isomorphism). [1] With the exception of the group with three elements, each of these has one (or more) of the above two-element semigroups as subsemigroups. [2] For example, the set {−1, 0, 1} under multiplication is a semigroup of order 3, and contains both {0, 1} and {−1, 1} as subsemigroups.

Finite semigroups of higher orders

Algorithms and computer programs have been developed for determining nonisomorphic finite semigroups of a given order. These have been applied to determine the nonisomorphic semigroups of small order. [2] [3] [4] The number of nonisomorphic semigroups with n elements, for n a nonnegative integer, is listed under OEIS:  A027851 in the On-Line Encyclopedia of Integer Sequences. OEIS:  A001423 lists the number of non-equivalent semigroups, and OEIS:  A023814 the number of associative binary operations, out of a total of nn2, determining a semigroup.

See also

Related Research Articles

<span class="mw-page-title-main">Binary operation</span> Mathematical operation with two operands

In mathematics, a binary operation or dyadic operation is a rule for combining two elements to produce another element. More formally, a binary operation is an operation of arity two.

In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type. The word homomorphism comes from the Ancient Greek language: ὁμός meaning "same" and μορφή meaning "form" or "shape". However, the word was apparently introduced to mathematics due to a (mis)translation of German ähnlich meaning "similar" to ὁμός meaning "same". The term "homomorphism" appeared as early as 1892, when it was attributed to the German mathematician Felix Klein (1849–1925).

<span class="mw-page-title-main">Monoid</span> Algebraic structure with an associative operation and an identity element

In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.

<span class="mw-page-title-main">Semigroup</span> Algebraic structure consisting of a set with an associative binary operation

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.

<span class="mw-page-title-main">Klein four-group</span> Mathematical abelian group

In mathematics, the Klein four-group is an abelian group with four elements, in which each element is self-inverse (composing it with itself produces the identity) and in which composing any two of the three non-identity elements produces the third one. It can be described as the symmetry group of a non-square rectangle (with the three non-identity elements being horizontal reflection, vertical reflection and 180-degree rotation), as the group of bitwise exclusive or operations on two-bit binary values, or more abstractly as Z2 × Z2, the direct product of two copies of the cyclic group of order 2. It was named Vierergruppe (German:[ˈfiːʁɐˌɡʁʊpə], meaning four-group) by Felix Klein in 1884. It is also called the Klein group, and is often symbolized by the letter V or as K4.

In mathematics, the concept of an inverse element generalises the concepts of opposite and reciprocal of numbers.

<span class="mw-page-title-main">Cyclic group</span> Mathematical group that can be generated as the set of powers of a single element

In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted Cn, that is generated by a single element. That is, it is a set of invertible elements with a single associative binary operation, and it contains an element g such that every other element of the group may be obtained by repeatedly applying the group operation to g or its inverse. Each element can be written as an integer power of g in multiplicative notation, or as an integer multiple of g in additive notation. This element g is called a generator of the group.

<span class="mw-page-title-main">General linear group</span> Group of n×n invertible matrices

In mathematics, the general linear group of degree n is the set of n×n invertible matrices, together with the operation of ordinary matrix multiplication. This forms a group, because the product of two invertible matrices is again invertible, and the inverse of an invertible matrix is invertible, with the identity matrix as the identity element of the group. The group is so named because the columns of an invertible matrix are linearly independent, hence the vectors/points they define are in general linear position, and matrices in the general linear group take points in general linear position to points in general linear position.

In abstract algebra, a magma, binar, or, rarely, groupoid is a basic kind of algebraic structure. Specifically, a magma consists of a set equipped with a single binary operation that must be closed by definition. No other properties are imposed.

In mathematics, an algebra over a field is a vector space equipped with a bilinear product. Thus, an algebra is an algebraic structure consisting of a set together with operations of multiplication and addition and scalar multiplication by elements of a field and satisfying the axioms implied by "vector space" and "bilinear".

Ring theory is the branch of mathematics in which rings are studied: that is, structures supporting both an addition and a multiplication operation. This is a glossary of some terms of the subject.

<span class="mw-page-title-main">Semiring</span> Algebraic ring that need not have additive negative elements

In abstract algebra, a semiring is an algebraic structure. It is a generalization of a ring, dropping the requirement that each element must have an additive inverse. At the same time, it is a generalization of bounded distributive lattices.

In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A∗. The free semigroup on A is the subsemigroup of A∗ containing all elements except the empty string. It is usually denoted A+.

Named after the 19th century British mathematician Arthur Cayley, a Cayley table describes the structure of a finite group by arranging all the possible products of all the group's elements in a square table reminiscent of an addition or multiplication table. Many properties of a group – such as whether or not it is abelian, which elements are inverses of which elements, and the size and contents of the group's center – can be discovered from its Cayley table.

In mathematics, there are many types of algebraic structures which are studied. Abstract algebra is primarily the study of specific algebraic structures and their properties. Algebraic structures may be viewed in different ways, however the common starting point of algebra texts is that an algebraic object incorporates one or more sets with one or more binary operations or unary operations satisfying a collection of axioms.

<span class="mw-page-title-main">Semifield</span> Algebraic structure

In mathematics, a semifield is an algebraic structure with two binary operations, addition and multiplication, which is similar to a field, but with some axioms relaxed.

In algebra, a transformation semigroup is a collection of transformations that is closed under function composition. If it includes the identity function, it is a monoid, called a transformationmonoid. This is the semigroup analogue of a permutation group.

In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an involutive anti-automorphism, which—roughly speaking—brings it closer to a group because this involution, considered as unary operator, exhibits certain fundamental properties of the operation of taking the inverse in a group: uniqueness, double application "cancelling itself out", and the same interaction law with the binary operation as in the case of the group inverse. It is thus not a surprise that any group is a semigroup with involution. However, there are significant natural examples of semigroups with involution that are not groups.

In mathematics, a trivial semigroup is a semigroup for which the cardinality of the underlying set is one. The number of distinct nonisomorphic semigroups with one element is one. If S = { a } is a semigroup with one element, then the Cayley table of S is

In abstract algebra, a semigroup with three elements is an object consisting of three elements and an associative operation defined on them. The basic example would be the three integers 0, 1, and −1, together with the operation of multiplication. Multiplication of integers is associative, and the product of any two of these three integers is again one of these three integers.

References

  1. ↑ Friðrik Diego; Kristín Halla Jónsdóttir (July 2008). "Associative Operations on a Three-Element Set" (PDF). The Montana Mathematics Enthusiast. 5 (2 & 3): 257–268. doi:10.54870/1551-3440.1106. S2CID   118704099 . Retrieved 6 February 2014.
  2. 1 2 Andreas Distler, Classification and enumeration of finite semigroups Archived 2 April 2015 at the Wayback Machine , PhD thesis, University of St. Andrews
  3. ↑ Siniša Crvenkovič; Ivan Stojmenovic. "An algorithm for Cayley tables of algebras". 23 (2). Univ. u Novom Sadu, Zb. Rad. Prirod.-Mat. Fak. Review of Research, Faculty of Science: 221–231.{{cite journal}}: Cite journal requires |journal= (help) (Accessed on 9 May 2009)
  4. ↑ John A Hildebrant (2001). Handbook of Finite Semigroup Programs. (Preprint).

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.