Incompleteness(1)-preliminary definitions

 

 

before considering incompleteness, we've to define some basic words.

 

1. definability.

 

 $k'th$ relation $R$ is definable in $\mathfrak{A}$ iff there exists some first order formula that defines it. In this case, the formula $\phi$ must have some free variables among $v_1, v_2, \cdots , v_k$. then the relation $R$ is constructed as $\{<a_1,a_2,\ldots , a_k>| \models \phi[a_1,a_2, \ldots , a_k]\}$.

($\phi[a_1,a_2,\ldots, a_k]$ means substituting free variables among $v_1, \ldots, v_k$ for $a_i$ where $a_i$ belongs to the universe of given structure).

for example, in the structure of reals, we can define $\{<a,b>\in \mathcal{R} \times \mathcal{R} | a\leq b \}$ by formulating $v_1 \leq v_2$ as $\exists v_3 v_2=v_1 + v_3 \cdot v_3$.

2. decidability.

 

 effective procedure means, without considering time/space, there exist some algorithms that any computer can follow, given finite instructions(and this computer can finally end algorithms).

 

 and a set $\Sigma$ of expressions is decidable iff there exists an effective procedure that, given any expression $\alpha$, will decide whether or not $\alpha\in\Sigma$.

 

3. axiomatiziability.

 

 a set of sentenes $T$ is a theory iff for any sentence $\sigma$, $T$ meets $T\models\sigma \rightarrow \sigma\in T$. roughly, theory is a set of sentences which is closed under implications. and consequences of $\Sigma$, $Cn\Sigma$ is defined as $\{\sigma | \Sigma \models\sigma\}$ where $\sigma$ is any sentence.

 Theory $T$ is axiomatizable iff there is a decidable set $\Sigma$ of sentences such that $T = Cn\Sigma$.

 

 

 

p.s. 설명하자면 definability는 집합기호 {x|x는 ~}에서 조건제시에 해당되는 부분입니다. 이것을 1차논리로써 표현가능하냐는 것이지요. decidability는 임의의 문장을 주었을 때 그 문장이 주어진 집합에 들어가냐 아니냐를 기계적으로 판단할 수 있는 절차가 있는지를 묻는 겁니다(즉, 컴퓨터가 할 수 있는 그런 알고리즘이 존재하는가의 문제). axiomatizability는 axiom의 뜻을 생각해보면 쉽습니다. theory T의 문장들을 모두 implication할 수 있는 어떤 결정가능한 집합이 있는가의 문제입니다. 가령 ZFC집합론의 모든 문장들은 ZFC의 공리들로부터 닫혀있고, 임의의 문장을 주었을 때 그 문장이 공리인지 아닌지를 판별할 수 있으므로 ZFC집합론은 axiomatizable하다고 할 수 있겠습니다.