べき集合しゅうごうpower setの基本きほん

1導入どうにゅう

べき集合しゅうごうpower setで重要じゅうようなのは、集合しゅうごうsetの元げんelementではなく、部分集合ぶぶんしゅうごうsubsetそのものを新あたらしい元げんelementとして扱あつかう視点してんである。$$A$$A の元げんelementを選えらぶか選えらばないかという全すべての選択せんたくを集あつめたものがべき集合しゅうごうpower setである。

この視点してんは、場合ばあいの数かず、論理ろんりlogic、状態空間じょうたいくうかんstate space、ブール束そくBoolean latticeに接続せつぞくする。べき集合しゅうごうpower setは、集合しゅうごうsetを 1 段だん「対象化たいしょうか」する操作そうさである。

空集合くうしゅうごうempty setと $$A$$A 自身じしんは、いつも $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) の元げんelementである。$$A$$A の各かく元げんelementについて「選えらぶ・選えらばない」を独立どくりつに決きめるので、有限集合ゆうげんしゅうごうでは個数こすうが $$2^{\left|A\right|}$$2^{|A|} になる。

2用語ようごと定義ていぎ

集合しゅうごうset $$A$$A のべき集合しゅうごうpower set $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) を

で定義ていぎする。つまり、$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) の元げんelementは、$$A$$A の部分集合ぶぶんしゅうごうsubsetである。

$$x\in A$$x\in A と $$B\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$B\in\mathcal P(A) は違ちがう種類しゅるいの主張しゅちょうである。前者ぜんしゃは $$x$$x が $$A$$A の元げんelementであるという主張しゅちょうであり、後者こうしゃは $$B$$B が $$A$$A の部分集合ぶぶんしゅうごうsubsetであるという主張しゅちょうである。

3方針ほうしん：個数こすうcardinalityを数かぞえる

べき集合しゅうごうpower setを理解りかいするときは、各かく元げんelementについて「選えらぶ」または「選えらばない」の 2 択たくを考かんがえる。有限集合ゆうげんしゅうごう $$A$$A で $$\left|A\right|=n$$|A|=n なら、各かく元げんelementについて 2 通とおりの選択せんたくがあるため、

となる。この式しきは、べき集合しゅうごうpower setという名前なまえの理由りゆうでもある。

4直感的ちょっかんてきな例れい

$$A=\{a,b,c\}$$A=\{a,b,c\} とする。べき集合しゅうごうpower setは、$$a,b,c$$a,b,c それぞれについて採用さいようするかどうかを決きめた結果けっかの全体ぜんたいである。

である。$$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing も $$A$$A の部分集合ぶぶんしゅうごうsubsetであり、$$A$$A 自身じしんも $$A$$A の部分集合ぶぶんしゅうごうsubsetであるため、どちらも $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) の元げんelementである。

5厳密げんみつな使つかい方かた

$$B\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$B\in\mathcal P(A) は、定義ていぎより $$B\subseteq A$$B\subseteq A と同値どうちである。したがって、べき集合しゅうごうpower setに関かんする証明しょうめいでは、

を最初さいしょに展開てんかいするのが基本きほんである。

たとえば $$A\subseteq C$$A\subseteq C なら $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)\subseteq \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(C\right)$$\mathcal P(A)\subseteq\mathcal P(C) である。任意にんいの $$B\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$B\in\mathcal P(A) を取とると、$$B\subseteq A$$B\subseteq A であり、$$A\subseteq C$$A\subseteq C なので、包含ほうがんinclusionの推移性すいいせいtransitivityより $$B\subseteq C$$B\subseteq C である。したがって $$B\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(C\right)$$B\in\mathcal P(C) である。

6境界例きょうかいれい：空集合くうしゅうごうempty set

$$A=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$A=\varnothing の場合ばあいを確認かくにんする。$$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing の部分集合ぶぶんしゅうごうsubsetは $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing 自身じしんだけであるため、

である。したがって $$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(\text{[PARSE ERROR: Undefined("Command("varnothing")")]}\left)\right|=1=2^0$$|\mathcal P(\varnothing)|=1=2^0 であり、個数こすうの公式こうしきと整合せいごうする。

7例題れいだい：べき集合しゅうごうpower setの元げんelementを判定はんていする

