Set Theory

Mathematical Logic. Set Theory deals with fundamental questions about the nature of mathematics. • Set theory is a branch of mathematics. • Set theory includes a study of the infinite. • Set theory and logic a symbiotic relationship. Why we study Set Theory? • To build foundations for the other branches of mathematics. • To understand the fundamental sets of mathematics: N, Z, Q, R, C.

0.1

Ingredients of the language for Set Theory

• Logical connectives: ∧ (and), ∨ (or), ¬ (not), → (implies), ↔ (iff); • Quantifiers: ∀ (forall) Universal Quantifier, ∃ (there exists) Existential Quantifiers; • Relational Symbols: ∈ and = . What do you mean by a Set? A set is a well defined class of objects. By a well define means that there exists a rule with the help of which it is possible to tell whether a given object belongs or does not belongs to the give collection. • Sets defined by their extent: Examples: {3, 5, 7}, {φ, φ}. • Sets described by their intent: Examples: {x ∈ N : x is prime}, {x ∈ R : x2 > 5}. Set of Sets. If the element of a set are sets themselves, then such a set is said to be ’class of sets’ or a ’family of sets’. 1

0.2

Axiom of Set Theory

• Axiom of Extension Tow sets are equal iff they have same members: A = B if x ∈ A ⇔ x ∈ B. • Axiom of Empty Set There is a set, φ with on element. • Powerset Axiom If A is a set, there is a set P(A), whose members are the subsets of A. Symbolically, P(A) = {T : T ⊆ A}. Obviously φ and A are both element of P(a). Singleton. A set consisting of a single element is called a singleton set. Subset of a set. If A, B are sets such that every element of A is also a element of B, Then A is said to be subset of B. In other words, A is a subset of B if x ∈ A ⇒ x ∈ B. Proper Subset. Disjoint Set. If two sets A and B have no common element, then A and B are disjoint, or mutually exclusive. Examples. Let A = {x : x2 + 1 = 0, x ∈ R}. Examples. Let A = {x : xis a straight line passing through three points on a circle.}. Theorem 0.1. If a finite set A has n elements, then the power set of A has 2n element. Proof. There are n Cr subsets consisting r elements out of n elements of set A, where r = 0, 1, . . . , n. Since A has only n elements then no subset of A can have more then n elements. Hence P(A) = 1 +n C1 + . . . +n Cn = (1 + 1)n = 2n . Theorem 0.2. If A is any set, then φ ⊆ A, i.e., then empty set is a subset of every set. Proof. Let φ & A. Then ∃ at least one element x such that x ∈ φ and x∈ / A. But ∀x, x ∈ / φ, since φ is the null set. Therefore ∃ no element x such that x ∈ φ and x ∈ / A. This contradict our initial assumption. Hence we must have φ ⊆ A. Theorem 0.3. If A and B are sets, then A = B iff A ⊆ B and B ⊆ A.

2

Proof. If A = B, Then by the Axiom of Extension every element of A is an element of B and every element of B is an element of A. Hence A ⊆ B and B ⊆ A. Conversely, if A ⊆ B and B ⊆ A, then every element of A is an element of B and every element of B is an element of A. Hence by the Axiom of Extension, A = B. Theorem 0.4. If A ⊆ B and B ⊆ C, then A ⊆ C. Proof. Let x be an arbitrary element of A. Since A ⊆ B, if we have x ∈ A ⇒ x ∈ B. Also It is given that B ⊆ C. This implies that x ∈ B ⇒ x ∈ C. Hence x ∈ A ⇒ x ∈ c. Hence by the definition, A ⊆ C. Union of sets. Let A and B be two sets. Then the union of A and B is the set of all elements which are either in A or in B. Union of A and B is denoted by A ∪ B. Mathematically, A ∪ B = {x : x ∈ A or x ∈ B}. Intersection of sets. Let A and B be two sets. Then the intersection of A and B is the set of all elements which are common in A and B. Intersection of A and B is denoted by A ∩ B. Mathematically, A ∩ B = {x : x ∈ A and x ∈ B}. Difference of sets. Let A and B be two sets. Then the difference of A and B is the set of elements which belongs to A but not belongs to B. The difference between A and B is denoted by A − B, A \ B or A ∼ B. Mathematically, A \ B = {x : x ∈ A and x ∈ B c }. Symmetric difference of two sets. Let A and B be two sets. Then the symmetric difference of A and B is define as the union of A \ B and B \ A and is denoted by A∆B. Index Set. A non-empty set, I,(say) having the property that to each of its element, i ∈ I, there is corresponds a set Ai . Such a set is known as index set. Let A be the collection of sets such that to each member i of I there corresponds a member of Ai ∈ A. Then A is called an index family of sets with index set I. Mathematically, A = {Ai : i ∈ I}. 3

Ordered Pair. Let A and B be two sets. Let a ∈ A and b ∈ B. Then (a, b) called an ordered pair. Cartesian Product of sets. Let A and B be two sets, then the set of all distinct ordered pairs whose first coordinate in an element of A and second coordinate is an element of B is called the cartesian product of A and B, and is denoted by A × B. Mathematically, A × B = {(a, b) : a ∈ A, b ∈ B}. Relation. Let A and B be two sets. Then a relation from A to B is a subset of A × B. Mathematically, R is a relation from A to B iff R ⊆ A × B. Example. Let Z be a set of all integers. The statement ”x is less than y”, where x, y ∈ I determines a relation in I. If we denote this relation by R, then R = {(x, y) : x, y ∈ I, x < y}. Equivalence Relation. Let R be a relation in a set A. Then R is an equivalence relation in A iff • R is reflexive, i.e., ∀a ∈ A, aRa. • R is symmetric, i.e., aRb ⇒ bRa. • R is transitive, i.e., aRb and bRc ⇒ aRc.

0.3

Definition and Properties.

Binary Operations. A binary operation ∗ on a set is a rule that assigns to each ordered pair of elements of the set some element of the set. More precisely, a binary operation on a set S is a binary function from S and S to S, in other words a function f from the Cartesian product S × S to S. Sometimes, the term is used for any binary function. That f takes values in the same set S that provides its arguments is the property of closure. Binary operations are the keystone of algebraic structures studied in abstract algebra: they form part of groups, monoids, semigroups, rings, and more. Many binary operations of interest in both algebra and formal logic are commutative or associative. Many also have identity elements and inverse elements. Typical examples of binary operations are the addition (+) and multiplication (∗) of numbers and matrices as well as composition of 4

