長文、有限のものの表現の仕方、集合・多重集合・文字列（順序対）

有限のものがあったとします。

・重複を許さない、順序を考えない、とします。
たとえば、aとbとcというものがあったとします。
これを表すのには、集合の記号を用いて、
{a,b,c}
と表します。

・重複を許す、順序を考える、とします。
たとえば、a,b,b,aという順にものがあったとします。
これは順序対の記号を用いて、
(a,b,b,a)
と表すと思います。
また、文字列とみなして、
abba
と表すこともあると思います。0から9の数字と+-記号を用いて、整数を表すのもこれに相当するとおもいます。
順序対の記号は、たとえば
http://oshiete1.goo.ne.jp/qa2861763.html
にあるように、集合の記号によって定義することもできます。
質問１．では逆に、集合の記号を、順序対の記号によって定義することはできるのでしょうか？

・重複を許す、順序を考えない、とします。
たとえば、aが2個、bが3個、cが1個というものがあったとします。
これは多重集合の考え方ですが、
{|aa,bbb,c|}
と表したりするようです。
質問２．多重集合を、集合の記号や順序対の記号を用いて、うまく表すことはできないものでしょうか?

・重複を許さない、順序を考える、とします。
たとえば、a,c,b,d,eという順にものがあったとします。
質問３．しかし、この考え方の具体的な名前、応用例、表し方を知らないので、教えていただきたいのです。

それは順序対の記号を用いて、
(a,c,b,d,e)
と表せばいいという方がいるかもしれませんが、その記号だと、重複を許さないという考えを伝えることができないので、よくはないと思うのです。

No.2 回答者： stomachman 回答日時： 2008/06/01 00:05

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番目の要素を取り出す、という操作も構成できそうだし、２つの無重複列を結合したり、無重複列を分割したりもできるでしょう。そして、
<<a,b,a>> = {{a},{a,b},{a,b,a}}={{a},{a,b},{a,b}}={{a},{a,b}}=<<a,b>>
も成り立ちますんで、旨く行きそうです。（今度は用心して「参考意見」。たははは…）

No.1 回答者： stomachman 回答日時： 2008/05/31 22:57

質問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
> 重複を許さない、順序を考える、
ここで仰る「順序」は「一列に並べることができる」という意味での「順序」だから、全順序関係（すなわち、どの２つの要素も比較できる順序関係）である。だからお考えなのは「有限集合であって、かつ、全順序集合であるもの」に他なりません。これを「無重複列」とでも名付けることにして、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>>
なので、重複を許さない、ということもちゃんと入っています。