-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathintro.tex
executable file
·1659 lines (1455 loc) · 61.2 KB
/
intro.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\chapter{Introduction}
\pagestyle{draft}
Algebraic structures of various types occur naturally in many different areas
of mathematics. The most straightforward examples arise in arithmetic, but
there are numerous other examples which are not as obvious. In this chapter
we start our study of group theory by looking at a number of concrete
situations where an algebraic structure arises naturally. We will see that all
these algebraic structures share common features, and these common features
will lead us to the definition of a group in Chapter 2.
\section{Symmetry}
\label{section:symmetry}
You are familiar, at least in an informal way, with the idea of symmetry from
Euclidean geometry and calculus. For example, the letter ``\textsf{A}'' has
reflective symmetry in its vertical axis, ``\textsf{E}'' has reflective
symmetry in its horizontal axis, ``\textsf{N}'' has rotational symmetry of
$\pi$ radians about its centre, ``\textsf{H}'' has all three types of
symmetry, and the letter ``\textsf{F}'' has none of these symmetries.
Symmetry is also important in understanding real world phenomena. As some
examples:
\begin{itemize}
\item The symmetries of molecules can affect possible chemical reactions.
For example, many proteins and amino acids (the basic building blocks of
life) have ``left-handed'' and ``right-handed'' versions which are
reflections of one-another. Life on earth uses the ``left-handed''
versions almost exclusively.
\item Crystals have very strong symmetries, largely determined by the
symmetries of the atoms or molecules of which the crystal is built.
\item Most animals and plants have some sort of symmetry in their
body-shapes, although they are never perfectly symmetrical. Most
animals have bilateral symmetry, while plants often have five-fold
or six-fold rotational symmetry.
\item In art and design, symmetrical patterns are often found to be more
pleasing to the eye than asymmetrical patterns, or simply more practical.
\item Waves in fluids, and the vibrations of a drumhead or string are often
symmetrical, or built out of symmetric components. These symmetries
are usually inherent in the underlying equations that we use to model
such systems, and understanding the symmetry can be crucial in finding
solutions to these equations.
\end{itemize}
But what, precisely, do we mean by symmetry?
\begin{definition}
Let $\Omega$ be a subset of $\reals^{n}$. A \defn{symmetry}{symmetry} of
$\Omega$ is a function $T: \reals^{n} \to \reals^{n}$ such that
\begin{theoremenum}
\item $\{ T(x) : x \in \Omega \} = \Omega$, and
\item $T$ preserves distances between points: if $d(x,y)$ is the
distance between the points $x$ and $y$, then $d(T(x),T(y)) =
d(x,y)$.
\end{theoremenum}
We denote the set of all symmetries of $\Omega$ by $\Sym(\Omega)$. Every
set $\Omega$ has at least one symmetry, the \defn{identity
symmetry}{symmetry!identity} $I(x) = x$.
Functions which preserve distance are called
\defn{isometries}{isometries}, so every symmetry is an isometry.
\end{definition}
\begin{proposition}\label{prop:symmetryfacts}
Let $\Omega$ be a subset of $\reals^{n}$, and let $S$ and $T$ be
symmetries of $\Omega$. Then
\begin{theoremenum}
\item $T$ is one-to-one and onto.
\item the inverse function $T^{-1}$ is a symmetry of $\Omega$
\item the composition $T \circ S$ is a symmetry of $\Omega$
\item the compositions $T \circ T^{-1}$ and $T^{-1} \circ T$ always
equal the identity symmetry $I$.
\end{theoremenum}
\end{proposition}
\begin{proof}
(i) This follows immediately from the technical result that every
isometry from $\reals^{n}$ to $\reals^{n}$ is one-to-one and onto
(this is proved in Lemma~\ref{lemma:isometrybijective} at the end of
this chapter).
(ii) Since $T$ is one-to-one and onto, it has an inverse function
$T^{-1}$. We observe that $T^{-1}(\Omega) = T^{-1}(T(\Omega)) =
\Omega$, and also that $d(T^{-1}(x), T^{-1}(y)) = d(T(T^{-1}(x)),
T(T^{-1}(y))) = d(x,y)$. Hence $T^{-1}$ is a symmetry of $\Omega$.
Parts (iii) and (iv) are left as a simple exercise.
\end{proof}
We\sidebar{Notation}{Many algebra texts write $ST$ for $T \circ S$, because
$S$ is applied first, then $T$. In these notes, however, we will remain
consistent with the traditional function composition order, but you must
keep this clear in your head to avoid confusion.\\
\indent Another commonly used convention in algebra is to apply functions
on the right, so $T(x)$ is written as $xT$, so that $S(T(x))$ would be
written as $xTS$.}
will usually write the composed symmetry $T \circ S$ as simply $TS$. Remember
that because function composition works from right to left, $TS$ means that the
symmetry $S$ is applied first, followed by the symmetry $T$.
You should also recall that composition of functions is associative
(see Proposition~\ref{prop:functionfacts}) so composition of
symmetries is always associative. In other words if $S$, $T$ and $U
\in \Sym(\Omega)$, then $S(TU) = (ST)U$. However, composition of
functions is not usually commutative, so without additional evidence,
we cannot conclude that $ST = TS$.
\begin{figure}\label{fig:symmetryofH}
\centering
\begin{picture}(7,7)(-1,-1)
\thicklines
\put(1,1){\line(1,0){1}}
\put(2,1){\line(0,1){1}}
\put(2,2){\line(1,0){1}}
\put(3,2){\line(0,-1){1}}
\put(3,1){\line(1,0){1}}
\put(4,1){\line(0,1){3}}
\put(4,4){\line(-1,0){1}}
\put(3,4){\line(0,-1){1}}
\put(3,3){\line(-1,0){1}}
\put(2,3){\line(0,1){1}}
\put(2,4){\line(-1,0){1}}
\put(1,4){\line(0,-1){3}}
\thinlines
\put(-1,2.5){\vector(1,0){7}}
\put(2.5,-1){\vector(0,1){7}}
\end{picture}
\caption{The set $\Omega$ of Example~\ref{eg:symmetryofH}}
\end{figure}
\begin{example}\label{eg:symmetryofH}
Let $\Omega \subseteq \reals^{2}$ be the H-shaped set illustrated in
Figure~\ref{fig:symmetryofH}. Then $\Omega$ has percisely the following
symmetries:
\begin{alignat*}{4}
I(x,y) &= (x,y) &\qquad& \text{(Identity)} \\
H(x,y) &= (x,-y) && \text{(Reflection in the $x$-axis)} \\
V(x,y) &= (-x,y) && \text{(Reflection in the $y$-axis)} \\
R(x,y) &= (-x,-y) && \text{(Rotation by $\pi$ radians about the origin)}
\end{alignat*}
We can confirm by direct calculation that $I^{-1} = I$, $H^{-1} = H$, $V^{-1}
= V$ and $R^{-1} = R$. In other words, each of these transformations is its
own inverse. These symmetries compose in the following ways:
\begin{alignat*}{6}
H \circ H &= I & \qquad & H \circ V &= R & \qquad & H \circ R &= V\\
V \circ H &= R && V \circ V &= I && V \circ R &= H\\
R \circ H &= V && R \circ V &= H && R \circ R &= I
\end{alignat*}
In fact we can summarize this using a ``multiplication table'':
\[
\begin{array}{c|cccc}
\circ & I & H & V & R \\
\hline
I & I & H & V & R \\
H & H & I & R & V \\
V & V & R & I & H \\
R & R & V & H & I
\end{array}
\]
This sort of ``multiplication table'' is called a \defn{Cayley table}{Cayley
table} for the operation.
The composition of symmetries in this example is commutative. You can verify
this by simply checking every possible product. For example, from the Cayley
table we have $HR = V$, and $RH = V$, so $HR = RH$.
\end{example}
There is nothing really special about the set $\Omega$ in the previous
example, other than the fact that composition is commutative for this set.
As the following example shows, we should not expect composition of
symmetries to be commutative in every case.
\begin{figure}\label{fig:symmtriangle}
\centering
\begin{picture}(7,7)(-3.5,-3.5)
\thicklines
\qbezier(2,0)(0,1.155)(-1,1.732)
\qbezier(2,0)(0,-1.155)(-1,-1.732)
\qbezier(-1,1.732)(-1,0)(-1,-1.732)
\thinlines
\put(-3.5,0){\vector(1,0){7}}
\put(0,-3.5){\vector(0,1){7}}
\put(2,0){\makebox(0,0)[tl]{1}}
\put(0,2){\makebox(0,0)[l]{1}}
\put(-2,0){\makebox(0,0)[t]{-1}}
\put(0,-2){\makebox(0,0)[l]{-1}}
\end{picture}
\caption{The equilateral triangle of Example~\ref{eg:symmtriangle}}
\end{figure}
\begin{example}\label{eg:symmtriangle}
Let $\Omega \subseteq \reals^{2}$ be an equilateral triangle with veritces
$(1,0)$, $(-1/2, \sqrt{3}/2)$ and $(-1/2, -\sqrt{3}/2)$. Then $\Omega$ has
the following symmetries:
\begin{tabular}{lp{3.5in}}
$I$ & Identity \\
$R_{1}$ & Rotation by $2\pi/3$ radians clockwise \\
$R_{2}$ & Rotation by $2\pi/3$ radians anticlockwise \\
$H_{0}$ & Reflection in the $x$-axis \\
$H_{1}$ & Reflection in the line through $(0,0)$ and $(-1/2,\sqrt{3}/2)$ \\
$H_{2}$ & Reflection in the line through $(0,0)$ and $(-1/2,-\sqrt{3}/2)$
\end{tabular}
The precise formulas for these symmetries are an exercise. A little thought
tells us that $I^{-1} = I$, $R_{1}^{-1} = R_{2}$, $R_{2}^{-1} = R_{1}$,
$H_{1}^{-1} = H_{1}$, $H_{2}^{-1} = H_{2}$, and $H_{3}^{-1} = H_{3}$.
The Cayley table for these symmetries is:
\medskip
\hspace{1in}\begin{tabular}{c|cccccc}
$\circ$ & $I$ & $R_{1}$ & $R_{2}$ & $H_{0}$ & $H_{1}$ & $H_{2}$ \\
\hline
$I$ & $I$ & $R_{1}$ & $R_{2}$ & $H_{0}$ & $H_{1}$ & $H_{2}$ \\
$R_{1}$ & $R_{1}$ & $R_{2}$ & $I$ & $H_{1}$ & $H_{2}$ & $H_{0}$ \\
$R_{2}$ & $R_{2}$ & $I$ & $R_{1}$ & $H_{2}$ & $H_{0}$ & $H_{1}$ \\
$H_{0}$ & $H_{0}$ & $H_{2}$ & $H_{1}$ & $I$ & $R_{2}$ & $R_{1}$ \\
$H_{1}$ & $H_{1}$ & $H_{0}$ & $H_{2}$ & $R_{1}$ & $I$ & $R_{2}$ \\
$H_{2}$ & $H_{2}$ & $H_{1}$ & $H_{0}$ & $R_{2}$ & $R_{1}$ & $I$ \\
\end{tabular}
\medskip
This operation is associative, but it is clearly \emph{not} commutative:
$H_{0} \circ H_{1} = R_{1}$, but $H_{1} \circ H_{0} = R_{2}$, for example.
\end{example}
Some sets have infinite collections of symmetries, but even in these cases
we can still understand how composition works.
\begin{example}\label{eg:circlesymmetry}
Let $\Omega = \{(x,y) \in \reals^{2} : x^{2} + y^{2} = 1\}$ be the unit
circle. Then $\Omega$ has infinitely many symmetries, which fall into two
classes:
\begin{tabular}{lp{3.5in}}
$R_{\theta}$ & Rotation by $\theta$ radians clockwise,
$0 \le \theta < 2\pi$ \\
$H_{\varphi}$ & Reflection in the line which makes an angle $\varphi$
to the $x$-axis at the origin, $0 \le \varphi < \pi$.
\end{tabular}
The identity is $R_{0}$, rotation by $0$ radians. We can also check that
the inverse of $R_{\theta}$ is $R_{2\pi - \theta}$ for $0 < \theta < 2\pi$,
and the inverse of $H_{\varphi}$ is $H_{\varphi}$.
Because the set of symmetries is infinite, we can't write down a Cayley
table, but we can list how the generic symmetries compose:
\begin{alignat*}{4}
R_{\theta} \circ R_{\omega} &= R_{\theta + \omega} &\qquad&
R_{\theta} \circ H_{\varphi} &= H_{\varphi - \theta/2}\\
H_{\varphi} \circ R_{\theta} &= H_{\varphi + \theta/2}&&
H_{\varphi} \circ H_{\psi} &= R_{2\psi - 2\varphi}
\end{alignat*}
where all angles are reduced to lie in the appropriate ranges. The easiest
way to verify this table is to note that $H_{\varphi} = H_{0} \circ
R_{2\varphi} = R_{-2\varphi} \circ H_{0}$, which greatly simplifies
calculations involving $H_{\varphi}$.
\end{example}
All the examples so far have used rotational and reflective symmetries, but
some sets also have translational symmetry.
\begin{example}
Let $\Omega \{(x,y) \in \reals^{2} : y = 0\}$ be the $x$-axis in
$\reals^{2}$. Then $\Omega$ has symmetries of the form
\[
T_{c}(x,y) = (x + c,y),
\]
ie. right translation by $c$, for any $c \in \reals$, and
\[
S_{c}(x,y) = (-x + c,y),
\]
ie. reflection about $0$, followed by right translation by $c$, for any $c
\in \reals$ (which is equal to reflection about the point $c/2$).
The identity symmetry is $T_{0}$, the inverse symmetry of $T_{c}$ is
$T_{-c}$, and the inverse symmetry of $S_{c}$ is $S_{c}$. The
symmetries of this set compose by the rules
\begin{alignat*}{4}
T_{a} \circ T_{b} &= T_{a+b} &\qquad&
T_{a} \circ S_{b} &= S_{a+b}\\
S_{a} \circ T_{b} &= S_{a-b}&&
S_{a} \circ S_{b} &= T_{a-b}
\end{alignat*}
\end{example}
\subsection*{Exercises}
\begin{exercises}
\item Find the set of symmetries for each capital letter of the alphabet
(assume uniform, sans serif letter shapes).
\item Prove Proposition~\ref{prop:symmetryfacts} (iii-iv).
\item Write down formulas for each of the symmetries in
Example~\ref{eg:symmtriangle}.
Hint 1: the point $(x,y) \in \reals^{2}$ rotated clockwise by an angle
$\theta$ about the origin is $(x\cos \theta + y\sin \theta, -x\sin \theta +
y\cos \theta)$.
Hint 2: from the Cayley table, we have $H_{1} = R_{1} \circ H_{0}$ and
$H_{2} = R_{2} \circ H_{0}$, and it is easy to find the formula of a
composition of functions.
\item Let $\Omega \subseteq \reals^{2}$ be a square, centred at the origin,
with side length 1.
Find all 8 symmetries of $\Omega$, and write down the formula for each.
Find the inverses of each symmetry.
Write out the Cayley table for the symmetries of a square.
\item\label{ex:symtetra} (*) Let $\Omega \subseteq \reals^{3}$ be a regular tetrahedron
centred at the origin. Show that $\Omega$ has 24 symmetries.
\item (*) Let $\Omega = \integers^{2} \subseteq \reals^{2}$ be the integer
lattice in the plane, ie.
\[
\integers^{2} = \{ (m,n) \in \reals^{2} : m, n \in \integers \}.
\]
Classify the symmetries of $\integers^{2}$.
Find the inverses of each symmetry.
As in Example~\ref{eg:circlesymmetry}, find the product of typical symmetries.
\end{exercises}
\section{Review: Sets}
Group theory does not require a great deal of mathematical background to
get started: we really only need the concepts of sets and functions to
present the basics of the theory. You should have come across the formal definitions of
these concepts in previous courses, such as a typical discrete mathematics
course. A large part of the discussion in this section and the next will be
to fix notation and terminology.
A \defn{set}{set} is a collection of mathematical objects. We do not care about
the order that the objects are presented, nor any potential duplication of
elements. The mathematical objects contained in a set $S$ are called
the \defn{elements}{element} or \defn{members}{member} of a set, and write $x \in S$ to say
that $x$ is an element of $S$. We say that two sets are equal if they have
exactly the same elements.
The simplest way to present a set is as a list of all the elements of
the set enclosed in braces, such as the set $\{1, 2, 3\}$. For sets
with large numbers of elements, or infinite sets, this presentation is
tedious (or impossible!), so there are two alternatives. If there is
a clear pattern to the elements, one can use ellipses to elide the
majority of the set, leaving just enough to make the pattern of
elements clear:
\[
\{2, 4, 6, \ldots, 100\} \qquad \text{and} \qquad \{2, 3, 5, 7, 11,
13, 17
\ldots\}
\]
are clearly meant to represent the set of all even numbers from 2 to 100,
and the set of all prime numbers respectively. However some sets are too
complicated for this sort of presentation, and for these we use ``set
builder'' notation. In set builder notation we simply specify the set by
some property $P$ which defines the set:
\[
\{x | x \text{ satisfies } P\} \qquad \text{or} \qquad \{x : x \text{ satisfies }
P\}.
\]
For example, one could write the set of all prime numbers as
\[
\{ x | x \text{ is prime}\},
\]
or the set of all numbers greater than $2$ and less than or equal to $10$ as
\[
\{ x : 2 < x \le 10 \}.
\]
This last example illustrates an ambiguity: which collection of numbers do
we mean? Integers? Rational numbers? Real numbers? To resolve this
ambiguity, we usually specify the set $S$ from which we take our elements,
and use the notation
\[
\{x \in S | x \text{ satisfies } P\} \qquad \text{or} \qquad \{x \in S : x
\text{ satisfies } P\}.
\]
Therefore the interval of all real numbers greater than 2 and less than or
equal to 10 would most clearly be represented by
\[
\{ x \in \reals : 2 < x \le 10\}.
\]
There are several special sets that come up with sufficient frequency to
deserve their own notation. The most important is the \defn{empty set}{set!empty}
$\emptyset = \{\}$, the set which contains no elements. The next most
important are the various sets of numbers:
\begin{alignat*}{4}
\naturals &= \{1, 2, 3, 4, \ldots \} & \qquad & \text{\defn{natural
numbers}{natural numbers}}\\
\integers &= \{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots \} &&
\text{\defn{integers}{integers}}\\
\rationals &= \{p/q : p \in \integers, q \in \naturals, \text{$p$ and $q$
coprime}\} && \text{\defn{rational numbers}{rational numbers}}\\
\reals &= \{ x : \text{$x$ is an infinite decimal\footnote{This is far
from the whole story: take a real analysis course for more information.}}\}
&& \text{\defn{real numbers}{real numbers}}\\
\complex &= \{ x+iy : x, y \in \reals \} && \text{\defn{complex numbers}{complex numbers}}
\end{alignat*}
We \sidebar{Proving Equality of Sets}{Often we have
two sets, $A$ and $B$, which we want to show are equal. A
very common technique to show that this is in fact the case is to show that
each set is a subset of the other. We can then conclude that they are
equal. In summary:\\
\hspace{2em}\fbox{\parbox{1in}{$A \subseteq B$ and $B \subseteq A$
implies $A = B$}} }
say that a set $A$ is a \defn{subset}{subset} of another set $B$, and write $A
\subseteq B$, if every element of $A$ is an element of $B$. For example,
$\{2, 4, 6\} \subseteq \{1, 2, 3, 4, 5, 6\}$. Note that if $A$ is equal to
$B$, it is still a subset of $B$, and that the empty set is always a subset
of any other set. We say that $A$ is a \defn{proper subset}{subset!proper} of $B$ if $A
\subset B$ and $A \ne B$, and we denote this by $A \subset B$.
We can combine sets using a number of different \defn{set operations}{set operations}. The
\defn{union}{union} of two sets $A$ and $B$ is the set containing all the elements
of both sets combined, ie.
\[
A \union B = \{ x : x \in A \text{ or } x \in B\}.
\]
The \defn{intersection}{intersection} of $A$ and $B$ is the set containing the objects that
are elements of both of the sets, ie.
\[
A \intersect B = \{ x : x \in A \text{ and } x \in B\}.
\]
Intersection and union are both \defn{commutative}{commutative} and \defn{associative}{associative}
operations, and are \defn{distributive}{distributive} with respect to one another:
\begin{align*}
A \union B &= B \union A\\
A \intersect B &= B \intersect A\\
A \union (B \union C) &= (A \union B) \union C = A \union B \union C\\
A \intersect (B \intersect C) &= (A \intersect B) \intersect C = A \intersect B \intersect
C\\
A \union (B \intersect C) &= (A \union B) \intersect (A \union C)\\
A \intersect (B \union C) &= (A \intersect B) \union (A \intersect C)\\
A \union \emptyset &= A\\
A \intersect \emptyset &= \emptyset
\end{align*}
If there is some natural \defn{universal set}{universal set} $U$ of elements which we are
considering, we can define the \defn{complement}{complement} of a set $A$ as the set of all
things in $U$ not in $A$, ie.
\[
A^{c} = \{x \in U : x \notin A \}.
\]
The complement of the complement is the original set, and complements
interact with union and intersection via \defn{DeMorgan's laws}{DeMorgan's laws}:
\begin{align*}
(A^{c})^{c} &= A\\
(A \union B)^{c} &= A^{c} \intersect B^{c}\\
(A \intersect B)^{c} &= A^{c} \union B^{c}\\
\emptyset^{c} &= U \\
U^{c} &= \emptyset.
\end{align*}
Note that sometimes the notation $\overline{A}$ is used for complements.
Even in the absence of a universal set, we can define the \defn{set
difference}{set difference} operation: $A \setminus B$ is everything in $A$ which is not in
$B$. That is
\[
A \setminus B = \{ x \in A : x \notin B\}.
\]
If complements make sense, then we have $A \setminus B = A \intersect
B^{c}$. We can also define the \defn{symmetric difference}{symmetric difference} of $A$ and $B$
as the set of all things in either $A$ or $B$, but not in both,
\[
A \symdiff B = \{x \in A \union B : x \notin A \intersect B\}
\]
or equivalently
\[
A \symdiff B = (A \union B) \setminus (A \intersect B) = (A \setminus B)
\union (B \setminus A).
\]
Clearly $A \symdiff B = B \symdiff A$.
Perhaps the most important set operation for our purposes, since it appears
in just about every core definition in abstract algebra, is the \defn{Cartesian
product}{cartesian product}. The product of two sets, $A \cross B$ is the set
consisting of tuples $(x,y)$, where $x \in A$ and $y \in B$, ie.
\[
A \cross B = \{(x,y) : x \in A, y \in B\}.
\]
More generally, we define a product of $n$ sets to be the set of $n$-tuples:
\[
A_{1} \cross A_{2} \cross \cdots \cross A_{n} = \{ (a_{1}, a_{2}, \ldots,
a_{n}) : a_{k} \in A_{k}, k = 1, 2, \ldots, n\}.
\]
We also define
\[
A^{n} = \underbrace{A \cross A \cross \cdots \cross A}_{n\text{ times}}
\]
to be the set of all $n$-tuples of elements of $A$. This notation is familiar
from calculus, where $\reals^{n}$ is the set of all $n$-tuples of real numbers.
Note that $A \times B$ is not equal to $B \times A$ in general, although they
are clearly closely related.
If $A \subseteq C$, and $B \subseteq D$ it is straightforward to see that
$A \cross B \subseteq C \cross D$.
We denote the \defn{cardinality}{cardinality} of a set $A$ by $|A|$. For sets
with a finite number of elements, the cardinality of $A$ is simply the number
of elements in the set. For infinite sets, cardinality is a more complicated
matter, but for the purposes of this course it really only matters whether a
set is infinite or not. You should, however, be aware that there are
countably infinite sets (such as $\naturals^{n}$, $\integers^{n}$ and
$\rationals^{n}$) and uncountably infinite sets (such as $\reals^{n}$ and
$\complex^{n}$) and that countable and uncountable sets have different
cardinality.
For finite sets, we have the following facts from basic counting theory:
the inclusion-exclusion principle
\[
|A \union B| = |A| + |B| - |A \intersect B|,
\]
and the multiplication principle
\[
|A \cross B| = |A||B|.
\]
Both of these will be of importance when exploring the structure of finite
groups.
\subsection*{Exercises}
\begin{exercises}
\item In this section many identities are stated without proof. Pick
8 of them and show why they hold. Be careful not to use any identity
or fact which is dependent on what you are proving.
\item Show that $|A \setminus B| = |A| - |A \intersect B|$.
\end{exercises}
\section{Review: Functions}
A \defn{function}{function} $f$ from $A$ to $B$ is a rule which relates every element $x$
of $A$ to some unique element $y$ of $B$. What is key here is that the
function associates $x$ with \emph{precisely} one element of $B$. We write $y
= f(x)$. More formally, we denote the function with the notation
\begin{align*}
f : A & \to B \\
x & \mapsto y.
\end{align*}
The set $A$ is the \defn{domain}{domain}, the set $B$ the \defn{codomain}{codomain}, while the
set
\[
f(A) = \{ f(x) : x \in A \}
\]
is the \defn{range}{range} of the function. The \defn{graph}{graph!of a function} of the function is
the subset
\[
\mathcal{G}_{f} = \{(x, f(x)) : x \in A \}
\]
of $A \cross B$.
From time to time, we will wish to specify an abstract function without
specifying an exact formula or rule. In this case, we will just write $f: A
\to B$, specifying the domain and codomain, but nothing else. We will also
write $\mathcal{F}(A,B)$ for the set of all functions from $A$ to
$B$. Some texts use $B^{A}$ instead for this set.
Given a function $f: A \to B$, and a subset $X \subseteq A$, we define the
\defn{image}{image} of $X$ to be the subset of $B$ given by
\[
f(X) = \{f(x) : x \in B\}.
\]
If $Y \subseteq B$, we also define the \defn{inverse image}{image!inverse}
of $Y$ to be the subset of $A$ given by
\[
f^{-1}(Y) = \{x \in A : f(x) \in Y\}.
\]
In other words $f^{-1}(Y)$ is the set of elements of $A$ whose value lies in
the set $Y$.
Given a function $g: A \to B$ and another function $f: B \to C$, we define
the \defn{composition}{composition!of two functions} of $f$ and $g$ to be
the function $f \circ g : A \to C$ defined by $(f \circ g)(x) = f(g(x))$.
A function is \defn{one-to-one}{one-to-one function} or \defn{injective}{injective function} if it satisfies the
condition
\[
f(x_{1}) = f(x_{2}) \text{ implies } x_{1} = x_{2}.
\]
A function is \defn{onto}{onto function} or \defn{surjective}{surjective function} if the range equals the
entire codomain, or equivalently
\[
f(A) = B.
\]
A function which is both injective and surjective is called a
\defn{bijective}{bijective function} function.
A bijective function automatically has an \defn{inverse
function}{function!inverse} $f^{-1}: B \to A$ defined by $f^{-1}(b) = a$ if
and only if $f(a) = b$. The fact that $f$ is onto guarantees that $f^{-1}$
is defined on all of $B$, while the fact that $f$ is injective ensures that
$f^{-1}$ is a function. It follows from the definition that $(f \circ
f^{-1})(x) = x$ and $(f^{-1} \circ f)(x) = x$.
\begin{proposition}\label{prop:functionfacts}
Let $A$, $B$ $C$ and $D$ be sets, and $f : A \to B$, $g : B \to C$ and
$h: C \to D$ be functions. Then we have:
\begin{theoremenum}
\item Composition of functions satisfies an associative law:
$(h \circ g) \circ f = h \circ (g \circ f)$.
\item If $f$ and $g$ are both one-to-one, then so is $g \circ f$.
\item If $f$ and $g$ are both onto, then so is $g \circ f$.
\item If $f$ and $g$ are both bijections, then so is $g \circ f$.
\item If $f$ is a bijection, then so is $f^{-1}$.
\item If $f$ is a bijection $|A| = |B|$.
\end{theoremenum}
\end{proposition}
\begin{proof}
The proof is left as an exercise.
\end{proof}
\begin{example}
We could formally write the function $f(x) = \sqrt{x}
+ 1$ as:
\begin{align*}
f : [0,\infty) &\to \reals \\
x &\mapsto \sqrt{x} + 1.
\end{align*}
As you would expect, the domain is $[0,\infty)$, the codomain is $\reals$,
the range is $[1, \infty)$, and the graph is the set of points
\[
\{(x, \sqrt{x} + 1) : x \in [0,\infty)\}.
\]
The function is one-to-one, but is not surjective or bijective.
\end{example}
\subsection*{Exercises}
\begin{exercises}
\item Prove Proposition~\ref{prop:functionfacts}.
\end{exercises}
\section{Permutations}
A \defn{permutation}{permutation} of a set $X$ is simply a re-arrangement of
the elements, or more precisely a function $p$ that maps each element of $X$ to
an element of $X$ with no two distinct elements being mapped to the same
element (and for infinite sets, we also need $p(X) = X$). Another way of
saying this is that a permutation of $X$ is simply a bijection $p: X \to X$.
Normally we are interested only in permutations of finite sets, and we
really only care how many elements there are to permute. Hence it is
customary to consider permutations of the set $\{1, 2, 3, ..., n\}$.
Since permutations are just functions,we can define them as we would any other
function, by specifying the value that the function takes at each point in the
domain. Unfortunately, unlike the usual functions you see in a calculus course,
you usually can't specify permutations using a formula.
\begin{example}
The following function $p$ is a permutation of the set $\{1,2,3,4,5,6,7,8\}$:
\begin{alignat*}{8}
p(1) &= 2 &\qquad&
p(2) &= 4 &\qquad&
p(3) &= 6 &\qquad&
p(4) &= 8 \\
p(5) &= 7 &&
p(6) &= 5 &&
p(7) &= 3 &&
p(8) &= 1
\end{alignat*}
\end{example}
A more compact way of writing down a permutation is to write it as an array of
numbers, with $1$, through $n$ on the top row, and the respective image of each
in the second row, like so:
\[
p = \begin{pmatrix}
1 & 2 & 3 & \ldots & n \\
p(1) & p(2) & p(3) & \ldots & p(n)
\end{pmatrix}
\]
\begin{example}
The permutation $p$ of the previous example can be written as follows:
\[
p = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
2 & 4 & 6 & 8 & 7 & 5 & 3 & 1
\end{pmatrix}
\]
\end{example}
We denote the set of all permutations of $\{1,2,3,\ldots,n\}$ by $S_{n}$.
\begin{example}\label{eg:perm3part1}
The set $S_{3}$ is
\[
\left\{\begin{pmatrix}
1 & 2 & 3 \\
1 & 2 & 3
\end{pmatrix},
\begin{pmatrix}
1 & 2 & 3 \\
3 & 1 & 2
\end{pmatrix},
\begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1
\end{pmatrix},
\begin{pmatrix}
1 & 2 & 3 \\
1 & 3 & 2
\end{pmatrix},
\begin{pmatrix}
1 & 2 & 3 \\
2 & 1 & 3
\end{pmatrix},
\begin{pmatrix}
1 & 2 & 3 \\
3 & 2 & 1
\end{pmatrix} \right\}
\]
\end{example}
Note that, as in the above example, the \defn{identity
permutation}{permutation!identity} $p(k) = k$ is always a permutation.
Since every permutation is a one-to-one and onto function, there is an inverse
function $p^{-1}$ associated with every permutation $p$.
We can ``multiply'' two permutations by applying the first permutation, and
then using the second permutation to permute the result. If $p$ and $q$ are
permutations of the same set, $pq(k)$ is the what you get from applying $q$
to $p(k)$, ie.\ $pq(k) = q(p(k))$, so $pq = q \circ p$ (note the reversal of
terms in the product versus the composition).
\begin{proposition}\label{prop:permgroup}
Let $X$ be any set, and $p$ and $q$ be permutations of $X$, then
\begin{theoremenum}
\item $p^{-1}$ is a permutation of $X$,
\item $pq$ is a permutation of $X$,
\item the product satisfies an associative law: $(pq)r = p(qr)$.
\end{theoremenum}
\end{proposition}
\begin{proof}
These follow immediately from Proposition~\ref{prop:functionfacts}:
the inverse
function of a bijection is a bijection, proving (i); the composition
of bijective functions is a bijective function, proving (ii); and
composition of functions is associative, so
\[
(pq)r = r \circ (q \circ p) = (r \circ q) \circ p = p(qr),
\]
proving (iii).
\end{proof}
\begin{example}
Let
\[
p = \begin{pmatrix}
1 & 2 & 3 \\
3 & 2 & 1
\end{pmatrix}
\qquad \text{and} \qquad
q = \begin{pmatrix}
1 & 2 & 3 \\
3 & 1 & 2
\end{pmatrix}.
\]
We can find $pq$ fairly easily: for example if
$k=1$, we know that $p(1) = 3$, and $q(3) = 2$, so $pq(1) = 2$. Repeating
for $k = 2$ and $3$, we get So
we have
\[
pq = \begin{pmatrix}
1 & 2 & 3 \\
2 & 1 & 3
\end{pmatrix}.
\]
\end{example}
\begin{example}\label{eg:perm3part2}
We listed all the elements of $S_{3}$ in Example~\ref{eg:perm3part1}.
To simplify notation we will give each of these a symbol to identify it:
\begin{alignat*}{6}
p_{0} &= \begin{pmatrix}
1 & 2 & 3 \\
1 & 2 & 3
\end{pmatrix} &\qquad&
p_{1} &= \begin{pmatrix}
1 & 2 & 3 \\
3 & 1 & 2
\end{pmatrix} &\qquad&
p_{2} &= \begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1
\end{pmatrix}\\
p_{3} &= \begin{pmatrix}
1 & 2 & 3 \\
1 & 3 & 2
\end{pmatrix} &&
p_{4} &= \begin{pmatrix}
1 & 2 & 3 \\
2 & 1 & 3
\end{pmatrix} &&
p_{5} &= \begin{pmatrix}
1 & 2 & 3 \\
3 & 2 & 1
\end{pmatrix}
\end{alignat*}
It is easy to verify that $p_{0}^{-1} = p_{0}$, $p_{1}^{-1} = p_{2}$,
$p_{2}^{-1} = p_{1}$, $p_{3}^{-1} = p_{3}$, $p_{4}^{-1} = p_{4}$,
and $p_{5}^{-1} = p_{5}$.
Just as with symmetries, we can write out a Cayley table for the products
of these permutations:
\[
\begin{array}{c|cccccc}
& p_{0} & p_{1} & p_{2} & p_{3} & p_{4} & p_{5} \\
\hline
p_{0} & p_{0} & p_{1} & p_{2} & p_{3} & p_{4} & p_{5} \\
p_{1} & p_{1} & p_{2} & p_{0} & p_{4} & p_{5} & p_{3} \\
p_{2} & p_{2} & p_{0} & p_{1} & p_{5} & p_{3} & p_{4} \\
p_{3} & p_{3} & p_{5} & p_{4} & p_{0} & p_{2} & p_{1} \\
p_{4} & p_{4} & p_{3} & p_{5} & p_{1} & p_{0} & p_{2} \\
p_{5} & p_{5} & p_{4} & p_{3} & p_{2} & p_{1} & p_{0}
\end{array}
\]
This product is not commutative.
It's probably not immediately obvious, but if you look closely you will see
that the pattern of this Cayley table is exactly the same as the pattern of
the Cayley table of Example~\ref{eg:symmtriangle}, with the correspondences
$p_{0} \leftrightarrow I$,
$p_{1} \leftrightarrow R_{1}$,
$p_{2} \leftrightarrow R_{2}$,
$p_{3} \leftrightarrow H_{0}$,
$p_{4} \leftrightarrow H_{1}$,
$p_{5} \leftrightarrow H_{2}$.
Indeed, the inverses of each element have the same pattern under these same
correspondences.
In other words, if we look at these two examples abstractly, we seem to be
getting the same underlying mathematical object.
This correspondence can be made even more concrete in the following way: if
we label the vertices of the equilateral triangle of Example~\ref{eg:symmtriangle}
with the numbers 1, 2 and 3, starting at $(0,0)$ and working clockwise, we
find that the symmetries of the triangle permute the vertices in exactly
the same way that the corresponding permutations permute the corresponding
numbers.
\end{example}
\subsection{Cycles}
Even with the current notation, expressing and working with permutations can
be cumbersome. There is another, alternative, notation which can speed up
the process of working with permutations. This notation works by looking at
the \defn{cycles}{cycle} withing a permutation. If $p$ is a permutation
of the set $X$, the cycle of an element $k$ of $X$ in $p$ is the sequence
of elements $(k, p(k), p^{2}(k), \ldots, p^{m}(k))$ (where $p^{l}$ is the product
of $p$ with itself $l$ times) such that $m$ is the smallest number such that,
$p^{m+1}(k) = k$.
Note that the order of the elements in a cycle is important, but not where we
start in the cycle. For example, we regard $(k, p(k), p^{2}(k), \ldots, p^{m}(k))$,
$(p(k),$ $p^{2}(k),\ldots, p^{m}(k), k)$, $(p^{2}(k), \ldots, p^{m}(k), k, p(k))$, etc.\ as
representing the same cycle. If $X$ is the set $\{1, 2, \ldots n\}$, it is
usual to write a cycle starting with the smallest number in the cycle.
A cycle with $m$ elements is called an \defn{$m$-cycle}{$m$-cycle}. A 2-cycle
is sometimes called a \defn{transposition}{transposition}, since it transposes
two elements.
\begin{example}
In the following permutation
\[
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
2 & 4 & 6 & 8 & 7 & 5 & 3 & 1
\end{pmatrix}
\]
we have $1 \to 2$, $2 \to 4$, $4 \to 8$ and $8 \to 1$, so $(1,2,4,8)$ is
a cycle. We could also write this cycle as $(2, 4, 8, 1)$, $(4,8, 1, 2)$,
or $(8, 1, 2, 4)$.
The smallest element not in this cycle is $3$, and we have
$3 \to 6$, $6 \to 5$, $5 \to 7$ and $7 \to 3$, so $(3, 6, 5, 7)$ is another
cycle.
Since every element is in one of these two cycles, these are the only cycles
in this permutation.
\end{example}
If we find all of the cycles of a permutation, we can represent the permutation
as a whole as a product of its cycles. But to do that we need to understand how
to multiply cycles.
To work out how a product of cycles permutes a particular element $k$, all you
need do is work from left to right until you find the element in a cycle, and
then find the element which follows it in that cycle. You continue from left
to right starting with the the next cycle looking for an occurrence of the new
element. If there is, then you find the element which follows it in the cycle.
Continue on in this fashion until you run out of cycles. The final value of
the element is the image of $k$ under the product of cycles.
\begin{example}
Consider the permutation $p = (1, 3, 5)(2)(4, 6)$ of the set
$\{1, 2, 3, 4, 5, 6\}$. We can calculate $p(1)$ be looking at the first
cycle, where we see that the element after $1$ in that cycle is $3$, and we also
note that $3$ does not occur in any cycle after the first, so $p(1) = 3$.
Similarly, we have $p(2) = 2$, $p(3) = 5$, $p(4) = 6$, $p(5) = 1$ and
$p(6) = 4$. This permutation could also be written as
\[
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6\\
3 & 2 & 5 & 6 & 1 & 4
\end{pmatrix}.
\]
\end{example}
Notice that there would be no difference in the above example if the cycle
$(2)$ was omitted. It is common practise to leave such single-element
cycles out, particularly when the set which is being permuted is clear.
\begin{example}
Consider the product of cycles $p = (1, 3, 5)(2, 3)(4, 6, 5)$ in the set
$\{1, 2, 3, 4, 5,$ $6\}$. We can calculate $p(1)$ be looking at the first
cycle, where we see that the element after $1$ in that cycle is $3$; however
$3$ occurs in the second cycle, and the element after it in the cycle is $2$;
and $2$ does not occur in the remaining cycle, so $p(1) = 2$. Similarly,
we have $3 \to 5$ in the first cycle, and $5 \to 4$ in the last cycle, so
$p(3) = 4$.
Calculating everything out, we have $p(2) = 3$, $p(4) = 6$, $p(5) = 1$ and
$p(6) = 5$. This permutation could also be written as
\[
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6\\
2 & 3 & 4 & 6 & 1 & 5
\end{pmatrix},
\]
or more simply in cycle notation as $(1, 2, 3, 4, 6, 5)$.
\end{example}
Any permutation can be written as a product of the cycles it contains.
\begin{theorem}
Every permutation of $S_{n}$ can be written as a product of disjoint cycles.
(Two cycles are disjoint if they have not elements in common.)
\end{theorem}
\begin{proof}
Let $p$ be a permutation of $S_{n}$. We let $c_{1}$ be the cycle which
includes $1$,
\[
c_{1} = \{1, p(1), p^{2}(1), \ldots, p^{m_{1}}(1)\},
\]
and we let $p_{1}$ be the permutation defined by
\[
p_{1}(k) = \begin{cases}
k & \text{if $k \in c_{1}$,}\\
p(k) & \text{otherwise}.
\end{cases}
\]
Then it is clear that $p = c_{1}p_{1}$.
Now if we have written $p = c_{1}\ldots c_{l}p_{l}$, where $c_{1}, \ldots,\
c_{l}$ are disjoint cycles, and $p_{l}$ is a permutation which satisfies
has $p_{l}(k) = k$ whenever $k$ is in one of the cycles, then one of two
things must be true: either every element of $\{1, 2, \ldots, n\}$ is an
element of one of the cycles, or there is some smallest element $k_{l}$
which is not in any of the cycles.
In the first case, we have that $p_{l}$ must be the identity permutation,
so $p = c_{1}\ldots c_{l}$, and we are done.
In the second case, we let $c_{l+1}$ be the cycle including $k_{l}$,
\[
c_{l+1} = \{k_{l}, p(k_{l}), p^{2}(k_{l}), \ldots, p^{m_{l}}(k_{l})\},
\]
and let $p_{l+1}$ be the permutation defined by
\[
p_{l+1}(k) = \begin{cases}
k & \text{if $k$ is an element of any cycle $c_{1}$, $c_{2}, \ldots, c_{l+1}$}\\
p(k) & \text{otherwise}.
\end{cases}
\]
Then $p = c_{1}\ldots c_{l+1}p_{l+1}$.
Since $\{1,2,3,\ldots, n\}$ is a finite set, an induction argument using
this construction proves the result.
\end{proof}
\begin{example}
The permutation