functions on a single set. Set A is said to be close under operation ∗, if (a ∗ b) ∈ G for all a, b ∈ G. Binary operations are often written using infix notation such as a∗b, a+b, or a · b rather than by functional notation of the form f (a, b). Sometimes they are even written just by juxtaposition(combination): ab. Powers are usually also written without operator, but with the second argument as superscript. Commutative. A binary operation ∗ is called commutative if and only if a ∗ b = b ∗ a, for all a, b ∈ S. Examples of operations that are not commutative are subtraction (−), division (/), and exponentiation. The well-known binary operations of addition (+) and multiplication (∗) on the real numbers are commutative because a + b = b + a and a ∗ b = b ∗ a for all real numbers. For example 8 + 3 = 11 = 3 + 8 and 5 ∗ 9 = 45 = 9 ∗ 5. An example of a binary operation which is not commutative is exponentiation on the real numbers, because in general ab ± ba , for instance 23 = 2 ∗ 2 ∗ 2 = 8 while 32 = 3 ∗ 3 = 9. Mathematically, A map or binary operation f : A × A → B from a set A to a set B is said to be commutative if, f (x, y) = f (y, x) ∀x, y ∈ A. Every element x belonging to the domain A of a binary operation ∗ commutes with itself. If a particular pair of elements a and b satisfy a ∗ b = b ∗ a under a certain binary operation then it is said that the two elements commute under that operation. A binary operation which is not commutative is called noncommutative. subtraction, division, exponentiation, matrix multiplication and function composition f og are the example of noncommutative binary operations. Example. Matrix multiplication is non-commutative     0 1 1 2 A= and B = ; 2 3 3 4 Then, AB =



3 4 11 16



6= 5



4 7 8 15



= BA.

Associative. A binary operation ∗ is called associative iff (a∗b)∗c = a∗(b∗c) for all a, b, c ∈ S. Important: Remember that changing the order of operations does not involve or permit changing the actual operations themselves by moving the operands around within the expression. Why is it we need associativity to solve 3x=11 in the reals? Well, the inverse of 3 is 1/3 and so 1/3(3x) =11/3 and now we use associativity to rewrite this as (3/3) x = 11/3 etc. Sets that have an associative binary operation are known as semigroups. In many practical applications of studying binary operations on sets it is not unusual to discover they are associative but it is something that cannot be assumed. Indeed, one commonly known operation, the cross product on three dimensional real vectors is not associative. Identity Element. Let ∗ : A × A → A be a binary operation on A. A element e ∈ A is called an identity element for the operation ∗ if e∗a=a =a∗e

∀a ∈ A.

Inverse Element. Let ∗ : A × A → A be a binary operation on A. A element a of a set A is said to be inversible for binary operation ∗ with identity element e if there exists b ∈ A. such that a ∗ b = e = b ∗ a. b = a−1 is said to be inverse of a.

e∗a=a =a∗e

0.4

∀a ∈ A.

Group.

Groupoid. A groupoid(magma) is a basic kind of algebraic structure. Specifically, a magma consists of a set A equipped with a single binary operation A × A → A. A binary operation is closed by definition, but no other axioms are imposed on the operation. Groupoids are often used to capture information about geometrical objects such as manifolds. Groupoids were first developed by Heinrich Brandt in 1926.

6

Example. The algebraic structure (N, +) is a groupoid. Example. The algebraic structure (N, −) is not a groupoid. Semigroup. A semigroup is an algebraic structure consisting of a set S closed under an associative binary operation. In other words, a semigroup is an associative magma. Mathematically, Let (A, ∗) be an algebraic system where ∗ is a binary operation on A. Then (A, ∗) ia called semigroup if the following conditions are satisfied: • ∗ is closed operation, • for every choice of elements a, b, c ∈ G; (a ∗ b) ∗ c = a ∗ (b ∗ c). Example. Let Z+ be the set of positive integers, and + (addition) be the set operation on it. Then (Z+ , +) is a semigroup. Solution. • Closure: If x1 and x2 are integers then x1 + x2 is an positive integer. • Associativity: If x1 , x2 , and x3 are integers, then (x1 + x2 ) + x3 = x1 + (x2 + x3 ). Monoid Let (A, ∗) be an algebraic system, where ∗ is a binary operation on A. Then (A, ∗) ia called monoid if the following conditions are satisfied: • ∗ is closed operation, • for every choice of elements a, b, c ∈ G; (a ∗ b) ∗ c = a ∗ (b ∗ c). • there exists an identity element e ∈ S; such that a ∗ e = a = e ∗ a∀a ∈ S. Example. Let Z be the set of integers, and + (addition) be the set operation on it. Then (Z, +) is a monoid. Solution. 7

• Closure: If x1 and x2 are integers then x1 + x2 is an integer. • Associativity: If x1 , x2 , and x3 are integers, then (x1 + x2 ) + x3 = x1 + (x2 + x3 ). • Identity element: 0 is an integer and for any integer x, 0 + x = a + 0 = x. Group. A semigroup with an identity in which every element has an inverse is termed as group. Mathematically, Let (G, ∗) be an algebraic system, where ∗ is a binary operation on G. Then (G, ∗) ia called group if the following conditions are satisfied: • ∗ is closed operation, • for every choice of elements a, b, c ∈ G; (a ∗ b) ∗ c = a ∗ (b ∗ c). • there exists an identity element e ∈ S; such that a ∗ e = a = e ∗ a∀a ∈ S. • every element of a ∈ S has an inverse in S, i.e. there is an element b ∈ S such that a ∗ b = e = b ∗ a. This element b is usually denoted by a−1 . Example. A familiar group is the group of integers under addition. Let Z be the set of integers, and let ”+” indicate the operation of addition. Then (Z, +) is a group. Solution. • Closure: If x1 and x2 are integers then x1 + x2 is an integer. • Associativity: If x1 , x2 , and x3 are integers, then (x1 + x2 ) + x3 = x1 + (x2 + x3 ). • Identity element: 0 is an integer and for any integer x, 0 + x = a + 0 = x. • Inverse elements: If x is an integer, then the integer −a satisfies the inverse rules: x + (−x) = (−x) + x = 0. 8

