直積集合ちょくせきしゅうごうCartesian productとべき集合しゅうごうpower set - 基本演習きほんえんしゅう

Cartesian products直積集合ちょくせきしゅうごう and power setsべき集合: basic exercises

1対応たいおうする講義こうぎlecture

1Corresponding lectures講義こうぎ

2演習えんしゅう方針ほうしん

直積集合ちょくせきしゅうごうCartesian productでは順序じゅんじょorderを確認かくにんし、べき集合しゅうごうpower setでは $$\in$$\in と $$\subseteq$$\subseteq の階層かいそうを区別くべつする。

2Exercise strategy

For a Cartesian product直積集合ちょくせきしゅうごう, check the order順序じゅんじょ of the components. For a power setべき集合, distinguish the levels represented by $$\in$$\in and $$\subseteq$$\subseteq.

3問題もんだい 1

$$A=\{0,1\}$$A=\{0,1\}、$$B=\{a,b\}$$B=\{a,b\} とする。$$A\times B$$A\times B と $$B\times A$$B\times A を書かき出だせ。

3.1解答かいとう

$$A\times B=\left\{\right(0,a),(0,b),(1,a),(1,b\left)\right\}$$A\times B=\{(0,a),(0,b),(1,a),(1,b)\} である。$$B\times A=\left\{\right(a,0),(a,1),(b,0),(b,1\left)\right\}$$B\times A=\{(a,0),(a,1),(b,0),(b,1)\} である。

3.2解説かいせつ

順序対じゅんじょついordered pairでは第だい 1 成分せいぶんと第だい 2 成分せいぶんを区別くべつする。したがって一般いっぱんに $$A\times B$$A\times B と $$B\times A$$B\times A は一致いっちしない。

3.3よくある誤あやまり

$$(0,a)$$(0,a) と $$(a,0)$$(a,0) を同おなじものとして扱あつかう誤あやまりである。

3Problem 1

Let $$A=\{0,1\}$$A=\{0,1\} and $$B=\{a,b\}$$B=\{a,b\}. List $$A\times B$$A\times B and $$B\times A$$B\times A.

3.1Answer

$$A\times B=\left\{\right(0,a),(0,b),(1,a),(1,b\left)\right\}$$A\times B=\{(0,a),(0,b),(1,a),(1,b)\}. Also $$B\times A=\left\{\right(a,0),(a,1),(b,0),(b,1\left)\right\}$$B\times A=\{(a,0),(a,1),(b,0),(b,1)\}.

3.2Explanation

In an ordered pair順序対じゅんじょつい, the first and second components are distinguished. Therefore $$A\times B$$A\times B and $$B\times A$$B\times A are generally not the same set.

3.3Common mistake

Do not treat $$(0,a)$$(0,a) and $$(a,0)$$(a,0) as the same object.

4問題もんだい 2

$$\left|A\right|=3$$|A|=3、$$\left|B\right|=4$$|B|=4 で、どちらも有限集合ゆうげんしゅうごうfinite setとする。$$|A\times B|$$|A\times B| を求もとめよ。

4.1解答かいとう

$$A$$A からの選択せんたくが 3 通とおり、$$B$$B からの選択せんたくが 4 通とおりある。したがって $$|A\times B|=3·4=12$$|A\times B|=3\cdot4=12 である。

4.2解説かいせつ

直積集合ちょくせきしゅうごうCartesian productの元げんelementは $$(a,b)$$(a,b) であり、2 段階だんかいの選択せんたくで決きまる。

4.3よくある誤あやまり

$$\left|A\right|+\left|B\right|=7$$|A|+|B|=7 と足たしてしまう誤あやまりである。直積ちょくせきは「同時どうじに選えらぶ」ので掛かけ算ざんになる。

4Problem 2

Suppose $$\left|A\right|=3$$|A|=3 and $$\left|B\right|=4$$|B|=4, and both are finite sets有限集合ゆうげんしゅうごう. Find $$|A\times B|$$|A\times B|.

4.1Answer

There are 3 choices from $$A$$A and 4 choices from $$B$$B. Therefore $$|A\times B|=3·4=12$$|A\times B|=3\cdot4=12.

4.2Explanation

An element元げん of a Cartesian product直積集合ちょくせきしゅうごう has the form $$(a,b)$$(a,b), so it is determined by two stages of choice.

4.3Common mistake

