g(f,x)が存在しないことの証明

　f(x)=1のとき　g(f,x)=A　…(1)
　f(x)=0のとき　g(f,x)=B　…(2)

となるようなg(f,x)が存在しないことを背理法を用いて証明する。
g(f,x)が存在したとすると

　g(f,f)=Bのとき　h(f)=1　…(3)
　g(f,f)=Aのとき　h(f)=0　…(4)

となるようなh(f)を用いて

[1]h(h)=1のとき
(3)より　g(h,h)=B
g(h,h)=Bのとき、(2)より　h(h)=0
これはh(h)=1と矛盾するので、g(f,x)=Bは存在しない

[2]h(h)=0のとき
(4)より　g(h,h)=A
g(h,h)=Aのとき、(1)より　h(h)=1
これはh(h)=1と矛盾するので、g(f,x)=Aは存在しない

[1]、[2]より、g(f,x)は存在しない。



上記の証明に関して、何か問題はあるか？

No.3 回答者： stomachman 回答日時： 2013/09/15 09:14

ANo.2へのコメントについてです。

> その式が何を示すのかは分かりませんが、


　記号論理が使えないと、抜けのない証明を書くのは大変でしょう。ただの記法としてなら簡単に覚えられますから、勉強してみてはいかが？　ともあれ、
　　∀F∀h( ￢( ∀f(f∈F ⇒ f(f)∈{1, 0}) ∧ ∀f(f∈F ⇒ h(f) = 1-f(f)) ∧ h∈F) )
はこういう意味です：

任意のFについて、任意のhについて、
(以下のことは成り立たない：
　(
　　(任意のfについて、
　　　(fがFの要素であるならば、f(f)は1か0である)
　　)
　　かつ
　　(任意のfについて、
　　　(fがFの要素であるならば、h(f)はf(f)の1,0を逆にしたものである)
　　)
　　かつ
　　(hはFの要素である)
　)
)


> fとhの間にgを介在させると成り立たないことをそれを使って証明するという話なのかもしれません

違います。

　ところで、このご質問では f(f)というのがクセモノで、fを関数として、そして関数を作用させる対象として、2通りの意味に使っています。しかし、数学で言う関数の定義に従えば、f(f)は（既に説明した通り）意味をなしません。（この点についてよく理解するには、数学基礎論を少し勉強せねばなりませんが。）
　このような（fを関数として、そして関数を作用させる対象として、2通りの意味に使う）考え方は、（元々はカントールが発明した）「対角線論法」というもので、これは（チャーチやチューリングらの）決定不能定理や（ゲーデルの）不完全性定理の要諦にもなっている、重要な手法です。ただし、いきなりf(f)という訳にはいかない。そこをなんとかする工夫が「ゲーデル数」です。

　一方、ご質問のfは普通の数学の意味での関数ではない、という解釈も可能ではあります。もしそうなら「f(x)という記号が一体何を意味するのか」を定義してから話を始めなくてはならない。なのでその場合、しかももしご質問の「証明」がご自身によるものではないのなら、引用元にはその定義が書かれているはずです。

No.2 回答者： stomachman 回答日時： 2013/09/13 19:18

　対角線論法の勉強をなさってるんでしょうか。

ご質問の「証明」にはイロイロ問題があるんですが、ことに重要なポイントはと言うと：「ナニカが存在しない」という話をするためには、そのナニカが一体どういう範囲には存在しないのか、その範囲を明確にしなくちゃいけません。ともあれ、中身を見てみましょ。

