集合しゅうごうsetと集合演算しゅうごうえんざんset operation-基本演習きほんえんしゅう

Sets集合しゅうごう and set operations集合演算しゅうごうえんざん - basic exercises

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

集合しゅうごうsetの問題もんだいでは、図ずで予想よそうしてよいが、解答かいとうでは $$x\in A$$x\in A の条件じょうけんに戻もどる。包含ほうがんinclusionは「任意にんいの元げんelement」から始はじめ、集合しゅうごうsetの等式とうしきは両側りょうがわの包含ほうがんinclusionで示しめす。

Venn図ずVenn diagramは方針ほうしんを立たてる補助ほじょであり、証明しょうめいそのものではない。等式とうしきでは左ひだりから右みぎ、右みぎから左ひだりの両方向りょうほうこうを示しめし、失敗しっぱいを示しめるときは条件じょうけんを破やぶる反例はんれいcounterexampleを挙あげる。

1Exercise method

In problems about sets集合しゅうごう, a diagram may help you guess, but the answer should return to the condition $$x\in A$$x\in A. An inclusion包含ほうがん proof begins with an arbitrary element元げん, and a set equality is proved by inclusions in both directions.

2問題もんだい 1

$$A=\{1,2,3\}$$A=\{1,2,3\}、$$B=\{3,2,1,1\}$$B=\{3,2,1,1\} とする。$$A=B$$A=B であることを説明せつめいせよ。

2Problem 1

Let $$A=\{1,2,3\}$$A=\{1,2,3\} and $$B=\{3,2,1,1\}$$B=\{3,2,1,1\}. Explain why $$A=B$$A=B.

2.1解答かいとう

集合しゅうごうsetでは順序じゅんじょと重複ちょうふくを記録きろくしない。$$A$$A の元げんelementは $$1,2,3$$1,2,3 であり、$$B$$B の元げんelementも $$1,2,3$$1,2,3 である。したがって任意にんいの $$x$$x について $$x\in A⟺x\in B$$x\in A\Longleftrightarrow x\in B が成なり立たつので、外延性がいえんせいextensionalityより $$A=B$$A=B である。

2.1Answer

A set集合しゅうごう does not record order or repetition. The elements元げん of $$A$$A are $$1,2,3$$1,2,3, and the elements of $$B$$B are also $$1,2,3$$1,2,3. Therefore, for every $$x$$x,

so $$A=B$$A=B by extensionality外延性がいえんせい.

2.2解説かいせつ

この問題もんだいは、集合しゅうごうsetの同一性どういつせいが表示ひょうじの仕方しかたではなく元げんelementの一致いっちで決きまることを確認かくにんしている。

2.2Explanation

This problem checks that the identity of a set is determined by equality of elements, not by the way the set is displayed.

2.3よくある誤あやまり

書かき出だしたリストの並ならび順じゅんや重複ちょうふくが違ちがうから別べつの集合しゅうごうsetだと判断はんだんする誤あやまりである。

2.3Common mistake

A common mistake is to decide that the sets are different because the order or repetition in the written lists is different.

3問題もんだい 2

全体集合ぜんたいしゅうごうuniversal setを $$U=\{1,2,3,4,5\}$$U=\{1,2,3,4,5\} とし、$$A=\{1,2,3\}$$A=\{1,2,3\}、$$B=\{3,4\}$$B=\{3,4\} とする。$$A\cup B$$A\cup B、$$A\cap B$$A\cap B、$$A\setminus B$$A\setminus B、$$A^c$$A^c を求もとめよ。

3Problem 2

Let the universal set全体集合ぜんたいしゅうごう be $$U=\{1,2,3,4,5\}$$U=\{1,2,3,4,5\}, and let $$A=\{1,2,3\}$$A=\{1,2,3\} and $$B=\{3,4\}$$B=\{3,4\}. Find $$A\cup B$$A\cup B, $$A\cap B$$A\cap B, $$A\setminus B$$A\setminus B, and $$A^c$$A^c.

3.1解答かいとう

和集合わしゅうごうunionは少すくなくとも一方いっぽうに属ぞくする元げんelementの集合しゅうごうなので、$$A\cup B=\{1,2,3,4\}$$A\cup B=\{1,2,3,4\} である。

共通部分きょうつうぶぶんintersectionは両方りょうほうに属ぞくする元げんelementの集合しゅうごうなので、$$A\cap B=\left\{3\right\}$$A\cap B=\{3\} である。

差集合さしゅうごうset differenceは $$A$$A に属ぞくし $$B$$B に属ぞくしない元げんelementの集合しゅうごうなので、$$A\setminus B=\{1,2\}$$A\setminus B=\{1,2\} である。

