1.2 Subsets, unions and intersections

Editorial note

Problems 1.5 and 1.8 (in the next section) contain printed errors. Problem 1.5 is corrected to an intersection on the right. Nonempty indexed families are assumed when no universal ambient set has been specified.

A set T is said to be a subset of S, or T is contained in S, if every member of T belongs to S. Symbolically, this is written $T\subseteq S$ ,

$$T\subseteq S\text{ iff }a\in T\Rightarrow a\in S.$$

We may also say S is a superset of T and write $S\supset T$ . Of particular importance is the empty set , to which no object belongs,

$$\forall a(a\notin \varnothing ).$$

The empty set is a subset of any set whatsoever,

$$\forall S(\varnothing \subseteq S).$$

This is the default position, consistent with the fact that $a\in \varnothing \Rightarrow a\in S$ , since there are no a such that $a\in \varnothing$ and the left-hand side of the implication is never true. We have here an example of the logical dictum that ‘an implication with a false antecedent is true’.

A common criterion for showing the equality of two sets, $T=S$ , is to show that $T\subseteq S$ and $S\subseteq T$ .

Proof

This follows from the axiom of extensionality:

$$\begin{array}{rl}T=S⟺(a\in T\iff a\in S)& \\ & ⟺(a\in T\Rightarrow a\in S)\text{ and }(a\in S\Rightarrow a\in T)\\ & ⟺(T\subseteq S)\text{ and }(S\subseteq T).\end{array}$$

Exercise

Show that the empty set is unique; i.e., if ${\varnothing }^{\prime }$ is an empty set then ${\varnothing }^{\prime }=\varnothing .$

The collection of all subsets of a set S forms a set in its own right, called the power set of S, denoted $2^S$

Example 1.1

If S is a finite set consisting of n elements, then $2^S$ consists of one empty set $\varnothing$ having no elements, n singleton sets having just one member, $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ sets having two elements, etc. Hence the total number of sets belonging to $2^S$ is, by the binomial theorem,

$$1+\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n}{n}\right)=(1+1{)}^n=2^n.$$

This motivates the symbolic representation of the power set.

Referenced 1 time

• 1.5 Infinite setsFor any two sets S and T the set of all maps … will be denoted by … . Justification for this notatio…

Unions and intersections

The union of two sets S and T, denoted $S\cup T$ , is defined as

$$S\cup T=\{x\mid x\in S\text{ or }x\in T\}.$$

The intersection of two sets S and T, denoted $S\cap T$ , is defined as

$$S\cap T=\{x\mid x\in S\text{ and }x\in T\}.$$

Two sets S and T are called disjoint if no element belongs simultaneously to both sets, $S\cap T=\varnothing$ . The difference of two sets S and $T$ is defined as

$$S-T=\{x\mid x\in S\text{ and }x\notin T\}.$$

Exercise

If S and T are disjoint, show that $S-T=S$

The union of an arbitrary (possibly infinite) family of sets is defined as the set of al elements x that belong to some member of the family,

$$\bigcup \mathcal{A}=\{x\mid \exists S\text{ such that }(S\in \mathcal{A})\text{ and }(x\in S)\}.$$

Similarly we define the intersection of to be the set of all elements that belong to every set of the collection,

$$\bigcap \mathcal{A}=\{x\mid x\in S\text{ for all }S\in \mathcal{A}\}.$$

When consists of a family of sets $S_i$ indexed by a set I, the union and intersection are frequently written

$$\bigcup _{i\in I}\{S_i\}\text{ and }\bigcap _{i\in I}\{S_i\}.$$

Problems

Problem 1.1

Show the distributive laws

$$A\cap (B\cup C)=(A\cap B)\cup (A\cap C),A\cup (B\cap C)=(A\cup B)\cap (A\cup C).$$

Problem 1.2

$\mathrm{If}B=\{B_i|i\in I\}$ is any family of sets, show that

$$A\cap \bigcup \mathcal{B}=\bigcup \{A\cap B_i\mid i\in I\},A\cup \bigcap \mathcal{B}=\bigcap \{A\cup B_i\mid i\in I\}.$$

Problem 1.3

Let B be any set. Show tha $(A\cap B)\cup C=A\cap (B\cup C)$ if and only if $C\subseteq A.$

Problem 1.4

Show that

$$A-(B\cup C)=(A-B)\cap (A-C),A-(B\cap C)=(A-B)\cup (A-C).$$

Problem 1.5

$\mathrm{If}B=\{B_i|i\in I\}$ is any family of sets, show that

$$A-\bigcup \mathcal{B}=\bigcap _{i\in I}(A-B_i).$$

Referenced 2 times

• 1.2 Subsets, unions and intersectionsProblems 1.5 and 1.8 (in the next section) contain printed errors. Problem 1.5 is corrected to an in…
• 1.2 Subsets, unions and intersectionsProblems 1.5 and 1.8 (in the next section) contain printed errors. Problem 1.5 is corrected to an in…

Problem 1.6

If E and F are any sets, prove the identities

$$2^E\cap 2^F=2^{E\cap F},2^E\cup 2^F\subseteq 2^{E\cup F}.$$

Problem 1.7

Show that if $\mathcal{C}$ is any nonempty family of sets then

$$\bigcap _{X\in \mathcal{C}}{2}^X=2^{\cap \mathcal{C}},\bigcup _{X\in \mathcal{C}}{2}^X\subseteq 2^{\cup \mathcal{C}}.$$