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

Basics of the 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 自身じしんは、いつも $$mathcalP\left(A\right)$$mathcal P(A) の元げんelementである。$$A$$A の各かく元げんelementについて「選えらぶ・選えらばない」を独立どくりつに決きめるので、有限集合ゆうげんしゅうごうでは個数こすうが $$2^{\left|A\right|}$$2^{|A|} になる。

1Introduction

The key shift in a power setべき集合 is that subsets部分集合ぶぶんしゅうごう themselves become new elements元げん, rather than focusing only on the elements of the original set集合しゅうごう. The power set collects every possible choice of which elements of $$A$$A to include.

This viewpoint connects to counting, logic論理ろんり, state spaces状態空間じょうたいくうかん, and Boolean latticesブール束そく. A power set is an operation that turns a set into an object one level higher.

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であるという主張しゅちょうである。

2Terms and definition

For a set集合しゅうごう $$A$$A, the power setべき集合 $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) is defined by

Thus the elements元げん of $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) are the subsets部分集合ぶぶんしゅうごう of $$A$$A.

The statements $$x\in A$$x\in A and $$B\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$B\in\mathcal P(A) are different kinds of statements. The first says that $$x$$x is an element of $$A$$A, while the second says that $$B$$B is a subset of $$A$$A.

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

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

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

3Method: count the cardinality個数こすう

To understand a power setべき集合, think of two choices for each element元げん: include it or do not include it. If $$A$$A is finite and $$\left|A\right|=n$$|A|=n, then each element gives two choices, so

This formula is also the reason for the name “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である。

4Intuitive example

Let $$A=\{a,b,c\}$$A=\{a,b,c\}. The power setべき集合 is the collection of all results obtained by deciding whether to include each of $$a,b,c$$a,b,c.

Both $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing and $$A$$A itself are subsets部分集合ぶぶんしゅうごう of $$A$$A, so both are elements元げん of $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A).

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) である。

5Precise use

By definition, $$B\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$B\in\mathcal P(A) is equivalent to $$B\subseteq A$$B\subseteq A. Therefore proofs about a power setべき集合 usually begin by expanding

For example, if $$A\subseteq C$$A\subseteq C, then $$\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). Take arbitrary $$B\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$B\in\mathcal P(A). Then $$B\subseteq A$$B\subseteq A, and since $$A\subseteq C$$A\subseteq C, transitivity推移性すいいせい of inclusion包含ほうがん gives $$B\subseteq C$$B\subseteq C. Hence $$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 であり、個数こすうの公式こうしきと整合せいごうする。

6Boundary case: the empty set空集合くうしゅうごう

For $$A=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$A=\varnothing, the only subset部分集合ぶぶんしゅうごう of $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing is $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing itself. Therefore

Thus $$\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, which agrees with the counting formula.

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

7.1問題もんだい

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

7Worked example: decide membership[元であること] in a power setべき集合

7.1Problem

Let $$A=\{1,2\}$$A=\{1,2\}. Decide the truth values of the following statements.

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) も真しんである。

7.2Explanation

The elements元げん of $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) are the subsets部分集合ぶぶんしゅうごう of $$A$$A. The object $$1$$1 is an element of $$A$$A, but it is not a subset of $$A$$A, so $$1\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$1\in\mathcal P(A) is false.

On the other hand, $$\left\{1\right\}\subseteq A$$\{1\}\subseteq A, so $$\left\{1\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\{1\}\in\mathcal P(A) is true. Also, the empty set空集合くうしゅうごう is a subset of every set集合しゅうごう, so $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\varnothing\in\mathcal P(A) is true.

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である。

8The power setべき集合 as an inclusion order包含順序ほうがんじゅんじょ

The formal definitions of orders順序じゅんじょ and lattices束そく come later. This section is a preview, and it uses only the minimum vocabulary for the inclusion order. A least element最小元さいしょうげん lies below every element, and a greatest element最大元さいだいげん lies above every element. The least upper bound上限じょうげん of two elements is the smallest element above both, and the greatest lower bound下限かげん is the largest element below both.

The set $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) can be ordered by inclusion包含ほうがん $$\subseteq$$\subseteq. For $$B,C\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$B,C\in\mathcal P(A), if $$B\subseteq C$$B\subseteq C, we regard $$B$$B as being below $$C$$C.

In this order順序じゅんじょ, the least element最小元さいしょうげん is $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing and the greatest element最大元さいだいげん is $$A$$A. The least upper bound上限じょうげん of $$B$$B and $$C$$C is $$B\cup C$$B\cup C, and the greatest lower bound下限かげん is $$B\cap C$$B\cap C. This structure is a 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 である。

9Proof supplement: equivalence between power sets and inclusion

An important theorem is

First assume $$A\subseteq B$$A\subseteq B. If $$X\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$X\in\mathcal P(A), then $$X\subseteq A$$X\subseteq A. Since $$A\subseteq B$$A\subseteq B, we get $$X\subseteq B$$X\subseteq B, so $$X\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(B\right)$$X\in\mathcal P(B).

Conversely, assume $$\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). Take arbitrary $$a\in A$$a\in A. Then $$\left\{a\right\}\subseteq A$$\{a\}\subseteq A, so $$\left\{a\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\{a\}\in\mathcal P(A). By the assumption, $$\left\{a\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(B\right)$$\{a\}\in\mathcal P(B), hence $$\left\{a\right\}\subseteq B$$\{a\}\subseteq B and $$a\in B$$a\in B. Therefore $$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 を使つかう。

10How to identify it and related links

• If a problem says to collect all subsets部分集合ぶぶんしゅうごう, think of the power setべき集合.
• Translate $$B\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$B\in\mathcal P(A) into $$B\subseteq A$$B\subseteq A.
• Distinguish $$x\in A$$x\in A from $$\left\{x\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\{x\}\in\mathcal P(A).
• For a finite set有限集合ゆうげんしゅうごう with $$\left|A\right|=n$$|A|=n, use $$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2^n$$|\mathcal P(A)|=2^n.