補集合ほしゅうごうcomplementは $$U$$U の中なかで $$A$$A に属ぞくしない元げんelementの集合しゅうごうなので、$$A^c=\{4,5\}$$A^c=\{4,5\} である。

3.1Answer

The union和集合わしゅうごう contains elements belonging to at least one of the two sets, so $$A\cup B=\{1,2,3,4\}$$A\cup B=\{1,2,3,4\}.

The intersection共通部分きょうつうぶぶん contains elements belonging to both sets, so $$A\cap B=\left\{3\right\}$$A\cap B=\{3\}.

The set difference差集合さしゅうごう contains elements belonging to $$A$$A and not to $$B$$B, so $$A\setminus B=\{1,2\}$$A\setminus B=\{1,2\}.

The complement補集合ほしゅうごう contains elements of $$U$$U that do not belong to $$A$$A, so $$A^c=\{4,5\}$$A^c=\{4,5\}.

3.2解説かいせつ

補集合ほしゅうごうcomplementでは全体集合ぜんたいしゅうごうuniversal setを固定こていする必要ひつようがある。この問題もんだいでは $$U$$U が明示めいじされているため $$A^c$$A^c を決きめられる。

3.2Explanation

For a complement補集合ほしゅうごう, the universal set全体集合ぜんたいしゅうごう must be fixed. In this problem, $$U$$U is explicitly given, so $$A^c$$A^c is determined.

3.3よくある誤あやまり

$$A^c$$A^c を「$$A$$A に書かかれていない全すべての数かず」と考かんがえ、全体集合ぜんたいしゅうごうuniversal setを確認かくにんしない誤あやまりである。

3.3Common mistake

A common mistake is to treat $$A^c$$A^c as "all numbers not written in $$A$$A" without checking the universal set.

4問題もんだい 3

任意にんいの集合しゅうごうset $$A,B,C$$A,B,C について、$$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$$A\cap(B\cup C)=(A\cap B)\cup(A\cap C) を示しめせ。

4Problem 3

For arbitrary sets集合しゅうごう $$A,B,C$$A,B,C, prove $$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$$A\cap(B\cup C)=(A\cap B)\cup(A\cap C).

4.1解答かいとう

任意にんいの $$x$$x を取とる。すると

である。論理ろんりlogicの分配法則ぶんぱいほうそくdistributive lawより、これは

と同値どうちである。したがって

である。任意にんいの $$x$$x について同値どうちなので、外延性がいえんせいextensionalityより等式とうしきが成なり立たつ。

4.1Answer

Take arbitrary $$x$$x. Then

By the distributive law分配法則ぶんぱいほうそく of logic論理ろんり, this is equivalent to

Therefore

Since the equivalence holds for arbitrary $$x$$x, the equality follows by extensionality外延性がいえんせい.

4.2解説かいせつ

この問題もんだいは、集合演算しゅうごうえんざんset operationを元げんelementの条件じょうけんへ翻訳ほんやくする練習れんしゅうである。

4.2Explanation

This problem practices translating a set operation集合演算しゅうごうえんざん into a condition on an element元げん.

4.3よくある誤あやまり

図ずだけで説明せつめいして、任意にんいの $$x$$x に対たいする同値性どうちせいを示しめさない誤あやまりである。

4.3Common mistake

A common mistake is to rely only on a diagram and not prove the equivalence for arbitrary $$x$$x.

5問題もんだい 4

$$A_n=\{m\in \mathbb{Z}\mid n\text{は}m\text{を割り切る}\}$$A_n=\{m\in\mathbb Z\mid n\text{ は }m\text{ を割り切る}\} とする。$$\bigcap _{n=1}^4{A}_n$$\bigcap_{n=1}^{4}A_n を説明せつめいせよ。

5Problem 4

Let $$A_n=\{m\in \mathbb{Z}\mid n\text{divides}m\}$$A_n=\{m\in\mathbb Z\mid n\text{ divides }m\}. Describe $$\bigcap _{n=1}^4{A}_n$$\bigcap_{n=1}^{4}A_n.

5.1解答かいとう

$$m\in \bigcap _{n=1}^4{A}_n$$m\in\bigcap_{n=1}^{4}A_n とは、$$m$$m が 1、2、3、4 のすべてで割わり切きれるという意味いみである。したがって $$m$$m は $$\mathrm{l}\mathrm{c}\mathrm{m}(1,2,3,4)=12$$\mathrm{lcm}(1,2,3,4)=12 の倍数ばいすうである。よって $$\bigcap _{n=1}^4{A}_n$$\bigcap_{n=1}^{4}A_n は 12 の倍数ばいすう全体ぜんたいである。

