• ベストアンサー
  • 困ってます

全順序集合と半順序集合

x=(x1,…xn) , y=(y1,…,yn) ∈R^n に対して x≦yを Σ(i=1からkまで)x(i) ≦ Σ(i=1からkまで)y(i) (k=1,2,…,n) によってR^nに関係≦を導入する。 R^nはこの≦に関して半順序集合になっていることを示せ。 また、x≦(にならない)y , y≦(にならない)x となるx,yの例をあげよ。 という順序集合の問題です。 反射的・反対称的・推移的の3つを示せば良いのは分かるのですが、どのように書いて良のか分かりません。 例:推移的を示す 任意のx=(x1,…xn) , y=(y1,…,yn) , z=(z1,…,zn) ∈R^n に対して Σ(i=1からkまで)x(i) ≦ Σ(i=1からkまで)y(i) かつ Σ(i=1からkまで)y(i) ≦ Σ(i=1からkまで)z(i) ならば Σ(i=1からkまで)x(i) ≦ Σ(i=1からkまで)z(i)  は成り立つ。 このように、そのまま書けば良いのでしょうか・・・? それから、最後の例をあげよのところは、全順序集合にはならないための反例になっているのだと思いますが、どうしても思いつきません。 ∞を考えるのでしょうか・・・? そもそも全順序集合は半順序集合が成り立つことが前提みたいに習いましたが、反対称的の 任意のa,b∈Xに対して aRb,bRa⇒a=b ここで、aRbとbRaが成り立つことを言ってしまっているので、必ずaRbかbRaになっているような半順序集合は全順序集合という定義も意味がないような気がしてしまいます。 よろしくお願いします。

共感・応援の気持ちを伝えよう!

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.6
  • old_sho
  • ベストアンサー率38% (20/52)

まだまだ、道は険しそうですが、定義の確認が不充分なようです。再度、 この問題にある、順序 ≦ は、R^nにおいて定義されています。その順序と R^nとをあわせて、{ R^n, ≦ }と書いて、順序集合と呼びます。そしてそれは、半順序集合です。全順序集合ではありません。 ーー以上の事を示すのが問題ですよね。 まずすべき事は、その ≦ の定義にもとづいて、それが、順序に関する3つの性質を持っている事を示さなければなりません。 ---ということは、この段階ではまだ、半順序集合とも、全順序集合とも決まっていないわけです。 1)任意のx=(x1,…xn) ∈R^n に対して Σ(i=1からkまで)x(i) ≦ Σ(i=1からkまで)x(i) (k=1,2,…,n) は明らかに成立する、よって x ≦ x 2)x=(x1,…xn) , y=(y1,…,yn) , z=(z1,…,zn) ∈R^n において x ≦ y かつ  y ≦ z であるとするならば、 ---ここから、あの ≦ の定義式を持ちだして証明を始めるのです。「任意の」ということばを使っていませんが、仮定法を使っているので 、文字を使ってx ≦ y 、 y ≦ z という関係のみを使って記述すれば、その関係を満たす任意のものに対する証明になります。 ---また、ここからが肝心な所で、人によって書き方が異なるでしょう。ガンバッテ! …… …… 故にx ≦ z ---と締める事が出来れば終わりです。 3)x=(x1,…xn) , y=(y1,…,yn) ∈R^n において x ≦ y かつ y ≦ x ならば ---ここも、「任意の」ということばを使っていません。一つ例を書いてみますと、 x1≦y1かつ y1≦x1であるから、 x1=y1 …(1) x1+x2 ≦ y1+ y2 かつ y1+y2 ≦ x1+ x2 であるから、x1+x2 = y1+ y2 …(2) ---以下同様と言うわけですが、これも工夫した書き方があるでしょう。 故にx=y よって「≦」は順序である。---と、ここまで来ればよいのですが。 以上で示したのは、「≦」 が順序であると言う事です。これだけで半順序集合である事は証明されています。半順序集合であるが、それは全順序集合ではない事を示せ、というのが、反例を示せと言うことです。この順序の定義では大小を示す事が出来ない例を一つ示せば、任意のx,yに順序がある「全順序集合」ではないことが、証明されるのです。 以上。一寸おせっかいかなと思いつつ書いてみました。

共感・感謝の気持ちを伝えよう!

その他の回答 (7)

  • 回答No.8
  • Tacosan
  • ベストアンサー率23% (3656/15482)