7.1問題もんだい

$$A=\{1,2\}$$A=\{1,2\} とする。次つぎの主張しゅちょうの真偽しんぎを判定はんていせよ。

7.2解説かいせつ

$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) の元げんelementは $$A$$A の部分集合ぶぶんしゅうごうsubsetである。$$1$$1 は $$A$$A の元げんelementではあるが、部分集合ぶぶんしゅうごうsubsetではないため、$$1\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$1\in\mathcal P(A) は偽ぎである。

一方いっぽう、$$\left\{1\right\}\subseteq A$$\{1\}\subseteq A なので、$$\left\{1\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\{1\}\in\mathcal P(A) は真しんである。また、空集合くうしゅうごうempty setは任意にんいの集合しゅうごうsetの部分集合ぶぶんしゅうごうsubsetなので、$$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\varnothing\in\mathcal P(A) も真しんである。

8包含順序ほうがんじゅんじょinclusion orderとしてのべき集合しゅうごうpower set

順序じゅんじょと束そくlatticeの正式せいしきな定義ていぎは後続こうぞくで扱あつかう。この節せつは先取さきどりであり、ここでは包含順序ほうがんじゅんじょinclusion orderに限かぎって最小限さいしょうげんの言葉ことばだけを使つかう。最小元さいしょうげんleast elementとは全すべての元げんの下したにある元げん、最大元さいだいげんgreatest elementとは全すべての元げんの上うえにある元げんである。2つの元げんの上限じょうげんleast upper boundは両方りょうほうを含ふくむ最小さいしょうの元げん、下限かげんgreatest lower boundは両方りょうほうに含ふくまれる最大さいだいの元げんである。

$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) には、包含ほうがんinclusion $$\subseteq$$\subseteq によって順序じゅんじょorderを入いれられる。$$B,C\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$B,C\in\mathcal P(A) に対たいして、$$B\subseteq C$$B\subseteq C なら「$$B$$B は $$C$$C 以下いかである」と考かんがえる。

この順序じゅんじょorderでは、最小元さいしょうげんleast elementは $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing、最大元さいだいげんgreatest elementは $$A$$A である。さらに、$$B$$B と $$C$$C の上限じょうげんleast upper boundは $$B\cup C$$B\cup C、下限かげんgreatest lower boundは $$B\cap C$$B\cap C である。この構造こうぞうがブール束そくBoolean latticeである。

9証明しょうめい補足ほそく：べき集合しゅうごうと包含ほうがんの同値性どうちせい

重要じゅうような定理ていりは

である。まず $$A\subseteq B$$A\subseteq B とする。$$X\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$X\in\mathcal{P}(A) なら $$X\subseteq A$$X\subseteq A である。$$A\subseteq B$$A\subseteq B なので $$X\subseteq B$$X\subseteq B であり、$$X\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(B\right)$$X\in\mathcal{P}(B) である。

逆ぎゃくに $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)\subseteq \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(B\right)$$\mathcal{P}(A)\subseteq\mathcal{P}(B) とする。$$a\in A$$a\in A を任意にんいに取とる。このとき $$\left\{a\right\}\subseteq A$$\{a\}\subseteq A なので $$\left\{a\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\{a\}\in\mathcal{P}(A) である。仮定かていより $$\left\{a\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(B\right)$$\{a\}\in\mathcal{P}(B) だから $$\left\{a\right\}\subseteq B$$\{a\}\subseteq B であり、$$a\in B$$a\in B である。よって $$A\subseteq B$$A\subseteq B である。

10見分みわけ方かたと関連かんれんリンク

• 「部分集合ぶぶんしゅうごうを全部ぜんぶ集あつめる」と書かかれていたら、べき集合しゅうごうpower setを考かんがえる。
• $$B\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$B\in\mathcal P(A) は $$B\subseteq A$$B\subseteq A に翻訳ほんやくする。
• $$x\in A$$x\in A と $$\left\{x\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\{x\}\in\mathcal P(A) を区別くべつする。
• $$\left|A\right|=n$$|A|=n の有限集合ゆうげんしゅうごうなら、$$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2^n$$|\mathcal P(A)|=2^n を使つかう。

11演習えんしゅうリンク