1.4 Example of Structures
이 Sec.에서는 수학이나 컴퓨터과학에서 자주 등장하는 structure들을 소개한다.
Graphs
Definition 1.4.1
Graph란 vertice라 부르는 점들과 edge라 부르는 선분의 집합으로, 모든 edge는 vertex에서 시작되며 vertex에서 끝난다.
두 vertex들이 하나의 edge로 연결되어 있다면, 두 vertex는 인접(adjacent)해 있다고 한다.
위는 graph들의 예시. 이렇게 그림으로 나타낼 수도 있지만 vertex와 edge를 나열하여 나타낼 수 있다. 예를 들자면,
- Vertices : a, b, c, d, e
- Edges : ab, ad, ae, bc, cd, ce, de
이렇게 쓰면 이 graph는 5개의 vertex와 7개의 edge를 가지고 있음을 알 수 있다. 참고로 위 Graph 2와 Graph 3이 이와 같다. 그러므로 Graph 2와 Graph 3는 같은 graph에 대한 묘사라고 볼 수 있다.
다른 방법으로, graph를 structure로써 볼 수 있다. Structure $G$의 underlying set $U$는 graph의 vertex들의 집합이다. $G$의 vocabulary $\mathcal{V}_G$는 하나의 binary relation $R$로 이루어져 있으며, structure $G$는 $R$을 edge relation으로 해석한다. 즉, $U$의 element $a$, $b$에 대해 $G \models R(a, b)$ iff Graph는 vertex $a$와 $b$ 사이에 edge를 가진다.
위 graph model들은 모두 다음 $\mathcal{V}_G$-sentence를 따른다.
\[\forall x \neg R (x, x)\] \[\forall x \forall y (R(x,y) \Leftrightarrow R(y, x))\]첫 번째 sentence는 binary relation $R$이 reflexive하지 않다는 것이다. 실제로 위 graph들은 모두 자기 자신과 인접한 vertex를 갖지 않는다.
두 번째 sentence는 binary relation $R$이 symmetric하다는 것이다. 이로부터…
Definition 1.4.2
Graph란 위 두 $\mathcal{V}_G$-sentence를 따르는 $\mathcal{V}_G$-structure를 말한다.
그래프이론의 설명을 빌리자면, 우리가 고려하고자 하는 graph란 “undirected graph with neither multiple edges nor loops”.
위 Graph 1~4은 모두 다음 sentence를 model한다는 공통점이 있다.
\[\forall x \exists y R(x,y)\]모든 vertex에는 인접한 다른 vertex가 존재한다는 뜻. 그러나 이건 모든 graph에 대해 참은 아니다. 예를 들어 다음 graph를 생각할 수 있다.
위 graph에서 중앙의 vertex는 어떠한 인접한 다른 vertex도 갖지 않는다. 따라서 이 graph는 $\exists x \forall y \neg R(x,y)$을 model하며 이는 $\forall x \exists y R(x,y)$의 부정과 같다.
Definition 1.4.3
Graph의 임의의 vertex $a$, $b$에 대해, $a$에서 $b$로의 path란 $a$에서 시작하여 $b$에서 끝나는 vertex들의 sequence로, $a$를 제외한 각 vertex는 sequence 내의 이전 vertex와 인접해 있다.
Definition 1.4.4
Graph $G$의 임의의 두 vertex $a$, $b$에 대해 $a$에서 $b$로의 path가 존재하면, graph는 connected(연결)되어있다.
그러므로 Graph 1~4는 연결되어 있다. 모두 하나보다 많은 vertex를 가지며, $\forall x \exists y R(x,y)$를 model한다. 반면 이들은 $\exists x \forall y R(x,y)$을 model하지는 못한다. 이 sentence는 모든 vertex와 인접한 vertex가 존재한다는 뜻이다. 자기 자신과 인접한 vertex가 없으므로!1
다만 적어도 Graph 1, 4에는 자기 자신을 제외하고 모든 다른 vertex와 인접한 vertex가 존재한다. 이걸 first-order logic으로 표현하면:
\[\exists x \forall y (\neg (x=y) \rightarrow R(x,y))\]그럼 Graph 1과 4는 어떻게 구분할 수 있을까? Graph 1에는 다른 모든 vertex와 인접한 vertex가 딱 하나 존재한다. 이걸 표현하려면 어떻게 해야 할까? 다시 말해, 유일하게 존재한다는 걸 first-order logic으로 어떻게 쓰지?
단순하게 sentence $\varphi(x)$를 $\forall y (\neg (x=y) \rightarrow R(x,y))$라고 하자. 임의의 graph $G$와 $G$의 임의의 vertex $a$에 대해, $G \models a$ iff $a$는 $G$의 다른 모든 vertex와 인접하다.
다음 sentence가 그런 element는 unique하다는 걸 말해준다.
\[\exists y \varphi(y) \wedge \forall z (\varphi(z) \rightarrow (z=y))\]반면 Graph 4는 다음 sentence로 구별할 수 있게 된다. $\varphi(x)$가 모든 vertex에 대해 성립한다는 뜻이다.
\[\forall x \forall y (\neg (x=y) \rightarrow R(x,y))\]이 sentence를 model하는 graph를 clique 또는 complete graph라고 한다. $n$개의 vertex를 갖는 clique는 $n$-clique이라 부르며 $K_n$로 표기한다. 그러므로 Graph 4는 $8$-clique $K_8$이다.
$n$만 정해지면, $n$-clique에 대한 정보는 다 알 수 있다고 해도 된다. 임의의 두 $n$-clique는 본질적으로 같기 떄문. 더 정확히 말하자면,
Definition 1.4.5
Graph $G_1$의 vertex들의 set에서 graph $G_2$의 vertex들의 set으로의 one-to-one correspondence $f$가 존재해서,
[$G_1$의 임의의 두 vertex $a$, $b$가 인접 iff $G_2$의 $f(a)$, $f(b)$가 인접]
하다면, $G_1$과 $G_2$는 isomorphic하다고 하며 그러한 함수 $f$를 isomorphism이라고 한다.
그래서 isomorphic한 두 graph는 본질적으로 같다.
지금까지 Graph 1부터 4까지를 구별하는 $\mathcal{V}_G$-sentence를 알아보았다. 더 나아가 Graph 1이 다른 graph와 isomorphic하지 않다는 $\mathcal{V}_G$-sentence도 생각해볼 수 있겠다.
$\mathcal{V}_G$-sentence $\varphi_G$가 존재해서 임의의 graph $H$에 대해 $H \models \varphi_G$ iff $H$는 $G$와 isomorphic.
위 명제의 증명은 Sec. 1.6에서.
그러나 first-order logic도 그렇게 강력하지는 못하다. 어떤 graph가 홀수 개 vertex를 갖는지 짝수 개 vertex를 갖는지를 말해주는 first-order sentence는 만들 수 없다. 심지어 어떤 graph가 connected인지도 말할 수 없다.2
Relational Databases
전화번호부, 가계도, 카탈로그 등 임의의 data를 모아놓은 것을 database로 볼 수 있다. Relational database란 table들의 set이다. 예를 들어 다음 세 table은 relational dataset이다.
| 부모 | 자녀 |
|---|---|
| Ray | Ken |
| Ray | Sue |
| Sue | Tim |
| Dot | Jim |
| Bob | Jim |
| Bob | Liz |
| Jim | Tim |
| Sue | Sam |
| Jim | Sam |
| Zelda | Max |
| Sam | Max |
| 여성 |
|---|
| Dot |
| Zelda |
| Liz |
| Sue |
| 이름 | 생일 |
|---|---|
| Ann | August 5 |
| Leo | August 8 |
| Max | July 28 |
| Sam | August 1 |
| Sue | July 24 |
이 relational database를 structure $D$로써 묘사하자. $D$의 universe는 column에 등장하는 모든 item들이다. 따라서 이 set에는 13개의 이름과 5개의 날짜가 포함된다.
$D$의 vocabulary $\mathcal{V}$는 $n$-ary relation으로 이루어지며, 여기서 $n$은 각 table의 column의 수와 같다. 즉 $\mathcal{V}$는 여성인지를 나타내는 unary relation $F$, 부모자식 관계를 나타내는 binary relation $P$, 생일을 나타내는 binary relation $B$로 이루어진다.
$\mathcal{V}$-structure $D$는 이 relation들은 table의 row로써 해석한다. 예를 들어 [$D \models B(a,b)$ iff “$ab$”는 Birthday table의 한 row]가 된다. 이를 통해 $D$를 완전히 묘사할 수 있게 된다. 다음 예시를 보자.
\[D \models F(Dot)\] \[D \models P(Zelda, Max)\] \[D \models \neg B(Zelda, July 28)\]$B, F, P$를 이용하면 $D$의 다른 relation을 표현하는 first-order formula도 정의할 수 있다. $\neg F(x)$는 $x$가 남성이라는 말이고, $\exists z (P(x,z) \wedge P(z, y))$는 $x$가 $y$의 손자라는 의미가 된다. $\exists y B(x,y)$는 $x$가 날짜라는 뜻이고, 이것의 부정은 $x$가 사람이라는 뜻이다.
Linear Orders
Vocalbulary $\mathcal{V}_{<}$가 다시 등장할 차례다. Binary relation $<$를 편의상 $<(x,y)$의 형태로 나타내기로 하자. 물론 해석은 우리가 아는 그 부등호대로다.
여기서 우리는 4가지 $\mathcal{V}_{<}$-structure $\mathbf{N}_{<}$, $\mathbf{Z}_{<}$, $\mathbf{Q}_{<}$, $\mathbf{R}_{<}$에 대해 생각할 것이다. 각 structure들의 universe는 해당하는 수 체계이다. 조금 더 정확하게 나타내자면,
- $\mathbf{N}_{<} = (\mathbb{N} \vert {<})$
- $\mathbf{Z}_{<} = (\mathbb{Z} \vert {<})$
- $\mathbf{Q}_{<} = (\mathbb{Q} \vert {<})$
- $\mathbf{R}_{<} = (\mathbb{R} \vert {<})$
이들은 모두 다음 $\mathcal{V}_{<}$-sentence를 model한다.
\[\forall x \forall ((x<y) \rightarrow \neg(y<x))\] \[\forall x (\neg (x < x))\] \[\forall x \forall y ((x<y) \vee (y<x) \vee (x=y))\] \[\forall x \forall y \forall z (((x < y) \wedge (y < z)) \rightarrow (x < z))\]위 sentence들을 만족하는 $<$는 underlying set을 linearly order한다고 표현한다.
다만 모든 $\mathcal{V}_{<}$-sentence들이 네 structure들에서 참이 되는 건 아니다. $\forall x \exists y (y<x)$를 sentence $\varphi$라고 하자. 이는 제일 작은 원소가 없다는 의미이다. $\mathbf{R}_{<}$, $\mathbf{Q}_{<}$, $\mathbf{Z}_{<}$에서는 $\varphi$를 model할 수 있으나, $\mathbf{N}_{<}$에서는 model할 수 없다. 가장 작은 원소 $1$이 있기 때문이다.
따라서 $\mathbf{N}_{<}$은 $\varphi$의 부정 $\exists x \forall y \neg(y<x)$를 model하며 이 sentence는 다른 세 structure와 $\mathbf{N}_{<}$을 구분시켜준다.
마찬가지로 다른 structure들과 $\mathbf{Z}_{<}$를 구분시켜주는 first-order sentence를 찾아 보자. $\mathbf{Z}_{<}$는 dense하지 않다. 임의의 두 정수 사이에 반드시 다른 정수가 있으리라곤 볼 수 없다. 다음 $\mathcal{V}_{<}$-sentence
\[\forall x \forall y ((x < y) \rightarrow \exists z ((x<z) \wedge (z < y)))\]는 임의의 두 원소 사이에 항상 다른 원소가 존재한다는 의미로, $\mathbf{Q}_{<}$, $\mathbf{R}_{<}$과 달리 $\mathbf{Z}_{<}$는 위 sentence를 model하지 못한다. 위 sentence를 $\delta$라고 하면, $\varphi \wedge \neg \delta$는 $\mathbf{Z}_{<}$를 다른 세 structure들과 구별시켜주는 $\mathcal{V}_{<}$-sentence가 된다.
다음은 $\mathbf{Q}_{<}$와 $\mathbf{R}_{<}$을 구별할 차례다. 여기서는 order-completeness라는 성질을 이용할 수 있다. Linear order가 두 개의 open interval로 분할할 수 없다면, 우리는 order-complete라고 한다. 예를 들어 유리수 집합은 두 open interval $(-\infty, \sqrt{2})$와 $(\sqrt{2}, \infty)$의 union이다. $\sqrt{2}$는 유리수가 아니므로 모든 유리수는 두 open interval 중 어느 하나에 들어가 있다. 따라서 $\mathbf{Q}_{<}$는 order-complete하지 않다. 반면 $\mathbf{R}_{<}$은 order-complete하며 이것이 $\mathbf{Q}_{<}$와 $\mathbf{R}_{<}$을 구별해 준다.
그래서 이를 토대로 $\mathcal{V}_{<}$-sentence를 찾으면… 잘 안 된다!
사실, 모든 $\mathcal{V}_{<}$-sentence $\varphi$에 대해, $\mathbf{R}_{<} \models \varphi$와 $\mathbf{Q}_{<} \models \varphi$는 동치이다!3
$\mathbf{Q}_{<}$와 $\mathbf{R}_{<}$은 order-completeness라는 차이가 있지만, 이 order-completeness는 first-order sentence로는 나타낼 수 없다. 왜냐하면 order-completeness는 second-order의 개념이 필요하기 때문이다.
그러므로 $\mathcal{V}_{<}$-sentence의 관점에서는 structure $\mathbf{Q}_{<}$와 $\mathbf{R}_{<}$은 동일하다.4
Number System
적어도 실수와 유리수의 차이라면 first-order logic에서도 구별 가능하다. Vocabulary of arithmetic $\{+, \cdot, 0, 1\}$가 다시 등장한다. Vocabulary $\mathcal{V}_{ar}$와 다음 $\mathcal{V}_{ar}$-structure들을 생각하자.
- $\mathbf{A} = (\mathbb{Z} \vert +, \cdot, 0, 1)$
- $\mathbf{Q} = (\mathbb{Q} \vert +, \cdot, 0, 1)$
- $\mathbf{R} = (\mathbb{R} \vert +, \cdot, 0, 1)$
- $\mathbf{C} = (\mathbb{C} \vert +, \cdot, 0, 1)$
자연수 계수를 갖는 임의의 polynomial은 $\mathcal{V}_{ar}$-term이다. 예를 들어,
\[x^5 - 9x+3=0\]은 $\mathcal{V}_{ar}$-formula이다. 유의할 점은 $3$이나 $x^5$는 $\mathcal{V}_{ar}$의 symbol이 아니라 $\mathcal{V}_{ar}$-term $(1+(1+1))$, $x \cdot (x \cdot (x \cdot (x \cdot x)))$을 축약했다는 것.
이 vocabulary에서는 order-completeness를 생각할 수 없지만 여기서 $\mathbf{R}$과 $\mathbf{Q}$를 구별할 수는 있다. $\mathcal{V}_{ar}$-sentence $\exists x (x^2 = 2)$는 $\sqrt{2}$의 존재를 주장한다. 따라서 이 sentence는 $\mathbf{R}$에서는 model할 수 있으나 $\mathbf{Q}$에서는 할 수 없다. 비슷하게 $2x + 3 = 0$은 $\mathbf{Q}$에서는 model할 수 있으나 $\mathbf{A}$에서는 할 수 없다.
$\mathbb{Z}$에서 $\mathbb{Q}$, $\mathbb{R}$로 갈 수록 더 많은 polynomial들의 해가 포함된다. 복소수 $\mathbb{C}$는 실수에 방정식 $x^2 + 1 = 0$의 해 $i$가 더해진다. $\mathcal{V}_{ar}$-sentence $\exists x (x^2 +1 = 0)$은 $\mathbf{C}$와 다른 structure들을 구분시켜준다.
The Fundanemtal Theorem of Algebra에 따르면 임의의 복소수 계수를 갖는 nonconstant polynomial $P(x)$에 대해 equation $P(x) = 0$은 $\mathbb{C}$에서 해를 갖게 된다. 따라서 여기서 더 이상 수 체계를 확장시킬 수는 없다.
마지막으로 사족을 덧붙이자면, 왜 $\mathbf{Z}$가 아니라 $\mathbf{A}$라고 쓸까? “$\textrm{A}$”는 arithmetic의 첫 글자이다. 위 순서와는 다르게, first-order logic에서는 $\mathbf{C}$가 가장 간단하며, 그 다음은 $\mathbf{R}$이다. Structure $\mathbf{R}$에는 여러 재밌는 성질들이 있다. 그 다음은 $\mathbf{Q}$ 순서이고, $\mathbf{A}$가 제일 복잡하다.