Example. Many of the structures investigated in mathematics turn out to be groups. These include familiar number systems, such as the integers, the rational numbers, the real numbers, and the complex numbers under addition, as well as the non-zero rationales, reals, and complex numbers, under multiplication. Other important examples are the group of non-singular matrices under multiplication and the group of invertible functions under composition. Group theory allows for the properties of such structures to be investigated in a general setting.

0.5

Properties of Groups.

Uniqueness of identity. Lemma 0.5. A group G has exactly one identity element ‘e’ satisfying ex = x = xe for all x ∈ G. Proof. Suppose that f is an element of G with property that f x = x for all element x of G. The in particular f = f e = e. similarly one can show that ‘e’ is the only element of G satisfying xe = x for all elements x of G. Uniqueness of inverse. Lemma 0.6. An element x of a group G has exactly one inverse x−1 . Proof. we know from the axioms that the group G contains at least one element x−1 which satisfies xx−1 = e and x−1 x = e. If z is any element of G which satisfy xz = e then z = ez = (x−1 x)z = x−1 (xz) = x−1 e = x−1 . Similarly, if w is any element of G which satisfies wx = e the w = x−1 . Hence we conclude that the inverse x−1 of x is uniquely determined, as required. Lemma 0.7. Let x and y be elements of a group G. Then (xy)−1 = y −1 x−1 . Proof. It follows from the group axioms that (xy)(y −1 x−1 ) = x(y(y −1 x−1 )) = (x(yy −1 )x−1 ) = x(ex−1 ) = xx−1 = e. Similarly, (y −1 x−1 )(xy) = e, and thus (y −1 x−1 ) is the inverse of xy, as required. Note that (x−1 )−1 = x for all elements x of a group G, since x has the

9

properties that characterize the inverse of the inverse x−1 of x. Abelian group. A group G is abelian if its binary operation is commutative. Example. (Z, +) is abelian group. Solution. (Z, +) is a group. As we shown earlier. Also it is abelian since x1 + x2 = x2 + x1 for all x1 , x2 ∈ Z. Order of a group. The order of a group G, usually denoted by | G | or occasionally by o(G), is the number of elements in the set G. If the order is not finite, then the group is an infinite group, denoted | G |= ∞. Example. A set G = {0o , 120o , 240o }, with the binary operation ∗ which is define as the rotation of a line at 120o in the plane, is a group (G, ∗), of order 3. Example. For each positive integer n the set of all nonsingular n × n matrices is a group, where the group operation is matrix multiplication. These groups are not Abelian when n ≥ 2. Integral power of element of a group. Let a ∈ G, and ‘∗′ multiplicative binary operation. Then be closure property a, a ∗ a, a ∗ a ∗ a, . . . , are all element of G. If n is a positive integers, we define an = a∗a∗. . . ∗a to n factors. Obviously an ∈ G. If e is the identity element of G, then we define a0 = e. If n is a positive integers, then −n is a negative integer. a−n = (an )−1 ,

(an )−1 ∈ G.

Thus we have define an , for all n ∈ Z. a−n = (an )−1 = (a ∗ × ∗ a, n times)−1 = (a−1 )(a−1 ) . . . (a−1 ) = (a−1 )n . Integral multiplication of element of a group. Let a ∈ G, and ‘+′ additive binary operation. Then be closure property a, a + a, a + a + a, . . . , are all element of G. 10

In place of a0 we write 0a. Thus we define 0a = e where e is the identity of G. If n is a positive integer, then in place of a−n we write (−n)a. Thus we define (−n)a = −(na), where −(na) denotes the inverse of na ∈ G. order of an element. The order of an element a in a group G is the least positive integer n such that an = e, where an is composition depending on the group operator on a by itself n times. If no such n exists, then the order of a is said to be infinity. Example. A set G = {0o , 120o , 240o }, with the binary operation ∗ which is define as the rotation of a line in the plane, is a group, (G, ∗). Then order of 0o is three, 120o is two and 240o is one.

0.6

Subgroup.

Let (G, ∗) be a group with binary operator ∗, and let H be a non empty subset of G. Then we say that H is a subgroup of G if the following are satisfied: • a ∗ b ∈ H,

∀a, b ∈ H.

• the identity element of G is an element of H. • the inverse of any element of H is itself an element of H. Then H is itself a group. Example. Let G = {1, −1, i, −i} be a set. Then (G, ∗) is a group, where ∗ is multiplication operation. Then H = {1, −1} is a subgroup of G. Example. Let (Z, +) is a group, where + is addition operation. Then (A, +) is a subgroup of G, where A = {2n : n ∈ Z}. Every group of G has a subgroups G improper subgroup itself and {e} trivial subgroup, where e is the identity element of G. A subgroup H of G is said to be proper if H 6= G. Following lemma help us to show that a subset of a group is a subgroup. Lemma 0.8. Let (G, ∗) be a group and then a subset H of a set G is a subgroup of G iff 11

• H is closed under the binary operation of G; • the identity e of G is in H; • for all x ∈ H it is true that x−1 ∈ H also. Proof. Let H be a subgroup of G. Then by the definition of subgroup H is closed under the binary operation, must contains the identity element in H and inverse element of every element of H must be in H. Conversely, Suppose H is a subset of a group G, such that all the conditions given in lemma are true. For being a subgroup of G, associativity must hold along with these given conditions. For this let x1 , x2 , x3 ∈ H, since H ⊆ G, we have x1 , x2 , x3 ∈ G, and we know that x1 ∗ (x2 ∗ x3 ) = (x1 ∗ x2 ) ∗ x3

∀ x1 , x2 , x3 ∈ G.

x1 ∗ (x2 ∗ x3 ) = (x1 ∗ x2 ) ∗ x3

∀ x1 , x2 , x3 ∈ H.

This implies

This completes the proof of theorem. Lemma 0.9. Let (G, ∗) be a group and then a non empty subset H of a set G is a subgroup of G iff a ∗ b−1 ∈ H,

∀a, b ∈ H.

Proof. The condition is necessary. Suppose H is a subgroup of G. Let a ∈ H, b ∈ H. Now each element of H must possess inverse because H is itself a group. i.e., b ∈ H ⇒ b−1 ∈ H. The condition is sufficient. It is given a ∗ b−1 ∈ H,

