Basics of the power setべき集合

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.

The empty set空集合くうしゅうごう and $$A$$A itself always belong to $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A). For a finite set, each element can independently be included or excluded, so $$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2^{\left|A\right|}$$|\mathcal P(A)|=2^{|A|}.

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.

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.”

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).

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).

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.

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.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.

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ブール束そく.

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.

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.

11Exercise links