プロが教えるわが家の防犯対策術！

２項関係に対する問題

締切済

  • 質問者：kitct
  • 質問日時：
  • 回答数：2件

以下の問題の解答がわかりません。解答とできれば考え方を教えてください。
S={1,2,...,n}において、S上の２項関係で反射的かつ対称的なものは全部で何個存在するか。

通報する

この質問への回答は締め切られました。

質問の本文を隠す

A 回答 (2件)

No.2

  • 回答者： settheory
  • 回答日時：

ご存知かもしれませんが、集合論ではＳ上の２項関係とは、Ｓ×Ｓ（直積）の部分集合であることに注意しましょう。

Rが二項関係の時、aRb は(a,b)がRの元になっているということです。

そうすると、反射的とは、対角成分をもつということ。
対称的は、n×nのマスの対角線についてＲが線対称になってるということです。

例えば、1だけ関係を持たせたいとしたら、Ｒ＝｛（1,1）｝とすれば、反射的かつ対称的です。
1と2にだけ関係を持たせたいとしたら、Ｒ＝｛(1,1) (2,2) (1,2) (2,1)｝とすれば良いです。

Ｓから、何か（自身を含む）と関係をもたせるものとして、ｋ個選んできます。（ｎＣｋ通り）

ｋ=1のときは、反射的、かつ対称的な関係は、最初に挙げた例のようにするしかありません。

ｋが２以上の時
選んだもの全体を、便宜的にＸとします。
反射的にするために、Ｘの各元xについて対角成分(x,x)をとります。これでＸのどの元も自身と関係を持ったことになります。

次に異なる元との関係について。つまり対角成分以外のものをどうとるかということになります。対角線について対称になるようにするので、
対角線より上のところ、x<yな(x,y)をどう選ぶかです。（対角線の下で考えてもＯＫ）そのような成分は全部でkＣ_2 個あります。このなかから、好きなものを好きなだけ取ってくればよいので、その取り方は2^{kＣ_2}通りです。ここで取ってきた成分(x,y)と、それをひっくり返した成分(y,x)と、最初にとった対角成分、全部足し合わせた集合が、反射的かつ対称的な関係になります。

Σ_{k=2 からnまで}nＣk × 2^{kＣ_2} ＋ n　

これが求める個数になるかと（空集合も二項関係としているなら、更に＋１）。この式がもっと整理できるかはわかりません・・・　
    • good
    • 1
    • 件
通報する

No.1

  • 回答者： Tacosan
  • 回答日時：

表を書いて「ここは 1 にしないとダメだから～」とか「こことここは一緒にしないとダメだな～」とかやればわかる.


答えは 2^(n(n-1)/2) 個だ.
    • good
    • 3
    • 件
通報する

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう！

Q質問する（無料）

このQ&Aを見た人はこんなQ&Aも見ています

関連するQ&A

関連するカテゴリからQ&Aを探す

専門家回答数ランキング

専門家

※過去一週間分の回答数ランキングです。

Q質問する（無料）

他の専門家の回答をチェック

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q離散数学　2項関係についての問題

某国立大の情報系の学科に通っているものです。情報系では離散数学を習うのですが、あまり理解が進まず困っています。
今回は下記の問題に関して質問があります。

Ｓ＝｛１，２，３，４，５，６，７，８，９，１０｝とする
（１）Ｓ上の2項関係で対照的なものはいくつあるか
（２）　　　〃　　　反射的なものはいくつあるか
（３）　　　〃　　　反射的かつ対照的なものはいくつあるか

という問題です。
Ｓ上の2項関係の総数は　２の１００乗　個あるというところまでは分かります。
Ｓ上の二項関係をＲとして
反射的・・・すべてのＳの要素Ｘに対して（Ｘ，Ｘ）∈Ｒ
対象的・・・（Ｘ，Ｙ）∈Ｒ　ならば　（Ｙ，Ｘ）∈Ｒ
こんな感じだとは思うのですが、ここからどう回答していけばよいのか見当がつきません。

