- 締切済み
計算機科学 同値関係の問題です。
計算機科学 同値関係の問題です。 問題 X*を空列を含むアルファベット集合X上の有限長の文字列の集合とする。 次の関係で(X*,≦)が半順序集合となることをしめせ。 w≦w’ ⇔ w1w’w2 = wとなるw1,w2∈X*が存在する。 反射律、対象律、推移律を示し解け。 これは空列があることを考えると、どれもなりたたなくなってしまうのでは・・・ という勝手な妄想をいだいているのですが、結局よくわかりません・・・ だれか回答またはアドバイス、ヒントをお願いします。
- みんなの回答 (2)
- 専門家の回答
みんなの回答
- Anti-Giants
- ベストアンサー率44% (198/443)
- Anti-Giants
- ベストアンサー率44% (198/443)
関連するQ&A
- 数学の同値関係の問題です
集合Zでm~nとは、m-nは3で割り切れるとするとき、~が同値関係であることを示せ、という問題に困っています……。 反射律まではわかるのですが、対象律、推移律の証明の仕方がわかりません。どなたか教えていただけないでしょうか。最近集合を勉強し始めたのですが、ネットの情報などを見てもどうしてもわからないので質問しました。どうぞよろしくお願いいたします……
- 締切済み
- 数学・算数
- 同値関係の問題です。
「反射律、対称律を満たすが、推移律は満たさない関係の例をあげよ」 という問題です。 同値関係については少しは理解しているのですがまだ勉強を始めたばかりでこういう問題はちょっと苦手です。 ヒントだけでも頂けないでしょうか?
- ベストアンサー
- 数学・算数
- 同値関係の問題です。
同値関係の問題です。 1)群Gと部分群Hで{(x,y)|xy∈H}がG上の同値関係でないものを与えよ。 2)群Gと部分群Hで{(x,y)|xyx^(-1)y^(-1)∈H}がG上の同値関係でないものを与えよ。 3)RをXの同値関係とする。与えられたx∈Xに対して、y∈Xを(x,y)∈Rとなるように選ぶ。対称律より(y,x)∈Rとなり、次に推移律より(x,x)∈Rが示される。それゆえ、同値関係の反射律は余計なように思える。この議論の何が問題なのだろうか? 1問でもいいので分かる方おねがいします。
- 締切済み
- 数学・算数
- 集合論の同値関係の基本的な問題
自然数の集合 N から N への写像全体の集合 F における二項関係 R を f R g ⇔ {n∈N: f(n)≠g(n)} は有限集合 によって定める.このとき,R は同値関係であることを示せ. という問題について. 反射律と対称律は自明ですが,推移律が自分にとって自明でありません. fRg ∧ gRh ⇒ fRh {n∈N: f(n)≠g(n)} は有限集合 かつ {n∈N: g(n)≠h(n)} は有限集合 ⇒ {n∈N: f(n)≠h(n)} は有限集合 なにかうまく理解できる方法などがありましたら教えてください.
- ベストアンサー
- 数学・算数
- 同値関係
R(x,y)はx=yを意味し、 1.∀xR(x,x)(反射律) 2.∀x∀y[R(x,y)→R(y,x)](対称律) 3.∀x∀y∀z[R(x,y)∧R(y,z)→R(x,z)](推移律) の三つがあります。 この三つを満たしたとき同値関係となることがわかりますが、 1.が成り立って2.3.が成り立たないとき 2.が成り立って1.3.が成り立たないとき 3.が成り立って1.2.が成り立たないとき 1.2.が成り立って3.が成り立たないとき 1.3.が成り立って2.が成り立たないとき 2.3.が成り立って1.が成り立たないとき の6つのパターン例を示すことはできるのでしょうか? 日常の例でかまいません><
- ベストアンサー
- 数学・算数
お礼
ありがとうございます。 参考にさせてもらいます。 ちなみに同条件で w≦w’ ⇔ l(w)≦l(w’) (このときl(w)は文字列wの長さ) が半順序集合であるか? という問題があり、僕は半順序集合だと思ったのですが、どうでしょうか? 反射律:w、w’∈X* に対して w≦w’ ⇔ l(w)≦l(w’)は成立。 推移律:・・・ このような答えでいってるのですが推移律対称律がわからないのです。 是非ともおしえてもらえないでしょうか??