isomorphism 중에는 (헷갈리게도) group G에서 자기자신으로 대응되는 isomorphism도 있을 수 있다.

φ: G → G

이러한 isomorphism을 'automorphism of G' 라고 한다. 당연히 identity map은 automorphism이다. 다른 예를 들면, group G = {1, x, x²} 를 order 3짜리 cyclic group이라고 하자(x³ = 1). 그러면 x와 x²을 서로 교환하는(interchange) 치환(transposition)은 automorphism of G 이다(φ 를 해당 치환으로 두는 것이다).

1 ⇝ 1
x ⇝ x²
x² ⇝ x

여기서 x² 도 x와 마찬가지로 이 group의 order 3인 엘리먼트 중 하나이다. x²를 y라고 부른다면, y에 의해 생성(generate)된 cyclic subgroup {1, y, y²} 을 만들 수 있다(y² = x).

이번엔 conjugation을 살펴보자. b ∈ G 를 고정된 엘리먼트라고 하자. 여기서 conjugation by b 란 G 에서 자기 자신으로 대응되는 φ 매핑을 아래와 같이 정의한 것이다.

φ(x) = bxb^-1

위 매핑은 automorphism이다. 우선 아래와 같이 group들 간 law of composition이 compatible 하다.

φ(xy) = bxyb^-1 = bxb^-1byb^-1 = φ(x)φ(y)

그리고 이 매핑은 inverse function이 있기 때문에 일대일 대응 매핑이다. inverse function은 바로 conjugation by b^-1 이다.

만일 이 group이 abelian 이라면(commutative 한 것), conjugation은 identity map: bab^-1 = abb^-1 = a 이 된다. 다시 말해서 noncommutative group은 자명하지 않은(nontrivial) conjugation을 갖는다는 것이다(nontrivial automorphisim).

bab^-1 의 결과 엘리먼트를 conjugate of a by b 라고 부른다. 그리고 group G에서 두 엘리먼트 a, a'가 a' = bab^-1 라면, 이 둘을 conjugate 라고 부른다.

a의 conjugate는 a와 (order가 같은 등) 매우 비슷하게 동작한다. conjugate는 a를 automorphism에 의해 사상시킨(image)것이기 때문이다.

끝으로 conjugation을 이용하면 재미난 동작을 만들어 낼 수 있다. a'을 bab^-1 라고 하면 아래와 같이 된다.

ba = a'b

