1 Sets

1.0 Definitions and examples

We will rely on the intuitive idea that a set is a collection of objects. The objects are called the elements, or members, of the set. We might ask what exactly is meant by a "collection", or by "objects", and there are problems with taking too broad an interpretation of these terms. We can make things more precise, and you could take the Part B Set Theory course if you want to explore this more deeply.

Notation
For a set \(S\), we write \(x \in S\) to mean that \(x\) is an element of \(S\), and we write \(x \notin S\) to mean that \(x\) is not an element of \(S\).

I usually read the expression "\(x\in S\)" as "\(x\) in \(S\)".

Definition 1.1 (Equal sets) 
Two sets \(S\) and \(T\) are equal if and only if they contain the same elements, and in that case we can write \(S = T\).

Definition 1.2 (Empty set) 
The empty set is the set with no elements and is denoted by \(\varnothing\).

The symbol \(\varnothing\) is not to be confused with the Greek letter phi, written as \(\phi\) or \(\varphi\). This notation, which was inspired by the Danish or Norwegian symbol Ø, was introduced by André Weil (who is himself not to be confused with Andrew Wiles).

Definition 1.3 (Subset) 
A set \(A\) is said to be a subset of a set \(S\) if every element of \(A\) is an element of \(S\).  We write \(A \subseteq S\). 

The symbol \(\subseteq\) can be read as "is a subset of" or "is contained in".

Definition 1.4 (Proper subset) 
If \(A \subseteq S\) and \(A \neq S\), we call \(A\) a proper subset of \(S\).

The symbol \(\subset\) is commonly used to mean the same thing as \(\subseteq\), and I'm afraid that it does not necessarily imply that the subset is proper (as you might otherwise imagine by analogy with \(\le\) and \(<\) symbols).

You might see the symbol \(A\nsubseteq S\) used to indicate that \(A\) is not a subset of \(S\), and \(A\varsubsetneq S\) used if \(A\) is a proper subset of \(S\), with that notation trying to capture both parts of the definition; \(A\) is a subset of \(S\), but \(A\) is not equal to \(S\).

As we have already seen, curly brackets are used to denote sets. 

Notation
The set with elements \(a_1, a_2, \ldots, a_n\) is written \(\{ a_1, a_2, \ldots, a_n \}\).

If nothing is written at the end of a string of dots, such as \(\{ a_1, a_2, \ldots \}\), it typically indicates an infinite list of elements, although this is not a hard and fast rule.  It is helpful practice to write the final element, as done here, to indicate if such a list is finite.

The order of the elements inside the curly brackets is not important, and repeating the elements does not mean anything extra, so \(\{ 3, 5\}=\{ 5,3\}\), and \(\{ 2, 3\}=\{ 2, 3, 3\}\).

We will often want to define a set in terms of some property \(P(x)\) that the elements \(x\) satisfy. Typically the set is a subset of some larger set \(S\), say.

Notation
We write \(\{ x \in S : P(x) \}\), or \(\{ x \in S \ |\ P(x) \}\), to mean the set of elements \(x \in S\) that have property \(P(x)\).

This is read as "the set of \(x\) in \(S\) such that \(P\) holds".

Example 1.5
    (i) The set of even natural numbers is \(\{ n \in \mathbb{N} : n \text{ is divisible by 2} \}\).
    (ii) The set \(\{ n \in \mathbb{N} : n^2 <0 \}\) is equal to the empty set \(\varnothing\), since no elements of \(\mathbb{N}\) satisfy the given property.
    (iii) The set \(\{n \in \mathbb{N} : 3|n,\, 5|n,\, 7|n \}\) is an example where multiple conditions are separated by commas, and all conditions must hold for a value of \(n\) to be included in the subset. This set is the multiples of \(105\) (prove it!), so I could have written \(\{n \in \mathbb{N} : 105|n \}\).

Do not confuse \(a\) with \(\{a\}\). The first is the element \(a\) and the second is the set containing the single element \(a\). It's easy to get confused if we start talking about sets of sets. For example, if \(a = \varnothing\), the empty set, then \(a\) is a set with no elements, but \(\{ a \}\) is a set with one element (namely \(\varnothing\)).

Example 1.6
Check that you agree that each of the following sets has exactly two elements;
\(\displaystyle 
A=\{\mathbb{N},3\},\qquad
B=\{\{1,2\}, \{1,3\}, \{1,2\}\},\qquad
C=\{\varnothing, \{\varnothing\}\}.
\)