5.1Answer

The statement $$m\in \bigcap _{n=1}^4{A}_n$$m\in\bigcap_{n=1}^{4}A_n means that $$m$$m is divisible by all of $$1,2,3,4$$1,2,3,4. Hence $$m$$m is a multiple of $$\mathrm{l}\mathrm{c}\mathrm{m}(1,2,3,4)=12$$\mathrm{lcm}(1,2,3,4)=12. Therefore $$\bigcap _{n=1}^4{A}_n$$\bigcap_{n=1}^{4}A_n is the set of all multiples of $$12$$12.

5.2解説かいせつ

添字付そえじつき共通部分きょうつうぶぶんindexed intersectionでは「すべての添字そえじindexについて」を確認かくにんする。この問題もんだいでは、複数ふくすうの割わり切きれる条件じょうけんを同時どうじに満みたすことが要求ようきゅうされている。

5.2Explanation

For an indexed intersection添字付き共通部分, one checks the condition for every index添字そえじ. Here the element must satisfy several divisibility conditions at the same time.

5.3よくある誤あやまり

共通部分きょうつうぶぶんintersectionを和集合わしゅうごうunionと混同こんどうし、「どれか少すくなくとも 1 つで割わり切きれる」と読よむ誤あやまりである。共通部分きょうつうぶぶんintersectionでは、指定していされた条件じょうけんをすべて同時どうじに満みたす必要ひつようがある。

5.3Common mistake

A common mistake is to confuse an intersection共通部分きょうつうぶぶん with a union和集合わしゅうごう and read the condition as "divisible by at least one of them".

6問題もんだい 5

順序上じゅんじょじょうの注意ちゅういとして、この問題もんだいだけ濃度のうどcardinalityの考かんがえ方かたを先取さきどりする。単射たんしゃinjectionとは違ちがう元げんが同おなじ相手あいてへ重かさならないこと、全射ぜんしゃsurjectionとは行いき先さきに余あまりがないこと、全単射ぜんたんしゃbijectionとはその両方りょうほうを満みたす対応たいおうである。