ba(b^-1b) 이기 때문이다. 위 식을 통해 conjugation by b가 b를 다른 편으로 옮길 때 a가 어떻게 변하느냐를 나타내는 것이라고 생각할 수도 있다(b의 위치가 바뀌고 a는 a'으로 변화함).

앞서 group G와 G'간의 대응(correspondence)관계를 아래와 같이 표현했다.

G ↔ G'

이와 같은 양방향 대응관계를 단방향으로 표현하기 위해 함수 표현식을 사용하거나 맵(map) 표현식을 사용할 수 있다. 맵 표현식을 사용하면 map φ: G → G' 이렇게 된다. 즉, 'G 에서 G'으로 가는 isomorophism φ'는 law of composition을 호환하는 일대일대응 맵(bijective map) 이 되겠다. law of composition을 호환한다는 말의 의미를 수식으로 쓰기 위해 대응관계 표현을 φ 함수를 사용하여 아래와 같이 쓸 수 있다.

φ(ab) = φ(a)φ(b), for all a, b ∈ G

위 식에서 우변은 group G에서 a와 b를 곱하여 φ 함수를 적용한다는 의미이고, 좌변은 이전에 a', b'을 나타내던 φ(a)와 φ(b) 를 G'에서 곱한다는 의미이다. group에서 곱한다는 말은 해당 group의 law of composition을 써서 composition 한다고 생각하면 된다. 이걸 다시 아래와 같이 쓸 수도 있다.

(ab)' = a'b'

물론 domain(정의역)과 range(치역)를 바꾸어도 된다. 즉, φ^-1: G' → G 이것도 성립한다.

다시 정리하면, 두 group G와 G'간에 φ G → G' 대응을 갖는 isomorphism이 존재한다면 이 둘을 isomorphic 하다고 한다. 두 group간 isomorphic을 나타내기 위해서 ≈ 기호를 사용할 것이다. 위키피디아 페이지 에서는 ≅ 기호를 사용하는데 책에서는 ≈ 기호를 쓴다.

G ≈ G' means G is isomorphic to G'

서로 다른 law of composition을 갖는 group간의 isomorphism에 대한 예를 살펴보자. infinite cyclic group C = {..., a^-2, a^-1, 1, a, a², ...} 는 아래 매핑에 의하여 group ℤ⁺와 isomorphism 관계를 이루게 된다.

φ: ℤ⁺ → C

여기서 φ(n) = aⁿ 이다.

주목해야하는 점은 law of composition이 domain(정의역)에서는 덧셈이고 range(치역)에서는 곱셈이라는 것이다. 이런 경우 isomorphism group 들을 φ 함수의 관계식으로 나타내면 위에서 본 것과는 달리 φ(m + n) = φ(m)φ(m) 또는 a^m+n = a^maⁿ 이렇게 된다.

이번에는 cyclic group간의 예를 들어보자. 두 cyclic group이 각각 엘리먼트 x와 y로 생성(generate)되었고, 둘 다 같은 order를 갖는다고 해 보자. 그러면 xⁱ에서 yⁱ로 대응되는 매핑은 isomorphism 이다. 즉, 같은 order를 갖는 두 cyclic group은 서로 isomorphic 이다.

다시 또 정리하자면, 두 group G와 G'이 isomorphic 하다는 것은 φ: G → G' 의 대응 관계를 갖는 isomorphism, 즉 law of composition을 호환하는 일대일대응 매핑(bijective map)이 있을 경우이다.

그리고 어떤 group G에 isomorphic한 group들을 모아서 isomorphism class 라고 부른다. isomorphism class 안의 어떤 두 group은 서로 isomorphic 하다.

Isomorphism은 우리말로 하면 '동형사상'이다. 위키피디아 한국어 페이지에서는 '서로 구조가 같은 두 대상 사이에, 모든 구조를 보존하는 사상이다'라고 설명한다. 이게 무슨 말인가?

두 group G와 G'이 있을 때 G의 모든 group 속성을 G'이 따를 경우 이 둘을 isomorphic하다 라고 한다.

예를 들어 group G가 아래와 같은 형태의 실수 행렬일 경우,

1	x
	1

위와 같은 형태의 행렬들은 GL₂(ℝ)의 subgroup 이며, 이러한 행렬 두 개를 곱하면 아래와 같이 우상단(1,2) 성분들이 더해지는 형태가 된다.

1	x
	1

 

1	y
	1

  =

1	(x + y)
	1

그래서 이런 형태의 행렬들을 서로 곱할 때에는 자연스럽게 우상단 entry만 보게 된다. 이 상황을 가리켜 group G가 실수 덧셈 group(additive group of real numbers)에 isomorphic 하다고 한다.

위의 예제를 보아도 isomorphism을 명확하게 하기가 어렵다. 다시 정리하면, 두 group의 모든 엘리먼트들을 일대일 대응(bijective correspondence)으로 연결시키는 것이다. 여기서 같은 group의 엘리먼트들을 composition하여 나온 결과 엘리먼트도 역시 다른 group의 대응되는 엘리먼트를 composition한 결과 엘리먼트와 일대일 대응되어야 한다(compatible with the laws of composition). 헉헉.

G ↔ G'

즉, G와 G'은 다음의 속성을 갖는다: a, b ∈ G 가 a', b' ∈ G' 에 대응(correspond)된다면, G에서 composition된 ab도 역시 G'에서 composition된 a'b'에 대응(correspond)된다. 이 내용을 만족할경우 한 group의 모든 속성은 (대응을 통해) 다른 group으로 이어질 수 있다.

예를 들어 G의 identity 엘리먼트도 G'으로 대응된다. group G identity 엘리먼트를 1이라고 하고 이게 group G'의 엘리먼트 ϵ' 에 대응된다고 하자. 그리고 G'의 임의의 엘리먼트 a'은 G의 엘리먼트 a에서 대응된다고 해 보자. 위에서 내린 가정에 의하면 composition한 결과도 똑같이 대응되어야 한다. group G에서 1a = a 이므로, group G'에서는 ϵ'a' = a' 이 되어야 한다. 따라서 ϵ' = 1' 이 되는 것이다.

다른 예를 들면, 서로 isomorphic한 group들 간에는 대응되는 엘리먼트의 order 또한 같다. group G에서 a가 group G'의 a'에 대응된다면, a^r = 1 이면 역시 a'^r = 1 이게 된다.

이렇게 서로 isomorphic한 group들이 같은 group 속성을 갖기 때문에 종종 이들을 같이 묶어서 구별하기도 한다. 예를 들어 한 symmetric group S_n이 어떤 permutation matrix group (GL_n(ℝ)의 subgroup)과 서로 isomorphic 하다면, 경우에 따라서 이 둘을 서로 구별 않고(blur the distinction) 사용할 수 있다.

Cyclic subgroup 역시 group 챕터에서 자주 등장하는 개념이다.

group G의 임의의 엘리먼트 x를 가지고 cyclic subgroup 이란 것을 생성(generate)해낼 수 있다. 여기서는 곱셈을 law of composition 으로 표기할 것이다. x에 의해 생성되는 cyclic subgroup H는 아래와 같이 x를 거듭 composition한 것이다.

H = {..., x^-2, x^-1, 1, x, x², ...}

이것은 x를 포함하는 가장 작은 G의 subgroup 이 된다. 그리고 또한 주목해야하는 내용은 xⁿ이 group G의 엘리먼트 중 하나를 나타낸다는 것이다.

x를 거듭 composition 하다보면 반복이 일어날 수도 있다. 예를 들어 x = 1 이면 모든 엘리먼트들은 1이 된다. 반복성을 가지고 경우를 나누어 보면 1) 모든 x의 거듭 composition이 다를 경우와 2) 그렇지 않은 경우로 나뉜다. 전자의 경우 group H를 infinite cyclic 이라고 부른다.