Do not add and write $$\left|A\right|+\left|B\right|=7$$|A|+|B|=7. A Cartesian product chooses simultaneously, so the counts multiply.

5問題もんだい 3

$$A=\{1,2\}$$A=\{1,2\} とする。$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) を書かき出だせ。

5.1解答かいとう

$$A$$A の部分集合ぶぶんしゅうごうsubsetは $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]},\left\{1\right\},\left\{2\right\},\{1,2\}$$\varnothing,\{1\},\{2\},\{1,2\} である。したがって $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)=\{\text{[PARSE ERROR: Undefined("Command("varnothing")")]},\{1\},\{2\},\{1,2\left\}\right\}$$\mathcal P(A)=\{\varnothing,\{1\},\{2\},\{1,2\}\} である。

5.2解説かいせつ

べき集合しゅうごうpower setの元げんelementは、元もとの集合しゅうごうsetの部分集合ぶぶんしゅうごうsubsetである。

5.3よくある誤あやまり

$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)=\{1,2\}$$\mathcal P(A)=\{1,2\} と書かく誤あやまりである。これは $$A$$A 自身じしんであって、べき集合しゅうごうpower setではない。

5Problem 3

Let $$A=\{1,2\}$$A=\{1,2\}. List $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A).

5.1Answer

The subsets部分集合ぶぶんしゅうごう of $$A$$A are $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]},\left\{1\right\},\left\{2\right\},\{1,2\}$$\varnothing,\{1\},\{2\},\{1,2\}. Therefore $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)=\{\text{[PARSE ERROR: Undefined("Command("varnothing")")]},\{1\},\{2\},\{1,2\left\}\right\}$$\mathcal P(A)=\{\varnothing,\{1\},\{2\},\{1,2\}\}.

5.2Explanation

The elements元げん of a power setべき集合 are the subsets部分集合ぶぶんしゅうごう of the original set集合しゅうごう.

5.3Common mistake

Do not write $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)=\{1,2\}$$\mathcal P(A)=\{1,2\}. That is $$A$$A itself, not its power set.

6問題もんだい 4

