불완전성 정리

위키백과 ― 우리 모두의 백과사전.

괴델의 불완전성 정리(Gödel's incompleteness theorems)는 1931년 쿠르트 괴델이 증명한 두 개의 정리로, 자연수를 포함하는 수학의 형식화에 대한 한계를 증명했다. 정리에 따르면, 자연수의 이론을 포함하며 모순이 없는 모든 공리계에는 참이지만 증명될 수 없는 명제가 존재하며, 또한 그 공리계는 자신의 무모순성을 증명할 수 없다.

이 정리는 수학의 체계를 완전하고 모순이 없는 공리계로 형식화하려는 힐베르트의 계획의 실패를 알리는 것으로 인식된다. 보다 구체적으로는, 이는 힐베르트의 두번째 문제에 대한 부정적인 해답으로 볼 수도 있다.

제1 불완전성 정리

괴델의 제1 불완전성 정리의 내용은 다음과 같다:

산술적으로 참인 명제를 증명할 수 있는 임의의 무모순인 계산가능한 가산 이론에 대해, 참이지만 이론 내에서 증명할 수 없는 산술적 명제를 구성할 수 있다. 즉, 산술을 표현할 수 있는 이론은 무모순인 동시에 완전할 수 없다.

여기에서 "이론"은 명제들의 무한집합으로, 여기에 속하는 것들 중 일부는 증명 없이 사실인 것으로 취급되는 공리이며 나머지는 공리들로부터 유도되는 정리이다. "(이론 내에서) 증명할 수 있는" 명제란 공리에 1차 논리를 적용하여 유도될 수 있는 것을 말한다. 이론 내에서 모순된 명제가 증명될 수 없을 경우 이를 무모순이라 한다. "구성할 수 있다"는 것은 이론 내에서 해당 명제를 실질적으로 제시할 수 있는 과정이 존재함을 말한다. 또한 여기에서 "산술"은 자연수의 덧셈과 곱셈만으로 이루어져 있으며, 이 정리의 결과로서 존재하는 참이지만 증명 불가능한 산술적 명제를 해당 이론의 "괴델 명제"라 한다.

제2 불완전성 정리

괴델의 제2 불완전성 정리의 내용은 다음과 같다:

공리로부터 출발한 산술체계가 무모순인지의 여부 자체가 참 또는 거짓인지 결정할 수 없다.

x=0:0.01:10;
y = exp(-0.5*x).*sin(5*x);

%그리기
plot(x,y)

%선만 바꾸어 그리기.
set(plot(x,y), 'LineStyle','--')

%점만 그리기
plot(x,y,'+')

plot(x,y,'r-.', x, y, 'ob')

axis([4,8,-0.3,0.3])

grid on   % grid만으로 토글 가능

xlabel('x');
ylabel('y');
title('aslkdfjasdfj');

print -dbimap ex1.bmp

% 그냥 plot과 별다를게 없지만 분할만 해준다.
subplot(221); % 이 때까지는 사분면에서 그림은 하나만그려짐.
subplot(222);
subplot(2,2,2);
subplot(223);
subplot(224);

% pi는 상수..
>> t=0:0.1:100;
>> x=1+0.5*exp(-0.05*t).*sin(t+pi/2);


x1=0:0.1:10;
y1=x1.^2 + 1;
x2=0:0.1:10;
y2=sin(sqrt(x2))./exp(x2)
plotyy(x1,y1,x2,y2)

t=0:900; A=1000; a=0.005; b=0.005;
z1=A*exp(-a*t);
z2=sin(b*t);
[haxes,hline1,hline2] = plotyy(t,z1,t,z2,'semilogy','plot');
axes(haxes(1))
ylabel('Semilog Plot');
axes(haxes(2))
ylabel('Linear Plot');
set(hline2,'LineStyle','--')

x=0:0.1:10;
y1=cos(x);
y2=1+cos(x);
y3=2+cos(x);
y4=3+cos(x);
plot(x,y1,'g-',x,y2,'b--',x,y3,'r:',x,y4,'k-.')

t=0:1:10;
x=0.5*exp(-0.5*t).*sin(t+pi/2);
plot(t,x,'b-.diamond');

%다음 두 문장은 색상과 선 타입만 빼고는 같다
plot(t,x,'b-.o');
plot(t,x,'-r',x,y,'ok');

% 그래프 겹붙일때 둘 사이에 넣는다
hold on
hold off

x=0:0.01:10;
y=exp(-0.5*x).*sin(5*x);
plot(x,y)
v=[0,6,-0.2,0.6];
axis(v)
v=[0,2,4,6,8,10];
set(gca,'xtick',v);    % change only tick, not scale
v=[-1.0,-0.5,0,0.5,1.0];
set (gca,'ytick',v);


t = linspace(0,2*pi,30)
x1=sin(t);
x2=cos(t);
plot(t,x1,'b-', t, x2,'r--')
legend('sin','cos');
text(1.5,0.5,'x1=sin(t)\rightarrow');
% 반드시 마우스로 클릭할것..
gtext('\ite^{i\omega\tau} = cos(\omega\tau)+i sin(\omega\tau)')

linspace(0,300);    % 자동으로 100개 value 생성
x=sin(t);
y=cos(t);
plot3(x,y,t);
xlabel('sin(t)');
x=-7.5:.5:7.5;
y=x;
[X,Y] = meshgrid(x,y);
R=sqrt(X.^2+Y.^2)+eps;
Z=sin(R)./R
size(Z)
mesh(X,Y,Z);
colorbar;

surf(X,Y,Z) % replace with meshc, surfc, pcolor
shading flat
contour(X,Y,Z,20);   % 등고선 20줄로 나눠 표현
contour(X,Y,Z,20.1); % 특 정 값에 대한 등고선 한줄.

[C,h] = contour(Z,10);
clabel(C,h) % 등고선 마다 값을 그래프에 직접 찍어준다.

[C,h]=contour3(X,Y,Z,20);
%% h =findobject('Type','patch'); % alternative
set(h,'LineWidth',2);

mesh(peaks(20)+7)
hidden off
hidden on


>> figure
>> Z=peaks;
>> caxis([-20 20]); % contour axis??