반복성을 띌 경우를 생각해 보자. 예를 들어 xⁿ = x^m 일 경우 n > m 이라면 x^{n - m} = 1 이 된다. 이는 곧 x의 0이 아닌 거듭제곱이 1이 된다는 뜻이다. 이와 관련하여 아래 Lemma를 살펴보자.

Lemma. xⁿ = 1 인 n 으로 이루어진 집합 S는 ℤ⁺의 subgroup 이다.

Proof. x^m = 1 이고 xⁿ = 1 이라면 x^m+n = x^mxⁿ = 1 이 된다. 따라서 m, n ∈ S 이라면 m + n ∈ S 이다. 이는 subgroup의 첫 번째 axiom(Closure: If a ∈ H and b ∈ H, then ab ∈ H)을 만족한다. 또한 x⁰ = 1 이기 때문에 두 번째 axiom(Identity: 1 ∈ H)도 만족한다. 마지막으로 xⁿ = 1 이라면 x^-n = xⁿx^-n = x⁰ = 1 이다. 따라서 n ∈ S 라면 또한 −n ∈ 이 된다(끝).

위의 Lemma와 ℤ⁺의 subgroup이 bℤ 의 형태를 갖는다는 Proposition을 상기하면서 S = mℤ 인 group을 만들 수 있다. 여기서 m은 x^m = 1 인 가장 작은 양의 정수이다. S에서 m 개의 엘리먼트들 1,x,...,x^m-1 은 모두 서로 다르다. 그리고 x의 거듭 composition인 xⁿ 들 중에서는 서로 같은 것들이 존재한다. 나머지(remainder) 표현식으로 정리하면 n = mq + r 이 되는데 나머지(reminder) r은 나눔수인 m 보다 작다. 이걸 다시 지수표현식으로 정리하면, xⁿ = (x^m)^qx^r = x^r 이 된다(x^m = 1). 따라서 group H는 아래와 같이 m개의 엘리먼트로 구성된다.

H = {1, x, ... , x^{m - 1}}, these posers are distinct, and x^m = 1