もし、解法をご存知の方がいましたらご助力願います。

Aベストアンサー

うん, S×S が 100個の要素からなっていて, R はその部分集合だから 2^100通り.
ちょいと #1 へのコメントを見たんだけど, 「反射的」と「対称的」が逆だよ....
反射的な関係であれば全ての x ∈ S に対して (x, x) ∈ R だから, 「R に入れるかどうか」の選択ができる組み合わせは x ≠ y であるような (x, y) に限定されます. これは何組ありますか?
対称的な関係も同様で, (x, y) ∈ R if and only if (y, x) ∈ R だということは, 「x > y であるような (x, y) については ((y, x) ∈ R かどうかを決めれば) 自動的に決まってしまうので考えなくてもよい」ということになります.

他の回答も見る

Q集合論＞二項関係＞反射律、対称律、推移律

タイトルのごとく、反射律、対称律、推移律の質問です。
集合A上の二項関係を～とする。

このときこの二項関係が対称律、推移律を満たせば
ｘ、ｙ∈Aとして、
「ｘ～ｙかつｙ～ｘ⇒ｘ～ｘ」
が成立する
故に、二項関係が対称律と推移律を持てば、反射律をもつと考えました。

しかし、大学のレポートで、「対称律と推移律はもつが、反射律をもたない二項関係をあげよ」という問題がでできました。
上記の僕の証明は間違っているのでしょうか？
どなたか知っている方、教えてもらえますか？

Aベストアンサー

No.2 は特殊すぎて面白くない？

では，整数全体において
ｍ～ｎ ⇔ ｍｎ＞０

０～０ でないので反射律は成り立たない。

要するに，
∃ｙ(ａ～ｙ) ⇒ ａ～ａ
が，対称律，推移律からいえるので，
∃ｘ∀ｙ(ｘ～ｙ でない)
ような例を考えればよいのです。

No.2 は，∀ｘ∀ｙ(ｘ～ｙ でない) の例
上のは，∀ｙ(０～ｙ でない) の例です

他の回答も見る

Q同値関係とは

同値関係について
教科書などを見ると
反射律、対象律、推移律の３つを満たすときに同値関係になるとかいてあるのですが、その意味がよくわかりません。

説明できる方がいらっしゃいましたら教えてください。よろしくお願いします。

Aベストアンサー

関係～について，

　反射律とは a～a を満たすこと
　対称律とは a～b ⇒ b～a を満たすこと
　推移律とは a～b，b～c ⇒ a～c を満たすこと

です。この３つをすべて満たすことを同値関係といい，
高校までに習った「同値」という概念の本質を端的に
言い表しています。

定義なのだから，そのまま認めればいいだけのことですが，
実感がつかみにくいなら，中学・高校で習った具体例を
あげるとよいでしょう。
例えば，線分の長さについて考えると
　　AB=AB，
　　AB=CD ⇒ CD=AB，
　　AB=CD，CD=EF ⇒ AB=EF
が成り立ちますから，「線分の長さが等しい」という関係は
同値関係ですね。

大学の数学って，今まであいまいにしてきたことを，
スッキリさせてくれますよね。

他の回答も見る

Q離散数学の２項関係について

「Ｓ＝｛1,2,3,…,n｝とする。　Ｓ上の２項関係は全部で何個？」
という問題なのですが、答えが良く分かりません。
　自分で考えたのは
(1,1),(1,2),…,(1,n)
(2,1),(2,2),…,(2,n)
　　　　　：
(n,1),(n,2),…,(n,n)
で、答えは n * n = 「n~2」　だと思うのですが、実際は「2~n~2」個らしいです。
　２項関係自体の理解も曖昧なのですが、よろしければ説明をお願いします。

Aベストアンサー

Ｓの２項関係とは、ＳとＳを組にしたものの集合、
つまりＳ×Ｓを考え、そのＳ×Ｓのある部分集合のこと
をＳの２項関係と考えます。

