Algebra

1. Definition

Definition 1

algebra는 다음의 3가지 component로 구성된다.

1) carrier라고 불리는 집합 A
2) carrier로 정의되어지는 Operators
3) carrier의 구별되는 elements, constants(추후 다루겠지마느 identity나 zero 같은 것들을 의미한다.)

2. Closed with respect to operations

Definition 2

$\circ$, $\triangleright$ 를 set T의 binary, unary operation이라고 정의하자 T'를 T의 subset이라고 한다면

T'는 closed with respect to $\circ$ $\Leftarrow a,b \in T' \land a \circ b \in T'$
T'는 closed with respect to $\triangleright$ $\Leftarrow a \in T' \land \triangleright a \in T'$

3. Subalgebra

Definition 3

A = $\langle S, \circ, \triangleright, k \rangle$이고, A' = $\langle S', \circ', \triangleright', k \rangle$를 algebra라고 한다면 A'는 A의 subalgebra이다. 만약
1) $S' \subseteq S$
2) $a \circ' b = a \circ b \text{ for all } a, b \in S'$
3) $\triangleright'a = \triangleright a \text{ for all } a \in S'$
4) $k' = k$

4. Identity and Zero Elements

Definition 4

$\circ$가 S의 binary operation이라고 한다면

1) 아래와 같은 상황일 때 특정 element c를 identity라고 부른다.
$\forall x \in S, c \circ x = x \circ c = x$
2) 아래와 같은 상황일 때 특정 element d를 zero라고 부른다.
$\forall x \in S, d \circ x = x \circ d = d$

ex)

$\langle \mathbb{R}, \ast \rangle$ : identity는 1이고, zero는 0이다.

$\langle \mathbb{R}, + \rangle$ : identity는 0이고, zero는 존재하지 않는다.

 

4-1. Left(of Right) identity and zero

Definition 5

만약 \circ이 S의 binary operation이고,

1) 다음과 같은 상황일 때 특정 element $c_l(c_r)$은 left(right) identity이다.
$\forall x \in S, c_l \circ x = x (x \circ c_r = x)$

2) 다음과 같은 상황일 때 특정 element $d_l(d_r)$은 left(right) zero이다.
$\forall x \in S, d_l \circ x = d (x \circ d_r = d)$

5. Inverse Element

Definition 6

만약 \circ이 S의 binary operation이고, c가 identity라면

1) $x \circ y = c$이면 x는 y의 left inverse 이며, y는 x의 right inverse이다.
2) $x \circ y = y \circ x = c$이면 x는 y의 inverse(inverse of y with respect to the operation $\circ$)이다.

6. algebraic structure

6-1. Semigroup

Definition 7

semigroup은 $\forall a, b, c \in S$에 대해 $a \circ (b \circ c) = (a \circ b) \circ c$의 associative한 특징을 가지는 operation $/circ$가 $\langle S, \circ \rangle$ 다음과 같이 묶인 것을 의미한다.

Theorem 1

만약 $\langle S, \circ \rangle$이 semigroup이고, $\langle T, \circ \rangle$이 $\langle S, \circ \rangle$의 subalgebra이면 $\langle T, \circ \rangle$도 semigroup이다.

6-2. Monoid

Definition 8

monoid는 $\langle S, \circ, 1 \rangle$ 다음과 같이 나타내어지며 $\circ$는 associative한 operation, 1은 identity, 그리고 $\forall a, b, c \in S$에 대해 다음과 같은 특징이 모두 만족한다.  

1) $a \circ (b \circ c) = (a \circ b) \circ c$
2) $a \circ 1 = a$
3) $1 \circ a = a$

6-3. Group

Definition 9

group은 $\langle S, \circ, \triangleright, 1$으로 나타내어지며, $\circ$는 associative한 binary operator, constant 1은 $\circ$의 identity, $\triangleright$는 unary operation이며 $\triangleright x$는 $\circ$의 inverse이다. 

Theorem 2