위와 같은 group을 'cyclic group of order m' 이라고 부른다.

어떤 group G의 order는 그러니까 엘리먼트의 갯수이다. order는 아래와 같이 절대값을 쓸때와 같은 형식으로도 표기한다.

| G | = number of elements of G

order는 물론 무한대가 될 수도 있다.

그리고 어떤 group의 엘리먼트가 order m을 갖는다는 말은 그 엘리먼트가 생성(generate)하는 cyclic subgroup이 order m 을 갖는다는 뜻이다. 그러면 m은 x^m = 1 인 가장 작은 양의 정수가 된다.

예를 들어 행렬

1	1
-1	0

  은 GL₂(ℝ) 에서 order 6인 엘리먼트이다. 즉, 이 행렬이 생성(generate)하는 cyclic subgroup은 order 6을 갖는다. 그러나 행렬

1	1
0	1

  은 무한대의 order인 엘리먼트이다. 왜냐하면 아래와 같이 거듭 composition이 계속해서 다른 값을 생성해내기 때문이다.

n power of

1	1
0	1

  =

1	n
0	1

상황은 이렇다. GLKMatrix4와 glUniformMatrix4fv()를 사용하려 한다. 문제는 GLKMatrix4가 Float 배열로 이루어진 게 아니라 16개짜리 튜플로 이루어져 있다는 점이다. 배열로 된 경우 자동으로 C포인터로 변환되어 C API에다 사용할 수 있지만 튜플일 경우 그럴 수가 없다. 참고로 여기를 보면 과거에는 GLKMatrix4의 내부 데이터가 튜플이 아니라 배열이었던 것 같다. 참고로 현재 내가 사용중인 Swift 버전은 3.1 이다.

즉, 아래와 같이 하면 컴파일 에러가 난다는게 문제다.

var trans: GLKMatrix4 = GLKMatrix4Identity
// trans에 조작 blah blah...
glUniformMatrix4fv(self.transformLoc, 1, GLboolean(GL_FALSE), &trans.m)

찾아낸 방법은 ios - pass a 4x4 matrix to glUniformMatrix4fv 이다. 요약하면 우선 튜플을 포인터로 변환하고(withUnsafePointer), 그 포인터를 다시 Float 포인터로 변환하는 것이다(withMemoryRebound).

withUnsafePointer는 입력된 변수를 그 타입의 포인터로 변환하여 클로저로 넘겨준다. 그리고 변환된 포인터는 클로저 밖에서는 쓸 수 없다.

withUnsafePointer(to: &trans.m) {
// 이제 $0로 넘어온 포인터로 뭔가를 조작하자
}

클로저 안으로 넘어온 인자의 타입은 UnsafePointer<(Float, Float,...)> 이다(튜플의 포인터: Pointee가 튜플임). 그런데 사용하려는 API의 입력 타입은 UnsafePointer<Float> 이므로 또 다시 변환해주어야 한다.

어떤 포인터를 다른 Pointee 타입의 포인터로 변환하기 위해 withMemoryRebound 메소드를 사용한다. 접근 가능한 갯수도 지정해 줄 수 있는데 원래는 접근할 갯수(16)를 정확히 넣어주어야 하겠지만 API가 포인터 하나만 쓸 것이므로 1을 주어도 상관없다. 모두 정리하면 아래와 같이 쓰면 동작한다.

withUnsafePointer(to: &trans.m) {
    $0.withMemoryRebound(to: Float.self, capacity: 16) {
        glUniformMatrix4fv(self.transformLoc, 1, GLboolean(GL_FALSE), $0)
    }
}

위와 같이 써도 좋지만 조금 더 직관적인 방법이 있다. 위에서 튜플 데이터에 대한 포인터를 만들기 위해 withUnsafePointer()를 썼는데, 이는 튜플 데이터를 바로 UnsafePointer 형태로 만드는게 불가능해서였다. 그런데 대상 데이터 변수를 UnsafeMutablePointer로 감싸는 것은 가능하다.

