In this section, we’ll seek to answer the questions:
What is a set?
How do we work with and describe sets and their members?
What does it mean for two sets to be equal?
Subsection4.1.1Describing Sets
As we have seen, mathematics proceeds via a tried-and-true litany of definitions, axioms, theorems, and proofs. However, there are a few undefined terms in mathematics. For instance, in geometry, we do not (officially) define a point. This is to avoid the problem of infinite regression; if we attempted a definition, we would have to use other words, for which a reasonable person might also request definitions. Those definitions might contain words which need defining, and so on. We therefore take it as understood that we know what a point is, and perhaps we occasionally attempt to give a general description of the idea of a point without officially defining it.
One of the most important undefined terms in mathematics is the set, which we might think of as a collection of objects (please don’t ask what an “object” is!), which we refer to as elements or members. We typically denote sets with uppercase Roman letters, such as \(A, B, S, T, X\text{,}\) and denote set elements using lowercase letters. If we want to state that the element \(x\) is in the set \(A\text{,}\) we write “\(x\in A\)” and say that “\(x\) is an element of \(A\text{.}\)” To state that \(x\) is not in the set \(A\text{,}\) we write “\(x\notin A\)”, and say that “\(x\) is not an element of \(A\text{.}\)”
LaTeX Code4.1.1.
To typeset \(x\in A\) in \(\LaTeX\text{,}\) use x \in A in math mode. To typeset \(x\notin A\) in \(\LaTeX\text{,}\) use x \notin A in math mode.
There are several ways of describing sets and their elements, including some which are specific to certain subfields of mathematics (such as the interval in real analysis).
Definition4.1.2.
Let \(A\) be a set. The roster form for \(A\) lists the elements of \(A\) between left and right curly braces. The set-builder form for \(A\) describes the elements of \(A\) using a rule by which set membership can be determined.
LaTeX Code4.1.3.
To typeset \(A = \{1, 7 \}\) in \(\LaTeX\text{,}\) use A = \{1, 7 \} in math mode. To typeset \(B = \{x | x^2 - 4 = 0\}\) in \(\LaTeX\text{,}\) use B = \{x | x^2 - 4 = 0\} in math mode.
Example4.1.4.
The following are examples of sets.
The set \(A = \set{1,7, \pi}\) contains only the elements 1, 7, and \(\pi\text{.}\)
The set \(B = \setof{x\in \Z}{x^2 -2x + 1 = 0}\) consists of all integers \(x\) which satisfy \(x^2 -2x + 1 = 0\text{.}\) Note that there is precisely one such integer, so we may also write \(B\) in roster form as \(B = \set{1}\text{.}\) Such a set, with only one element, is called a singleton.
The set \(C = \set{ 2, -\sqrt{7}, \set{2, - \sqrt{7}}}\) contains three elements: \(2\text{,}\)\(-\sqrt{7}\text{,}\) and the set \(\set{2, -\sqrt{7}}\text{.}\)
Definition4.1.5.
The following special sets will be important throughout your mathematical career.
The set of rational numbers is denoted by \(\Q\) and consists of ratios of integers \(a\) to nonzero integers \(b\text{:}\)
The empty set is the set with no elements, and is denoted by \(\emptyset\) (or, sometimes, \(\{\}\)).
LaTeX Code4.1.6.
To typeset \(\Q\) in \(\LaTeX\text{,}\) use \mathbb{Q} in math mode. To typeset \(\C\) in \(\LaTeX\text{,}\) use \mathbb{C} in math mode. To typeset \(\emptyset\) in \(\LaTeX\text{,}\) use \emptyset in math mode.
Subsection4.1.2Subsets and Set Equality
As described above, one of the fundamental relationships involving a set is its relationship to its elements. Also important is how sets, via their elements, relate to one another.
Axiom4.1.7.
Sets \(A\) and \(B\) are equal if they consist of precisely the same elements.
If the sets you are given are in roster form and consist of finitely many elements, then it is fairly straightforward to check if Axiom 4.1.7 is satisfied. But, if you are given two sets \(S\) and \(T\) which consist of an unknown number of elements, or are not given in roster form, how can you check to see that they have the same elements? To definitively answer this question, we introduce the notion of subsets.
Definition4.1.8.
Let \(A\) be a set. We say \(B\) is a subset of \(A\) if whenever \(x\in B\text{,}\) we have \(x\in A\text{.}\) In this case, we write \(B\subseteq A\text{,}\) and say “\(B\) is a subset of \(A\)” or that \(B\) is “contained in” \(A\) (or that \(A\) “contains” \(B\)). We also sometimes say that \(A\) is a superset of \(B\) and write \(A\supseteq B\text{.}\) If \(B\) is not a subset of \(A\text{,}\) we write \(B\not\subseteq A\text{.}\)
If \(B\subseteq A\) and \(B\ne A\text{,}\) we say that \(B\) is a proper subset of \(A\) and write \(B\subsetneq A\text{.}\)
Remark4.1.9.
There is some ambiguity in the literature about the symbol \(\subset\text{.}\) Some texts use \(\subset\) and \(\subseteq\) interchangeably, while others use \(\subset\) and \(\subsetneq\) interchangeably. We take no position on the issue and avoid using \(\subset\) altogether.
LaTeX Code4.1.10.
To typeset \(B\subseteq A\) in \(\LaTeX\text{,}\) use B\subseteq A in math mode. To typeset \(B\subsetneq A\) in \(\LaTeX\text{,}\) use B\subsetneq A in math mode. To typeset \(A\supseteq B\) in \(\LaTeX\text{,}\) use A\supseteq B in math mode. To typeset \(A\supsetneq B\) in \(\LaTeX\text{,}\) use A\supsetneq B in math mode.
Activity4.1.11.
Let \(A = \set{5,10,15}\text{,}\)\(B = \set{\emptyset, 5, \pi}\text{,}\)\(C = \set{ 2, -\sqrt{7}, \set{2, - \sqrt{7}}}\text{,}\) and \(D = \set{2, -\sqrt{7}}\text{.}\) Determine which of \(A,B,C,D\text{,}\)\(\in\text{,}\)\(\notin\text{,}\)\(\subseteq\text{,}\)\(\supseteq\text{,}\)\(\not\subseteq\) could go in the blank. Ensure that you can justify your choices.
\(5\) ______ \(A\)
\(\emptyset\) ______ \(B\)
\(2 \in \) ______
\(D\) ______ \(C\)
______ \(\supsetneq \emptyset\)
Theorem4.1.12.
Let \(A\) be a set. Then \(\emptyset\subseteq A\) and \(A\subseteq A\text{.}\)
Theorem4.1.13.The Transitive Property.
Let \(A,B,C\) be sets with \(A\subseteq B\) and \(B\subseteq C\text{.}\) Then \(A\subseteq C\text{.}\)
Given a set \(S\text{,}\) we may construct a new set whose elements are the subsets of \(S\text{.}\) This is known as the power set of \(S\text{.}\)
Definition4.1.14.
Let \(S\) be a set. The power set of \(S\), denoted \(\mathcal{P}(S)\text{,}\) is the set whose elements are the subsets of \(S\text{.}\)
LaTeX Code4.1.15.
To typeset \(\mathcal{P}(S)\) in \(\LaTeX\text{,}\) use \mathcal{P}(S) in math mode.
Activity4.1.16.
Calculate the power sets of \(A, C\text{,}\) and \(D\) from Activity 4.1.11.
Subsection4.1.3Cardinality
One natural question we can ask about a given set is how many elements it has. This is roughly called the set’s cardinality. Calculating cardinality is tricky, however, particularly for sets like \(\N\text{,}\)\(\Q\text{,}\) and \(\R\text{.}\) The fundamental idea required for calculating cardinality is that of one-to-one correspondence. We give a first version of the definition here; it will be explored in more detail in Chapter 5.
Definition4.1.17.
Let \(A\) and \(B\) be sets. A one-to-one correspondence between \(A\) and \(B\) is a pairing of elements of \(A\) with elements of \(B\) such that each element of \(A\) is paired with precisely one element of \(B\text{,}\) and vice versa.
Activity4.1.18.
Consider the following sets.
\(\displaystyle A = \set{1,2,3,4,5}\)
\(\displaystyle B = \setof{x\in \R}{x^2 - 2 = 0}\)
\(\displaystyle C = \setof{x\in\R}{x^2 + 1 = 0}\)
\(\displaystyle D = \set{\spadesuit, \heartsuit}\)
\(\displaystyle E = \set{\text{tetrahedron}, \text{cube}, \text{octahedron}, \text{dodecahedron}, \text{icosahedron}}\)
\(\displaystyle F = \emptyset\)
Exhibit a one-to-one correspondence between at least two pairs of sets, and explain why no one-to-one correspondence exists between at least one pair of sets.
Definition4.1.19.
Let \(S\) be a set. We say that \(S\) is finite if either \(S = \emptyset\) or there is some \(k\in \N\) such that there is a one-to-one correspondence between \(S\) and \(\set{1,2,\ldots,k}\text{.}\) In this case, we say \(S\) has cardinality \(k\) and write \(|S| = k\text{;}\) or, if \(S = \emptyset\text{,}\) we define \(|S| = 0\text{.}\)
If \(S\) is not finite, we say it is infinite.
On the level of finite sets, then, the definition of cardinality presented in Definition 4.1.19 corresponds with an intuitive notion of “size.” This notion of using other sets to measure the “size” of a given set was formalized and extended by Georg Cantor. In fact, Cantor showed that one could find one-to-one correspondences between infinite sets like \(\N\text{,}\)\(\Z\text{,}\) and \(\Q\text{.}\) But, in a famous argument known as the diagonal argument, Cantor showed that no such correspondence exists between \(\N\) and \(\R\text{.}\)
Activity4.1.20.
Calculate the cardinalities of the power sets of the following sets.
\(\displaystyle F = \set{\text{tetrahedron}, \text{cube}, \text{octahedron}, \text{dodecahedron}, \text{icosahedron}}\)
Problem4.1.21.
Based on your work in Activity 4.1.20, conjecture and use induction to establish a formula for the cardinality of the power set of a general finite set \(S = \set{s_1, s_2, \ldots, s_n}\text{.}\)
