順序対の定義

Last-modified: Fri, 28 Apr 2017 10:53:39 JST (1681d)
Top > 順序対の定義
冪集合の存在へ戻る。
定義1(集合の順序対の定義
2つの集合\( a \)\( b \)に対し、\( \{ \{ a \}, \{ a, b \} \} \)\( a \)\( b \)の順序対(ordered pair)と呼び*1\( \langle a, b \rangle \)と略記する。

順序対という呼び方から推察できるように、\( \langle a, b \rangle \)の集合としての構造の情報だけから(つまり一旦\( a \)\( b \)を忘れても)、次の命題によってその「成分」である\( a \)\( b \)を復元できます。

命題2(順序対の基本性質)
4つの任意の集合\( a \)\( b \)\( a' \)\( b' \)に対し、\( \langle a, b \rangle = \langle a', b' \rangle \)である必要十分条件は\( a = a' \)かつ\( b = b' \)が成り立つことである。

証明

十分条件であることは良い。必要条件であることを示す。\( \langle a, b \rangle = \langle a', b' \rangle \)と仮定する。

\( \{ a \} \in \langle a, b \rangle = \langle a', b' \rangle \)より、\( \{ a \} = \{ a' \} \)または\( \{ a \} = \{ a', b' \} \)である。いずれの場合も\( a' \in \{ a \} \)となるので\( a' = a \)である。

\( \{ a, b \} \in \langle a, b \rangle = \langle a', b' \rangle \)より、\( \{ a, b \} = \{ a' \} \)または\( \{ a, b \} = \{ a', b' \} \)である。

まず\( \{ a, b \} = \{ a' \} \)と仮定する。\( b \in \{ a, b \} = \{ a' \} \)より、\( b = a' = a \)となる。\( \{ a', b' \} \in \langle a', b' \rangle = \langle a, b \rangle = \langle b, b \rangle = \{ \{ b \}, \{ b, b \} \} = \{ \{ b \}, \{ b \} \} = \{ \{ b \} \} \)より\( \{ a', b' \} = \{ b \} \)となる。従って\( b' \in \{ a', b' \} = \{ b \} \)となり、\( b' = b \)を得る。

次に\( \{ a, b \} = \{ a', b' \} \)と仮定する。\( b' \in \{ a', b' \} = \{ a, b \} \)より、\( b' = a \)または\( b' = b \)となる。\( b' = a \)ならば\( b \in \{ a, b \} = \{ a', b' \} = \{ a, a \} = \{ a \} \)となり、\( b = a = b' \)を得る。また、\( b' = b \)ならば\( b' = b \)であることも自明*9である。従って、いずれの場合も\( b' = b \)である。

以上より、\( a = a' \)かつ\( b = b' \)が成り立つ。

順序対の基本性質には色々な証明手順がありますが、どの手順で証明するにしてもきちんと「定義の確認」と「場合分け」を駆使する必要がありますので、数学における証明の演習としてとても良い題材です。

ここで、順序対は集合に対してしか定義されていないことに注意しましょう。実際\( \langle a, b \rangle \)の定義には\( \{ a \} \)を用いており、\( \{ a \} \)が定義されるのは\( a \)が集合の場合に限られます。しかしながらクラスに対しても順序対に類するものが必要になることがありますので、ここでは順序対の類似物として「組」という概念を便宜的に導入することにします。

定義3(クラスの組の定義)
2つのクラス\( A \)\( B \)に対し、\( \{ \langle a, 0 \rangle \mid a \in A \} \cup \{ \langle b, 1 \rangle \mid b \in B \} \)\( A \)\( B \)の組(doubleまたはcoupleまたは\( 2 \)-tuple)と呼び、\( (A,B) \)と略記する*2

順序対の基本性質より、\( (A,B) \)\( C \)と置くと、\( A = \{ a \mid \langle a, 0 \rangle \in C \} \)\( B = \{ b \mid \langle b, 1 \rangle \in C \} \)と表すことが出来ます*3。従って、\( (A,B) \)のクラスとしての構造の情報だけからその「成分」である\( A \)\( B \)を復元することが出来ます。更に、組の構成を集合に制限すれば、集合だけで閉じた議論も出来ることが次の命題で確認できます。

命題4(クラスの組と集合の関係性)
2つの任意のクラス\( A \)\( B \)に対し、以下は同値である:
(1) \( A \)\( B \)がいずれも集合をなす。
(2) \( (A,B) \)が集合をなす。

証明

(1)を仮定する。\( (A,B) = \{c \in P(P(A \cup B \cup 2) ) \mid (\exists a \in A, c = \langle a, 0 \rangle) \vee (\exists b \in B, c = \langle b, 1 \rangle) \} \)と表せることから、\( (A,B) \)は集合をなす*10。従って(2)が成り立つ。

(2)を仮定する。\( A = \{ a \in \bigcup (\bigcup (A,B)) \mid \langle a, 0 \rangle \in (A,B) \} \)及び\( B = \{ b \in \bigcup (\bigcup (A,B)) \mid \langle b, 1 \rangle \in (A,B) \} \)より、\( A \)\( B \)も集合をなす。従って(1)が成り立つ。

クラス\( A \)\( B \)に対し、\( A \times B := \{ c \mid \exists a \in A, \exists b \in B, c = (a,b) \} \)と置きます*4\( A \)\( B \)がいずれも集合である時、\( A \times B = \{c \in P(P(A \cup B \cup 2)) \mid \exists a \in A, \exists b \in B, c = (a,b) \} \)と表せる*5ことから、\( A \times B \)も集合をなすことが分かります。慣れないうちは\( \times \)\( \emptyset \)の関係を失念しやすい*6ので、次の命題と演習で確認しましょう。

命題5(クラスの2項直積と空集合の関係性)
2つの任意のクラス\( A \)\( B \)に対し、以下は同値である。
(1) \( A \times B \neq \emptyset \)
(2) \( A \neq \emptyset \)かつ\( B \neq \emptyset \)

証明

(1)を仮定する。仮定より、ある\( a \in A \)\( b \in B \)が存在し、\( (a,b) \in A \times B \)である*11。従って\( a \in A \neq \emptyset \)かつ\( b \in B \neq \emptyset \)である。以上より(2)が成り立つ。

(2)を仮定する。仮定より、ある{a \in A};が存在する。また仮定より、ある\( b \in B \)が存在する。すると\( (a,b) \in A \times B \)である。以上より(1)が成り立つ。

演習6(クラスの2項直積と包含関係の関係性)
4つの任意のクラス\( A \)\( B \)\( C \)\( D \)に対し、以下が同値であることを示せ:
(1) \( A \times B \subset C \times D \)
(2) \( A \subset C \)かつ\( B \subset D \)、または\( A = \emptyset \)、または\( B = \emptyset \)

さて、組の構成を反復的に用いることでクラスの「3つ組」等を定義することが出来ます。

定義7(クラスの3つ組の定義)
(1) 3つのクラス\( A \)\( B \)\( C \)に対し、\( (A,(B,C) ) \)\( A \)\( B \)\( C \)の3つ組(tripleまたはtriadまたは\( 3 \)-tuple)と呼び、\( (A,B,C) \)と略記する*7
(2) 4つのクラス\( A \)\( B \)\( C \)\( D \)に対し、\( (A,(B,C,D) ) \)\( A \)\( B \)\( C \)\( D \)の4つ組(quadrupleまたはquadまたは\( 4 \)-tuple)と呼び、\( (A,B,C,D) \)と略記する。
(3) 5つのクラス\( A \)\( B \)\( C \)\( D \)\( E \)に対し、\( (A,(B,C,D,E) ) \)\( A \)\( B \)\( C \)\( D \)\( E \)の5つ組(quintupleまたはpentupleまたは\( 5 \)-tuple)と呼び、\( (A,B,C,D,E) \)と略記する。
(4) 6つのクラス\( A \)\( B \)\( C \)\( D \)\( E \)\( F \)に対し、\( (A,(B,C,D,E,F) ) \)\( A \)\( B \)\( C \)\( D \)\( E \)\( F \)の6つ組(sextupleまたはhextupleまたは\( 6 \)-tuple)と呼び、\( (A,B,C,D,E,F) \)と略記する。

同じ方法で定義を繰り返すことが出来ますが、Encyclopedia of \( P \)-adic Numbersでは6つ組までしか使わないのでここで止めておきます。また、集合の組のなすクラスを\( \times \)で表したように、集合の3つ組のなすクラス等も同様の表記をすることにします。

定義8(クラスの3項直積の定義)
(1) 3つのクラス\( A \)\( B \)\( C \)に対し、\( A \times (B \times C) \)\( A \times B \times C \)と略記する*8
(2) 4つのクラス\( A \)\( B \)\( C \)\( D \)に対し、\( A \times (B \times C \times D) \)\( A \times B \times C \times D) \)と略記する。
(3) 5つのクラス\( A \)\( B \)\( C \)\( D \)\( E \)に対し、\( A \times (B \times C \times D \times E) \)\( A \times B \times C \times D \times E \)と略記する。
(4) 6つのクラス\( A \)\( B \)\( C \)\( D \)\( E \)\( F \)に対し、\( A \times (B \times C \times D \times E \times F) \)\( A \times B \times C \times D \times E \times F \)と略記する。

例えば\( A \times B \times C \)の元は\( A \)の元と\( B \times C \)の元の組に他ならず、ある\( a \in A \)\( b \in B \)\( c \in C \)を用いて\( (a,(b,c) ) \)と表わせますが、これは3つ組\( (a,b,c) \)に他なりません。従って、\( A \times B \times C \)\( A \)\( B \)\( C \)の元の3つ組全体からなるクラスと一致します。

順序対や組の意義は、それらの集合やクラスとしての構造の情報が成分の情報を持っているという点であり、実際にどのように集合やクラスとして実装したかはあまり問題にされません。実際、上までに述べた性質と同様の性質を持つ別の構成を用いても数学のほとんど全ての議論が同様に行われます。特に、順序対や組がどのような集合を元に持つか、は基本的にあまり重要ではありません。

それはさておき、順序対や組の実装の方法を1つ固定している状況で何が成り立つかを考えることは、集合やクラスに慣れるための軽い演習になります。というわけで、今後扱う演習や命題にはそれらに依存するものも混ぜていくことにし、そういったものには組の定義に依存という注意書きをして区別することにします。

命題9(クラスの組と包含関係の関係性|組の定義に依存
4つの任意のクラス\( A \)\( B \)\( C \)\( D \)に対し、以下は同値である。
(1) \( (A,B) \subset (C,D) \)
(2) \( A \subset C \)かつ\( B \subset D \)

証明

(1)を仮定する。\( a \in A \)とする。\( \langle a, 0 \rangle \in (A,B) \subset (C,D) \)より、ある\( c \in C \)が存在して\( \langle a, 0 \rangle = \langle c, 0 \rangle \)、またはある\( d \in D \)が存在して\( \langle a, 0 \rangle = \langle d, 1 \rangle \)である。命題2及び\( 0 \neq 1 \)より、任意の\( d \in D \)に対して\( \langle a, 0 \rangle \neq \langle d, 1 \rangle \)である。従ってある\( c \in C \)が存在して\( \langle a, 0 \rangle = \langle c, 0 \rangle \)である。再び命題2より、\( a = c \)である。従って\( a \in C \)である。以上より\( A \subset C \)である。

\( b \in B \)とする*12\( \langle b, 1 \rangle \in (A,B) \subset (C,D) \)より、ある\( c \in C \)が存在して\( \langle b, 1 \rangle = \langle c, 0 \rangle \)、またはある\( d \in D \)が存在して\( \langle b, 1 \rangle = \langle d, 1 \rangle \)である。命題2及び\( 0 \neq 1 \)より、任意の\( c \in C \)に対して\( \langle b, 1 \rangle \neq \langle c, 0 \rangle \)である。従ってある\( d \in D \)が存在して\( \langle b, 1 \rangle = \langle d, 1 \rangle \)である。再び命題2より、\( b = d \)である。従って\( b \in D \)である。以上より\( B \subset D \)である。以上より、(2)が成り立つ。

(2)を仮定する。\( x \in (A,B) \)とする。ある\( a \in A \)が存在して\( x = \langle a, 0 \rangle \)である、またはある\( b \in B \)が存在して\( x = \langle b, 1 \rangle \)である。前者を仮定すると、\( a \in A \subset C \)より\( x = \langle a, 0 \rangle \in (C,D) \)である。後者を仮定すると、\( b \in B \subset D \)より\( x = \langle b, 1 \rangle \in (C,D) \)である。従って、いずれの場合も\( x \in (C,D) \)である。以上より、(1)が成り立つ。

それでは、クラスの組を用いて、「写像」という概念を定式化していきます。写像とは、初等数学で扱われる「関数」という概念を公理的集合論の中に実装した概念です。写像を用いて関数という概念を定義し直すことも出来、その意味で写像は関数の一般化となります。




*1 順序対の定義の仕方は他にもあります。これはクラトウスキー(Kuratowski)の記法と呼ばれています。
*2 クラスと集合を同時に扱うために便利ですが、一般的ではありません。クラスを扱わない流儀では、&mathjax{\langle a, b \rangle};のことをそのまま&mathjax{(a,b)};と表記したりします。
*3 左辺が右辺に含まれることは定義から従いますが、右辺が左辺に含まれることを証明するには[[順序対の基本性質>#OP]]が必要になります。
*4 これは後に定義する直積という概念の特別な場合と自然に「同一視」されます。
*5 クラスを用いずに集合の組を順序対で直接定義する流儀でも、&mathjax{A \times B = \{c \in P(P(A \cup B
*6 例えば&mathjax{A \times B};を考える際に&mathjax{A};や&mathjax{B};が&mathjax{\emptyset};である場合を考えずに元を取ろうとしてしまうことがあります。
*7 &mathjax{(A,(B,C) )};の代わりに&mathjax{( (A,B),C)};を&mathjax{(A,B,C)};の定義とする流儀もあり、そちらの方が広く用いられているかもしれません。しかし&mathjax{(A,(B,C) )};を採用することで、&mathjax{(A,B,C)};の「第1成分」という用語が&mathjax{A};を指すものとして自然に意味を持ち、それは&mathjax{(A,B,C)};のクラスの構造のみで定まります。&mathjax{( (A,B),C)};を採用しても「第1成分」は意味を持ちますが、組としての第1成分&mathjax{(A,B)};なのか3つ組としての第1成分&mathjax{A};を指すものなのかが文脈に依存してしまいます。
*8 &mathjax{A \times (B \times C)};の代わりに&mathjax{(A \times B) \times C};を&mathjax{A \times B \times C};の定義とする流儀もあり、そちらの方が広く用いられているかもしれません。しかし&mathjax{A \times (B \times C)};を採用することで、&mathjax{A \times B \times C};の「第1成分」という用語が&mathjax{A};を指すものとして自然に意味を持ち、それは&mathjax{A \times B \times C};のクラスの構造のみで定まります。&mathjax{(A \times B) \times C};を採用しても「第1成分」は意味を持ちますが、2項直積としての第1成分&mathjax{A \times B};なのか3項直積としての第1成分&mathjax{A};を指すものなのかが文脈に依存してしまいます。
*9 こういった同語反復こそが、「自明な主張」の典型例です。「自分では直感的に理解していることに疑いの余地がないけれど証明を記述することが出来ない主張」のことを「自明な主張」と呼ぶ人も見掛けますが、あまり慣例ではありません。
*10 クラスを用いずに集合の組を順序対で直接定義する流儀では、定義から&mathjax{(A,B)};が集合をなします。
*11 これは慣例的な言い回しで、「仮定より、ある集合&mathjax{x \in A \times B};が存在する。&mathjax{A \times B};の定義より、ある&mathjax{a \in A};と&mathjax{b \in B};が存在し、&mathjax{x = (a,b)};である」という議論を表しています。
*12 以下、&mathjax{A \subset C};の証明と同様に&mathjax{B \subset D};を証明します。