UnsafeMutablePointer는 UnsafeRawPointer로 변환할 수 있는데 UnsafeRawPointer는 bindMemory() 메소드를 사용할 수 있다. bindMemory()는 원하는 데이터형(Pointee)의 포인터로 바꾸어준다. 즉, 아래와 같이도 쓸 수 있다. 블록 없이 쓸 수 있어서 개인적으로 이 방식이 더 마음에 든다.

let m = UnsafeMutablePointer(&trans.m)
let p = UnsafeRawPointer(m).bindMemory(to: Float.self, capacity: 16)
glUniformMatrix4fv(self.transformLoc, 1, GLboolean(GL_FALSE), p)

물론 이걸 with절로 묶어서 쓸 수도 있다. 그런데 with절로 묶었을 때 들어오는 포인터(주소)값이 그냥 UnsafeMutablePointer로 감쌌을 경우의 포인터값과 다른 것으로 보아 with절을 쓰면 카피가 일어나는 것 같다.

withUnsafeMutablePointer(to: &trans.m) {
    m in
    let p = UnsafeRawPointer(m).bindMemory(to: Float.self, capacity: 16)
    glUniformMatrix4fv(self.transformLoc, 1, GLboolean(GL_FALSE), p)
}

이번에는 덧셈을 law of composition으로 하는 정수 group인 ℤ⁺ 의 subgroup 들을 살펴보자. 우선 특정 정수 b의 배수로 이루어진 ℤ⁺ 의 subgroup은 아래와 같이 쓸 수 있다.

bℤ = {n ∈ ℤ | n = bk for some k ∈ ℤ}.

그러면 여기서 (놀랍게도!) ℤ⁺ 의 모든 subgroup은 위와 같은 형태가 된다는 명제가 하나 나온다.

Proposition. 모든 정수 b에 대해서 부분집합(subset) bℤ 는 ℤ⁺의 subgroup이다. 게다가 (심지어) ℤ⁺의 모든 subgroup H는 'H = bℤ for some integer b' 이렇게 쓸 수 있다!

책에서는 bℤ가 ℤ⁺의 subgroup이라는 것에 대한 증명은 생략하고 모든 subgroup이 bℤ 와 같은 형태라는 것만 증명한다.

우선 H를 ℤ⁺의 subgroup이라고 하자. law of composition이 덧셈이고, identity 엘리먼트는 0이고, 엘리먼트 a의 inverse는 −a 이므로 아래와 같은 axiom(룰) 들을 정리할 수 있다.

1. if a ∈ H and b ∈ H, then a + b ∈ H;
2. 0 ∈ H;
3. if a ∈ H, then −a ∈ H.

두 번째 axiom 에 의해서 0이 H의 유일한 엘리먼트일 경우(자명한 subgroup {0}), H = 0ℤ 이므로 해당 명제는 만족한다.

그리고 a ∈ H인 a가 음수이든 양수이든 세 번째 axiom에 의해서 −a는 H에 포함된다.

그리고 H에서 가장 작은 양의 정수를 뽑아서 H = bℤ 라고 해보자. 이것을 다르게 표현하면 양의 정수 k에 대해서 bk = b + b + ... + b (k 번 반복) 이 된다. 이를 첫 번째 axiom 과 induction을 사용하면 bk는 H의 엘리먼트임을 만족하게 된다. k가 음수인 경우는 -bk 이므로 역시 H의 엘리먼트임을 만족한다(세 번째 axiom).

마지막으로 H ⊂ bℤ 인 것을 보이자. 이 말은 H의 모든 엘리먼트 n ∈ H 가 b의 배수인 정수라는 말이다. n을 b의 배수와 나머지 형태로 수식으로 표현하면 아래와 같이 쓸 수 있다.

n = bq + r

여기서 q, r 은 정수이고 나머지(remainder)인 r은 0 ≤ r < b 의 범위를 갖는다. 그러면 n과 bq는 모두 H의 엘리먼트이다(위의 내용과 이어지니 잘 따라오자). 그리고 위 식을 r에 대하여 고쳐쓰면 r = n - bq 가 되는데 이것 역시 첫 번째 axiom과 세 번째 axiom에 의하여 H의 엘리먼트가 된다. 또한 b가 H에서 가장 작은 양의 정수라고 정했고 0 ≤ r < b 이니 r = 0 이고 n = bq ∈ bℤ 이다(끝).