正せいの偶数ぐうすう全体ぜんたい $$E=\{2,4,6,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$E=\{2,4,6,\dots\} と $$\mathbb{N}=\{1,2,3,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{1,2,3,\dots\} の間あいだに全単射ぜんたんしゃbijectionを構成こうせいせよ。

6Problem 5

Order note: this problem briefly previews the idea of cardinality濃度のうど. An injection単射たんしゃ means that distinct inputs do not overlap at the same output, a surjection全射ぜんしゃ means that no output is left over, and a bijection全単射ぜんたんしゃ means both conditions hold.

Construct a bijection全単射ぜんたんしゃ between the set $$E=\{2,4,6,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$E=\{2,4,6,\dots\} of positive even numbers and $$\mathbb{N}=\{1,2,3,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{1,2,3,\dots\}.

6.1解答かいとう

$$f:\mathbb{N}\to E$$f:\mathbb N\to E を $$f\left(n\right)=2n$$f(n)=2n と定義ていぎする。$$f\left(n_1\right)=f\left(n_2\right)$$f(n_1)=f(n_2) なら $$2n_1=2n_2$$2n_1=2n_2 なので、実数じっすうの非零定数ひれいていすう $$2$$2 で割わって $$n_1=n_2$$n_1=n_2 を得える。よって $$f$$f は単射たんしゃinjectionである。

任意にんいの $$e\in E$$e\in E は $$e=2n$$e=2n と書かける正せいの整数せいすう $$n$$n を持もつ。したがって $$f\left(n\right)=e$$f(n)=e であり、$$f$$f は全射ぜんしゃsurjectionである。よって $$f$$f は全単射ぜんたんしゃbijectionである。

6.1Answer

Define $$f:\mathbb{N}\to E$$f:\mathbb N\to E by $$f\left(n\right)=2n$$f(n)=2n. If $$f\left(n_1\right)=f\left(n_2\right)$$f(n_1)=f(n_2), then $$2n_1=2n_2$$2n_1=2n_2, and dividing by the nonzero real constant $$2$$2 gives $$n_1=n_2$$n_1=n_2. Hence $$f$$f is an injection単射たんしゃ.

For arbitrary $$e\in E$$e\in E, there is a positive integer $$n$$n such that $$e=2n$$e=2n. Thus $$f\left(n\right)=e$$f(n)=e, so $$f$$f is a surjection全射ぜんしゃ. Therefore $$f$$f is a bijection全単射ぜんたんしゃ.

6.2解説かいせつ

濃度のうどcardinalityは、数かぞえ終おえることではなく、全単射ぜんたんしゃbijectionで比較ひかくする。この問題もんだいは、無限集合むげんしゅうごうでは真しんの部分集合ぶぶんしゅうごうproper subsetが全体ぜんたいと同おなじ濃度のうどcardinalityを持もちうることを確認かくにんしている。

6.2Explanation

Cardinality濃度のうど is compared by bijections, not by whether one can finish counting. This problem checks that an infinite set may have the same cardinality as a proper subset.

6.3よくある誤あやまり

$$E⊊\mathbb{N}$$E\subsetneq\mathbb N だから濃度のうども小ちいさいと判断はんだんする誤あやまりである。これは有限集合ゆうげんしゅうごうの直感ちょっかんを無限集合むげんしゅうごうへそのまま移うつしたことによる。

6.3Common mistake

A common mistake is to conclude that $$E$$E has smaller cardinality because $$E⊊\mathbb{N}$$E\subsetneq\mathbb N. That transfers finite-set intuition directly to infinite sets.

7関連かんれんリンク

7Related links

8証明しょうめい演習えんしゅう：集合演算しゅうごうえんざんが包含ほうがんを保たもつこと

8Proof exercise: set operations preserve inclusion

8.1問題もんだい

$$A\subseteq B$$A\subseteq B のとき、任意にんいの集合しゅうごう $$C$$C について

を証明しょうめいせよ。また、全体集合ぜんたいしゅうごう $$U$$U を固定こていしたとき

も証明しょうめいせよ。

8.1Problem

Assume $$A\subseteq B$$A\subseteq B. Prove that, for every set集合しゅうごう $$C$$C,

Also, after fixing a universal set全体集合ぜんたいしゅうごう $$U$$U, prove

8.2解答かいとう

$$x\in A\cup C$$x\in A\cup C とする。$$x\in A$$x\in A または $$x\in C$$x\in C である。$$x\in A$$x\in A なら $$A\subseteq B$$A\subseteq B より $$x\in B$$x\in B なので $$x\in B\cup C$$x\in B\cup C である。$$x\in C$$x\in C でも $$x\in B\cup C$$x\in B\cup C である。よって $$A\cup C\subseteq B\cup C$$A\cup C\subseteq B\cup C である。

$$x\in A\cap C$$x\in A\cap C とする。$$x\in A$$x\in A かつ $$x\in C$$x\in C である。$$A\subseteq B$$A\subseteq B より $$x\in B$$x\in B なので $$x\in B\cap C$$x\in B\cap C である。よって $$A\cap C\subseteq B\cap C$$A\cap C\subseteq B\cap C である。

$$x\in U\setminus B$$x\in U\setminus B とする。もし $$x\in A$$x\in A なら $$A\subseteq B$$A\subseteq B より $$x\in B$$x\in B となり矛盾むじゅんする。したがって $$x\notin A$$x\notin A であり、$$x\in U\setminus A$$x\in U\setminus A である。

8.2Answer

Take $$x\in A\cup C$$x\in A\cup C. Then $$x\in A$$x\in A or $$x\in C$$x\in C. If $$x\in A$$x\in A, then $$x\in B$$x\in B by $$A\subseteq B$$A\subseteq B, so $$x\in B\cup C$$x\in B\cup C. If $$x\in C$$x\in C, then $$x\in B\cup C$$x\in B\cup C as well. Hence $$A\cup C\subseteq B\cup C$$A\cup C\subseteq B\cup C.

Take $$x\in A\cap C$$x\in A\cap C. Then $$x\in A$$x\in A and $$x\in C$$x\in C. Since $$A\subseteq B$$A\subseteq B, we have $$x\in B$$x\in B, so $$x\in B\cap C$$x\in B\cap C. Hence $$A\cap C\subseteq B\cap C$$A\cap C\subseteq B\cap C.

Take $$x\in U\setminus B$$x\in U\setminus B. If $$x\in A$$x\in A, then $$A\subseteq B$$A\subseteq B would imply $$x\in B$$x\in B, a contradiction. Therefore $$x\notin A$$x\notin A, so $$x\in U\setminus A$$x\in U\setminus A.

8.3解説かいせつ

この問題もんだいは、集合演算しゅうごうえんざんが包含ほうがんをどう保存ほぞんし、補集合ほしゅうごうだけは包含ほうがんの向むきを反転はんてんさせることを確認かくにんする演習えんしゅうである。

8.3Explanation

This problem checks how set operations集合演算しゅうごうえんざん preserve inclusion包含ほうがん, and why complement reverses the direction of inclusion.