すべての関数をもとめよ

質問

「以下の条件を見たすすべての関数を求めよ」みたいの問題で、「すべて」かどうかを証明するのってどうするのでしょうか
例えばx,yは自然数とし
1) f(x,x)=x
2)f(x,y)=f(y,x)
3)f(x,y)=f(x,x+y)
をみたすすべての関数を求めよというので、f(x,y)をx,yの最大公約数をあわらすかんすうとすれば条件をすべて満たすというのはわかるのですが、ほかの関数があるかもしれないというのはどうすればいいのでしょうか？

回答No.5

stomachman · ベストアンサー

唯一性を言いたいとき、「fとは別の解gがある」と仮定するとなんか矛盾が出ちゃう、というストーリーがよく使われます。fとgの比がいつも1だからf=g、fとgの差がいつも0だからf=g、f-g≠0なので(f-g)で何かを割り算するとへんてこなことが起こる。あるいは、{(x,y) | g(x,y)≠f(x,y)}が空集合である。
　ご質問の場合、f(x,y)が「x,yの最大公約数をあわらすかんすう」であると天下りに言う代わりに、数学的帰納法によって「解fはx,yの最大公約数をあわらすかんすうであって、しかも唯一である」を証明すればいいでしょう。つまり、既にANo.1で示唆してもらったようなユークリッドの互除法の帰納法による証明の中に、「しかも唯一である」を一緒に含めて書き直すだけ。
　「唯一である」の部分は、たとえば「与えられた連立関数方程式の任意の解f, gについて、∀x∀y(x＜n ∧ y＜m → g(x,y)=f(x,y))」と表しておいて、これを仮定して「任意の解f, gについてg(n,m)=f(n,m)」を証明すれば良い。

回答No.7

funoe

回答を閉じていないってことを待っている？と考えマメマメしく。

ＮＯ６さんご指摘のとおり、ｆの条件からｆ（ｘ、ｙ）はｘ，ｙの最大公約数でなければならない
ということが導ければ唯一性は議論の対象ではない。（存在性には言及要）

1)f(x,x)=x
2)f(x,y)=f(y,x)
3)f(x,y)=f(x,x+y)
ｆは、（ｘ、ｙ）∈Ｎ^2で定義されていることを前提にします。

ユークリッドの互除法が使いやすいよう、次のことを先に示しておく。

ｆ（ｘ、ｙ）
＝ｆ（ｘ、ｘ＋（ｙ－ｘ））　：ｘ＜ｙのとき、（ｙ－ｘ）なるＮの元が存在しこの変形が可能
＝ｆ（ｘ、ｙ－ｘ）　　　　　：条件３より、但し0＜ｙ－ｘのときのみ
＝ｆ（ｘ、ｘ＋（ｙ－２ｘ））
＝ｆ（ｘ、ｙ－２ｘ）　　　　：条件３より、但し0＜ｙ－２ｘのときのみ
＝・・・
＝ｆ（ｘ，ｙ－ｎｘ）　　：但し0＜ｙ－ｎｘのときのみ、「・・・」の部分は厳密には数学的帰納法

ｙをｘで割った商をｍ、余りをｒとすると
ｙ＝ｘｍ＋ｒ　であり、
ｆ（ｘ、ｙ）＝ｆ（ｘ、ｙ－ｍｘ）＝ｆ（ｘ、ｒ）　　//

＜＜ここからは、ユークリッドの互除法の手順で＞＞

いま、ｘ、ｙ∈Ｎ　に対し、互いに素なａ１，ａ２∈Ｎが存在し、
ｘ＝ａ１ｇ、ｙ＝ａ２ｇ　とおける。（ｇはｘ、ｙの最大公約数である。最大公約数の定義）

1）ａ１ｇ＝ａ２ｇのとき
ａ１＝ａ２＝１、ｘ＝ｙ＝ｇ　であり、このときｆ（ｘ、ｙ）＝ｆ（ｘ、ｘ）＝ｇ　となる。

2）ａ１ｇ＜ａ２ｇのとき
ａ２ｇをａ１ｇで割った商をｍ、余りをｒとする。
2-1）
ｒ＝０のとき
　ａ２ｇをａ１ｇが割り切ることから　（ａ２ｇ）／（ａ１ｇ）＝ａ２／ａ１　が整数。ａ２，ａ１が互いに素なので
　ａ１＝１　となる。
　このとき
　ｆ（ｘ、ｙ）＝ｆ（ｇ、ａ２ｇ）＝ｆ（ｇ、ａ２ｇ－（ａ２－１）ｇ）＝ｆ（ｇ，ｇ）＝ｇ
2-2)
ａ２ｇ＝ａ１ｇｍ＋ｒ　から
ｒ＝ａ２ｇ－ａ１ｇｍ　であり
ａ２ｇ－ａ１ｇｍ＝（ａ２－ａ１ｍ）ｇ＝ｒ
いま、改めてａ２－ａ１ｍ＝ａ３とおくと、ａ１とａ３は互いに素。
このとき
ｆ（ａ１ｇ、ａ２ｇ）＝ｆ（ａ１ｇ、ａ２ｇ－ｍａ１ｇ）＝ｆ（ａ１ｇ、ｒ）　であり、ｒ＝ａ３ｇ　（ａ１とａ３は互いに素）
となる。

3)ｘ＞ｙのとき
　条件２によりｘとｙを入れ替える。ｆの値は変わらない。

2)、3)のときは、先頭に戻りａの添字を増やしながら数列ａ１，ａ２，ａ３，ａ４，・・・を得れば
これは自然数の単調減少数列なので有限回数で　1)のａｉ＝ａ（ｉ＋１）が成り立ち、
当初与えたｘ、ｙについてのｆ（ｘ、ｙ）＝ｇ　：ｘ、ｙの最大公約数　となる。