한편, subgroup bℤ는 b로 나누어 떨어지는 정수들이다. 그렇다면 여기서 두 정수 a와 b를 정하고 a와 b로 생성되는 subgroup을 만들어 볼 수 있을 것이다. 책에서는 'subgroups which are generated by two integers a, b' 라고 표현한다. 즉 아래 집합은 ℤ⁺의 subgroup 이다.

aℤ + bℤ = {n ∈ ℤ | n = ar + bs for some integers r, s}

위와 같은 형태로 구성된 subgroup을 subgroup generated by a and b 라고 한다. 이런 subgroup은 두 엘리먼트를 모두 포함하는 가장 작은 규모의 subgroup 이다.

앞의 proposition을 잠시 떠올려보면(bℤ 형태의 subgroup) aℤ + bℤ 이것도 어떤 정수 d 에 의해서 dℤ 로 표현될 수 있다(ℤ⁺의 subgroup이기 때문에). 즉 d 로 나뉘어 떨어지는 정수들의 집합인 것이다. 여기서 d는 'greatest common divisor of a and b'라고 불린다. 이어서 아래 proposition을 살펴보자.

Proposition. a, b를 0이 아닌 정수라고 하자. 그리고 d는 subgroup aℤ + bℤ 를 generate하는 양의 정수라고 하자. 그러면,

1. d can be written in the form d = ar + bs for some integers r and s.
2. d divides a and b
3. If an integer e divides a and b, it also divides d

위 proposition을 증명해보자. 우선 첫 번째 assertion은 d가 subgroup aℤ + bℤ 의 generator 라고 한 사실을 다시 적은 것일 뿐이다. 두 번째는 dℤ = aℤ + bℤ 이기 때문에 d 가 a와 b를 나눌 수 있다. 마지막으로 e가 a와 b를 나눌 수 있다면 a와 b는 eℤ 의 형태가 된다. 이 말은 어떤 정수 n = ar + bs 가 eℤ 에 포함된다는 이야기이고, d역시 이러한 형태이기 때문에 e가 d를 나눌 수 있게된다(끝).

집합과 부분집합의 관계가 있듯이 group이 있으면 subgroup이 있을 수 있다. 어떤 group G의 subgroup H는 아래와 같은 성질을 갖는다.

1. Closure: If a ∈ H and b ∈ H, then ab ∈ H
2. Identity: 1 ∈ H
3. Inverses: If a ∈ H, then a^-1 ∈ H

위에서 첫 번째 Clusure는 group G의 law of composition이 subgroup H에도 사용될 수 있다는 것을 시사한다. 이렇게 부모 group의 law of composition과 subgroup의 그것이 같을 경우 induced law of composition 이라고 부른다.

두 번째(Identity)와 세 번째(Inverse)에서는 H가 induced law of composition에 의해 group으로 구성됨을 나타낸다. Associative에 대해서 이야기하지 않는 이유는 group G에서 정의한 law of composition이 이미 Associative하기 때문이다.

모든 group은 두 개의 자명한(obvious) subgroup을 가진다. (말장난같아 보이지만) 자기 자신과 {1} 이다. {1} 은 identity 엘리먼트만으로 이루어진 group이다. 이 두 가지에 해당되지 않는 subgroup을 다시 proper subgroup 이라고 한다.

subgroup의 예를 들어보면 아래와 같은 것들이 있다.

1. The set T of invertible upper triangular 2 × 2 matrices
   

   a	b
   	d

     (a, d ≠ 0)
   is a subgroup of the general linear group GL₂(ℝ).
2. The set of complex numbers of absolute value 1 ‐ the set of points on the unit circle in the complex plane ‐ is a subgroup of ℂ^×.

Symmetric Group의 개념은 Group 챕터에서 자주 등장한다. 볼때마다 계속 잊어먹고 있는데 잘 숙지해 둬야겠다.

Permutations