∀a, b ∈ H.

We have to prove that H is subgroup of G. Existence of Identity. We have a ∈ H, a ∈ H ⇒ a ∗ a−1 ∈ H ⇒ e ∈ H. Thus identity e is an element of H. Existence of Inverse. We have e ∈ H, a ∈ H ⇒ e ∗ a−1 ∈ H ⇒ a−1 ∈ H. 12

Thus each element of H possesses inverse in H. Closure Property. Let b ∈ H ⇒ b−1 ∈ H. Therefore applying the given condition, we have a ∈ H, b−1 ∈ H ⇒ a ∗ (b−1 )−1 ∈ H ⇒ a ∗ b ∈ H. Associativity. The element of H are also element of G. Therefore associativity must hold for H. Lemma 0.10. Let (G, ∗) be a group and let H and K be subgroups of a group G. Then H ∩ K is also a subgroup of G. Proof. The identity element of G belongs to H ∩ K, since it belongs to both the subgroups H and K. If x and y are elements of H ∩ K, implies that x and y elements of both subgroups H and K. Then xy is an element of both subgroups H and K, and therefore xy is an element of H ∩ K. Also the inverse x−1 of an element x of H ∩ K belongs to both subgroups H and K and thus belongs to H ∩ K. More generally, the intersection of any collection of a subgroups of a given group is itself a subgroup of that group. Subgroup generated by x. Let (G, ∗) be a group and x be an element of G. The subgroup generated by ‘x’ is the subgroup consisting of all elements of G that are of the form xn for some integer n.

0.7

Cyclic Group.

A Group (G, ∗) is said to be cyclic group, with generator ′ x′ , if every element of G is of the form xn for some integer n, and denote by < x > . Example. The group Z of integers under addition is a cyclic group generated by 1. 1−3 = (13 )−1 = −3, 1−2 = (12 )−1 = −2, 1−1 = −1, 10 = 0, 11 = 1, 12 = 1+1 = 2, and so on. Example. The group of all rotations of the plane about the origin through an integer multiple of 2π/n radians is a cyclic group of order n for 13

all integers n. This group is generated by an anticlockwise rotation through an angle of 2π/n radians. Cyclic Subgroup. If (G, ∗) be a group and x ∈ G, then H = {xn | n ∈ Z} is a subgroup of G. This group is called cyclic subgroup of G generated by ‘x’. Theorem 0.11. Every cyclic group is abelian. Proof. Let G be a cyclic group and let x be a generator of G so that G =< x >= {xn | n ∈ Z}. If x1 and x2 are any two elements of G, there exist integers r and s such that x1 = xr and x2 = xs . Then x1 ∗ x2 = xr xs = xr+s = xs+r = x2 ∗ x1 . This completes the proof. Lemma 0.12. Let (G, ∗) be a group and H be a subset of G. If H is a finite set, Then (H, ∗) is a subgroup of (G, ∗), if ∗ is a closed operation on H. Proof. Let x be an element of H. If ∗ is a close operation on H, the elements x, x2 , x3 , . . . are all in H. Because H is a finite set, we have xi = xj for some i and j, i < j, i.e., xi = xi ∗ xj−i . It follows that xj−i is the identity of (G, ∗), and it is included in the subset H. If j − i > 1, according to xj−i = x ∗ xj−i−1 , we can conclude that xj−i−1 is inverse of x, and it is included in the subset of H. If j − i = 1, we have xi = xi ∗ x. Thus x must be the identity element and is its own inverse. Consequently, that ∗ is a closed operation on H guarantees that (H, ∗) is a subgroup. Theorem 0.13. Let (G, ∗) be a group and x ∈ G, then H = {xn | n ∈ Z} is a subgroup of G and is the smallest subgroup of G that contains x, that is every subgroup containing ‘x′ contain H.

14

Proof. To prove H be a subgroup of G, we must show that it is close under group operation of G, must have identity element and must contains inverse element of every element in H. Since xr xs = xr+s ∈ Z, ∀xr , xs ∈ Z. Thus H is closed under the group operation. Also x0 = e, so e ∈ H, and for xr ∈ H, x−r ∈ H and xr x−r = e. Hence H satisfied all the necessary and sufficient conditions for being a subgroup. Also every subgroup of G containing ‘x’ must contain H. This implies H be the smallest subgroup of G containing ‘x′ . Lemma 0.14. Let (G, ∗) be a group and x be an element of G. Then the set of all elements of G that are of the form xn for some integer n is a subgroup of G. Proof. Let H = {xn : n ∈ Z}. Then the identity element belongs to H, since it is equal to x0 . The product of two elements of H is itself an element of H, since xm xn = xm+n for al integers m and n. Also the inverse of an element of H is itself an element of H since (xn )−1 = x−n for all integers n. Thus H is a subgroup of G.

0.8

Symmetric Group

Let E n denote n−dimensional Euclidean space, so that E 2 denotes the Euclidean plane, and E 3 denotes three dimensional Euclidean space. Let X be a subset of E n . Then a symmetry of X is a transformation T : E n → E n of E n which sends straight lines to straight lines, preserves all lengths and angles, and has the property that T (X) = X. The collection of all symmetries of a geometric figure is a group, the symmetry group on X, the group operation being that of composition of transformations. Mathematically, Let X be any non empty set. A group arises from the set SX of all one-to-one mapping of X on to X, called the symmetry group on X. this group is usually describe as • SX is the set of all mappings of the non empty set X with itself. • If σ, τ ∈ SX then we define στ to be the composition of the mapping σ and τ. Here we must verify that στ is a mappings of X with itself. Suppose x ∈ X; then as τ is onto, we can find x′′ ∈ X such that x′′ = x. But σ is also onto, so we can find x′ ∈ X such that x′ σ = x′′ .

15

