Permutation Groups - Revision history

Lila: /* Licensing */

2021-11-17T20:13:46Z

Licensing

Lila: /* Licensing */

2021-11-17T20:13:03Z

Licensing

Lila: /* Examples */

2021-11-17T20:12:12Z

Examples

Lila: /* Oligomorphic groups */

2021-11-17T20:05:16Z

Oligomorphic groups

Lila at 20:03, 17 November 2021

2021-11-17T20:03:24Z

Lila: /* Isomorphisms of permutation groups */

2021-11-17T20:01:50Z

Isomorphisms of permutation groups

Lila: /* Cayley's theorem */

2021-11-17T20:01:21Z

Cayley's theorem

Lila: /* Primitive actions */

2021-11-17T19:58:11Z

Primitive actions

Lila: /* Group actions */

2021-11-17T19:57:54Z

Group actions

Lila: /* Notation */

2021-11-17T19:57:34Z

Notation

@@ Line 164: / Line 164: @@
 Content obtained and/or adapted from:
 * [https://en.wikipedia.org/wiki/Permutation_group Permutation group, Wikipedia] under a CC BY-SA license
-* [http://mathonline.wikidot.com/the-permutation-groups-on-a-set-x-sx, mathonline.wikidot.com] under a CC BY-SA license
+* [http://mathonline.wikidot.com/the-permutation-groups-on-a-set-x-sx The Permutation Groups on a Set X, SX, mathonline.wikidot.com] under a CC BY-SA license

← Older revision		Revision as of 20:13, 17 November 2021
Line 164:		Line 164:
	Content obtained and/or adapted from:		Content obtained and/or adapted from:
	* [https://en.wikipedia.org/wiki/Permutation_group Permutation group, Wikipedia] under a CC BY-SA license		* [https://en.wikipedia.org/wiki/Permutation_group Permutation group, Wikipedia] under a CC BY-SA license
		+	* [http://mathonline.wikidot.com/the-permutation-groups-on-a-set-x-sx, mathonline.wikidot.com] under a CC BY-SA license

← Older revision		Revision as of 20:12, 17 November 2021
Line 78:		Line 78:

	As another example consider the group of symmetries of a square. Let the vertices of a square be labeled 1, 2, 3 and 4 (counterclockwise around the square starting with 1 in the top left corner). The symmetries are determined by the images of the vertices, that can, in turn, be described by permutations. The rotation by 90° (counterclockwise) about the center of the square is described by the permutation (1234). The 180° and 270° rotations are given by (13)(24) and (1432), respectively. The reflection about the horizontal line through the center is given by (12)(34) and the corresponding vertical line reflection is (14)(23). The reflection about the 1,3−diagonal line is (24) and reflection about the 2,4−diagonal is (13). The only remaining symmetry is the identity (1)(2)(3)(4). This permutation group is abstractly known as the dihedral group of order 8.		As another example consider the group of symmetries of a square. Let the vertices of a square be labeled 1, 2, 3 and 4 (counterclockwise around the square starting with 1 in the top left corner). The symmetries are determined by the images of the vertices, that can, in turn, be described by permutations. The rotation by 90° (counterclockwise) about the center of the square is described by the permutation (1234). The 180° and 270° rotations are given by (13)(24) and (1432), respectively. The reflection about the horizontal line through the center is given by (12)(34) and the corresponding vertical line reflection is (14)(23). The reflection about the 1,3−diagonal line is (24) and reflection about the 2,4−diagonal is (13). The only remaining symmetry is the identity (1)(2)(3)(4). This permutation group is abstractly known as the dihedral group of order 8.
		+
		+	==The Permutation Groups on a Set X, SX==
		+	<p>If <span class="math-inline"><math>\{ 1, 2, ..., n \}</math></span> is the <span class="math-inline"><math>n</math></span>-element set of positive integers and if <span class="math-inline"><math>S_n</math></span> denotes the set of all permutations on <span class="math-inline"><math>\{ 1, 2, ..., n \}</math></span> then <span class="math-inline"><math>(S_n, \circ)</math></span> where <span class="math-inline"><math>\circ</math></span> is the operation of function composition defines a group called the symmetric group on <span class="math-inline"><math>n</math></span>-elements.</p>
		+	<p>Now suppose that <span class="math-inline"><math>X</math></span> is any set. We can analogously define a group on the set of permutations on <span class="math-inline"><math>X</math></span>.</p>
		+	<blockquote style="background: white; border: 1px solid black; padding: 1em;">
		+	<td><strong>Definition:</strong> Let <span class="math-inline"><math>X</math></span> be any set and let <span class="math-inline"><math>S_X</math></span> denote the set of all permutations on <span class="math-inline"><math>X</math></span>. Then <span class="math-inline"><math>(S_X, \circ)</math></span> is called the <strong>Permutation Group</strong> on <span class="math-inline"><math>X</math></span>.</td>
		+	</blockquote>
		+	<p>Note that if <span class="math-inline"><math>X = \{ 1, 2, ..., n \}</math></span> then <span class="math-inline"><math>S_X = S_n</math></span> is the permutation group on <span class="math-inline"><math>n</math></span>-elements. If <span class="math-inline"><math>X = A = \{ x_1, x_2, ..., x_n \}</math></span> is a general <span class="math-inline"><math>n</math></span>-element set then <span class="math-inline"><math>S_X = S_A</math></span> is a symmetric group on a general <span class="math-inline"><math>n</math></span>-element set <span class="math-inline"><math>A</math></span>. Of course, what's more interesting is when <span class="math-inline"><math>X</math></span> is a countably infinite or uncountably infinite set.</p>
		+	<p>For example, consider the set <span class="math-inline"><math>X = \mathbb{Z}</math></span>. Then <span class="math-inline"><math>S_{X} = S_{\mathbb{Z}}</math></span> is the set of all permutations on <span class="math-inline"><math>\mathbb{Z}</math></span>. For example, the following functions <span class="math-inline"><math>\sigma : \mathbb{Z} \to \mathbb{Z}, \delta : \mathbb{Z} \to \mathbb{Z} \in S_{\mathbb{Z}}</math></span> are permutations on <span class="math-inline"><math>\mathbb{Z}</math></span> as you should verify:</p>
		+	<div style="text-align: center;"><math>\begin{align} \quad \sigma (x) = x + 1 \end{align}</math></div>
		+	<div style="text-align: center;"><math>\begin{align} \quad \delta(x) = x - 1 \end{align}</math></div>
		+	<p>Then the composition <span class="math-inline"><math>\sigma \circ \delta</math></span> is given for all <span class="math-inline"><math>x \in \mathbb{Z}</math></span> by</p>
		+	<div style="text-align: center;"><math>\begin{align} \quad (\sigma \circ \delta)(x) = \sigma(\delta(x)) = \sigma(x - 1) =(x - 1) + 1 = x \end{align}</math></div>
		+	<p>Therefore we see that <span class="math-inline"><math>\sigma \circ \delta = i</math></span> where <span class="math-inline"><math>i</math></span> is the identity permutation on <span class="math-inline"><math>\mathbb{Z}</math></span>.</p>

	==Group actions==		==Group actions==

← Older revision		Revision as of 20:05, 17 November 2021
Line 146:		Line 146:

	The interest in oligomorphic groups is partly based on their application to model theory, for example when considering automorphisms in countably categorical theories.		The interest in oligomorphic groups is partly based on their application to model theory, for example when considering automorphisms in countably categorical theories.
		+
		+	== Licensing ==
		+	Content obtained and/or adapted from:
		+	* [https://en.wikipedia.org/wiki/Permutation_group Permutation group, Wikipedia] under a CC BY-SA license

@@ Line 28: / Line 28: @@
 & 5 & 1 & 2 & 3\end{pmatrix}.</math>
-Permutations are also often written in cyclic notation (''cyclic form'')<ref>especially when the algebraic properties of the permutation are of interest.</ref> so that given the set ''M'' = {1, 2, 3, 4}, a permutation ''g'' of ''M'' with ''g''(1) = 2, ''g''(2) = 4, ''g''(4) = 1 and ''g''(3) = 3 will be written as (1, 2, 4)(3), or more commonly, (1, 2, 4) since 3 is left unchanged; if the objects are denoted by single letters or digits, commas and spaces can also be dispensed with, and we have a notation such as (124). The permutation written above in 2-line notation would be written in cyclic notation as <math> \sigma = (125)(34).</math>
+Permutations are also often written in cyclic notation (''cyclic form'') so that given the set ''M'' = {1, 2, 3, 4}, a permutation ''g'' of ''M'' with ''g''(1) = 2, ''g''(2) = 4, ''g''(4) = 1 and ''g''(3) = 3 will be written as (1, 2, 4)(3), or more commonly, (1, 2, 4) since 3 is left unchanged; if the objects are denoted by single letters or digits, commas and spaces can also be dispensed with, and we have a notation such as (124). The permutation written above in 2-line notation would be written in cyclic notation as <math> \sigma = (125)(34).</math>
 ==Composition of permutations&ndash;the group product==
-The product of two permutations is defined as their composition as functions, so <math>\sigma \cdot \pi</math> is the function that maps any element ''x'' of the set to <math>\sigma (\pi (x))</math>. Note that the rightmost permutation is applied to the argument first, because of the way function composition is written.<ref>
+The product of two permutations is defined as their composition as functions, so <math>\sigma \cdot \pi</math> is the function that maps any element ''x'' of the set to <math>\sigma (\pi (x))</math>. Note that the rightmost permutation is applied to the argument first, because of the way function composition is written. Some authors prefer the leftmost factor acting first, but to that end permutations must be written to the ''right'' of their argument, often as a superscript, so the permutation <math>\sigma</math> acting on the element <math>x</math> results in the image <math>x ^{\sigma}</math>. With this convention, the product is given by <math>x ^{\sigma \cdot \pi} = (x ^{\sigma})^{\pi}</math>. However, this gives a ''different'' rule for multiplying permutations. This convention is commonly used in the permutation group literature, but this article uses the convention where the rightmost permutation is applied first.
 Since the composition of two bijections always gives another bijection, the product of two permutations is again a permutation. In two-line notation, the product of two permutations is obtained by rearranging the columns of the second (leftmost) permutation so that its first row is identical with the second row of the first (rightmost) permutation. The product can then be written as the first row of the first permutation over the second row of the modified second permutation. For example, given the permutations,
@@ Line 54: / Line 47: @@
 The identity permutation, which maps every element of the set to itself, is the neutral element for this product. In two-line notation, the identity is
 :<math>\begin{pmatrix}1 & 2 & 3 & \cdots & n \\ 1 & 2 & 3 & \cdots & n\end{pmatrix}.</math>
-In cyclic notation, ''e'' = (1)(2)(3)...(''n'') which by convention is also denoted by just (1) or even ().<ref>{{harvnb|Rotman|2006|loc=p. 108}}</ref>
+In cyclic notation, ''e'' = (1)(2)(3)...(''n'') which by convention is also denoted by just (1) or even ().
 Since bijections have inverses, so do permutations, and the inverse ''σ''<sup>−1</sup> of ''σ'' is again a permutation. Explicitly, whenever ''σ''(''x'')=''y'' one also has ''σ''<sup>−1</sup>(''y'')=''x''. In two-line notation the inverse can be obtained by interchanging the two lines (and sorting the columns if one wishes the first line to be in a given order). For instance
@@ Line 88: / Line 81: @@
 ==Group actions==
-In the above example of the symmetry group of a square, the permutations "describe" the movement of the vertices of the square induced by the group of symmetries. It is common to say that these group elements are "acting" on the set of vertices of the square. This idea can be made precise by formally defining a '''group action'''.<ref name=Dixon96>{{harvnb|Dixon|Mortimer|1996|loc=p. 5}}</ref>
+In the above example of the symmetry group of a square, the permutations "describe" the movement of the vertices of the square induced by the group of symmetries. It is common to say that these group elements are "acting" on the set of vertices of the square. This idea can be made precise by formally defining a '''group action'''.
 Let ''G'' be a group and ''M'' a nonempty set. An '''action''' of ''G'' on ''M'' is a function ''f'': ''G'' × ''M'' → ''M'' such that
@@ Line 95: / Line 88: @@
 This last condition can also be expressed as saying that the action induces a group homomorphism from ''G'' into ''Sym''(''M''). Any such homomorphism is called a ''(permutation) representation'' of ''G'' on ''M''.
-For any permutation group, the action that sends (''g'', ''x'') → ''g''(''x'') is called the '''natural action''' of ''G'' on ''M''. This is the action that is assumed unless otherwise indicated.<ref name=Dixon96 /> In the example of the symmetry group of the square, the group's action on the set of vertices is the natural action. However, this group also induces an action on the set of four triangles in the square, which are: ''t''<sub>1</sub> = 234, ''t''<sub>2</sub> = 134, ''t''<sub>3</sub> = 124 and ''t''<sub>4</sub> = 123. It also acts on the two diagonals: ''d''<sub>1</sub> = 13 and ''d''<sub>2</sub> = 24.
+For any permutation group, the action that sends (''g'', ''x'') → ''g''(''x'') is called the '''natural action''' of ''G'' on ''M''. This is the action that is assumed unless otherwise indicated. In the example of the symmetry group of the square, the group's action on the set of vertices is the natural action. However, this group also induces an action on the set of four triangles in the square, which are: ''t''<sub>1</sub> = 234, ''t''<sub>2</sub> = 134, ''t''<sub>3</sub> = 124 and ''t''<sub>4</sub> = 123. It also acts on the two diagonals: ''d''<sub>1</sub> = 13 and ''d''<sub>2</sub> = 24.
 {| class="wikitable"
 |-
@@ Line 118: / Line 111: @@
 ==Transitive actions==
-The action of a group ''G'' on a set ''M'' is said to be ''transitive'' if, for every two elements ''s'', ''t'' of ''M'', there is some group element ''g'' such that ''g''(''s'') = ''t''.  Equivalently, the set ''M'' forms a single orbit under the action of ''G''.<ref>{{harvnb|Artin|1991|p=177}}</ref>  Of the examples above, the group {e, (1 2), (3 4), (1 2)(3 4)} of permutations of {1, 2, 3, 4} is not transitive (no group element takes 1 to 3) but the group of symmetries of a square is transitive on the vertices.
+The action of a group ''G'' on a set ''M'' is said to be ''transitive'' if, for every two elements ''s'', ''t'' of ''M'', there is some group element ''g'' such that ''g''(''s'') = ''t''.  Equivalently, the set ''M'' forms a single orbit under the action of ''G''.  Of the examples above, the group {e, (1 2), (3 4), (1 2)(3 4)} of permutations of {1, 2, 3, 4} is not transitive (no group element takes 1 to 3) but the group of symmetries of a square is transitive on the vertices.
 === Primitive actions ===

@@ Line 141: / Line 141: @@
 : ''λ''(''f''<sub>1</sub>(''g'', ''x'')) = ''f''<sub>2</sub>(''ψ''(''g''), ''λ''(''x'')) for all ''g'' in ''G'' and ''x'' in ''X''
-If {{nowrap|1=''X'' = ''Y''}} this is equivalent to ''G'' and ''H'' being conjugate as subgroups of Sym(''X''). The special case where {{nowrap|1=''G'' = ''H''}} and ''ψ'' is the identity map gives rise to the concept of ''equivalent actions'' of a group.
+If ''X'' = ''Y'' this is equivalent to ''G'' and ''H'' being conjugate as subgroups of Sym(''X''). The special case where ''G'' = ''H'' and ''ψ'' is the identity map gives rise to the concept of ''equivalent actions'' of a group.
-In the example of the symmetries of a square given above, the natural action on the set {1,2,3,4} is equivalent to the action on the triangles. The bijection ''λ'' between the sets is given by {{nowrap|''i'' ↦ ''t''<sub>''i''</sub>}}. The natural action of group ''G''<sub>1</sub> above and its action on itself (via left multiplication) are not equivalent as the natural action has fixed points and the second action does not.
+In the example of the symmetries of a square given above, the natural action on the set {1,2,3,4} is equivalent to the action on the triangles. The bijection ''λ'' between the sets is given by ''i'' ↦ ''t''<sub>''i''</sub>. The natural action of group ''G''<sub>1</sub> above and its action on itself (via left multiplication) are not equivalent as the natural action has fixed points and the second action does not.
 == Oligomorphic groups ==

← Older revision		Revision as of 20:01, 17 November 2021
Line 127:		Line 127:

	==Cayley's theorem==		==Cayley's theorem==
−	~~{{main\|Cayley's theorem}}~~

	Any group ''G'' can act on itself (the elements of the group being thought of as the set ''M'') in many ways. In particular, there is a regular action given by (left) multiplication in the group. That is, ''f''(''g'', ''x'') = ''gx'' for all ''g'' and ''x'' in ''G''. For each fixed ''g'', the function ''f''<sub>''g''</sub>(''x'') = ''gx'' is a bijection on ''G'' and therefore a permutation of the set of elements of ''G''. Each element of ''G'' can be thought of as a permutation in this way and so ''G'' is isomorphic to a permutation group; this is the content of Cayley's theorem.		Any group ''G'' can act on itself (the elements of the group being thought of as the set ''M'') in many ways. In particular, there is a regular action given by (left) multiplication in the group. That is, ''f''(''g'', ''x'') = ''gx'' for all ''g'' and ''x'' in ''G''. For each fixed ''g'', the function ''f''<sub>''g''</sub>(''x'') = ''gx'' is a bijection on ''G'' and therefore a permutation of the set of elements of ''G''. Each element of ''G'' can be thought of as a permutation in this way and so ''G'' is isomorphic to a permutation group; this is the content of Cayley's theorem.

@@ Line 121: / Line 121: @@
 === Primitive actions ===
-{{main|Primitive permutation group}}
 A permutation group ''G'' acting transitively on a non-empty finite set ''M'' is ''imprimitive'' if there is some nontrivial set partition of ''M'' that is preserved by the action of ''G'', where "nontrivial" means that the partition isn't the partition into singleton sets nor the partition with only one part.  Otherwise, if ''G'' is transitive but does not preserve any nontrivial partition of ''M'', the group ''G'' is ''primitive''.

@@ Line 14: / Line 14: @@
 ==Notation==
-{{main|Permutation#Notations}}
 Since permutations are bijections of a set, they can be represented by Cauchy's ''two-line notation''. This notation lists each of the elements of ''M'' in the first row, and for each element, its image under the permutation below it in the second row. If <math>\sigma</math> is a permutation of the set <math>M = \{x_1,x_2,\ldots,x_n\}</math> then,
 : <math> \sigma = \begin{pmatrix}