　第一に、（既出の回答でご指摘のように）そもそもfって何者なのか。すなわち、fの集合Fが存在するのかどうか。
　fが普通の意味での関数で、その値域がNだとすると
　　∀f((f∈F) ⇒ (f: F → N))
ということであり、すると関数というもの一般の定義から明らかに
　　(f: F → N) ⇒ (f ∈ F×N)
なので
　　F ⊂ F×N
という変なことになる。これじゃダメっすね。なので、fは普通の関数ではないナニカである。ひと工夫が必要です。
　たとえば 「f(x)」ってのは実は f(z(x)) の略記であって、Qを有理数の集合、Zを整数の集合として、
　　f: Z → Q, f∈(整数の多項式)
　　z: F → Z, z(f) = (fのゲーデル数）
なのだ」ということだったなら、Fが確かにあるわけで、すると、ご質問の「証明」は「h∈Fだと仮定すると矛盾に至る。だからh∉Fだ」と言おうとしてるってことになります。（一方、Fが存在するかどうか不明のまま話を進めたなら、「h∈Fだと仮定すると矛盾に至る」ということから得られるのは「Fが存在しないか, h∉Fだ」という結論になりますね。）

　第二に、
> 　g(f,f)=Bのとき　h(f)=1　…(3)
> 　g(f,f)=Aのとき　h(f)=0　…(4)
とお書きなのも、hがナニモノなのかが不明なんで落第です。そこで
　「h(f) は　h: F→Q であって、
　　h(f) = もしg(f,f)=Bなら1, もしg(f,f)=Aなら0
　　となるもの」
という意味なのだと解釈したとしましょうか。これなら（もちろん(1)(2)も同様の意味だと思った上でですが）hが「ナンラカの関数」としてなら存在する、ということは心配しなくていい。しかし、もしFを(f:Z→Q)の集合であるということにしたのなら、h:F→Qなんだからh∉Fは自明です。これじゃまずいだろうから、たとえば「h(f)ってのも実はh(z(f))の事であって、だから本当はh:Z→Qなのだ」ってな事にでもしとかなくてはね。

　第三に、g(f,f)がAでもBでもない場合にはh(f)はどうなるんでしょうか？
(a) その場合にもしh(f)が1でも0でもない値しか取れないのなら、[1][2]だけでは場合分けを尽くしていない。だから最後の
> [1]、[2]より、
ってところがジレンマになっておらず、証明は誤り。

(b) その場合にもしh(f)が1か0の値を取れるのなら、h(h)=1のとき

> (3)より　g(h,h)=B
だとか、h(h)=0のとき
> (4)より　g(h,h)=A
とは言えず、だから証明は誤り。

　以上から、お書きの「証明」が意味をなすためには
　　∀f(f∈F ⇒ g(f,f)∈{A, B}), A≠B
という前提が不可欠で、ならばfも
　　∀f(f∈F ⇒ f(f)∈{1, 0})
でなくちゃならんでしょう。

　第四に、（これはモンダイという訳ではないが）gなんてものを介在させたために話が不必要に複雑になってませんかね。gを取り除いて以上を整理すると、（もちろん、f(x)だのh(f)だのが何を意味するかをはっきりさせた上で、ですが）定理
　　∀F∀h( ￢( ∀f(f∈F ⇒ f(f)∈{1, 0}) ∧ ∀f(f∈F ⇒ h(f) = 1-f(f)) ∧ h∈F) )
を証明する、という話なんじゃ？

この回答への補足

>　　∀F∀h( ￢( ∀f(f∈F ⇒ f(f)∈{1, 0}) ∧ ∀f(f∈F ⇒ h(f) = 1-f(f)) ∧ h∈F) )
>を証明する、という話なんじゃ？


その式が何を示すのかは分かりませんが、

　fが0か1を出力したら、その逆を出力するhが存在する

といった定理があり、fとhの間にgを介在させると成り立たないことをそれを使って証明するという話なのかもしれません（少し調べてみただけなので曖昧です）。

補足日時：2013/09/14 15:35

No.1 回答者： muturajcp 回答日時： 2013/09/13 13:57

fの定義域,

gの定義域,
hの定義域が定義されていないので
h(f)の存在が証明されていない
存在が証明されていないh(f)を用いることはできない

f(x)=1のとき　g(f,x)=A　…(1)
f(x)=0のとき　g(f,x)=B　…(2)
となるような
g(f,x)が存在したとすると

g(f,f)=Bのとき　h(f)=1　…(3)
g(f,f)=Aのとき　h(f)=0　…(4)

となるようなh(f)が存在すると仮定すると
それを用いて

[1]h(h)=1のとき
(3)より　g(h,h)=B
g(h,h)=Bのとき、(2)より　h(h)=0
これはh(h)=1と矛盾するので、
h(f)は存在しない

[2]h(h)=0のとき
(4)より　g(h,h)=A
g(h,h)=Aのとき、(1)より　h(h)=1
これはh(h)=1と矛盾するので、
h(f)は存在しない

[1]、[2]より、h(f)は存在しない。