permutation of T란 어떤 집합 S = Maps(T,T) - 집합 T를 입력으로 받고 T를 출력으로 내놓는 매핑 함수들의 집합 - 안의 어떤 함수 map f: T ↝ T 가 inverse를 갖고 이것이 일대일 매핑(bijective)할 경우 이 map 함수를 permutation of T 라고 부른다. 이런 permutation들을 집합으로 모아 놓으면 (신기하게도!) group을 형성한다. 예를 들어 identity와 transposition을 나타내는 매핑 i와 𝜏 역시 group을 형성한다. 두 개의 엘리먼트들이 집합 {a,b} 의 permutation인 것이다.

Symmertric Group

정수 1부터 n까지의 집합 {1,2,...,n} 의 permutation 들로 형성된 group을 symmertric group 이라고 부르고 S_n으로 표기한다.

S_n = group of permutations of {1, ... , n}.

n개의 엘리먼트들의 집합에서 permutation의 갯수는 n!이 된다. 순서가 있는 순열을 생각하면 처음에는 n개의 선택권이, 그 다음에는 (n-1)개, ... 이렇게 해서 총 n!개의 경우의 수가 생긴다. 따라서 symmetric group의 엘리먼트의 개수는 n! 개가 된다. 여기서 이걸 order라고 부른다. 즉, symmetric group의 엘리먼트의 개수는 order 인 것이다.

엘리먼트가 2개로 이루어진 symmetric group S₂는 { i, 𝜏 } 이다. 여기서 𝜏𝜏  = 𝜏² = i 인것을 생각하면, 각 엘리먼트들은 자기자신을 inverse로 갖게 되며, commutative한 abelian group이다.

S₃

엘리먼트가 3개로 이루어진 symmetric group S₃는 order가 6, 즉 엘리먼트를 6개 가지고 있다. symmetric group에서 n이 커지면 커질수록 order는 지수승으로 늘어나기 때문에 매우 복잡해지는데, S₃은 commutative 하지 않은 symmetric group들 가운데 order가 가장 작은 group 이기 때문에 주목할 필요가 있다.

S₃의 모든 엘리먼트들은 (놀랍게도!) 2개의 permutation으로 표현할 수 있다. 이들을 x,y라고 이름짓고, x를 cyclic permutation으로, y를 1,2를 서로 바꾸면서 3을 고정하는 permutation으로 정의해보자.

x =

0	1	0
0	0	1
1	0	0

, y =

0	1	0
1	0	0
0	0	1

그러면 집합 {1, 2, 3} 의 permutation 6개는 아래와 같이 x,y 만으로 표현할 수 있다.

{ 1, x, x², y, xy, x²y } = { xⁱy^j | 0 ≤ i ≤ 2, 0 ≤ j ≤ 1}

1은 identity permutation을 의미한다.

여기서 x³ = 1, y², yx = x²y 이기 때문에 각종 composition들이 group에 닫혀있는지에 대해서나 inverse를 만들어 낼 수 있는지에 대해서도 확인할 수 있다.

Abelian group은 law of composition이 commutative한 group 들을 일컫는다. 아래 예시들은 모두 abelian group이다.

• ℤ⁺: the integers, with addition
• ℝ⁺: the real numbers, with addtion
• ℝ^×: the nonzero real numbers, with multiplication
• ℂ⁺, ℂ^×: the analoguous groups, where the set ℂ of complex numbers replaces the real numbers ℝ

어떤 집합 S의 law of composition을 다음과 같이 정의해보자. 일단 집합 S에서 두 원소 a,b를 뽑는다. 그다음 그 둘을 조합해서 집합 S내의 다른 원소 p로 만든다고 하자.

위의 law of composition을 함수로 생각해보면, 이 함수는 S의 원소 두개를 인자로 받아서 S의 원소 하나로 출력한다. 일종의 map 과 같은 것이다.

S × S → S
a,b ↝ p.

여기서 S × S 는 집합 S내의 원소 pair (a, b)의 product를 의미한다.

p = f(a, b)와 같은 functional notiation 은 불편해서 잘 쓰이지 않는다. 대신 law of composition의 종류 혹은 성질에 따라 아래와 같이 덧셈이나 곱셈 등의 많이 쓰인다.

p = ab, a × b, a ◦ b, a + b, and so on.

