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

1Corresponding lectures講義こうぎ

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.

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.

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.

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.

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

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.

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