1.1 What a set is
Definition 1.1. A set is a collection of well defined objects. The objects in it are called its elements or members. A set is written by listing its elements inside braces, \(\{\ \}\).
The phrase well defined is doing real work. It means there must be no argument about whether a given object is in the set. “The set of whole numbers between \(1\) and \(6\)” is well defined; “the set of interesting numbers” is not, because nobody can settle whether \(7\) belongs.
Two conventions to fix straight away.
Note 1.3. Order does not matter and repetition does not count. The sets \(\{1,2,3\}\), \(\{3,1,2\}\) and \(\{1,2,2,3\}\) are all the same set. A set records only which objects are in it.
Sets are named with capital letters and their elements usually with small letters. To say an object belongs to a set we use the symbol \(\in \), and to say it does not we strike it through: \[4\in \{1,2,3,4\},\qquad 7\notin \{1,2,3,4\}.\] Read \(\in \) as “is an element of”.
1.1.1 Set-builder notation
Listing works when there are a few elements. For larger sets we describe the elements instead.
Definition 1.4. Set-builder notation writes a set as \[\{x : \text {condition on } x\}\] read “the set of all \(x\) such that …”. The colon may be written as a vertical bar, \(\{x \mid \dots \}\); the two mean the same thing.
| Listed | Described |
| \(A=\{1,2,3,4,5\}\) | \(A=\{x : x \text { is a natural number less than } 6\}\) |
| \(V=\{a,e,i,o,u\}\) | \(V=\{x : x \text { is a vowel}\}\) |
| \(C=\{2,4,6,8,10,\ldots \}\) | \(C=\{x : x \text { is a positive even number}\}\) |
Not every collection can be written both ways. A set such as \(\{\text {dog},\ \text {plate},\ \text {Earth}\}\) has no property in common to describe, so listing is the only option — which is fine.
Example 1.5. List the elements of each set.
- (a).
- \(A=\{x : x \text { is an odd natural number}\}\)
- (b).
- \(B=\{k : k=3n+1,\ n=0,1,2,3\}\)
- (c).
- \(D=\{x : x \text { is a month whose name begins with } J\}\)
Solution. (a) \(A=\{1,3,5,7,9,\ldots \}\). The three dots mean the pattern continues without end; this set is infinite.
(b) Here \(n\) is given four values, so substitute each one in turn: \[n=0:\ 3(0)+1=1,\quad n=1:\ 3(1)+1=4,\quad n=2:\ 3(2)+1=7,\quad n=3:\ 3(3)+1=10.\] \[\therefore \quad B=\{1,4,7,10\}.\]
(c) \(D=\{\text {January},\ \text {June},\ \text {July}\}\).
1.1.2 Kinds of set
Definition 1.6. A set is finite if its elements can be counted and the counting stops. It is infinite if the counting never stops.
\(V=\{x:x\text { is a vowel}\}\) is finite; \(C=\{2,4,6,\ldots \}\) is infinite.
Definition 1.7. The universal set, written \(U\) or \(E\), is the set of everything under discussion in a particular problem.
The universal set is not fixed once and for all — it is chosen to suit the question. In a problem about a class of students, \(U\) is that class; in a problem about digits, \(U=\{0,1,2,\ldots ,9\}\). It matters because complements depend on it.
Definition 1.8. The empty set or null set contains no elements at all. It is written \(\varnothing \) or \(\{\ \}\).
Remark 1.9. \(\{\varnothing \}\) is not the empty set. It is a set with one element, and that element happens to be the empty set. Compare an empty box with a box containing an empty box: the second is not empty. So \[|\varnothing |=0\qquad \text {but}\qquad |\{\varnothing \}|=1.\]
1.1.3 Subsets and equality
Definition 1.10. \(S\) is a subset of \(T\), written \(S\subseteq T\), if every element of \(S\) is also an element of \(T\). If in addition \(T\) has at least one element that \(S\) does not, then \(S\) is a proper subset of \(T\), written \(S\subset T\).
Example 1.11. Let \(A=\{a,b,c\}\), \(B=\{a,b,c,d\}\) and \(C=\{2,5,9\}\), \(D=\{2,3,5,6,9,10\}\). Then \(A\subset B\) and \(C\subset D\), both proper, since \(d\in B\) but \(d\notin A\), and \(3\in D\) but \(3\notin C\).
Note 1.12. Two facts that look strange the first time and are used constantly afterwards: \[\varnothing \subseteq A\quad \text {for every set } A,\qquad \text {and}\qquad A\subseteq A.\] The first holds because to fail, \(\varnothing \) would need an element that is not in \(A\) — and it has no elements to offer. The second is immediate from the definition.
Definition 1.13. Sets \(A\) and \(B\) are equal, written \(A=B\), if they have exactly the same elements. Equivalently, \(A=B\) precisely when \(A\subseteq B\) and \(B\subseteq A\).
That second form is how equality of sets is usually proved: show each is contained in the other.
1.1.4 Cardinality and the power set
Definition 1.15. The cardinality of a finite set \(A\), written \(n(A)\) or \(|A|\), is the number of elements it contains. The power set of \(A\), written \(P(A)\), is the set of all subsets of \(A\).
Example 1.16. Find the power set of each of the following, and its cardinality.
- (a).
- \(A=\varnothing \)
- (b).
- \(B=\{1,2\}\)
- (c).
- \(T=\{p,q,r\}\)
Solution. (a) The only subset of the empty set is the empty set itself, so \[P(A)=\{\varnothing \},\qquad |P(A)|=1.\] Note again that \(P(A)\) here is not empty — it has one member.
(b) Take the subsets by size: none, one element, two elements. \[P(B)=\big \{\varnothing ,\ \{1\},\ \{2\},\ \{1,2\}\big \},\qquad |P(B)|=4.\]
(c) Same method, now with four sizes: \[P(T)=\big \{\varnothing ,\ \{p\},\ \{q\},\ \{r\},\ \{p,q\},\ \{p,r\},\ \{q,r\},\ \{p,q,r\}\big \}, \qquad |P(T)|=8.\]
The three answers were \(1\), \(4\) and \(8\) for sets of size \(0\), \(2\) and \(3\). That is not a coincidence.
Note 1.17. If a set has \(n\) elements, its power set has \(\boldsymbol {2^n}\) members.
The reason is worth a moment, because it saves listing. Building a subset means going through the elements one at a time and deciding, for each, whether to put it in or leave it out. That is \(n\) decisions with two answers each, so the number of different subsets is \[\underbrace {2\times 2\times \cdots \times 2}_{n\ \text {times}}=2^n.\]
Check it against the example above: \(2^0=1\), \(2^2=4\) and \(2^3=8\). All three agree. It also tells you when you have finished listing — a set of \(4\) elements must have \(16\) subsets, so if you have written down \(15\) you have missed one.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.