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{.}\)”
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).
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.
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.
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{.}\)
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.
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.
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.
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{.}\)
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.
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.
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.
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.
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.
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.
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{.}\)
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{.}\)
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{.}\)
