9.

완전성(Completeness)


 

우리는 대수에서 입증 가능한 귀결은 산술 관련 증명 가능한 정리를 지시해야 한다는 점을 보았다. 이러한 방식에서, 대수에서 귀결들은 산술의 속성들을 나타내고 있다고 말해질 수 있다. 특히, 그것들은 방정식의 형식으로 표현할 수 있는 산술의 속성들을 나타내고 있다.

   우리는 대수가 이들 속성들에 대한 완전한 설명인지 아니면 단지 부분적 설명인지 의구심을 가질 수 있다. 말하자면, 산술 관련 정리로 증명될 수 있는 모든 방정식 형식들이 대수에서 귀결들로 입증될 수 있느야 그럴 수 없느냐 하고 물을 수 있다.

 

정리 17  완전성(Completeness)

   일차 대수는 완전하다.

   말하자면, α = β 가 일차 산술 관련 정리로 증명될 수 있다면, 그때 이 방정식은 일차 대수에서 α, β 모두에 대한 귀결로 입증될 수 있다.

   우리는 이 정리를 귀납으로 증명한다. 우리는 먼저 α = β 의 모든 경우들이 구별된 변수들의 양의 수 n 이하로써 대수적으로 입증될 경우, 그렇다면, n 개의 구별된 변수들로 이루어진  α = β 가 있다는 것을 보인다. 이때 우리는 n 개 이하 변수들의 경우들에서 완전한 입증가능성의 조건은 실상 n 에 대한 양의 값을 유지하는 것임을 보인다.

 

증명

   n 개 이하의 일단의 구별된 변수들을 포함하는 등가 α, β 모두에 대해, α = β 의 입증가능성은 확립되어 있다고 가정한다.

   주어진 등가, α, β 는 n 개의 구별된 변수들 사이에 포함되도록 한다.

 

절차   주어진 α, β 를 그것들의 규준 형식, 말인즉, 변수 v 에 관한 α´, β´로 환원하라.

   우리는, T14 와 T15 의 증명들에서, 이러한 환원은 대수적이기에 α = α´, β = β´ 모두 입증가능하다는 것과 이 과정이 진행되는 동안 그 어떤 구별된 변수도 추가되지 않는다는 것을 알고 있다.

   T15 에 따라, 우리는 α 의 규준 형식은 , β 의 규준 형식은 으로 가정할 수 있다. 그러므로,

   

그리고

  

는 모두 입증가능한 것들이다. 그래서, 우리가 아직

                

가 입증 가능한지 아닌지 모를지라도, 이것은 참이다. 그러나 v 에 대해 상수 값들을 대입함으로서, 우리는

임을 알 수 있다.

이제, E3, E4 는 각각, 기껏해야 n - 1 개의 구별 변수들을 갖기에, 가설에 따라 입증될 수 있다. 그러므로, E1~4 는 모두 입증 가능하며, 그래서 우리는

          

            

 를 입증할 수 있다.

따라서, α = β 는, n 개 이하 변수로 입증 가능하다는 조건에서, n 개 변수로 입증 가능하다.

   아직 남아 있는 것은, α = β 가 n 개 이하 변수로 모든 α, β 등가에 대해 입증 가능하면 양의 n 값이 존재한다는 것을 보여주는 것이다.

   그 조건은 n = 1에 대해 증명하는 것으로 충분하다. 그래서 우리는 α = β 가 어떤 변수도 함유하지 않는다면 그것은 대수에서 입증 가능하다는 것을 보일 필요가 있다.

   α, β가 어떤 변수도 함유하지 않는다면, 그것들은 일차 산술에서 표현들로 간주될 수 있다.

   우리는 T1~4의 증명들에서 모든 산술 방정식들은 산술에서 입증 가능하다는 것을 보았다. 남은 것은, 그것들이 대수에서 입증 가능하다는 것을 보이는 것이다.

   C3에서 이면

              인데

이것은 I1 이다.

   C1에서  이면

                         인데

이것은 I2이다.

   따라서, 산술의 초기들은 대수에서 입증 가능한 것들이며, 그렇기에, α = β 가 어떤 변수도 함유하지 않는다면 이것은 대수에서 입증 가능하다.

   이것으로 증명은 끝난다.