$$A=\{1,2\}$$A=\{1,2\} とする。$$1\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$1\in\mathcal P(A)、$$\left\{1\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\{1\}\in\mathcal P(A)、$$\left\{1\right\}\subseteq A$$\{1\}\subseteq A の真偽しんぎを判定はんていせよ。

6.1解答かいとう

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

$$\left\{1\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\{1\}\in\mathcal P(A) は真しんである。$$\left\{1\right\}$$\{1\} は $$A$$A の部分集合ぶぶんしゅうごうsubsetだからである。

$$\left\{1\right\}\subseteq A$$\{1\}\subseteq A も真しんである。

6.2解説かいせつ

この問題もんだいは、元げんelementとしての $$1$$1 と、集合しゅうごうsetとしての $$\left\{1\right\}$$\{1\} を区別くべつする練習れんしゅうである。

6.3よくある誤あやまり

$$1$$1 と $$\left\{1\right\}$$\{1\} を同一視どういつしする誤あやまりである。

6Problem 4

Let $$A=\{1,2\}$$A=\{1,2\}. Decide the truth values of $$1\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$1\in\mathcal P(A), $$\left\{1\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\{1\}\in\mathcal P(A), and $$\left\{1\right\}\subseteq A$$\{1\}\subseteq A.

6.1Answer

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

The statement $$\left\{1\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\{1\}\in\mathcal P(A) is true because $$\left\{1\right\}$$\{1\} is a subset of $$A$$A.

The statement $$\left\{1\right\}\subseteq A$$\{1\}\subseteq A is also true.

6.2Explanation

This problem practices distinguishing $$1$$1 as an element元げん from $$\left\{1\right\}$$\{1\} as a set集合しゅうごう.

6.3Common mistake

Do not identify $$1$$1 with $$\left\{1\right\}$$\{1\}.

7問題もんだい 5

$$\left|A\right|=n$$|A|=n の有限集合ゆうげんしゅうごうfinite setについて、$$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2^n$$|\mathcal P(A)|=2^n となる理由りゆうを説明せつめいせよ。

7.1解答かいとう

$$A$$A の各かく元げんelementについて、部分集合ぶぶんしゅうごうsubsetに入いれるか入いれないかの 2 通とおりを選えらぶ。$$n$$n 個この元げんelementについて独立どくりつに選択せんたくするので、総数そうすうは $$2^n$$2^n である。

7.2解説かいせつ

べき集合しゅうごうpower setは、選択せんたくの全体ぜんたいを集あつめた集合しゅうごうsetである。$$n=0$$n=0 の場合ばあいも、$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(\text{[PARSE ERROR: Undefined("Command("varnothing")")]}\right)=\left\{\text{[PARSE ERROR: Undefined("Command("varnothing")")]}\right\}$$\mathcal P(\varnothing)=\{\varnothing\} なので $$2^0=1$$2^0=1 と整合せいごうする。

7.3よくある誤あやまり

$$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2n$$|\mathcal P(A)|=2n と考かんがえる誤あやまりである。各かく元げんelementについて 2 択たくを掛かけ合あわせるため $$2^n$$2^n である。

7Problem 5

For a finite set有限集合ゆうげんしゅうごう with $$\left|A\right|=n$$|A|=n, explain why $$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2^n$$|\mathcal P(A)|=2^n.

7.1Answer

For each element元げん of $$A$$A, choose whether to include it in a subset部分集合ぶぶんしゅうごう or not. These two choices are made independently for all $$n$$n elements, so the total number is $$2^n$$2^n.

7.2Explanation

A power setべき集合 collects all possible choices. The boundary case $$n=0$$n=0 also agrees, because $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(\text{[PARSE ERROR: Undefined("Command("varnothing")")]}\right)=\left\{\text{[PARSE ERROR: Undefined("Command("varnothing")")]}\right\}$$\mathcal P(\varnothing)=\{\varnothing\} and $$2^0=1$$2^0=1.

7.3Common mistake

Do not write $$\left|\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A\left)\right|=2n$$|\mathcal P(A)|=2n. The two choices for each element are multiplied, giving $$2^n$$2^n.

8証明しょうめい演習えんしゅう：直積ちょくせきCartesian productとべき集合しゅうごうpower setの保存性ほぞんせい

8.1問題もんだい

つぎを証明しょうめいせよ。

また、$$A\subseteq A^{\prime }$$A\subseteq A'、$$B\subseteq B^{\prime }$$B\subseteq B' なら

であることを証明しょうめいせよ。

8Proof exercise: preservation for Cartesian products直積集合ちょくせきしゅうごう and power setsべき集合

8.1Problem

Prove the following equivalence.

Also prove that if $$A\subseteq A^{\prime }$$A\subseteq A' and $$B\subseteq B^{\prime }$$B\subseteq B', then

8.2解答かいとう

$$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 である。したがって $$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) となり、$$a\in B$$a\in B である。したがって $$A\subseteq B$$A\subseteq B である。

$$(a,b)\in A\times B$$(a,b)\in A\times B とする。$$a\in A$$a\in A かつ $$b\in B$$b\in B である。$$A\subseteq A^{\prime }$$A\subseteq A'、$$B\subseteq B^{\prime }$$B\subseteq B' より $$a\in A^{\prime }$$a\in A'、$$b\in B^{\prime }$$b\in B' なので、$$(a,b)\in A^{\prime }\times B^{\prime }$$(a,b)\in A'\times B' である。

8.3解説かいせつ

べき集合しゅうごうpower setは部分集合ぶぶんしゅうごうsubsetを要素ようそにするため、包含ほうがんinclusionの情報じょうほうをもう一ひと段だん上うえの集合しゅうごうsetへ移うつしている。直積ちょくせきCartesian productは各成分かくせいぶんごとに包含ほうがんを確認かくにんすればよい。

8.2Answer

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. Hence $$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). If $$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). Hence $$\left\{a\right\}\in \text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(B\right)$$\{a\}\in\mathcal P(B), which means $$a\in B$$a\in B. Therefore $$A\subseteq B$$A\subseteq B.

Now suppose $$(a,b)\in A\times B$$(a,b)\in A\times B. Then $$a\in A$$a\in A and $$b\in B$$b\in B. From $$A\subseteq A^{\prime }$$A\subseteq A' and $$B\subseteq B^{\prime }$$B\subseteq B', we get $$a\in A^{\prime }$$a\in A' and $$b\in B^{\prime }$$b\in B', so $$(a,b)\in A^{\prime }\times B^{\prime }$$(a,b)\in A'\times B'.

8.3Explanation

A power setべき集合 has subsets部分集合ぶぶんしゅうごう as its elements, so it lifts inclusion包含ほうがん information one level up. A Cartesian product直積集合ちょくせきしゅうごう is checked component by component.