自分勝手な理解をしていませんか? 「p⇒q」という式の意味を再確認してください.

共感・感謝の気持ちを伝えよう!

質問者からのお礼

「p⇒q」という式は「p が成り立っていれば q が成り立つ」と言っているだけで, そこに「p は必ず成り立っている」という意味は含まれていない。 では、pが成り立っていないときは、どうすればいいのでしょうか・・・。

  • 回答No.7
  • old_sho
  • ベストアンサー率38% (20/52)

3)の個所で、最後の所で一つ抜けてました、 (2)の式がでて、(1)より、x2=y2となる。 ---で以下同様に、何とかかんとかと したがって、x=y

共感・感謝の気持ちを伝えよう!

  • 回答No.5
  • Tacosan
  • ベストアンサー率23% (3656/15482)

それは誤解です. 「aRb,bRa⇒a=b」 に 「aRb,bRaは成り立っていることが前提」 という意味は全く含まれていません. 単純に「aRb と bRa の両方が成り立っていれば」と言っているだけです. ここはきちんと理解してください. 「p⇒q」という式は「p が成り立っていれば q が成り立つ」と言っているだけで, そこに「p は必ず成り立っている」という意味は全く含まれません.

共感・感謝の気持ちを伝えよう!

質問者からのお礼

なるほど。 ということは、aRb と bRa の両方が成り立っていないこともあるのですね。 aRb と bRa の両方が成り立っている時でないと反対称的の証明はできなくなりますよね。 つまり、半順序集合になっていることを示す際に、3つの条件のうち、反対称的の条件が満たされていない場合もあるということですかね。 半順序集合になっていることを示す際、「aRb と bRa の両方が成り立っている時に限り、反対称的の証明もする必要がある」と言えるのでしょうか。 すると、↑のΣの例では半順序集合になっていることを示す際に、反対称的の証明はする必要がなくなるわけですかね。

  • 回答No.4
  • old_sho
  • ベストアンサー率38% (20/52)

おそらく誤解があります。 全順序集合は、任意の二要素a,bに対して、a≦b or b≦a が定義されている。 半順序集合は、任意の要素aに、a≦b or b≦a、となる要素bは、存在するが、任意の二要素a,b間に、a≦b or b≦a が定義されているわけではない。この事を示しているのが、先に挙げた「反例」なのです。 --半順序集合の定義を再確認される事をお勧めします。 また、任意のx, y, z ではないと言うのは舌ったらずでした。 x≦y が成立する任意の二要素x, y に対して y≦z が成立するならば、x≦z となる、というパターンの証明です。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

ありがとうございます。 ようやく理解できた気がします。 先ほどの例を使うと、 ~半順序集合~ x=(1,2,3) (任意の要素) これにx≦yとなる要素はy=(5,5,5)が存在する。 ~全順序集合~ x=(1,2,3) (任意の要素) y=(0,3,1) (任意の要素) n=1の時、1>0 n=2の時、2<3 となって、x≦yが定義されない。 ということですね(便宜上省いたところがあります)。 ありがとうございました。

  • 回答No.3
  • Tacosan
  • ベストアンサー率23% (3656/15482)

最後のところで 「反対称的の 任意のa,b∈Xに対して aRb,bRa⇒a=b ここで、aRbとbRaが成り立つことを言ってしまっている」 とは, 何を意味しているのでしょうか? これは言い換えると「a ≠ b なら aRb と bRa 高々一方が成り立つ」という意味であり, 「aRb と bRa の少なくとも一方が成り立つ」という意味は含まれません. ついでに言うと「全順序集合は半順序集合が成り立つことが前提」というのは日本語として正しくありません. 「半順序集合が成り立つ」というのが変です. 「半順序集合の条件が成り立つ」なら意味が通る.

共感・感謝の気持ちを伝えよう!

質問者からのお礼

ありがとうございます。 日本語として正しくない、理解しました、すみません。 全順序集合の条件が成り立つには半順序集合の条件が成り立つことが必須ですよね。 その上で、任意のa,b∈Xに対して、aRbかbRaが成り立てば全順序集合という意味なのですが、半順序集合の条件の中にすでにaRb,bRa⇒a=bという条件が存在しています。 つまり、aRb,bRaは成り立っていることが前提なので、「半順序集合なら全順序集合」になってしまわないのでしょうか・・・。 お手数おかけします、お願いします。

  • 回答No.2
  • old_sho
  • ベストアンサー率38% (20/52)

