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

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.

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.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.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.3Common mistake

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

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

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

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

4.3Common mistake

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

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

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

7Related links

8Proof exercise: set operations preserve inclusion

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

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