Note that it is correct to write \(\mathbb{N}\in A\) and incorrect to write \(\mathbb{N}\subseteq A\).

Note that \(1\notin B\).

Note that \(\varnothing \in C\) and also \(\varnothing \subseteq C\) (in fact, for any set \(S\), \(\varnothing \subseteq S\)).

We have already seen the natural numbers, \(\mathbb{N} = \left\{ 0,1,2,\ldots \right\}\), as an example of a set.  Some other important examples are:

Notation
The set of integers, \(\mathbb{Z} = \left\{  \ldots,-2,-1,0,1,2,\ldots\right\}\), consisting of \(0\), the non-zero natural numbers (also known as the positive integers), and the negative integers \(-1,-2,-3,-4,\dots \) made by writing a minus sign in front of each of the positive integers.

This is notation rather than a definition because, done properly, I would need to explain how to add and multiply these negative integers. Note that \(\mathbb{N}\subset\mathbb{Z}\).

Notation
The set of rational numbers (or simply `rationals'), \(\mathbb{Q}\), is the set comprising all fractions where the numerator \(m\) and denominator \(n\) are both integers.  That is, 
\(\displaystyle 
\mathbb{Q}=\left\{  \frac{m}{n} : m\in\mathbb{Z},n\in\mathbb{Z},n>0\right\}.
\)

This is close to a definition, except I haven't captured the idea that two fractions can be equivalent to each other like \(\frac{1}{2}\) and \(\frac{3}{6}\). Chapter 2 on equivalence relations will give us a way to describe this. Note that the rationals of the form \(\frac{m}{1}\) are (loosely speaking) a copy of \(\mathbb{Z}\), and so \(\mathbb{Z}\subset \mathbb{Q}\).

Notation
The set of real numbers, \(\mathbb{R}\), is the set containing numbers with a decimal expansion. These will be formally introduced in Analysis I.

You will notice that I'm avoiding the question of how to define these. The real numbers include the rational numbers (and so \(\mathbb{Q}\subset \mathbb{R}\)), but also irrational numbers such as \(\sqrt{2}\) and \(\pi\).

Notation
The set of complex numbers, \(\mathbb{C}=\{a+b\textrm{i} : a,b\in\mathbb{R}\}\), with the multiplication rule \(\textrm{i}^2=-1\).

Note that, if we identify a number of the form \(a+0\textrm{i}\in\mathbb{C}\) with \(a\in \mathbb{R}\), then we have \(\mathbb{R}\subset\mathbb{C}\).

The symbols for each of these sets are written in `blackboard bold' font.  When writing them by hand there is no need to make them look quite so fancy; simply adding an extra line somewhere in the capital letter is sufficient.

Some frequently occurring subsets of the real numbers are intervals, which can be visualised as sections of the real line.

Definition 1.7 (Bounded interval, unbounded interval, open interval, closed interval) 
Given real numbers \(a,b\) with \(a \le b\) we define bounded intervals

\( \begin{align*} \left( a,b\right) & = \left\lbrace x\in \mathbb{R} : a < x < b \right\rbrace\\ \left[ a,b\right] & = \left\lbrace x\in \mathbb{R} : a \leqslant x \leqslant b \right\rbrace\\ \left[ a,b\right) & = \left\lbrace x\in \mathbb{R} : a \leqslant x < b \right\rbrace\\ \left( a,b\right] & = \left\lbrace x\in \mathbb{R} : a < x \leqslant b \right\rbrace \end{align*} \)

An interval of the form \((a,b)\) or \((a,\infty)\) or \((-\infty,a)\) is called an open interval.

An interval of the form \([a,b]\) or \([a,\infty)\) or \((-\infty,a]\) is called a closed interval.

Sadly, "closed" and "open" are not mutually exclusive. The interval \((a,b]\) is neither an open interval nor a closed interval.

If \(a = b\), then \([a,b] = \{ a\}\), while \((a,b)\) and \([a,b)\)and \((a,b]\) are all \(\varnothing\).

The notation above uses the \(\infty\) symbol, which you might have seen before to represent the concept of `infinity'. Please note that \(\infty\notin\mathbb{R}\) and it is not meaningful to write things like \(x< \infty\). The notation for unbounded intervals is not a subset of the notation for bounded intervals!

The diagram below visualises three intervals as sections of the real line, using filled circles at the endpoints to indicate that the number there is included, and an empty circle to indicate that it is not.

We have seen some examples where the elements of the set are also sets. An important example of this is given by the following definition.

Definition 1.8 (Power set) 
The power set of a set \(A\), denoted \(\mathcal{P}(A)\), is the set of all subsets of \(A\).

Example 1.9
    (i) For \(A=\left\{  0,1\right\}\), we have \(\mathcal{P}(A)=\left\{  \varnothing, \left\{ 0\right\}  ,\left\{ 1\right\} ,\left\{ 0, 1\right\}  \right\}.\)
    (ii) For \(A=\mathbb{N}\), \(\mathcal{P}(A)\) has elements including the set of all even numbers, the set \(\{0,1\}\), the set of all primes \(p\) such that \(p+2\) is also prime, the empty set, and many more.

If we have two objects \(a\) and \(b\) we can combine them together to make a set \(\{a,b\}\), but we could also combine them to make an ordered pair \((a,b)\).  The distinction is that in an ordered pair the order matters.

Two pairs \((a_1,b_1)\) and \((a_2,b_2)\) are equal if and only if \(a_1 = a_2\) and \(b_1 = b_2\).  Unlike the set \(\{a,a\}\), which we consider equal to the set \(\{a\}\), for an ordered pair \((a,a)\) is not considered equal to \((a)\). Indeed, \((a)\) is not even considered to be an ordered pair.

You are probably familiar with such objects in the context of vectors or coordinates.  If the elements are real numbers, for example, then \((a,b)\) is a two-dimensional vector, and can be thought of as representing the \(x\)-\(y\) coordinates of a point on a plane (in that context it is clear that \((1,2)\) is quite different from \((2,1)\); order matters!).   Although we will often use ordered pairs in this way, the definition is much more general, since there is no reason why the elements \(a\) and \(b\) need come from the same sets or even be similar `types' of object.

Definition 1.10 (Cartesian product) 
Given sets \(A\) and \(B\), the Cartesian product, denoted \(A \times B\), is the set of all ordered pairs with the first element of the pair coming from \(A\) and the second from \(B\).  That is,
\(\displaystyle 
A \times B = \left\{ (a,b) : a \in A \text{ and } b \in B \right\}.
\)

Cartesian products are named after René Descartes.

Notation
If \(A = B\), we might write \(A \times A\) as \(A^2\).  

Example 1.11
The case where \(A = B = \mathbb{R}\) is a particularly important one that you will see in the Geometry course. In that case, the Cartesian product is \(\mathbb{R}^2\) (usually read as "r two" rather than "r squared"), and represents the two-dimensional plane.

We can similarly create ordered triples \((a,b,c)\), quadruples \((a,b,c,d)\) and so on.  If there are \(n\) elements it is called an \(n\)-tuple.

Definition 1.12 (Cartesian product of \(n\) sets) 
We define \(A_1 \times A_2 \times \ldots \times A_n\) to be the set of all ordered \(n\)-tuples \((a_1,a_2,\ldots, a_n)\), where \(a_i \in A_i\) for \(1\le i \le n\).  If all the \(A_i\) are copies of \(A\), we might write this Cartesian product as \(A^{n}\).

You will have noticed that, regrettably, the same notation is used for open intervals \((a,b)\) and ordered pairs \((a,b)\). The context usually helps!

Remark. The following example is known as Russell's paradox (after the mathematician and philosopher Bertrand Russell, 1872--1970).  It provides a warning as to the looseness of our definition of a set.  Suppose
\(\displaystyle 
H = \left\{\text{sets } S : S \notin S \right\}.
\)
That is, \(H\) is the collection of sets \(S\) that are not elements of themselves.  All the sets we have come across seem to be in \(H\) (for example, \(\mathbb{N}\) is in \(H\) since the elements of \(\mathbb{N}\) are individual numbers and clearly none of them is the set \(\mathbb{N}\) itself).  The problem arises when we ask the question of whether or not \(H\) is itself in \(H\)?

On the one hand, if \(H\notin H\) then \(H\) meets the precise criterion for being in \(H\) and so \(H\in H\), a contradiction. On the other hand, if \(H\in H\) then by the property required for this to be the case, \(H\notin H\), another contradiction.  Thus we have a paradox: \(H\) seems to be neither in \(H\) nor not in \(H\).

The modern resolution of Russell's Paradox is that we have taken too naïve an understanding of "collection", and that Russell's "set" \(H\) is in fact not a set.  It does not fit within axiomatic set theory (which relies on the so-called ZF axioms), and so the question of whether or not \(H\) is in \(H\) simply doesn't make sense.

1.1 Algebra of sets

Definition 1.13 (Union, intersection, complement, set difference) 
Given subsets \(A\) and \(B\) of a set \(S\), the union \(A\cup B\) is the set consisting of those elements that are in \(A\) or \(B\) (or both), that is:
\(\displaystyle 
A\cup B=\{x\in S : x\in A\text{ or }x\in B\}.
\)
The intersection \(A\cap B\) is the set consisting of those elements that are in both \(A\) and \(B\), that is:
\(\displaystyle 
A\cap B=\{x\in S : x\in A\text{ and }x\in B\}.
\)
The complement of \(A\), written \(A^{c}\) or sometimes \(A^{\prime}\),
is the subset consisting of those elements that are not in \(A\), that is:
\(\displaystyle 
A^{c}=\{x\in S : x\notin A\}.
\)
The set difference, or complement of \(B\) in \(A\), written
\(A\backslash B\), is the subset of \(A\) consisting of those
elements that are not in \(B\), that is:
\(\displaystyle 
A\backslash B=\{x\in A : x\notin B\}.
\)
Note that \(A \backslash B = A \cap B^{c}\).

A useful way of visualising these is using a Venn diagram.  The following is an example, where \(A\) and \(B\) are the regions inside the two circles, respectively:

Definition 1.14 (Disjoint sets) 
Two sets \(A\) and \(B\) are said to be disjoint if \(A\cap
B=\varnothing\), that is the two subsets have no element in common.

More generally, we can take unions and intersections of arbitrary numbers of sets, even infinitely many.  If we have a family of subsets \(\left\{ A_i : i \in I \right\}\), where \(I\) is called an indexing set, we write 
\(\displaystyle  
\bigcap_{i \in I} A_i = \left\{ x\in S : x \in A_i \text{ for all } i \in I \right\},
\)
and
\(\displaystyle  
\bigcup_{i \in I} A_i = \left\{ x\in S : x \in A_i \text{ for at least one } i \in I \right\}.
\)
Often \(I\) might be a subset of \(\mathbb{N}\), in which case we write things like 
\(\displaystyle 
\bigcap_{i = 1}^{n} A_i , \qquad
\bigcup_{i = 1}^{\infty} A_i,
\)
but it could be an even "larger" set such as \(\mathbb{R}\).

Example 1.15
Let \(S\) be the set of all students at Oxford, \(A \subseteq S\) be the set of students studying mathematics, and \(B \subseteq S\) be the set of students at your college.  Then \(A\cap B\) is the set of students studying mathematics at your college, \(A \cup B\) is the set of students either at your college or studying mathematics (this is probably the set where many of your friends will come from), \(B^{c}\) is the the set of all students at other colleges, \(A\backslash B\) is the set of students studying mathematics at other colleges.

Example 1.16
The set of irrational numbers is \(\mathbb{R}\backslash \mathbb{Q}\).

Example 1.17
Some authors define the set of natural numbers to be what I would write as \(\mathbb{N}\backslash\{0\}\). Note that I have to wrap the \(0\) in curly braces, because \(0\) is not a set and \(A\backslash B\) is only defined when \(B\) is a set.

The following result may well seem obvious, but it provides quite an important recipe for how to show that two sets are the same, as we will see below.

Proposition 1.18 (Double Inclusion)
Let \(A\) and \(B\) be two subsets of a set \(S\). Then \(A=B\) if and only if \(A\subseteq B\) and \(B\subseteq A.\)

Proof. If \(A = B\), then every element in \(A\) is an element in \(B\), so certainly \(A \subseteq B\), and similarly \(B \subseteq A\).

Conversely, suppose \(A \subseteq B\), and \(B \subseteq A\).  Then for every element \(x \in S\), if \(x \in A\) then \(A \subseteq B\) implies that \(x \in B\), and if \(x \notin A\) then \(B \subseteq A\) means \(x \notin B\).

So \(x\in A\) if and only if \(x\in B\), and therefore \(A = B\).

\(\square\)

Here is an example of how we can make use of double inclusion to show that two sets are equal:

Proposition 1.19 (Distributive Laws)
Let \(A,B,C\) be subsets of a set \(S\). Then
    (i) \(A\cup\left(B\cap C\right) = \left(A\cup B\right) \cap \left(A\cup C\right)\)
    (ii) \(A\cap\left(B\cup C\right) = \left(A\cap B\right) \cup \left(A\cap C\right)\)

Proof. We first prove (i). 

Suppose \(x\) is in the LHS of (i), that is \(x\in A\cup\left(B\cap C\right)\). This means that \(x\in A\) or \(x\in B\cap C\). Thus either \(x\in A\) or \(x\) is in both \(B\) and \(C\). If \(x \in A\) then \(x \in A \cup B\) and \(x \in A \cup C\), and therefore \(x\) is in the RHS. If \(x\) is in both \(B\) and \(C\) then similarly \(x\) is in both \(A\cup B\) and \(A \cup C\). Thus every element of the LHS is in the RHS, which means we have shown \(A\cup\left(B\cap C\right) \subseteq \left(A\cup B\right)   \cap \left(A\cup C\right)\).

Conversely suppose that \(x\in\left(A\cup B\right)  \cap\left( A\cup C\right).\)  Then \(x\) is in both \(A\cup B\) and \(A\cup C\).   Thus either \(x \in A\) or, if \(x \notin A\), then \(x\in B\) and \(x\in C\).  Thus \(x \in A \cup \left(B\cap C\right)\).  Hence \(\left(A\cup B\right) \cap\left(A\cup C\right) \subseteq A\cup\left(B\cap C\right)\).

By double inclusion, \(\left(A\cup B\right) \cap\left(A\cup C\right) = A\cup\left(B\cap C\right)\).

The proof of (ii) follows similarly and is left as an exercise.

\(\square\)

In the proof above there were two separate things to show (that is, LHS \(\subseteq\) RHS, and RHS \(\subseteq\) LHS, which combine to give the required result).  When laying out a proof like this it is helpful to separate the two things out clearly, both to aid your own understanding and that of the reader.  Here we have done that by starting a new paragraph, while the smaller individual steps of the argument were written as sentences.  When hand-writing a proof, some people tend to put each step of the logic on a new line, in which case leaving a larger gap or using different indentation may help to distinguish the separate sections.

Here is an example of how set complements work.

Proposition 1.20 (De Morgan's Laws)
Let \(A\) and \(B\) be subsets of a set \(S\). Then
\(\displaystyle 
(A\cup B)^{c} = A^{c} \cap B^{c} 
\qquad \text{ and } \qquad
(A\cap B)^{c} = A^{c} \cup B^{c}.
\)
Proof. For the first one, suppose \(x \in (A\cup B)^{c}\).  Then \(x\) is not in either \(A\) or \(B\).  Thus \(x\in A^{c}\) and \(x\in B^{c}\), and therefore \(x \in A^{c} \cap B^{c}\).

Conversely, suppose \(x \in A^{c} \cap B^{c}\).  Then \(x \notin A\) and \(x \notin B\), so \(x\) is in neither \(A\) nor \(B\), and therefore \(x \in (A\cup B)^{c}\).  

By double inclusion, the first result holds.

The second result follows similarly and is again left as an exercise.

\(\square\)

De Morgan's laws extend naturally to any number of sets, so if \(\left\{ A_i : i \in I \right\}\) is a family of subsets of \(S\), then
\(\displaystyle 
\left( \bigcap\limits_{i\in I}A_{i} \right)^{c}=\bigcup\limits_{i\in I} A_{i}^{c}
\qquad \text{and} \qquad
\left( \bigcup\limits_{i\in I}A_{i}\right)^{c}=\bigcap\limits_{i\in I} A_{i}^{c}.
\)

1.2 Truth tables

Another way of proving set-theoretical identities is via truth tables.  These provide a systematic way of cataloguing all the different cases for whether or not a given element is in each set.  Here is an example:

The different cases are listed in the rows, one row for each, and various sets are placed along the columns. We put a T or an F in each column to indicate whether it is true or false that the given element is in that set for each case.  There will be different numbers of cases to consider depending on the number of sets involved; in this example with two sets, there are four (the first two columns effectively define these four different cases, and the entries in the other columns then follow from those).

Truth tables like this are more often used to catalogue the cases of `true' or `false' for a series of logical statements.  These truth tables for sets are a particular instance, where the statements are of the form `\(x \in A\)', `\(x \in B\)', `\(x \in A\cap B\)', and so on.

Here is an alternative proof of De Morgan's laws using a truth table:

Proof of Proposition 1.20. We list the four combinations of cases for whether or not \(x\in A\) and \(x \in B\):

Comparing columns, the fact that \((A\cap B)^{c}\) and \(A^{c} \cup B^{c}\) are the same in every case shows that those two sets are the same.  Similarly, the fact that \((A\cup B)^{c}\) and \(A^{c} \cap B^{c}\) are the same in every case shows that those two sets are the same.

\(\square\)

1.3 Cardinality

Informally, the cardinality of a set \(S\), denoted \(|S|\), is a measure of its `size'.  For finite sets, there is little ambiguity about this -- it is simply the number of distinct elements in the set (we give a formal definition below, which will also clarify what it means to say that a set is finite).  But for infinite sets, things are more interesting.  For example, one might be tempted to think that the set of even natural numbers is in some sense `smaller' than the set of natural numbers -- there might reasonably seem to be `fewer' of them, since we have left the odd numbers out. But if we simply divide every element in that set by \(2\), then we see that for each even natural number we have a natural number, and vice versa (multiplying by \(2\)) for each natural number we have an even natural number. By this logic it seems that these two sets ought to be the same size. Indeed, these two sets do have the same cardinality, \(\aleph_{0}\) (pronounced `aleph-null'). This is the smallest infinite cardinal. The concept of cardinals was invented and investigated widely by Georg Cantor, 1845--1918. Perhaps surprisingly, the rational numbers \(\mathbb{Q}\) also have the same cardinality \(\aleph_{0}\). But the cardinality of the real numbers \(\mathbb{R}\) is larger, as will be discussed more in the Analysis I course.

We will be able to give a nicer definition of cardinality later, once we have discussed bijections, but the following provides a recursive definition of the cardinality for a finite set.

Definition 1.21 (Finite set (recursive definition)) 
A set \(S\) is finite if either
    (i) it is the empty set \(\varnothing\), or
    (ii) there exists \(s \in S\) such that \(S\backslash \{s\}\) is finite.

Any set that is not finite is said to be infinite.

Definition 1.22 (Cardinality of a finite set (recursive definition))
The cardinality of a finite set \(S\), written \(|S|\), is a natural number defined as follows;
    (i) if \(S=\varnothing\) then \(|S|=0\).
    (ii) if \(S\) is not empty, then by definition of finiteness there exists \(s \in S\) such that \(S \backslash \{s\}\) is finite. If \(| S \backslash \{s\}|=n\) then we define \(|S| = n + 1\).

It is not hard to see that this means that if \(S =\{ x_1,x_2, \ldots x_n \}\), and \(x_i \neq x_j\) whenever \(i \neq j\), then \(|S| = n\).  Conversely, if \(|S| = n\) then \(S\) is a set with \(n\) elements.

Proposition 1.23
Let \(A\) and \(B\) be finite sets. Then \(|A\cup B| = |A| + |B| - |A\cap B|\).

The proof is left as an exercise (see problem sheet).

Proposition 1.24 (Subsets of a finite set)
If a set \(A\) is finite with \(|A| = n\), then its power set has \(|\mathcal{P}(A)| = 2^{n}\).

Proof. We use induction.  For the initial step, note that if \(|A| = 0\) then \(A = \varnothing\) has no elements, so there is a single subset, \(\varnothing\), and therefore \(|\mathcal{P}(A)| = 1 = 2^{0}\).  

Now suppose that \(n\ge 0\) and that \(|\mathcal{P}(S)| = 2^{n}\) for any set \(S\) with \(|S| = n\).  Let \(A\) be any set with \(|A|= n+1\).  By definition, this means that there is an element \(a\) and a set \(A' = A \backslash \{a\}\) with \(|A'| = n\).  Any subset of \(A\) must either contain the element \(a\) or not, so we can partition \(\mathcal{P}(A) = \mathcal{P}(A') \cup \left\{ S \cup \{a\} : S \in \mathcal{P}(A') \right\}\). These two sets are disjoint, and each of them has cardinality \(|\mathcal{P}(A')| = 2^{n}\) by the inductive hypothesis. Hence \(|\mathcal{P}(A)| = 2^{n} + 2^{n} = 2^{n+1}\).

Thus, by induction, the result holds for all \(n\).

\(\square\)

An alternative, perhaps easier, way to see why the size of the power set should be \(2^{|A|}\) for a finite set \(A\), is to consider the process of creating a subset. We can do this systematically by going through each of the \(|A|\) elements in \(A\) and making the yes/no decision whether to put it in the subset. Since there are \(|A|\) such choices, that yields \(2^{|A|}\) different combinations of elements and therefore \(2^{|A|}\) different subsets.