- 締切済み
長文、有限のものの表現の仕方、集合・多重集合・文字列(順序対)
有限のものがあったとします。 ・重複を許さない、順序を考えない、とします。 たとえば、aとbとcというものがあったとします。 これを表すのには、集合の記号を用いて、 {a,b,c} と表します。 ・重複を許す、順序を考える、とします。 たとえば、a,b,b,aという順にものがあったとします。 これは順序対の記号を用いて、 (a,b,b,a) と表すと思います。 また、文字列とみなして、 abba と表すこともあると思います。0から9の数字と+-記号を用いて、整数を表すのもこれに相当するとおもいます。 順序対の記号は、たとえば http://oshiete1.goo.ne.jp/qa2861763.html にあるように、集合の記号によって定義することもできます。 質問1.では逆に、集合の記号を、順序対の記号によって定義することはできるのでしょうか? ・重複を許す、順序を考えない、とします。 たとえば、aが2個、bが3個、cが1個というものがあったとします。 これは多重集合の考え方ですが、 {|aa,bbb,c|} と表したりするようです。 質問2.多重集合を、集合の記号や順序対の記号を用いて、うまく表すことはできないものでしょうか? ・重複を許さない、順序を考える、とします。 たとえば、a,c,b,d,eという順にものがあったとします。 質問3.しかし、この考え方の具体的な名前、応用例、表し方を知らないので、教えていただきたいのです。 それは順序対の記号を用いて、 (a,c,b,d,e) と表せばいいという方がいるかもしれませんが、その記号だと、重複を許さないという考えを伝えることができないので、よくはないと思うのです。
- みんなの回答 (2)
- 専門家の回答
みんなの回答
- stomachman
- ベストアンサー率57% (1014/1775)
ANo.1、自信ありとか言っといて間違えましたんで、毎度の事ながら訂正。 > = {(b,0),(b,1),(a,0),(a,1),(a,2)} > = <<b,a>> 嘘です。bag{(b,0),(b,1),(a,0),(a,1),(a,2)}は <<b,a>> = {(b,0),(a,0),(a,1)} とは違う。 これをどう訂正するかというと、えーと、まず、bagのことは忘れて下さい。 全順序関係をすなおに利用して、 <<a,b,c>> = {{a},{a,b},{a,b,c}} と定義するのは如何でしょう。すなわち、無重複列の要素pを「pか、無重複列の中でpより左にあるもの」の集合に対応付けてやるんです。 そうすれば、x∈<<a,b,c>>について、|x| (xの要素の個数)がxの順番を表している。n番目の要素を取り出す、という操作も構成できそうだし、2つの無重複列を結合したり、無重複列を分割したりもできるでしょう。そして、 <<a,b,a>> = {{a},{a,b},{a,b,a}}={{a},{a,b},{a,b}}={{a},{a,b}}=<<a,b>> も成り立ちますんで、旨く行きそうです。(今度は用心して「参考意見」。たははは…)
- stomachman
- ベストアンサー率57% (1014/1775)
質問1 有限集合に限った話ですから、「順序対Pにある要素xが含まれている」という事を表す関係が定義されていれば可能です。 この関係を"x<P"と書く事にすると、x∈P とは x<Pのことだと定義すれば良い。そして、集合の同値関係を(P=Qと書くと順序対としての同値関係になっちゃうんで)~と書く事にして、 P~Q ⇔ ∀x(x<P ⇔ x<Q) と定義する。 質問2 仰る所の多重集合は「bag」とも呼ばれます。これを集合で表すには、順序対(要素, 要素の識別番号)を要素とする集合、と考えれば良い。つまり、 B={|aa,bbb,c|} の実体は B={(a,0),(a,1),(b,0),(b,1),(b,2),(c,0)} である。 「bag Bにある要素xが含まれている」という事を x←B と書くことにすると、 x←B ⇔ ∃n(n∈N ∧ (x,n)∈B) 「bag Bにxがいくつ含まれているか」という関数をC(x,B)とすると C(x,B) = | {n|(x,n)∈B} | あるいは C(x,B) = max {n|(x,n)∈B} + 1 もちろん、他にもやりようはあるでしょうけれど。 質問3 > 重複を許さない、順序を考える、 ここで仰る「順序」は「一列に並べることができる」という意味での「順序」だから、全順序関係(すなわち、どの2つの要素も比較できる順序関係)である。だからお考えなのは「有限集合であって、かつ、全順序集合であるもの」に他なりません。これを「無重複列」とでも名付けることにして、a,c,b,d,eがこの順に並んでできる無重複列を<<a,c,b,d,e>>とでも書くことにすると、その実体は、例えばbagを使って {|a,cc,bbb,dddd,eeeee|} のことだと決めたらいいんじゃないかな。すると例えば、 <<a,b,a>> = {|a,bb,aaa|} = {(a,0),(b,0),(b,1),(a,0),(a,1),(a,2)} = {(b,0),(b,1),(a,0),(a,1),(a,2)} = <<b,a>> なので、重複を許さない、ということもちゃんと入っています。