Skip to main content

Discrete Structures: Course Notes

Mike Janssen

Section 4.3 Families of Sets

Guiding Questions.

In this section, we’ll seek to answer the questions:
  • What is an index set?
  • How can we extend the operations from Section 4.2 to indexed families?
In Section 4.2, we discussed operations on sets. However, we only considered operations on a small number of sets. In this section, we explore a way of describing the same operations on families of sets; either arbitrarily large finite collections, or infinite collections. To keep track of such collections, we use the best tool in our toolbox: a(nother) set.

Definition 4.3.1.

Let \(U\) be a (universal) set and \(\mathcal{F} = \setof{S_\alpha}{\alpha\in \Lambda}\) a collection of subsets of \(U\text{.}\) We call \(\mathcal{F}\) a(n) (indexed) family of subsets, \(\Lambda\) the index set of the family, and each \(\alpha\in \Lambda\) an index (plural: indices). We sometimes write \(\mathcal{F} = \set{S_\alpha}_{\alpha\in\Lambda}\text{.}\)
While Definition 4.3.1 is a fairly abstract, we see its power in its flexibility —we can use index sets to describe finite collections of sets or infinite collections, as Example 4.3.2 illustrates.

Example 4.3.2.

Consider the following indexed families.
  • Given \(\Lambda = \set{1,2}\text{,}\) the family \(\mathcal{F} = \setof{\set{\alpha,\alpha+1}}{\alpha\in\Lambda}\) consists of \(\set{1,2}\) and \(\set{2,3}\text{.}\)
  • Given \(\Lambda = \N\text{,}\) the family \(\mathcal{G} = \setof{\set{1,2,\ldots,\alpha}}{\alpha\in\Lambda}\) consists of all subsets of \(\N\) of the form \(\set{1,2,\ldots,n}\) for some \(n\in\N\text{.}\)
  • Given a real number \(r \gt 0\text{,}\) define \(C_r = \setof{(x,y)\in\R^2}{x^2 + y^2 = r^2}\text{.}\) Then \(\mathcal{C} = \setof{C_r}{r\in \R, r \gt 0}\) is a family of subsets of the Cartesian plane indexed by the positive real numbers.
As promised, we can apply our set-theoretic operations to entire indexed families of sets. In this text, we explore only union and intersection, but know that indexed Cartesian products are also sensible and useful mathematical objects.

Definition 4.3.3.

Let \(\mathcal{F} = \set{S_\alpha}_{\alpha\in\Lambda}\) be an indexed family of subsets of a universal set \(U\text{.}\) The union over \(\Lambda\) is the set
\begin{equation*} \bigcup\limits_{\alpha \in \Lambda} S_\alpha := \setof{x\in U}{\exists \alpha\in \Lambda, x\in S_\alpha} \end{equation*}
Similarly, the intersection over \(\Lambda\) is the set
\begin{equation*} \bigcap\limits_{\alpha \in \Lambda} S_\alpha := \setof{x\in U}{x\in S_\alpha \forall \alpha\in\Lambda}. \end{equation*}

LaTeX Code 4.3.4.

To typeset \(\bigcup\limits_{\alpha\in\Lambda} S_{\alpha}\) in \(\LaTeX\text{,}\) use \bigcup\limits_{\alpha\in\Lambda} S_{\alpha} in math mode. To typeset \(\bigcap\limits_{\alpha\in\Lambda} S_{\alpha}\) in \(\LaTeX\text{,}\) use \bigcap\limits_{\alpha\in\Lambda} S_{\alpha} in math mode.
While we are now dealing with unions and intersections of possibly infinitely many sets, the idea is the same. To have \(x\in A\cup B\text{,}\) we need \(x\) to be in at least one of \(A, B\text{;}\) to have \(x\in \bigcup\limits_{\alpha\in\Lambda} S_\alpha\text{,}\) we must find at least one \(S_\alpha\) that contains \(x\text{.}\)
When the index set is \(\N\text{,}\) we sometimes write \(\bigcup\limits_{i=1}^\infty S_i\) or \(\bigcap\limits_{i=1}^\infty S_i\) for the indexed union and intersection.

Activity 4.3.5.

Calculate each of the following. Be prepared to explain your thinking.
  1. \(\displaystyle \bigcap\limits_{j=1}^\infty \set{0,1,\ldots, j}\)
  2. \(\displaystyle \bigcup\limits_{j=1}^\infty \set{0,1,\ldots,j}\)
  3. \(\displaystyle \bigcup\limits_{j=1}^\infty \set{j,j+1}\)
  4. \(\displaystyle \bigcap\limits_{j=1}^\infty \set{j,j+1}\)
  5. \(\displaystyle \bigcup\limits_{j=1}^\infty (\N\setminus \set{1,2,\ldots, j})\)
  6. \(\displaystyle \bigcap\limits_{j=1}^\infty (\N\setminus \set{1,2,\ldots, j})\)
We conclude with a few theorems which (hopefully!) should look familiar.
PrevTopNext