Consequently x′ (στ ) = (x′ σ)τ = x′′ τ = x and hence στ is onto. If x(στ ) = y(στ ), then (xσ)τ = y(στ ) by he definition of composition of mappings; this means τ is one-to-one, that xσ = yσ. This in turn implies, since σ is one-to-one, that x = y. Therefore στ is also one-to-one. Thus composition of mapping is a binary operation in SX . • The identity mapping e : x → x is in SX and is an identity element of SX . • The groupoid (SX , ·) is a semigroup since composition of mappings is associative. • Let σ ∈ SX . Since σ is one-to-one and onto, then it implies σ has an inverse, τ in MX . Now, στ = e = τ σ means σ is an inverse of τ. We know the only elements in MX which have inverse are those which are one-to-one and onto mapping. Therefore τ ∈ SX and τ is the required inverse of σ. It completes the proof. Example. The symmetries of a rectangle that is not a square constitute a group of order 4. This group consists of the identity transformation, reflection in the axis of symmetry joining the midpoints of the shorter side, reflection in the axis of symmetry joining the two longer sides, and rotation though an angle of radian (180o ). If I denote the identity transformation, A and B denote the reflections in the two axes of symmetry, and C denotes the rotation through π radians then A2 = B 2 = C 2 = I, AB = BA = C, AC = CA = B and BC = CB = A. This group is Abelian. Permutation. An element of SX is a permutation of X. In particular case when X = {1, 2, . . . , n}, we write SX = Sn , and Sn is called the symmetric group of degree n. The number of element in Sn is | Sn |= n!, since there are n! different permutation of n elements. Permutation Multiplication. It is natural binary operation, and define on the permutations of a set. Let G be a set, and let σ and τ be the permutations of G so that σ and τ are both one-to-one functions mapping G onto G.

16

Example. Let G = {1, 2, 3, 4, 5} and let σ and τ be two permutation of A. Then     1 2 3 4 5 1 2 3 4 5 σ= , τ= . 4 2 5 3 1 3 5 4 2 1 Then, στ =



1 2 3 4 5 4 2 5 3 1



1 2 3 4 5 3 5 4 2 1



=



1 2 3 4 5 2 5 1 4 3



.

Lemma 0.15. The composite function στ will be a permutation if it is one-to-one and onto G. Proof. Let x1 , x2 , . . . , xn ∈ G. To show composite function στ on G is one-to-one. Let x1 (στ ) = x2 (στ ), then (x1 σ)τ = (x2 σ)τ, and since τ is one-to-one, we know that x1 σ = x2 σ. Since σ is also one-toone, this implies that x1 = x2 . Hence στ is one-to-one. To show thatστ is onto A, let x ∈ A. Since τ is onto A, there exists x′ ∈ A such that x′ τ = x. Since σ is onto A, there exists x′′ ∈ A such that x′ = x′′ σ. Then x = x′ τ = (x′′ σ)τ = x′′ (στ ), so στ is onto G. Equality of Two Permutations. Two permutations f and g of degree n are said to be equal if we have f (a) = g(a) ∀a ∈ SX . Example. Let     1 2 3 4 3 2 4 1 f= and g = 2 3 4 1 4 3 1 2 are two permutations of degree 4, then we have f = g. Hence we see that both f (a) = g(a) ∀a ∈ {1, 2, 3, 4}. Theorem 0.16. Let G be a non empty set, and let SG be a collection of all permutations of G. Then SG is a group under permutation multiplication. Proof. To show that SG is a group. We have to show that SG satisfies the three axioms of group. Existence of identity and inverse is very simply to prove. Now we have to show that function composition is associative, i.e., (στ )µ = σ(τ µ), 17

for permutations σ, τ and µ of G. for this we have to show that each composite function maps each x ∈ G into the same image in G, i.e., x[(στ )µ] = x[σ(τ µ)]

∀x ∈ G.

