불완전성 정리

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

괴델의 불완전성 정리(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??

1. Beginnings of Genetics: From Mendel to Hitler
• 키워드: heredity, mendel, pangenesis(정자 내부에 인체의 미니어쳐가 존재한다는 이론), genes, Sutton-Bovery theory, fruit flies, eugenics(우생학, 우수한 유전자만 남겨 인류를 개량해야한다는 것)
• Eugenics vs Genetics
• dominant: 우성의, recessive: 열성의
2. The Double Helix : This is Life
• 키워드: what is life, Pauling's alpha-helix, helix, structure of DNA, chemical backbone of DNA
• 주된 실험 그룹: Avery's Group
• Pneumococcus: pneumonia의 bacterial agent
• has sugarlike coats
• transforms (R->S) by DNA
• alpha-helix - chains of amino acids foldup in proteins
• Adenine (T와 결합)
• Thymine (A와 결합)
• Guanine (C와 결합)
• Cytosine(G와 결합)
• unzipping idea for DNA replication
• replication 이 일어난 직후 두 strand중 하나는 heavy하고 하나는 light하다
• DNA에 유전정보가 있는지는 어떻게 알았을까? -> avery 이후에도 확신 못함. but...?
• Schrodinger는 life가 생물정보의 저장과전달로 설명된다고 주장하였다.
• avery의 발견 : DNA가 transform의 factor
• 저자가 alpha helix영향받음-> 3-chain이 아니라 2-chain임을 발견 (이것이 돌연변이도 설명한다, 3개 단위의 돌연변이만이 유독 변형을 일으키지 않았다, unzipping에 대한 증거도 발견)
3. Reading the Code : bring DNA to life
• protein - a string of amino acids
• triplet code
• transfer RNA (specific RNA adaptor, 리보솜과 붙어 필요한 아미노산 운반해준다)
• messenger RNA - DNA정보를 읽어 복사한 부분
• ribosomes (molecular factory) - messenger RNA를 스캔하면서 이에 맞는 단백질 형성
• DNA에 의해 amino acid가 어떻게 결정되는가?
• DNA vs RNA -> RNA에서는  T 대신 U 사용
• process for generating protein, gene switch
• RNA가 DNA이전에 나타났으므로 RNA mediate가 단백질 생성 과정에 필요한 것이다.
4. Playing God : Customized DNA Molecules
• 키워드: viral DNA, DNA-cutting, plasmid, sequences, cloning a gene, SV40, safe bacteria, legislation, politics, sanger method, introns / exons
• recombinant DNA tech.
• supporting technology & foundings
• DNA polymerase: DNA열릴 때 이를 복사해 주는 enzyme
• plasmid: DNA 내부의 small loops. 박테리아 안에서 복제된다.
• restriction enzyme : cuts DNA
• cloning DNA w/ plasmid - 구체적 방법 설명
• 법적 문제
• Sequencing
• break DNA chains for inferring sequence
• ddA, ddT, ddG, ddC를 이용하여 자른다.
• 전기충격으로 이들이 무게(길이)에 따라 정렬되게 하면 이를 분석가능하다
• Introns vs Exons
• intron - 단백질 생성에 직접 연관되지 않는 부분, 진화 과정에서 퇴화된 부분일 수 있다.
• exon - 단백질 생성에 직접 연관하는 부분, messenger RNA에서 edit단계를 거칠때 이것만이 남겨지고 intron은 제거된다.
5. DNA, Dollars, and Drugs : Biotechnology
• insulin : the first commercial biotech.
• reverse transcriptase (made insulin-selling possible), human-made micro-organism is patentable subj.? (it took 8 years to the answer yes)
• reverse transcriptase: an enzyme that does "mRNA -> DNA"
• p4 containment facility : 완전 봉쇄된 시설 for biomedical research, 그 당시 이러한 시설은 매우 희귀했다.
• 두번째 부흥 - chemical messengers (neurotransmitters, hormones, and growth factor - 세포 증식 촉진제)
6. Tempest in a Cereal Box : Genetically Modified Agriculture
• against bugs, weeds, disease on plants, Agrobacterium, seed business, oppositions
7. The Human Genome: Life's Screenplay (시나리오)
• Human Genome Project에 대한 이야기들, 진행과정과 상업화
• PCR : Polymerase Chain Reaction, 원하는 유전자 부분만 골라서 증식 가능하게 한다.
• (1) 95 degree celsius, two strands come apart ( =   -> 二 )
• (2) add primer (원하는 유전자가 있는 곳에 달라붙는다)
• (3) add polymerase (복사 시작)
• sequencing은 예전의 방법을 그대로 사용한다.
• polymerase : DNA의 complementary로 pair를 생성하는 enzyme
8. Reading Geomes: Evolution in Action
• intron을 파악하는 것은 쉽지 않을 일
• different gene-density
• gene-family : human과 mouse사이의 DNA유사성을 발견
• 진화하면서 유전자의 특정 부분이 intron화 되어감, ex) 인간의 후각기능 감소, mouse와 후각 기능 부분 DNA가 비슷하지만 사람은 더 많은 부분이 intron으로 되어있다.
• mobile genetic elements: genetic seq.의 증식, 복제 등을 가능케한다. 여기저기 점프한다.(진화과정에서? 아니면 증식과정에서?)
• 박테리아 DNA분석 등을 통해 진화론은 신뢰를 얻어만 가고...
• 개인질문: gene vs DNA : gene은 intron과 exon을 포함하여 단백질 생성에 관여하는 하나의 기능적인 단위를 말하는 것 같다.
9. Out of Africa : DNA and the Human Past
• 인류는 Africa에서 시작되었다. (mitochondrial DNA 분석결과)
10. ... 별로 안중요하다고 생각함
11. ... 별로 안중요하다고 생각함
12. ... 별로 안중요하다고 생각함
13. ... 별로 안중요하다고 생각함