要素の組だけでなく、「要素の組の集合」を考えた
ものが２項関係の正体です。

chromium_aiさんの例示したのはＳ×Ｓの全体の集合です。

２項関係はＳ×Ｓの部分集合なので、
例えば(1,2)だけの集合{(1,2)}も、1と2の間に２項関係が
あるというだけのきわめて小さな２項関係ですし、
他に例えばiが1からnまでとるとして、全てのiについて
(i,i)からなる集合{(1,1), (2,2), ... , (n,n)}も、
それぞれのiが自分自身とだけ関係があるという
２項関係のひとつとなります。
上記の二つの２項関係はＳ上の２項関係の一例ですが、
他にもたくさんのＳ上の２項関係を考えることができます。

このように可能な全ての部分集合をそれぞれが
別個の２項関係だと考えていき、
最大でn^2個の要素があるＳ×Ｓにはいくつの
部分集合があると考えることができるでしょうか
というのがもともとの設問となります。

Ｓの２項関係とは、ＳとＳを組にしたものの集合、
つまりＳ×Ｓを考え、そのＳ×Ｓのある部分集合のこと
をＳの２項関係と考えます。

要素の組だけでなく、「要素の組の集合」を考えた
ものが２項関係の正体です。

chromium_aiさんの例示したのはＳ×Ｓの全体の集合です。

２項関係はＳ×Ｓの部分集合なので、
例えば(1,2)だけの集合{(1,2)}も、1と2の間に２項関係が
あるというだけのきわめて小さな２項関係ですし、
他に例えばiが1からnまでとるとして、全てのiについて
(i,i)からなる集合{(1,1), (...続きを読む

他の回答も見る

Q関数（全域的関数）の個数について

集合Ｔ＝{1,2,3,…,n}について
ＴからＴへの全域的関数で、相異なものの個数を求めたいのですが、この場合 関数をfとおいて

・fにＴの全ての要素を当てはめてＴのどれかの要素に対応させたもの

を一つとカウントすればよいのでしょうか。
この場合だと、Ｔの要素一つにn個の対応付けがあるので、関数の個数は n~n (nのn乗) となると思いますが、正しいでしょうか。

また、この場合１対１対応にはなっていないのですが、問題はありませんか。

文章にわかりにくい点などがあるかもしれませんが、よろしければ御回答お願いします。

Aベストアンサー

正解と思います。ちなみに集合Aから集合Bへの関数(写像)の集合をB^Aと書きます。BをA回直積している
イメージです。
これはAからBへの写像にほかなりません。
3次元実空間 R^3は3点からなる集合から実数Rへの写像の全体と同じですよね。
集合Aの部分集合の全体は2^Aと書きます。なぜなら
Aの部分集合は「Aから２点集合への写像」と同一視
できるからです。
A,Bが有限集合の場合は#(B^A)=#B^#Aです。質問者さんの場合ですと #T＝nなので#(T^T)=n^nです。(#Aは集合Aの個数を表すとしました)

他の回答も見る

Q最大元と極大元の定義の違いが分かりません

数学の基礎「齋藤正彦著」p22からの抜粋です。

定義
(X,≦)を順序集合,AをXの部分集合とする。
「1) aがAの元でAの全ての元xに対してx≦aが成り立つ時,aをAの最大元といい,maxAと書く,Aの全ての元xに対してa≦xが成り立つ時,aをAの最小元といい,minAと書く。最大元や最小元は存在するとは限らない,あるとすれば一つしかない。
2) aがAの元で,Aのいかなる元xに対してもa<xとならない時,aを極大元という。x<aなるAの元が存在しない時,aを極小元という。極大元や極小元は存在しない事も有るし,沢山存在する事もある」

と定義が紹介されてるのですが最大元と極大元についてのこの文意
"aがAの元でAの全ての元xに対してx≦aが成り立つ"と"aがAの元で,Aのいかなる元xに対してもa<xとならない"
とは同値だと思います。
違いが分かりません。

