일계논리의 긴밀성과 Löwenheim-Skolem 정리

긴밀성 정리와 Löwenheim-Skolem 정리는 일계논리에서 핵심적인 역할을 하는 정리이다. 이들 두 정리는 모두 Gödel의 불완전성 정리로부터 나온다. 여기서는 Gödel의 불완전성 정리를 도입하는 대신 긴밀성 정리와 Löwenheim-Skolem 정리의 증명을 간략하게 살펴보기로 한다. 또한 이 글에서는 일계논리언어가 가산인 경우로 논의를 한정한다. 정리 1.  일계논리의 긴밀성. \(\varSigma\)가 가산인 일계논리언어의 문장의 모임이고 \(\varSigma\)의 임의의 유한부분집합이 모델을 가지면 \(\varSigma\)도 모델을 가진다. 증명. 완전성… Read More »

일계논리의 건전성과 완전성

일계논리언어 \(\mathcal{L}\)에서 논리식 \(\phi\)가 논리적으로 유효하다(logically valid)는 것은 임의의 \(\mathcal{L}\)-구조 \(M\)과 \(M\)에서의 임의의 값매김에 대하여 \(\phi\)의 값이 \(\mathrm{T}\)가 되는 것을 의미한다. 만약 \(\phi\)가 문장이면 \(\phi\)의 참거짓 여부는 값매김에 영향을 받지 않고 오직 구조에 의해서만 결정된다. 그러므로 다음을 얻는다. 문장 \(\phi\)가 논리적으로 유효할 필요충분조건은 임의의 \(\mathcal{L}\)-구조 \(M\)에 대하여 \(M \models \phi\)인 것이다. 위 정리에 의하면, 논리식 \(\phi\)가 논리적으로 유효하지… Read More »

일계논리의 추론규칙

일계논리의 형식계는 명제논리와 마찬가지로 알파벳(alphabet), 공리(axioms), 추론규칙(rules of inference)으로 이루어져 있다. 추론규칙은 유한 개의 논리식을 입력받아 하나의 논리식을 출력하는 규칙이다. 증명(proof)이란 논리식의 유한열이다. 이때 증명의 각 줄은 공리이거나 또는 앞에 나타난 줄에 추론규칙을 적용하여 얻어지는 것이다. 증명의 마지막 줄을 정리(theorem)라고 부른다. 더 일반적으로, \(\varSigma\)가 논리식의 집합일 때, \(\varSigma\)로부터의 \(\phi\)의 증명이란 논리식의 유한열인데, 이때 증명의 각 줄은 공리이거나, \(\varSigma\)에… Read More »

일계논리의 의미론

일계논리의 구문론을 소개하면서 일계논리에서 사용하는 기호에 'not', 'if and only if', 'for all'과 같은 이름을 붙였다. 이것은 구문론에서 비록 의미를 부여하지 않은 기호의 나열을 논하지만, 실은 그러한 기호로 이루어진 문장이 어떠한 의미를 갖는지를 방법을 암시한 것이다. 이 글에서는 그러한 방법을 명확하게 밝힌 의미론(semantics)을 살펴본다. \(\mathcal{L}\)-구조 \(\mathcal{L}\)이 일계논리언어라고 하자. \(\mathcal{L}\)은 그것이 가지고 있는 관계기호, 함수기호, 상수기호에 의하여 완전히 결정된다.… Read More »

일계논리의 구문론

일계논리란 간단히 말하면 명제논리의 체계에 한정기호를 추가하여 확장한 것이다. 논리체계에 한정기호를 추가함으로써 명제논리에서는 다루지 못하였던 수학의 다양한 체계를 일계논리에서 다룰 수 있게 된다. 명제논리와 마찬가지로 일계논리에 대하여 논할 때에도 구문론과 의미론을 생각할 수 있다. 여기서는 일계논리의 구문론을 살펴보자. 일계논리언어 수학에서 '일계논리'를 적용하여 설명할 수 있는 분야는 여러 가지가 있다. 그리고 각각의 분야는 그 분야 고유의 일계논리언어를 가진다. 수학에서… Read More »

Christina’s World

크리스티나. 그는 멀리 떨어진 집을 향하고 있지만 실제로 그의 시선이 어디를 향해 있는지, 그가 어디로 가고자 하는지, 어떤 생각을 하고 있는지는 알 길이 없다. 비틀어진 몸과 앙상한 팔, 헝클어진 머리, 황량한 벌판. 지나치게 사실적이면서도 지나치게 비현실적인 이 그림에서 나는 나를 보았고, 당신을 보았다. 익숙한 것들로 가득하지만 익숙하지 않은 공간. 손에 잡힐 듯이 가까워 보이지만 결코 닿을 수 없는… Read More »

Chatting Functions

The functions are sitting in a bar, chatting (how fast they go to zero at infinity etc.). Suddenly, one cries "Beware! Derivation is coming!" All immediately hide themselves under the tables, only the exponential sits calmly on the chair. The derivation comes in, sees a function and says "Hey, you don't fear me?" "No, I am e to… Read More »

도함수가 자기 자신과 같은 함수

지수함수 \(y = e^x\)의 도함수를 구하면 \(y ' =e^x\)으로서 도함수가 자기 자신과 같다. 그렇다면 도함수가 자기 자신과 같은 함수는 이 외에 어떤 것이 있을까? \(f : \mathbb{R} \to \mathbb{R}\)가 임의의 실수에 대하여 미분 가능하고 \(f ' (x) = f(x) \tag{1}\) 를 만족시키는 함수라고 하자. 이 식의 양변에 \(e^{-x}\)을 곱하고 우변을 좌변으로 이항하면 다음을 얻는다. \(e^{-x} f ' (x)… Read More »

\(e^{\pi}\)과 \(\pi^e\)의 크기 비교

실수계에서 덧셈과 곱셈에 대해서는 교환법칙이 성립하기 때문에 더하는 순서나 곱하는 순서에 상관 없이 그 결과는 일정하다. 즉 임의의 실수 \(a , \) \(b\)에 대하여 \(a+b = b+a , \quad ab = ba\) 가 성립한다. 그러나 거듭제곱의 경우에는 교환법칙이 성립하지 않는다. 예컨대 \(2^3 \neq 3^2\) 이다. 위 식에서와 같이 \(a\)와 \(b\)가 정수인 경우에는 \(a^b\)와 \(b^a\)의 크기를 비교하는 것이 크게… Read More »

비 내리는 소리

비 내리는 소리 손에 잡힐 듯한 소리 빗방울 다가오는 소리 빗줄기가 하늘에서 땅까지 이어져 있다면 장마철 빗줄기를 몇 웅큼 썰어다가 빗방울 옷을 지어야겠다 빗줄기가 씨실 날실이 되어 부끄러움을 감추고 치마 끝에는 동그란 빗방울이 반짝반짝 달리겠다 빗방울 옷을 입고 동네를 한 바퀴 돌면 무지개가 뜨겠지? 땀방울 모자 쓰고 있던 어머니 얼굴에 미소가 뜨겠지? 비 그치는 소리 빗방울 멀어지는 소리… Read More »