1.1.4: Unions and Intersections

\(\def\Assign#1#2{ { #1^{\Struct{#2}} } }\)
\(\def\Atom#1#2{ { \mathord{#1}(#2) } }\)
\(\def\Bin{ {\mathbb{B}} }\)
\(\def\cardeq#1#2{ { #1 \approx #2 } }\)
\(\def\cardle#1#2{ { #1 \preceq #2 } }\)
\(\def\cardless#1#2{ { #1 \prec #2 } }\)
\(\def\cardneq#1#2{ { #1 \not\approx #2 } }\)
\(\def\comp#1#2{ { #2 \circ #1 } }\)
\(\def\concat{ { \;\frown\; } }\)
\(\def\Cut{ { \text{Cut} } }\)
\(\def\Discharge#1#2{ { [#1]^#2 } }\)
\(\def\DischargeRule#1#2{ { \RightLabel{#1}\LeftLabel{\scriptsize{#2} } } }\)
\(\def\dom#1{ {\operatorname{dom}(#1)} }\)
\(\def\Domain#1{ {\left| \Struct{#1} \right|} }\)
\(\def\Elim#1{ { {#1}\mathrm{Elim} } }\)
\(\newcommand{\Entails}{\vDash}\)
\(\newcommand{\EntailsN}{\nvDash}\)
\(\def\eq[#1][#2]{ { #1 = #2 } }\)
\(\def\eqN[#1][#2]{ { #1 \neq #2 } }\)
\(\def\equivclass#1#2{ { #1/_{#2} } }\)
\(\def\equivrep#1#2{ { [#1]_{#2} } }\)
\(\def\Exchange{ { \text{X} } }\)
\(\def\False{ { \mathbb{F} } }\)
\(\def\FalseCl{ { \lfalse_C } }\)
\(\def\FalseInt{ { \lfalse_I } }\)
\(\def\fCenter{ { \,\Sequent\, } }\)
\(\def\fdefined{ { \;\downarrow } }\)
\(\def\fn#1{ { \operatorname{#1} } }\)
\(\def\Frm[#1]{ {\operatorname{Frm}(\Lang #1)} }\)
\(\def\fundefined{ { \;\uparrow } }\)
\(\def\funimage#1#2{ { #1[#2] } }\)
\(\def\funrestrictionto#1#2{ { #1 \restriction_{#2} } }\)
\(\newcommand{\ident}{\equiv}\)
\(\newcommand{\indcase}[2]{#1 \ident #2\text{:}}\)
\(\newcommand{\indcaseA}[2]{#1 \text{ is atomic:}}\)
\(\def\indfrm{ { A } }\)
\(\def\indfrmp{ { A } }\)
\(\def\joinrel{\mathrel{\mkern-3mu}}\)
\(\def\lambd[#1][#2]{\lambda #1 . #2}\)
\(\def\Lang#1{ { \mathcal{#1} } }\)
\(\def\LeftR#1{ { {#1}\mathrm{L} } }\)
\(\def\len#1{ {\operatorname{len}(#1)} }\)
\(\def\lexists#1#2{ { \exists #1\, #2 } }\)
\(\def\lfalse{ {\bot} }\)
\(\def\lforall#1#2{ { \forall#1\, #2 } }\)
\(\newcommand{\lif}{\rightarrow}\)
\(\newcommand{\liff}{\leftrightarrow}\)
\(\def\Log#1{ { \mathbf{#1} } }\)
\(\def\ltrue{ {\top} }\)
\(\def\Id#1{ {\operatorname{Id}_#1} }\)
\(\def\Int{ {\mathbb{Z}} }\)
\(\def\Intro#1{ { {#1}\mathrm{Intro} } }\)
\(\def\mModel#1{ { \mathfrak{#1} } }\)
\(\newcommand{\mSat}[3][{}]{\mModel{#2}{#1}\Vdash{#3}}\)
\(\newcommand{\mSatN}[3][{}]{\mModel{#2}{#1}\nVdash{#3}}\)
\(\def\Nat{ {\mathbb{N}} }\)
\(\def\nicefrac#1#2{ {{}^#1/_#2} }\)
\(\def\num#1{ { \overline{#1} } }\)

\(\def\ran#1{ {\operatorname{ran}(#1)} }\)
\(\newcommand{\Obj}[1]{\mathsf{#1}}\)
\(\def\Rat{ {\mathbb{Q}} }\)
\(\def\Real{ {\mathbb{R}} }\)
\(\def\RightR#1{ { {#1}\mathrm{R} } }\)
\(\def\Part#1#2{ { \Atom{\Obj P}{#1, #2} } }\)
\(\def\pto{ { \hspace{0.1 cm}\to\hspace{-0.44 cm}\vcenter{\tiny{\hbox{|}}}\hspace{0.35 cm} } }\)
\(\def\PosInt{ {\mathbb{Z}^+} }\)
\(\def\Pow#1{ {\wp(#1)} }\)
\(\newcommand{\Proves}{\vdash}\)
\(\newcommand{\ProvesN}{\nvdash}\)
\(\def\Relbar{\mathrel{=}}\)
\(\newcommand{\Sat}[3][{}]{\Struct{#2}{#1}\vDash{#3}}\)
\(\newcommand{\SatN}[3][{}]{\Struct{#2}{#1}\nvDash{#3}}\)
\(\newcommand{\Sequent}{\Rightarrow}\)
\(\def\Setabs#1#2{ { \{#1:#2\} } }\)
\(\newcommand{\sFmla}[2]{#1\,#2}\)
\(\def\Struct#1{ {#1} }\)
\(\def\subst#1#2{ { #1/#2 } }\)
\(\def\Subst#1#2#3{ { #1[\subst{#2}{#3}] } }\)
\(\def\TMblank{ { 0 } }\)
\(\newcommand{\TMendtape}{\triangleright}\)
\(\def\TMleft{ { L } }\)
\(\def\TMright{ { R } }\)
\(\def\TMstay{ { N } }\)
\(\def\TMstroke{ { 1 } }\)
\(\def\TMtrans#1#2#3{ { #1,#2,#3 } }\)
\(\def\Trm[#1]{ {\operatorname{Trm}(\Lang #1)} }\)
\(\def\True{ { \mathbb{T} } }\)
\(\newcommand{\TRule}[2]{#2#1}\)
\(\def\tuple#1{ {\langle #1 \rangle} }\)
\(\newcommand{\Value}[3][\,]{\mathrm{Val}_{#1}^{#3}(#2)}\)
\(\def\Var{ { \mathrm{Var} } }\)
\(\newcommand{\varAssign}[3]{#1 \sim_{#3} #2}\)
\(\def\Weakening{ { \text{W} } }\)

In section 1.1, we introduced definitions of sets by abstraction, i.e., definitions of the form \(\Setabs{x}{\phi(x)}\). Here, we invoke some property \(\phi\), and this property can mention sets we’ve already defined. So for instance, if \(A\) and \(B\) are sets, the set \(\Setabs{x}{x \in A \lor x \in B}\) consists of all those objects which are elements of either \(A\) or \(B\), i.e., it’s the set that combines the elements of \(A\) and \(B\). We can visualize this as in Figure \(\PageIndex{1}\), where the highlighted area indicates the elements of the two sets \(A\) and \(B\) together.

Figure \(\PageIndex{1}\): The union \(A \cup B\) of two sets is set of elements of \(A\) together with those of \(B\).

This operation on sets—combining them—is very useful and common, and so we give it a formal name and a symbol.

Definition \(\PageIndex{1}\): Union

The union of two sets \(A\) and \(B\), written \(A \cup B\), is the set of all things which are elements of \(A\), \(B\), or both.

\[A \cup B = \Setabs{x}{x \in A \lor x \in B}\nonumber\]

Example \(\PageIndex{1}\)

Since the multiplicity of elements doesn’t matter, the union of two sets which have an element in common contains that element only once, e.g., \(\{ a, b, c\} \cup \{ a, 0, 1\} = \{a, b, c, 0, 1\}\).

The union of a set and one of its subsets is just the bigger set: \(\{a, b, c \} \cup \{a \} = \{a, b, c\}\).

The union of a set with the empty set is identical to the set: \(\{a, b, c \} \cup \emptyset = \{a, b, c \}\).

Problem \(\PageIndex{1}\)

Prove that if \(A \subseteq B\), then \(A \cup B = B\).

We can also consider a “dual” operation to union. This is the operation that forms the set of all elements that are elements of \(A\) and are also elements of \(B\). This operation is called intersection, and can be depicted as in Figure \(\PageIndex{2}\).

Figure \(\PageIndex{2}\): The intersection \(A \cap B\) of two sets is the set of elements they have in common.

Definition \(\PageIndex{2}\): Intersection

The intersection of two sets \(A\) and \(B\), written \(A \cap B\), is the set of all things which are elements of both \(A\) and \(B\).

\[A \cap B = \Setabs{x}{x \in A \land x \in B}\nonumber\]

Two sets are called disjoint if their intersection is empty. This means they have no elements in common.

Example \(\PageIndex{2}\)

If two sets have no elements in common, their intersection is empty: \(\{ a, b, c\} \cap \{ 0, 1\} = \emptyset\).

If two sets do have elements in common, their intersection is the set of all those: \(\{a, b, c \} \cap \{a, b, d \} = \{a, b\}\).

The intersection of a set with one of its subsets is just the smaller set: \(\{a, b, c\} \cap \{a, b\} = \{a, b\}\).

The intersection of any set with the empty set is empty: \(\{a, b, c \} \cap \emptyset = \emptyset\).

Problem \(\PageIndex{2}\)

Prove rigorously that if \(A \subseteq B\), then \(A \cap B = A\).

We can also form the union or intersection of more than two sets. An elegant way of dealing with this in general is the following: suppose you collect all the sets you want to form the union (or intersection) of into a single set. Then we can define the union of all our original sets as the set of all objects which belong to at least one element of the set, and the intersection as the set of all objects which belong to every element of the set.

Definition \(\PageIndex{3}\)

If \(A\) is a set of sets, then \(\bigcup A\) is the set of elements of elements of \(A\): \[\begin{aligned} \bigcup A & = \Setabs{x}{x \text{ belongs to an element of } A}, \text{ i.e.,}\\ & = \Setabs{x}{\text{there is a } B \in A \text{ so that } x \in B}\end{aligned}\]

Definition \(\PageIndex{4}\)

If \(A\) is a set of sets, then \(\bigcap A\) is the set of objects which all elements of \(A\) have in common: \[\begin{aligned} \bigcap A & = \Setabs{x}{x \text{ belongs to every element of } A}, \text{ i.e.,}\\ & = \Setabs{x}{\text{for all } B \in A, x \in B}\end{aligned}\]

Example \(\PageIndex{3}\)

Suppose \(A = \{ \{ a, b \}, \{ a, d, e \}, \{ a, d \} \}\). Then \(\bigcup A = \{ a, b, d, e \}\) and \(\bigcap A = \{ a \}\).

Problem \(\PageIndex{3}\)

Show that if \(A\) is a set and \(A \in B\), then \(A \subseteq \bigcup B\).

We could also do the same for a sequence of sets \(A_1\), \(A_2\), … \[\begin{aligned} \bigcup_i A_i & = \Setabs{x}{x \text{ belongs to one of the } A_i}\\ \bigcap_i A_i & = \Setabs{x}{x \text{ belongs to every } A_i}.\end{aligned}\]

When we have an index of sets, i.e., some set \(I\) such that we are considering \(A_i\) for each \(i \in I\), we may also use these abbreviations: \[\begin{aligned} \bigcup_{i \in I} A_i & = \bigcup \Setabs{A_i }{i \in I}\\ \bigcap_{i \in I} A_i & = \bigcap\Setabs{A_i}{i \in I}\end{aligned}\]

Finally, we may want to think about the set of all elements in \(A\) which are not in \(B\). We can depict this as in Figure \(\PageIndex{3}\).

Figure \(\PageIndex{3}\): The difference \(A \setminus B\) of two sets is the set of those elements of \(A\) which are not also elements of \(B\).

Definition \(\PageIndex{5}\): Difference

The set difference \(A \setminus B\) is the set of all elements of \(A\) which are not also elements of \(B\), i.e.,

\[A\setminus B = \Setabs{x}{x\in A \text{ and } x \notin B}.\nonumber\]

Problem \(\PageIndex{4}\)

Prove that if \(A \subsetneq B\), then \(B \setminus A \neq \emptyset\).