反例として例えば、 x=(1,2,10)、y=(3,5,0) n=1, 1<3 n=2, 1+2<3+5 n=3, 1+2+10>3+5+0 なのですから、このx,yには、その大小関係はない訳でしょう。 順序関係の証明は、 x,yに順序がつき、x<y、かつy,zに順序がつきy<z ならば、x,zにも順序がつき、x<z である。と言う証明パターンです。任意のx、y,zではありません。半順序で集合で、上の例のように順序がつかない例もあるのですから。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

なるほど、ありがとうございます。 反例はそのように考えるのですね、勘違いをしていました。 順序関係の証明ですが、任意のx,y,zでなければ、何なのでしょうか? 特定の、という意味なのでしょうか? 半順序集合の証明は任意のx,y,zについて反射的・反対称的・推移的を示すように習ったのですが・・・。 すみませんが、お願いします。

  • 回答No.1

n=2 として、 x = (1, 0) y = (0, 1) とすると、 x ≦ y かつ y ≦ x しかし、 x と yは等しくない。  したがって、半順序集合ではない。  はずしてたらごめんなさい。

参考URL:
http://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88

共感・感謝の気持ちを伝えよう!

関連するQ&A

  • 集合Sがディオファントス的の意味を教えて下さい。

    定義 自然数N個の組の集合Sが”ディオファントス的である”とは、 整数係数の多項式P (x1, x2, ..., xn, y1, y2, ..., ym) があって、 集合Sは (x1, x2, ..., xn) を含む <=> 自然数の組 (y1, y2, ..., ym) があり、P (x1, x2, ..., xn, y1, y2, ..., yn) =0となることである と定義する。 とありますが、 理解出来ません。 わかる方、 よりわかりやすく教えて下さい。

  • 代数学の問題を教えて下さい。

    この問題が分かりません。お願いいたします。 行列A= (0 2 -1) (1 1 -1) (-2 2 1) とする。 X=1,Y0=0,Z0=0である。n>=0で漸化式 X(n+1)=2Yn-Zn Y(n+1)=Xn+Yn-Zn Z(n+1)=-2Xn+2Yn+Zn を満たす数列{Xn}{Yn}{Zn}を考える(n>=0)。このとき 一般項Xn,Yn.Znを求めなさい という問題です。どうかお願いいたします。

  • 離散数学

    Z*を非負整数全体の集合とする。 Z*上の関係R={(x,y)|x+y=0}に対し、反射性、反反射性、対称性、反対称性、推移性のそれぞれが成り立つかどうか述べよ という問題で、 答えは「対称性、反対称性、推移性が成り立つ」なのですが、 理由がわかりません。 どなたか、どうか教えてくださいm(__)m

  • 離散数学の半順序集合に関する問題

    離散数学の半順序集合に関する問題 離散数学の問題が解けずに困っています。 以下の問題を詳しく解説を交えて解いていただけるとありがたいです。 Aを集合とするとき、半順序集合(P(A),⊆)について、次の(1)(2)に答えよ。 (1)X,Y∈P(A)の上限、下限をそれぞれsup{X,Y}、inf{X,Y}とする。 このとき、sup{X,Y}=X∪Y      inf{X,Y}=X∩Y をそれぞれ証明せよ。 (2)半順序集合(P(A),⊆)は束であるかどうか述べよ。 以上です。よろしくお願いします。

  • C言語 所々の意味を教えてください><;

    #include <stdio.h> #define N 100 int main(void) { double xn[N], yn[N], x, y; int i, cnt; FILE *fp; if((fp=fopen("data.txt", "r"))==NULL) return 0; for(i=0; fscanf(fp, "%lf%lf", xn + i, yn + i)==2; i++); cnt = i; scanf("%lf", &x); if(x < xn[0] || xn[cnt-1] <= x) return 0; for(i=0; xn[i] < x; i++); y = (yn[i+1] - yn[i]) * (x - xn[i]) / (xn[i+1] - xn[i]) + yn[i]; printf("y = %f\n", y); return 0; } この文の FILE *fp; if((fp=fopen("data.txt", "r"))==NULL) return 0; for(i=0; fscanf(fp, "%lf%lf", xn + i, yn + i)==2; i++); cnt = i; ここの部分でデータテキストを読み込んでるのはわかるんですが fscanf(fp, "%lf%lf", xn + i, yn + i)部分で何をやってるかわかりません。誰か教えてください

  • 「半順序集合になるようにせよ」という問が解けません

    急ぎです。 次の問が全く解けません。どなたかお願いします。 以下の集合Aと二項関係Rの組は順序集合ではないが、Rに対して操作(要素の除去や追加)によって半順序集合(A,R)になるようにせよ(反射律、反対称律、推移律を満たすようにせよ)。なお、行ってよい操作は最大で除去は2回、追加は1界までとする。 A={a,b,c,d,e,f,g} R={(a,a),(a,c),(a,e),(a,g),(b,a),(b,b),(b,e),(c,c),(c,g),(d,b),(d,d),(d,f),(e,e),(e,g),(f,f),(f,g),(g,g)} 除去する組:(  ,  ) 除去する組:(  ,  ) 追加する組:(  ,  ) 宜しくお願いします

  • 代数学☆イデアルの問題!!

    次の問題について教えてください!! N:自然数 R:環 L,M:左イデアル LM={x1・y1+x2・y2+・・・+xn・yn |         xi∈L,yi∈M (i=1,2,・・・,n),n∈N} LMがイデアルであることを示せ。 左イデアルであることは示せたんですが、右イデアルであることが示せません。 右イデアルを示すために a∈LM,r∈Rに対して a=x1・y1+x2・y2+・・・+xn・yn (xi∈L,yi∈M) とおくと、 a・r=(x1・y1+x2・y2+・・・+xn・yn)・r    =(x1・y1)・r+(x2・y2)・r+・・・+(xn・yn)・r    =x1・(y1・r)+x2・(y2・r)+・・・+xn・(yn・r) になって、 a・r∈LMを示すのにyi・r∈Mを示すのかな、と思ったのですが、 どう示すのか分りません。  やり方自体間違っているのでしょうか、それともyi・r∈Mを示す方法があるのでしょうか。教えてください!!

  • 不等式の問題

    x1>x2>・・・・>xn y1>y2>・・・・>yn という関係のある実数がある。 yの並べ替えたものをz1、z2・・・・znとする。 Σ(k=1~n)xk・yk≧Σ(k=1~n)xk・zk となることを証明せよ。 という問題がありました。 どうやって解けばよいでしょうか?結構いろいろな解法があるようですが、わかりません。

  • 綺麗なローレンツ・アトラクタの描き方?

    ローレンツ方程式 dx/dt = p*(-x + y) dy/dt = r*x - y - x*z dz/dt = -b*z + x*y をEuler法を利用して、プログラムを作成して、gnuplotでplotしているのですがこのローレンツ・アトラクターの2つの円の中心が均一に(私の場合は左円の中心が小さく、右円の中心が大きい)なるようにして、 綺麗なアトラクターを描くには刻み幅と計算回数をどれくらいの値にすればいいのでしょうか? 私は刻み幅h = 0.001、計算回数n = 100000としてます。 *Euler法に変換したプログラムと図は下の通りです。 図 http://www26.tok2.com/home/parshem//image/lorenz-O.jpg #include <stdio.h> #include <math.h> int main(void) { /*---Parameter---*/ int p = 10; int r = 28; double b = 8.0/3.0; double x, y, z, xn, yn, zn, h, i, n; x = 1.0; y = 1.0; z = 1.0; h = 0.001;//ステップの刻み n = 400000; /*---Lorenz Equation & Euler---*/ for(i = 0.0 ; i < n ; i++){ xn =x + h * p*(-x + y) ; yn =y + h * ( r*x - y - x*z ); zn =z + h * ( -b*z + x*y ); printf("%lf\t%lf\t%lf \n", xn, yn, zn); x = xn; y = yn; z = zn; } return 0; }

  • 論理回路

    2n変数論理関数 fn(x1,x2,...,xn,y1,y2,...,yn)={ 1 N(x1,x2,...,xn)>N(y1,y2,...,yn)の時                 0 その以外 について、以下の問に答えよ。ここで、Nは入力を2進数とみなしたときの数を値として持つ関数であり、N(x1,x2,...,xn)=Σ(i=1~n)xi2^n-iと表すことができる。 問 任意のn>=2に対して     fn(x1,x2,...,xn,y1,y2,...,yn)= x1・y1(bar) + (x1+y1(bar))・fn-1(x2,...,xn,y2,...yn) が成り立つことを示せ。ただし、(bar)が論理否定、・が論理積、+は論理和を表す という問なのですが、どのように証明をすればよいのでしょうか? お願いします。