[이산수학] Homomorphism, Isomorphism (동형 사상)

사상 (morphism)

수학적 구조를 보존하는 함수의 개념을 추상화한 것

 

말이 너무 어렵다.

사상은 수학에서 특정한 구조를 유지하면서 한 구조에서 다른 구조로 연결하는 함수이다. 

어떤 규칙에 따라 두 수학적 대상이나 집합을 이어주는 다리 역할을 한다.

• 집합의 사상은 일반적인 함수 -> 숫자 1을 2로 보내고, 3을 4로 보내는 규칙이 있을 때 이것도 하나의 사상이다.
• Group의 사상은 Group의 구조를 보존하는 함수이다.
  • 예를 들어, 덧셈 구조가 있는 숫자 집합에서 덧셈 결과를 동일하게 유지하면서 다른 집합에 매핑한다.
  • G에서 H로 가는 함수 f가 사상이 되기 위해서는 G에서의 덧셈이 H에서도 동일하게 유지되어야 한다.
    • 덧셈을 먼저 하고 함수 f를 적용한 결과 f(a + b) 와 
    • 각각 f(a)와 f(b)를 구해서 그 둘을 더한 결과 f(a) + f(b) 가 동일
• 함수와 비슷하지만 함수보다는 더 일반적인 개념으로 본다.
  • 함수는 일대일 , 다대일에 한정되어있음
  • 사상은 일대일, 일대다, 다대일, 다대다 가능
• Mapping이라고도 함

종류

Endomorphism

• 변환을 시켰는데 나 자신과 같을 때
• G라는 group의 원소들을 G내의 다른 원소로 매핑 
• ex) 함수 $f: \ Z_4 \rightarrow Z_4 $  를 정의해서 $Z_4$의 원소들을 동일한 구조 내에서 다른 원소로 매핑
  • $f(x) = 2x \ mod \ 4$ 
  • f(0)= 0
  • f(1) = 2
  • f(2) = 0
  • f(3) = 2

Automorphism

• Endomorphism에서 역함수가 존재해야 한다. (일대일 대응)
• Endomorphism의 subgroup
• 모든 원소가 유일하게 다른 원소에 대응되며 역함수가 존재하여 되돌리기 가능할 경우
• ex) 함수 $f: \ Z_4 \rightarrow Z_4 $  
  • $f(x) = 3x mod 4$
  • f(0) = 0
  • f(1) = 3
  • f(2) = 2
  • f(3) = 1
  • 이 때 역함수는 $3x mod 4$ 가 된다.

Homomorphism

• $<G, \square>, \ <H, *> $ 가 있을 때 그룹 G에 속하는 모든 a, b에 대해 $f(a\  \square \ b) = f(a) * f(b) $
• ex)$<Z, +>$ 와 $<Z_4, +>$ 가 있을 때 $f: Z \rightarrow Z_4$ 를 정의한다.
  • $f(x)$ = $[x]$ = $\{x + 4k \ | \ k \in Z \}$ : 정수 x를 모듈로 4한 값
  • 정수 집합에 속하는 모든 a, b는, $\mathbf{f(a + b) = [a + b] = [a] + [b] = f(a) + f(b)}$를 만족한다.
  • $f(7 + 5) = [7 + 5] = [12] = [0] = [7] + [5] = f(7) + f(5)$
    • $f(7 + 5) = f(7) + f(5)$ 이므로 Homomorphism이다. 

특성

$<G, \square>, \ <H, *> $  가 각각 항등원 $\mathbf{e_G}$, $\mathbf{e_H}$ 를 가진다고 가정하자. $f : G \rightarrow H$ 가 Homomorphism이면 다음 성질들을 만족한다.

• $f(e_G) = e_H$ : 항등원은 항등원에 매핑된다.
• $f(a^{-1}) = [f(a)]^{-1}$ : a의 역원은 f(a)의 역원으로 매핑된다.
• $f(a^n) = [f(a)]^n$ : 거듭제곱은 동일한 성질을 가진다.
• $f(S)$ 가 H의 부분군이면 S는 G의 부분군이다.
• ex) $f: Z \rightarrow Z_4$
  • f(0) = [0]
  • f($5^{-1}$) = f(-5) = [-5] = [3] = $[1]^{-1}$ = $[5]^{-1}$ = $[f(5)]^{-1}$
  • $[f(5)]^3$ = $[5]^3$ = [5] + [5] + [5] = [15] = $[5^3]$ = $f(5^3)$

Isomorphism

• 서로 다른 두 그룹의 일대일 대응 함수, 우선 Homomorphism을 만족해야한다.
• G의 모든 원소가 H의 고유한 원소로 매핑되고 모든 원소가 매핑되어야함
• ex) $f: <R^+, \cdot>\  \rightarrow \ <R, +>$ $f(x) = log_{10}(x)$ : 양의 실수, 곱셈 연산에서 실수, 덧셈 연산으로 매핑
• 양의 실수에 속하는 모든 a, b에 대해서
  • $f(ab) = log_{10}(ab) = log_{10}(a) + log_{10}(b) = f(a) + f(b)$ : 곱셈의 로그 성질 만족
  •  위는 일대일이며, 전사함수이다. 그러므로 $f$는 isomorphism이다.