一体,どのように違うのでしょうか?

Aベストアンサー

>最大元と極大元の定義の違いが分かりません
最大元と極大元は抽象的に考えても違いが分からなくて当然だと思います。ここは具体例で理解するのがよいと思います。

例はいろいろ考えられますが、たとえば、(x,y)∈R^2について、
(x1,y1)≦(x2,y2)をx1≦x2かつy1≦y2と定義します。
A={(0,0),(0,1),(0,2),(1,0),(1,1),(2,0)}
のとき、Aの最大元は存在しませんが、極大元は３個あります。ちなみに最小限は(0,0)の１個ですね。

ところで、最大元が存在する場合は、全順序集合、半順序集合に関係なく、それは極大元でもあります。しかし、その逆は成り立ちません。
その意味で、「同値」ではありませんね。

他の回答も見る

Q10進数の14.5を浮動小数点(IEEE754形式)の2進数に変換するにはどうしたらよいでしょうか？

10進数の14.5を浮動小数点(IEEE754形式)の2進数に変換するにはどうしたらよいでしょうか？
10進数の-7.5を浮動小数点(IEEE754形式)の2進数に変換するにはどうしたらよいでしょうか？
計算方法を教えてください。

Aベストアンサー

14.5を符号と指数と仮数に分けます。
符号は正の数なので符号は0
次に14.5を符号無し2進数に変換すると
1110.1
小数点を左に移動させて1だけ残すと
1110.1=1.1101*2^3
仮数は23ビットで小数点より右側だけなので、足りない分を0でうめて
11010000000000000000000
指数の3を127でバイアスするので
3+127=130
これを2進数に直すと
10000010
全て合わせると、
01000001011010000000000000000000
で、32ビットの2進数に変換できました。
同じように、-7.5を変換すると、
符号は負の数なので1
-7.5を符号無し2進数に変換すると、
　111.1
=1.111*2^2
なので、仮数は
11100000000000000000000
指数の2を127でバイアスすると
2+127=129
これを2進数に直すと
10000001
全て合わせると
11000000111100000000000000000000
になります。
64ビットの場合は、指数のバイアスを127から1023にし、仮数の23ビットを52ビットまで増やせばOKです。

14.5を符号と指数と仮数に分けます。
符号は正の数なので符号は0
次に14.5を符号無し2進数に変換すると
1110.1
小数点を左に移動させて1だけ残すと
1110.1=1.1101*2^3
仮数は23ビットで小数点より右側だけなので、足りない分を0でうめて
11010000000000000000000
指数の3を127でバイアスするので
3+127=130
これを2進数に直すと
10000010
全て合わせると、
01000001011010000000000000000000
で、32ビットの2進数に変換できました。
同じように、-7.5を変換すると、
符号は負の数なので1
-7.5を...続きを読む

他の回答も見る

Q集合｛１，２｝上の半順序関係は何個存在するか？

自分で解いてみると2個になったんですが3個のようです
｛（１，１）,（１，２）,（２，２）｝と
｛（１，１）,（２，１）,（２，２））は出たのですけど
もうひとつありますか?
｛（１，１）,（２，２）｝だと対称的が入ってしまうので…
誰か教えてください　お願いします

Aベストアンサー

>反射、反対称、推移、対称　が満たされていても半順序関係といえるのですね?
>先の3つだけ満たされている場合が半順序関係ではないのですね?

対称とはおそらく
(１,１)と(２,２)のことを言っておられるのだと思いますが、これは順序関係の公理でいうと反射律が成り立つということを言っているに過ぎません。