－－－
ｆの条件から、ｆが存在するならその値は与えられた２数の最大公約数でなければならないことは
わかった。
逆に、ｇ（ｘ，ｙ）＝ｇｃｍ（ｘ、ｙ）　とおけば、ｇが上記３条件を満たすことは容易に確認できる。

－－－
以上より、ｆ（ｘ、ｙ）＝ｇｃｍ（ｘ、ｙ）　である。

回答No.6

alice_44

x=gm, y=gn (mとnは互いに素)と置き、
(1)(2)(3)に沿って計算すれば、
f(x,y)=g が示せます。
計算は、互除法の手順に従えばいい。
他の関数も何も、f の値が判ってしまう
のですから。

回答No.4

noname#221368

他人の褌で相撲を取ります・・・。

　関数定義の一意性の問題は、関数fの具体的形とか、fは最大公約数などという意味を先に与えておいて、それならばfは、1)，2)，3)という性質を満たすとやっておいて、逆にfが1)，2)，3)を満たせば、fの具体的形は最初に与えたものか、最初に与えて意味しかありえない、とやりますよね？。要するにWelldefined性（ちゃんと定義できる事）の証明の中で、良く見かけます。

　典型的例は、行列式の公理的（形式化された）定義です。そこでは、行列式の多重線形関数としての性質だけを用いて、行列式の具体的形を定めていったら、置換を利用した行列式の具体的表現に達してしまった、という証明をします。この場合、行列式という関数の形式化された性質だけから、具体的数式が定まってしまうので、一意性の証明は不要になります。

　以上の手順で具体的形が定まっても、具体的形が未定定数などを含んでいて、一意性の証明が必要な時だけ、一意性の証明を別途行います。ただしその時も、1)，2)，3)に従ったら、未定定数を含んだ具体的形（意味）はこれしかないから、もう一個1)，2)，3)を満たすg(x，y)があったとして、g(x，y)の具体的形（意味）も同じだから、そこに1)，2)，3)を適用したら、未定定数などは一個に定まり、f(x，y)＝g(x，y)になるよ、とやるのが普通です。つまり、1)，2)，3)に従って、fの具体的形を先に定めるのが、基本です。

　今の場合で言えば、f(x，y)＝g(x，y)を示すだけなら、1)，2)，3)の性質から、任意の自然数の組(x，y)に対してf(x，y)の値は、具体的に全部計算できますよ、というのが#3さんの言ってる事だと思います。gは同じ1)，2)，3)を満たすのだから、当然f(x，y)＝g(x，y)で、f＝gですよね？と。#3さんの応えの・・・の後は、自力でおやりなさいと。

　#3さんの計算手順を言葉で述べてくれたのが、#2さんだと思います。

　もしかすると、もう少し一般的ケースでの質問かも知れませんが、少なくとも1)，2)，3)の例では、Welldefined性の証明になってしまい、この場合は一意性の証明は不要です。

　関数や計算手順を公理化（形式化）する目的を考えてみて下さい。それは、性質1)，2)，3)なんかがあると、関数や計算を具体的に行わなくても、色々な結果を予想できるからです。「それで良いのだ」という事を保証してくれるのが、Welldefined性の証明で、その証明は形式化された性質が、具体的計算手順などを導けるかどうかを確認するのが目的です。なので、1)，2)，3)からfの具体的形や意味を、まっさきに計算してみせる事が先決です。その目的で公理（形式化された性質）は、選ばれています。

回答No.3

hugen

1=f(1,1)=f(1,2)=f(1,3)=・・・
2=f(2,2)=f(2,4)=f(2,6)=・・・
f(2,3)=f(2,5)=f(2,7)=・・・=f(2,1)=f(1,2)=1

回答No.2

ringohatimitu

まずこの場合は「ユークリッドの互除法」から最大公約数が求めるfですね。
以下それを簡単に示します。
x＜yとします。
y=qx+rと余りを計算すれば、3)からf(x,y)=f(x,r)です。
次にx=q'r+r'と余りを計算すれば、2)と3)からf(x,r)=f(r,x)=f(r,r')です。
この操作を続けていけばやがて余りが0となるときがやってくるでしょう（まさにeuclidean algorithmですね）。そのとき、1)からその商がfの値となるので結局x,yの最大公約数となるわけです。

一般にある特殊な関数が条件を満たすことが分かってもそれが唯一のものかどうかの判定は難しいです。
未解決問題にもそういった類のものはたくさんあります。
基本は個別に調べていくことです。満たすべき性質に着目する。
例えば、自然数で与えられている条件なら帰納法で何とかなるかもしれないし、実数で与えられている条件なら連続性とか利用すれば一意性を言えるかもしれません。
どのケースでも大事なのは与えられた性質から出来るだけ多くの事実を導き出すことです。
これによってある程度形を決めることは出来るはずです。
あまり多くの事実を期待できない場合は逆に他の関数を探すきっかけになるでしょう。

回答No.1

funoe

なるほどーー。ユークリッドの互除法の定式化なんですねぇ。
確かに、「最大公約数を求める関数」ですね。

互除法は、「割り算して余り」を求めますが、この式は「割る数を何回か引き算する」ことで
同じ意味になっているんですね。

「ユークリッドの互除法　証明」でググれば、あなたの求める解答が得られます。

厳密に書き下すには数学的帰納法。
（自然数論では数学的帰納法以外の証明手段なんて事実上ないですから）

お礼

回答ありがとうございます。　ユークリッドの証明ではなくて、問題の条件をみたす関数がユークリッドの互除法の形式化以外にないことの説明のしかたです。。。