그리고 a와 b를 composition 한 것이 곱셈의 성질을 갖는다면 이걸 product 라고 부를 것이고, 덧셈의 성질을 가질 경우 sum 이라고 부를 것이다.

그러면 n × n matrix 들의 집합에서 law of composition이 matrix multiplication 인 Group을 예로 들어 자세히 살펴보자.

Group에서 중요한 사실 중 하나는 S의 두 원소 a와 b를 composition한 결과인 ab가 역시 S의 원소라는 점이다. 예를 들어 a =  

1	3
0	2

  , b =  

1	0
2	1

  라면 이 둘의 product인 ab는  

7	3
4	2

  가 된다. 그리고 product 연산이 이루어져서 일단 ab가 되고 나면 다시는 원래 원소였던 a와 b로 복구할 수 없게된다.

law of composition에는 associative 와 commutative 라는 특성이 있을 수 있다. associative는 아래와 같은 결합법칙을 의미한다.

(ab)c = a(bc)

그리고 commutative는 아래와 같이 교환법칙을 말한다.

ab = ba

matrix multiplication이 law of composition인 경우에는 associative 하지만 commutative 하지는 않다. 반면, 정수집합에서 덧셈이 law of composition인 경우에는(ℤ⁺) commutative 까지 가능하다. 때문에 보통 associative 한 Group에서 composition을 표기할 경우 곱셈 방식으로 표기하고(commutative 여부는 관심없음), commutative 까지 한 경우는 덧셈 방식으로 표기한다.

일반적으로 associative 한지 여부가 commutative 한지 여부보다 더 근본적으로 중요하게 여겨진다. 그 근거 중에 하나는 composition이 여러개의 함수들인 경우 이들 함수들을 조합하여 하나의 함수로 나타낼 수 있기 때문이다.

예를 들어 집합 T가 있고 T에서 T로 가는(T를 입력으로 받고 T를 내놓는) 함수 g와 f가 있다고 하자. 그리고 g ◦ f 를 조합된 map, t ↝ g(f(t)) 를 나타낸다고 하자. 그리고 S를 T에서 T로 가는 매핑들의 집합이라고 한다면(S = Maps(T,T)), 하나로 조합된 g ◦ f 이 모든 S의 경우에 대해서 law of composition이 될 수가 있다. 함수 레벨에서 하나로 합쳐써도 된다는 이야기다.

다시 단순한 예를 들어보자. 집합 T가 두 원소 a와 b를 가질 때 T에서 T로 가는 매핑의 종류는 모두 네 가지가 된다.

• i: the identity map defined by i(a) = a, i(b) = b;
• 𝜏: the transposition, defined by 𝜏(a) = b, 𝜏(b) = a;
• α: the constant function α(a) = α(b) = a;
• β: the constant function β(a) = β(b) = b.

이들 중 두개를 조합하여 하나의 law of composition을 만든다고 해 보면 그 경우들은 아래와 같이 multiplication table로 나타낼 수 있다.

그리고 이들 중 임의의 2개의 조합의 결과는 아래와 같이 보면 된다.

여기서 𝜏 ◦ α = β 인데 순서를 뒤바꾼 α ◦ 𝜏 = α 이다. 이걸 보면 함수들의 composition은 commutative 하지 않음을 알 수 있다.

방금전 살펴본 2개 함수 조합의 associative를 보다 일반적인 n개를 조합하는 경우로 확장하여 생각해보자.

a₁a₂...a_n = ?

이들을 어떻게 조합하여 하나의 연산으로 만들 수 있을까? 우선 익숙한 방법인 왼쪽부터 두 개씩 짝을지어 차근차근 조합해 나가는 경우가 있을 수 있다.

((a₁a₂)a₃)a₄ ...

만일 n=4 라면 위와 같은 경우를 포함해서 4가지 조합 방법이 있을 수 있다. 예를 들면 (a₁a₂)(a₃a₄) 같은. 그런데 만일 composition 연산이 associative 하다면 이 모든 경우의 함수 조합이 결과적으로는 동일하게 된다(induction으로 증명할 수 있는데 생략한다).