$\langle S, \circ, \triangleright, 1 \rangle$이 group이라면, S의 모든 element는 unique한 inverse를 가진다. inverse를 정의하는 함수 f$(f : S \rightarrow S)$에 대해 bijection 관계를 가진다.

ex)

 

Monoid : $\langle \mathbb{R}, \ast, 1 \rangle$, $\langle \mathbb{R}, +, 0 \rangle$, $\langle \mathbb{Z}, \ast, 1 \rangle$, $\langle \mathbb{Z}, +, 0 \rangle$

 

group : $\langle \mathbb{R} - {0}, \ast, 1/x, 1 \rangle$, $\langle \mathbb{R} - {0}, +, -x, 0 \rangle$, $\langle \mathbb{Z}, +, -x, 0 \rangle$

 

not a group : $\langle \mathbb{Z} - {0}, \ast, 1/x, 1 \rangle$

=> 1/x의 경우 Z의 범위가 아닐 수 있어서 inverse를 가지지 않는 x가 존재한다.

 

6-4. summary

Remark 1

Semigroup과 monoid와 group은 다음과 같은 포함관계를 가진다.

{semigroup} $\supseteq$ {monoids} $\supseteq$ {groups}

각각의 Signiture는

semigroup = $\langle S, \circ \rangle$
monoid = $\langle S, \circ, 1 \rangle$
group = $\langle S, \circ, \triangleright, 1 \rangle$

Remark 2

ring과 field는 잘 알려진 algebraic structure다. 각각 +와 *가 속해있는 structure.

7. Homomorphism

Definition 10

A = $\langle S, \circ, \triangleright, k \rangle$ 이고, A' = $\langle S', \circ' \triangleright' k' \rangle$일 때, function h가 $h : S \rightarrow S'$가 다음과 같은 특징을 가진다면

1) $h(x \circ y) = h(x) \circ' h(y)$
2) $h(\triangleright x) = \triangleright'h(x)$
3) h(k) = k'

의 관계를 만족할 때 h를 A to A'의 homomorphism이라 부른다.

ex)

A = $\langle \mathbb{R}, +, -x, 0 \rangle$, $B = \langle \mathbb{R}^{+}, \ast, 1/x, 1 \rangle$이면,

homomorphism이 존재하는지를 보여라

 

h(x) = $e^x$ : $\mathbb{R} \rightarrow \mathbb{R^{+}}$ 라고 한다면

 

1) $h(x \circ y) = h(x) \circ'$ h(y) : h(x + y) = $e^{x+y}$ = $e^x \ast e^y$ = $h(x) \ast h(y)$

2) $h(\triangleright x) = \triangleright'$ h(x) : h(-x) = $e^{-x}$ = $\frac{1}{e^x}$ = $\frac{1}{h(x)}$

3) h(k) = k' : h(0) = $e^0 = 1$

 

h는 homomorphism이다.

 

7-1. Epimorphism, Monomorphism, Isomorphism

 

Definition 11

1) h가 homomorphism이고 onto(surjection)일 때, h는 eprmorphism이다.
2) h가 homomorphism이고 one-to-one(injection)일 때, h는 monomorphism이다.
3) h가 homomorphism이고, bijection이면 h는 isomorphism이다. => most important concept!

 

8. Congruence Relation

Definition 12

algebra A = $\langle S, \circ, \triangleright \rangle$이라면 equivalence relation E는 right(or left) congruence relation이다. $\forall x, y, z \in S$에 대해 다음을 만족할 때,

1) $(x, y) \in E \Rightarrow (x \circ z, y \circ z) \in E\ (or\ (z \circ x, z \circ y) \in E)$
2) $(x, y) \in E \Rightarrow (\triangleright x, \triangleright y) \in E$

if E is Right AND Left congruence relation, then E is congruence relation

만약 signature에 unary operator가 없다면 2번째 조건은 무시해도 congruence relation은 만족한다.

 

ex)

 