とにかく、順序関係は反射・反対称・推移の３つの公理を満たすもの、と定義されているのですから順序の３公理を満たしさえすれば対称的であろうがなかろうがそれは半順序集合です。
おそらく「反対称」という言葉にひきづられて対称的な組があると反対称律と矛盾するような気がするのでしょうが、そんなことはありません。
すべての(「すべての」ということが重要です)要素間に(自分自身も含めて)対称的かつ反対称律を満たすような関係がある場合は、反対称律よりその集合のすべての要素は等しい、いいかえれば１点集合{1}と言うことになります。
もちろん{1}には{(1,1)}という(ただひとつの)半順序関係が成り立ちます。これは「すべての」関係が対称的であるような唯一の半順序集合です。
｛（１，１）,（２，２）｝の場合は１と２の間に関係は定義されませんから、「すべての」要素間に対称的な関係があるわけではないですよね。

というわけでこの問題については対称的等は気にする必要はありません。

>反射、反対称、推移、対称　が満たされていても半順序関係といえるのですね?
>先の3つだけ満たされている場合が半順序関係ではないのですね?

対称とはおそらく
(１,１)と(２,２)のことを言っておられるのだと思いますが、これは順序関係の公理でいうと反射律が成り立つということを言っているに過ぎません。

とにかく、順序関係は反射・反対称・推移の３つの公理を満たすもの、と定義されているのですから順序の３公理を満たしさえすれば対称的であろうがなかろうがそれは半順序集合です。
おそらく「...続きを読む

他の回答も見る

Qmodとは

倍数の判定方法の理論的根拠を調べていたところ、10A+c≡0(mod7)等と表記されていたのですが
modというのはどういうものなのか、分かりやすく教えて頂けないでしょうか。

そのHPにはmodについての説明がなく、調べてみても
法やmodulusの略などと書かれているだけで、詳しく書かれていなかったので。
簡単に説明できるものではないのでしょうか。

高校数学ではまだ理解できないものなのでしょうか。
出来れば、宜しくお願いします。

Aベストアンサー

mod nというのはnで割ったときの剰余が等しければ，同じものと見なしてしまうことです．

つまり，割った余りが等しければ≡になるんですね．

たとえば
1≡2005 (mod 3)
1≡59 (mod 28)
となります．

一般には，
a≡b (mod c)
を，(a-b)がcで整除される
で定義します．

他の回答も見る

Q偏微分の記号∂の読み方について教えてください。

偏微分の記号∂(partial derivative symbol)にはいろいろな読み方があるようです。
（英語）
curly d,　rounded d,　curved d,　partial,　der
正統には∂u/∂x で「partial derivative of u with respect to x」なのかもしれません。
（日本語）
ラウンドディー、ラウンドデルタ、ラウンド、デル、パーシャル、ルンド
MS-IMEはデルで変換します。JIS文字コードでの名前は「デル、ラウンドディー」です。

そこで、次のようなことを教えてください。
(1)分野ごと（数学、物理学、経済学、工学など）の読み方の違い
(2)上記のうち、こんな読み方をするとバカにされる、あるいはキザと思われる読み方
(3)初心者に教えるときのお勧めの読み方
(4)他の読み方、あるいはニックネーム

Aベストアンサー

こんちには。電気・電子工学系です。

（１）
工学系の私は，式の中では「デル」，単独では「ラウンドデルタ」と呼んでいます。あとは地道に「偏微分記号」ですか(^^;
その他「ラウンドディー」「パーシャル」までは聞いたことがあります。この辺りは物理・数学系っぽいですね。
申し訳ありませんが，あとは寡聞にして知りません。

（３）
初心者へのお勧めとは，なかなかに難問ですが，ひと通り教えておいて，式の中では「デル」を読むのが無難かと思います。

（４）
私はちょっと知りません。ごめんなさい。ニックネームは，あったら私も教えて欲しいです。

（２）
専門家に向かって「デル」はちょっと危険な香りがします。
キザになってしまうかどうかは，質問者さんのパーソナリティにかかっているでしょう(^^

＊すいません。質問の順番入れ替えました。オチなんで。

では(∂∂)/

他の回答も見る
ページトップページトップ

Q質問する（無料）

このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング

おすすめ情報