(注意)
ここに書いていることには間違いが含まれている可能性が多分にありますので，ちゃんと知りたい方は他も参考によく調べましょう.
あとレイアウトをまったく考量していないので非常に見づらいとは思いますが勘弁してください．そのうち気が向いたり要望があったら直すかもしれません.
なにかお気づきの点など有りましたらtwitterで@pukka_TiMあてにリプライを飛ばしてくださると幸いです．
ゲーデルの不完全性定理とは無矛盾系(矛盾を許さない論理系)ではある論理式もしくはその否定のどちらも証明可能ではないような論理式が存在するというものです．
ではその証明をやってみましょう．
論理式の列
R[0],R[1],.....
があるとします．
論理式は有限個の記号の列であると考えられるので，たかだか加算無限個しかないと言えます．ということは上のように順番に並べる事が出来ます．
上の場合では[]の中の数字が何番目の論理式であるかを表していることにします．
また，これらの論理式は1変数の論理式だとします．つまりそれぞれ一つ引数をとるものとします．
それを以下では
R[0](1)のように()の中に引数を書くものとします．
普段見慣れたf(1)の形で例えればfがR[0]の部分，(x)が(1)の部分に対応しています．
さらに次のような集合Kを定義します．
n∈K ←→ ¬Prove(R[n](n))-----(1)
Proveというのはその論理式が証明可能であるかどうかという論理式とします．
そして
x∈K ←→ R[q](x)-----(2)
とします．これはR[q](q番目の論理式)がx∈K(xが変数)であるとする，ということです．
ではR[q](q)という論理式がもしくはその否定が証明可能か考えてみましょう．
とりあえずどちらかが証明可能だと仮定してみます．それは上で出てきたProveを用いれば表せます．
Prove(R[q](q))
Prove(¬R[q](q))
R([q](q))が証明可能ということはそれが成り立つということです．つまり(2)から
Prove(R[q](q))←→q∈K
否定の場合は逆に成り立たないことが証明可能なので
Prove(¬R[q](q))←→¬(q∈K)
であることが分かります.
さらに(1)からそれぞれ次のように言えます・
q∈K ←→ ¬Prove(R[q](q))
¬(q∈K) ←→ Prove(R[q](q))
これらをすべて繋いで書くと
Prove(R[q](q)) ←→ q∈K ←→ ¬Prove(R[q](q))
Prove(¬R[q](q)) ←→ ¬(q∈K) ←→ Prove(R[q](q))
となります.上は証明可能と仮定したのに証明出来ないと出ますし，下は否定が証明可能と過程したのに否定ではないものが証明可能と出ました．
明らかに両方とも矛盾していますのでR[q](q)もしくはその否定が証明可能という過程が間違っていることになりますね．
つまりこのどちらとも証明できない，という事になります．
これで無矛盾系ではある論理式とその否定の両方が証明出来ない物が存在するという事が証明されてしまいました．
まぁ記号ばかりのではあまりよくわからないかもしれません．という事で分かりやすい例を一つ
「私は嘘つきである」
という言葉．これも論理式に出来るものです．
しかしもし本当に嘘つきなら上の事は嘘になりその人は正直者という事になります．
逆に嘘つきでないとすると上の事は本当になるので嘘つきであるということになりますが，結論と仮定が矛盾します．