A = $\langle \mathbb{Z}, + \rangle$이라고 하면 다음 binary relation이 congruence relation인지 구해라

 

1) $(x, y) \in R_1 \iff |x - y| \lt 10$

=> 일단 해당 relation이 equivalence인지부터 판별해야한다.

하지만 transitive하지 않기 때문에 equivalence relation이 아님.

따라서 congruence relation이 아님

 

2) (x, y) $\in R_2 \iff x \ge y$

=> 해당 relation이 symmetric하지 않기 때문에 equivalence 아님

 

3) $(x,y) \in R_3 \iff (x \lt 0 \land y \lt 0) \lor (x \ge 0 \land y \ge 0)$

=> 해당 relation은 equivalence하지만 congruence하지는 않음.

counter example)

$(-7, -5) \in R_3, (-7 + 6, -5 + 6) = (-1, 1) \notin R_3 $

 

Theorem 3 

A = $\langle S, \circ \rangle$이고, E가 S의 equivalence relation일 때


$$\text{ E는 congruence relation } \iff (\forall x_1, x_2, y_1, y_2) (\langle x_1, x_2 \rangle \in E \land \langle y_1, y_2 \rangle \in E) \Rightarrow \langle x_1 \circ y_1, x_2 \circ y_2 \rangle \in E$$

(if $\Leftarrow$) $(x, y) \in E$라면, E는 reflexive이기 때문에, $\forall z \in S, (z, z) \in E$이다.

 

$$ (\forall x_1, x_2, y_1, y_2) (\langle x_1, x_2 \rangle \in E \land \langle y_1, y_2 \rangle \in E) \Rightarrow \langle x_1 \circ y_1, x_2 \circ y_2 \rangle \in E$$

을 각각 (x, y)와 (z, z)로 바꾸면

 

$$((x, y) \in E \land (z, z) \in E \Rightarrow (x \circ z, y \circ z) \in E) \text{  $\therefore$ left congruence}$$

 

각각 (z, z)와 (x, y)로 바꾸면

 

$$((z, z) \in E \land (x, y) \in E \Rightarrow (z \circ x, z \circ y) \in E) \text{  $\therefore$ right congruence}$$

 

(only if $\Rightarrow$)

 

$(x_1, x_2) \in E, (y_1, y_2) \in E$라고 가정하면 E는 right congruence이기 때문에

 

$$(x_1 \circ y_1, x_2 \circ y_1) \in E$$

 

또 E는 left congruence이기 때문에

 

$$(x_2 \circ y_1, x_2 \circ y_2) \in E$$

 

E는 transitice이기 때문에 $(x_1 \circ y_1, x_2 \circ y_2) \in E$이다. 따라서

 

$$(\forall x_1, x_2, y_1, y_2) (\langle x_1, x_2 \rangle \in E \land \langle y_1, y_2 \rangle \in E) \Rightarrow \langle x_1 \circ y_1, x_2 \circ y_2 \rangle \in E$$

 

를 만족시킨다.

 

(Problem 1)

 

A = $\langle S, + \rangle$ 이고, B = $\langle T, \cdot \rangle$ 이라고 할 때, $h : S \rightarrow T$이고 A to B의 homomorphism이라고 한다면 relation R = {$(x, y) | h(x) = h(y)$} 이 congruence relation인 것을 보여라

 

우선 R이 equivalence 인 것을 먼저 보인다.

 

그 후

$(x_1, x_2) \in R, (y_1, y_2) \in R \Rightarrow h(x_1) = h(x_2) \land h(y_1) = h(y_2)$이다.

또한 h는 homomorphism이기 때문에 $\forall x, y \in S, h(x_1 + y_1) = h(x_1) \cdot h(y_1) ,  h(x_2 + y_2) = h(x_1) \cdot h(y_2)$이다. 

 

따라서

 

$$(x_1, x_2) \in R \land (y_1, y_2) \in R \Rightarrow (x_1 + y_1, x_2 + y_2) \in R$$

 

따라서 R은 congruence relation이다.