2nd order logic 자체의 syntax가



1차 술어 논리의 문법에



다음 3가지 종류의 variable을 추가한다고 하네요.

  • A sort of variables that range over sets of individuals. If S is a variable of this sort and t is a first-order term then the expression t ∈ S (also written S(t), or St to save parentheses) is an atomic formula. Sets of individuals can also be viewed as unary relations on the domain.
  • For each natural number k there is a sort of variables that ranges over all k-ary relations on the individuals. If R is such a k-ary relation variable and t1,...,tk are first-order terms then the expression R(t1,...,tk) is an atomic formula.
  • For each natural number k there is a sort of variables that ranges over all functions taking k elements of the domain and returning a single element of the domain. If f is such a k-ary function variable and t1,...,tk are first-order terms then the expression f(t1,...,tk) is a first-order term.


한국어로는,


0. 주어진 모델의 원소를 의미하는 변수.

1. 주어진 모델의 원소들로 이루어진 집합을 의미하는 변수. S가 그런 변수이고, t가 1차 술어 논리의 term이라면, t∈S, S(t) 등으로 표현.

2. 주어진 모델의 원소들 k개의 순서쌍들로 이루어진 집합을 의미하는 k-ary 변수.  (I가 모델의 domain이면, I^k의 부분집합)

3. 주어진 모델의 원소들 k개의 모든 순서쌍들로 이루어진 집합에서 주어진 모델로 가는 함수를 의미하는 k-ary 변수. (I가 모델의 domain이면, I^k -> I로 가는 함수.)



가령, 실수 집합에서 Least upper bound property는 다음과 같이 공리화할 수 있다고 함.

(∀ A) ([(∃ w) (w ∈ A) ∧ (∃ z)(∀ u)(u ∈ A → u ≤ z)]

→ (∃ x)(∀ y)([(∀ w)(w ∈ A → w ≤ x)] ∧ [(∀ u)(u ∈ A → u ≤ y)] → x ≤ y))


A는 1번의 변수, u, w, x, y, z는 0번 변수.


그러면 A가 주어진 모델의 부분집합이기만 하면 됨.



2nd order logic은 relation들이 고정되어 있고, 그 relation에 대해서만 서술한다고 생각했는데, 크게 잘못 생각했음.


고정된 relation들은, 1st-order logic 관점에서 보면, 상수 기호 같은 것들이었고,

∀이나 ∃를 붙일 때는 그런 상수 뿐만 아니라 해당 변수에 넣어질 수 있는 모든 것들에 대해서 성립한다고 해석해야 되는 거였음.


2nd-order logic에서
∀B (∀n B(n)) 이라고 하면,
모든 unary-relation은 전체 집합이라는 얘기도 되면서, 주어진 모델의 부분 집합이 모델의 모든 원소를 포함해야 된다는 의미가 됨.

가령, unary relation이 P 하나 뿐인 2nd-order logic에서
모델을 전체 집합 I = { a, b, c}, P={a, b, c}라고 하면,
∀B (∀n B(n)) 를 만족해요. 하지만, I의 부분집합 {a, b}가 저 B 자리에 들어가면 거짓이 되므로, I는 ∀B (∀n B(n)) 를 만족하지 않음.