We have x[(στ )µ] = x[(στ )]µ = [(xσ)τ ]µ = x[σ(τ µ). Thus, (στ )µ and σ(τ µ) map each x ∈ G into the same element [(aσ)τ ]µ and hence the same permutation. Cycles and Products of Cycles. A permutation σ of a set G is a cycle of length n if there exist x1 , x2 , . . . , xn ∈ G such that x1 → x2 , x2 → x3 , . . . , xn → x1 and x → x for x ∈ G but x ∈ / {x1 , x2 , . . . , xn }. Example.   1 2 5 3 4 6 f= 2 4 5 1 6 3 it can be represented by the cycle (1 2 4 3). Note. A cycle does not change by changing the place of its elements provided their cyclic order is not changed. The cycles in a collection of cycles are disjoint if there is no common between any two cycles. Multiplication of disjoint cycles is commutative. Note that neither every permutation is not a cycle nor is the product of any two cycle is necessarily a cycle. In general, a cycle of length one is denoted by identity element, and a cycle of length two is called a transposition. Inverse of a permutation. Inverse of a cyclic permutation. The inverse of the cycle a = (x1 , x2 , . . . , xn ) is the cycle b = (xn , xn−1 , . . . , x1 ), since xi (ab) = (xi a)b = xi+1 b = xi ∀i 6= n, while xn (ab) = (xn a)b = x1 b = xn . Inver of a product of cyclic permutation. If f and g are any two cycles, then we have (f g)−1 = g−1 f −1 .

18

Also, if f, g, h are three cycles, then (f gh)−1 = h−1 g−1 f −1 . If f and g are disjoint cycles then (gf )−1 = (f g)−1 = f −1 g−1 . Example. [(1 2 3)(4 5)(2 6)] = (2 6)−1 (4 5)−1 (1 2 3)−1 = (6 2)(5 4)(3 2 1). Example. [(1 3 5)(2 4)]−1 = (1 3 5)−1 (2 4)−1 = (5 3 1)(4 2). Even or Odd Permutation. A permutation of a finite set is even and odd according to whether it can be expressed as the product of an even number of transposition or the product of an odd number of transpositions, respectively. Alternating Group. The subgroup of Sn consisting of the even permutations of n letters is the alternating group An on n letters.

0.9

Cosets and Lagrange’s Theorem.

Let (G, ∗) be a group and H be a subgroup of G. A left coset of H in G is a subset of G that is of the form xH, where x ∈ G and xH = {y ∈ G : y = xh for some h ∈ H}. Similarly a right coset of H in G is a subset of G that is of the form Hx, where x ∈ G and Hx = {y ∈ G : y = hx for some h ∈ H}. Note that a subgroup H of a group G is itself a left coset of H in G. Lemma 0.17. Let (G, ∗) be a group and H be a subgroup of G. Then the left cosets of H in G have the following properties: • x ∈ xH for all x ∈ G; • if x and y are elements of G, and if y = xa for some a ∈ H, then xH = yH; • if x and y are elements of G, and if xH ∩ yH is non empty then xH = yH. 19

Proof. Let x ∈ G. Then x = xe, where e is the identity element of G. Also, e ∈ H. It follows that x ∈ xH. This prove the first condition. Let x, y ∈ G, where y = xa for some a ∈ H. Then yh = (xa)h = x(ah) and xh = y(a−1 h) for all h ∈ H. Moreover ah ∈ H and a−1 h ∈ H for all h ∈ H, since H is a subgroup of G. It follows that yH ⊂ xH and xH ⊂ yH, and hence xH = yH. This completes the prove of second condition. Finally suppose that xH ∩ yH is a non empty for some elements x and y of G. Let z be an element of xH ∩ yH. Then z = xa for some a ∈ H, and z = yb for some b ∈ H. It follows from second condition that zH = xH and zH = yH. therefore xH = yH. This completes the proof. Lemma 0.18. Let (G, ∗) be a group and H be a subset of G. Then each left coset of H in G has the same number of elements as H. Proof. Let H = {h1 , h2 , . . . , hn }, where h1 , h2 , . . . , hn are distinct, and let x be an element of G. Then the left coset xH consists of the elements xhj for j = 1, 2 . . . , n. Suppose that j and k are integers between 1 and n for which xhj = xhk . Then hj = x−1 (xhj ) = x−1 (xhk ) = hk , and thus j = k, since h1 , h2 , . . . , hn are distinct. It follows that the elements xh1 , xh2 , . . . , xhn are distinct. We conclude that the subgroup H and the left coset xH both have n elements, as required. Lemma 0.19. Let xH and yH be two cosets of H. Either xH and yH are disjoint or they are identical. Proof. Let H be a subgroup of a group G. Let xH and yH are two left cosets of H in G. Let xH and yH are not disjoint, and have f as a common element, i.e., there exists h1 and h2 in H such that f = xh1 = yh2 . Then xh1 = xh2 −1 ⇒ xh1 h−1 1 = yh2 h1

⇒ xe = y(h2 h−1 1 ) ⇒ x = y(h2 h−1 1 )

−1 Since H be a subgroup, therefore h2 h−1 1 ∈ H. Let h2 h1 = h3 . Then x = yh3 . Now xH = yh3 H = y(h3 H) = yH. Since h3 ∈ H. This implies h3 H = H. therefore left cosets are identical if they are not disjoint. In the similar way we can show that any two right coset Hy and Hx are identical if they are not disjoint.

20

Lemma 0.20. Let (G, ∗) be a group and H be a subgroup of G. Let a, b ∈ G. Then a ∈ Hb ⇔ Ha = Hb and a ∈ bH ⇔ aH = bH. Proof. Let a ∈ Hb, this implies ab−1 ∈ Hbb−1 ⇒ ab−1 ∈ H ⇒ Hab−1 = H ⇒ Hab−1 b = Hb ⇒ Ha = Hb.

Conversely, let Ha = Hb. If a ∈ Ha, therefore a ∈ Hb. Theorem 0.21. Let H be any subgroup of G and let h ∈ H. Then Hh = H = hH. Proof. Let h ∈ H, then to prove Hh = H. Suppose h′ is an arbitrary element of H. Then h′ h is an arbitrary element of Hh. Since H is a subgroup, we have h′ ∈ H, h ∈ H ⇒ h′ h ∈ H, By closure property. Thus every element of Hh is also an element of H. Hence Hh ⊆ H. Again, h′ = h′ (h−1 h) = (h′ h−1 )h ∈ Hh. Since h ∈ H ⇒ h−1 ∈ H and h′ ∈ H, h−1 ∈ H ⇒ h′ h−1 ∈ H. Thus every element h′ of H is also an element of Hh. Hence H ⊆ Hh. Hence Hh = H. In the very similar way we can prove H = hH, and hence Hh = H = hH. Theorem 0.22. Lagrange Theorem Let G be a finite group, and let H b a subgroup of G. Then the order of H divides the order of G. Proof. Let G be a group of finite order n. Let H be a subgroup of G and let o(H) = m. Suppose h1 , h2 , . . . , hm are the m members of H. Let a ∈ G. Then Ha is the right coset of H in G and we have Ha = {h1 a, h2 a, . . . , hm a}

21

Ha has m distinct members, since hi a = hj a ⇒ hi = hj . Therefore each right coset of H in G has m distinct members. Also any two right cosets of H in G are disjoint. Since G is a finite group, the number of distinct right cosets of H in G will be finite, say, equal to k. Then union of these k distinct right cosets of H in G is equal to G. Thus, if Ha1 , Ha2 , . . . , Hak are k distinct right cosets of H in G. Then G = Ha1 ∪ Ha2 ∪ . . . ∪ Hak ⇒ o(G) = km ⇒ n = km n ⇒ o(H) is a divisor of o(G). ⇒k= m Index. Let G be a group, and let H be a subgroup of G. If the number of left cosets of H in G is finite then the number of such cosets is referred as the index of H in G, denoted by [G : H]. The proof of Lagrange’s Theorem shows that the index [G : H] of a subgroup H of a finite group G is given be [G : H] =| G | \ | H | . Corollary 0.23. Any finite group of prime order is cyclic. Proof. Let G be a group of prime order, and let x become element of G that is not the identity element. Then the order of x is greater than one and divides the order of G. But then the order of x must be equal to the order of G, since the latter i a prime number. Thus G is a cyclic group generated by x.

0.10

Homomorphism.

A homomorphism f : G → K from a group (G, ∗) to a group (K, ∗) is a function with property that f (x1 ∗ x2 ) = f (x1 )f (x2 ) for all x1 , x2 ∈ G. Example. Let q be an integer. The function from the group Z of integers to itself that sends each integer n to qn is a homomorphism. Example. Identity mapping f : G → G, is a homomorphism. Example. Let x be an element of a group G. The function that send each integer n to the element xn is a homomorphism from the group Z of integers to G, since xm+n = xm xn for all integers m and n.

22

Kernel. The kernel, ker f of the homomorphism f : G → K is the set of all elements of G that mapped by f onto the identity element of K. ker f = {x ∈ G : f (x) = e′ , where e′ be the identity element of K..} Example. Let the group operation on the set {+1, −1} be the multiplication, and let f : Z → {+1, −1} be the homomorphism that sand each integer n to (−1)n . then the kernel of homomorphism f is the subgroup of Z consisting of all even numbers.

0.11

Isomorphism.

An algebraic systems (G, ∗) is isomorphic to the algebraic systems (K, o), if one can obtain (G, ∗) from (K, o) by renaming the elements and/or the operation in (K, o.) Mathematically, An isomorphism f : G → K between groups G and K is a one-to-one function f mapping from G on to K, such that for all x and y in G, f (x ∗ y) = f (x)of (y). The groups G and K are the isomorphic. The usual notation for isomorphism is ≃ . Two groups G and K are isomorphic if there exists an isomorphism mapping G on to K. Example. Let R be the group of real numbers with the operation of addition, and let R+ be the group of strictly positive real numbers with the operation of multiplication. the function exp : R → R+ that sends each real number x to the positive real number ex is an isomorphism: it is both a homomorphism of groups and a bijection. The inverse of this isomorphism is the function log : R+ → R that sends each strictly positive real number to its natural logarithm. Lemma 0.24. Let f : G → K is an isomorphism of G with K, and e is the identity of G, then the f -image of an element a ∈ G is the inverse of the f -image of a i.e., f (a−1 ) = [f (a)]−1 . Proof. Let e be the identity element of G and e′ be the identity element of K. Then f (e) = e′ . Now let a ∈ G, then a−1 ∈ G and aa−1 = e ∈ G. We have e′ = f (e) = f (aa−1 ) = f (a)f (a−1 ). 23

Therefore f (a−1 ) is the inverse of f (a) in K. Thus f (a−1 ) = [f (a)]−1 . Lemma 0.25. Let f : G → K is an isomorphism of G with K. Then the order of an element a ∈ G is equal to the order of its f -image f (a). Proof. Let e be the identity element of G and e′ be the identity element of K. Let order of an element a be finite and let it is equal to n, and let order of f (a) is m. Then an = e ⇒ f (an ) = f (e) ⇒ f (a . . . a, n times) = f (e) ⇒ f (a) . . . f (a), n times = f (e) ⇒ [f (a)]n = f (e) ⇒ o(f (a)) ≤ n.

(1)

Now, [f (a)]m = f (e) ⇒ f (a) . . . f (a), m times = f (e) ⇒ f (a . . . a, m times) = f (e) ⇒ f (am ) = f (e) ⇒ am = e ⇒ o(a) ≤ m.

(2)

From eq.(1) and eq.(2) we have m = n. Lemma 0.26. If f : G → K is an isomorphism of G with K, and e is the identity of G, then ef is the identity in K. Also, a−1 f = (af )−1

∀a ∈ G.

Proof. Let x′ ∈ K. Since f is onto, there is x ∈ G such that xf = x′ . Then x′ = xf = (ex)f = (ef )(xf ) = (ef )x′ . Similarly, x′ = xf = (xe)f = (xf )(ef ) = x′ (ef ). 24

Thus for every x′ ∈ K, we have (ef )x′ = x′ x′ (ef ), so ef is the identity of K. Also for a ∈ G, we have ef = (a−1 a)f = (a−1 f )(af ). Similarly, ef = (aa−1 )f = (af )(a−1 f ). Thus a−1 f = (af )−1 .

0.12

Automorphism and Normal Subgroup.

Automorphism. An automorphism is an isomorphism mapping a group onto itself. Inner Automorphism. For each x ∈ G, the mapping ix : G → G given by yix = x−1 yx is an automorphism of G, the inner automorphism of G under conjugation by G. Let A and B be subsets of a group G. then product AB of the sets A and B is defined as AB = {xy : x ∈ A, y ∈ B}. We denote {x}A and A{x} by xA and Ax, for all elements x of G and subsets A of G. The Associative Law for multiplication of elements G ensures that (AB)C = A(BC) for all subsets A, B and C of G. We can therefore use the notation ABC to denote the products (AB)C and A(BC); and we can use analogous notation to denote the product of four or more subsets of G. If A, B and C are subsets of a group G, and if A ⊂ B then clearly AC ⊂ BC and CA ⊂ C. Note that if H is a subgroup of group G and if x is an element of G then xH is the left coset of H in G that contains the element x. Similarly Hx is the right coset of H in G that contains the element x. If H is a subgroup of G then HH = H. Indeed HH ⊂ H, since the product of two elements of a subgroup H is itself an element of H. Also H ⊂ HH since h = eh for any element h of H, where e, the identity element of G, belongs to H. Normal Subgroup. A subgroup N of a group G is said to be a normal subgroup of G if xnx−1 ∈ N for all n ∈ N and x ∈ G. 25

The notation ‘N ⊳ G’ signifies ‘N is a normal subgroup of G’. A non trivial group G is said to be simple if the only normal subgroups of G are the whole of G and the trivial subgroup {e} whose only element is the identity element e of G. Lemma 0.27. Every subgroup of an abelian group is a normal subgroup. Proof. Let N be a subgroup of an abelian group G. Then xnx−1 = (xn)x−1 = (nx)x−1 = n(xx−1 ) = ne = n ∀n ∈ N, x ∈ G. Thus x ∈ G, h ∈ N ⇒ xhx−1 ∈ N. Hence N is normal subgroup. Example. Let S3 be the group of permutations of the set {1, 2, 3}, and let H be the subgroup of S3 consisting of the identity permutation and the transposition (12). Then H is not normal in G, since (23)−1 (12)(23) = (23)(12)(23) = (13) and (13) does not belong to the subgroup H. Proposition 0.28. A subgroup N of a group G is a normal subgroup of G iff xN x−1 = N for all elements x of G. Proof. Suppose that N is a normal subgroup of G. Let x be an element of G. Then xN x−1 ⊂ N. On replacing x by x−1 we get x−1 N x ⊂ N, and thus N = x(x−1 N x)x−1 ⊂ xN x−1 . This each of the sets N and xN x−1 is contained in the order, and therefore xN x−1 = N. Conversely if N is a subgroup of G with the property that xN x−1 = N for all x ∈ G, then it follows immediately from the definition of a normal subgroup that N is a normal subgroup of G. Proposition 0.29. Intersection of any two normal subgroups of a group is again an normal subgroup. Proof. Let H and K be two normal subgroups of a group G. This implies H ∩ K is also a subgroup of G. Let x ∈ G and n ∈ H ∩ K. Then we haven ∈ H, n ∈ K. Since H is an normal subgroup of G. Therefore x ∈ G, n ∈ H ⇒ xnx−1 ∈ H. Similarly, we can show xnx−1 ∈ K. Thus xnx−1 ∈ H ∩ K. Hence H ∩ K is aa normal subgroup.

26

Proposition 0.30. A subgroup H of G is normal iff xHx−1 = H, ∀x ∈ G. Proof. Let xHx−1 = H, ∀x ∈ G. Then xHx−1 ⊆ H, ∀x ∈ G. Therefore H is a normal subgroup of G. Conversely, Let H be an normal subgroup of G. Then xHx−1 ⊆ H, ∀x ∈ G.

(3)

Also x ∈ G ⇒ x−1 ∈ G. Therefore x−1 H(x−1 )−1 ⊂ H, ∀x ∈ G ⇒ x−1 Hx ⊂ H, ∀x ∈ G ⇒ x(x−1 Hx)x−1 ⊂ xHx−1 , ∀x ∈ G ⇒ H ⊂ xHx−1 , ∀x ∈ G

(4)

From equ.(3) and equ.(4), we have xHx−1 = H, ∀x ∈ G. Conjugate. Two subgroups H and K of a group G are conjugate if H = a−1 Ka for some a ∈ G, i.e., if one is mapped onto the other by some inner automorphism of G. Lemma 0.31. Let G and K be groups, and let f : G → K be a homomorphism from G to K. Then the kernel ker f of f is a normal subgroup of G. Proof. Let x and y be elements of ker f. Then f (x)eK and f (y) = eK , where eK denotes the identity element of K. But then f (xy) = f (x)f (y) = eK eK = eK . Thus xy belongs to kerf. Also f (x−1 ) = f (x)−1 = e−1 K eK . Thus −1 x belongs to ker f. We conclude that kar f is a subgroup of K. Moreover ker f is a normal subgroup of G, for if k ∈ G and x ∈ ker f then f (kxk−1 ) = f (k)f (x)f (k)−1 = f (k)f (k−1 ) = eK . Quotient Homomorphism. If N is a normal subgroup of some group G then N is the kernel of the quotient homomorphism f : G → G/N tat sends x ∈ G to the coset xN. It follows therefore that a subset of a group G is normal subgroup of G iff it the kernel of some homomorphism. Proposition 0.32. Let G and K be subgroups, let f : G → K be a homomorphism from G to K, and let N be a normal subgroup of G. Suppose that N ⊂ ker f. The the homomorphism f : G → K induces a homomorphism fˆ : G/N → K sending xN ∈ G/N to f (x). Moreover fˆ : G/N → K is injective iff N = ker f. 27

Proof. Let x and y be elements of G. Now xN = yN iff x−1 y ∈ N. Also f (x) = f (y) iff x−1 y ∈ ker f. Thus if N ⊂ ker f then f (x) = f (y) whenever xN = yN, and thus f : G → K induces a well define function since fˆ : G/N → K sending xN ∈ G/N to f (x). This function is a homomorphism, ˆ )f (yN ˆ ). since fˆ((xN )(yN )) = fˆ(xyN ) = f (xy) = f (x)f (y) = f (xN Suppose now that N = ker f. Then f (x) = f (y) iff xN = yN. Thus the homomorphism fˆ : G/N → K is injective. Conversely if fˆ : G/N → K is injective then N must be the kernel of f. Corollary 0.33. Let (G, o) and (K, ) be groups, and let f : G → K be a homomorphism. Then f (G) ∼ = C/ker f. Lemma 0.34. Let f : G → K be a homomorphism. Then f (eG ) = eK , where eG and eK denotes the identity elements of groups G and K. Also f (x−1 ) = f (x)−1 for all elements of G. Proof. Let z = f (eG ). Then z 2 = f (eG )f (eG ) = f (eG eG ) = f (eG ) = z. The result that f (eG ) = eK now follows from the fact that an element z of K satisfied z 2 = z iff z is the identity element of K. Let x be an element of G. The element f (x−1 ) satisfies f (x)f (x−1 ) = f (xx−1 ) = f (eG ) = eK , and similarly f (x−1 )f (x)eK . The Uniqueness of the inverse of f (x) now ensures that f (x−1 ) = f (x)−1 . Lemma 0.35. Let (G, ∗) be a group, let H be a subgroup of G, and let N be a normal subgroup of G. The the set HN is a subgroup of G, where HN = {hn : h ∈ H, n ∈ N }. Proof. The set HN clearly contains the identity element of G. Let x and y be elements of HN. We have to show that xy and x−1 belongs to HN. Now x = hu and y = kv for some elements h and k of H and for some elements u, v ∈ N. Then xy = (hk)(k−1 ukv). But k−1 uk ∈ N, since N is normal. It follows that (k−1 ukv) ∈ N, since N is a subgroup and (k−1 ukv) is the product of the elements (k−1 uk and v of N. Also hk ∈ H. It follows that xy ∈ HN. We must also show that x−1 ∈ HN. Now x−1 = u−1 h−1 = h−1 (hu−1 h−1 ). Also h−1 ∈ H, since H is a subgroup of G, and hu−1 h−1 ∈ N, since N is a normal subgroup of G, as required. Theorem 0.36. (First Isomorphism Theorem) Let (G, ∗) be a group, let H be a subgroup of G, and let N be a normal subgroup of G. Then HN ∼ H . = N N ∩H 28

Proof. Every element of HN/N is a coset of N, i.e., of the form hN for some h ∈ H. Thus if f (h) = hN ∀h ∈ H then f : H → HN ?N is a surjective homomorphism, and ker f = N ∩ H. But f (H) ∼ = H/karf. Therefore HN/N ∼ H/(N ∩ H). = Theorem 0.37. (Second Isomorphism Theorem) let M and N be normal subgroups of a group G, where M ⊂ N. Then G ∼ G/M . = N N/M Proof. There is a well-define homomorphism f : G/M → G/N that sends xM to xN for all x ∈ G. Moreover the homomorphism f is surjective, and kerf = N/M. But f (G/M ) ∼ = (G/M )/kerf. Therefore G/N is isomorphic to (G/M )/(N/M ).

29