In school, we learn how a line has an equation… and a circle has an equation… what does this mean?

points $(x_0,y_0)$ on curve $\longleftrightarrow$ solutions $(x_0,y_0)$ of equation

however this note explains all of this from first principles, with a particular emphasis on the set-theoretic fundamentals.

## Set Theory

set is a collection of objects. The objects of a set are referred to as the elements or members and if we can list the elements we include them in curly-brackets. For example, call by $S$ the set of whole numbers (strictly) between two and nine. This set is denoted by

$S=\{3,4,5,6,7,8\}$.

We indicate that an object $x$ is an element of a set $X$ by writing $x\in X$, said, $x$ in $X$ or $x$ is an element of $X$. We use the symbol $\not\in$ to indicate non-membership. For example, $2\not\in S$.

Elements are not duplicated and the order doesn’t matter. For example:

$\{x,x,y\}=\{x,y\}=\{y,x\}$.

The cardinality of a set is a measure of the size of the set and for finite sets is just given by the number of elements. For example, the cardinality of $S=\{3,4,5,6,7,8\}$ is equal to six. The cardinality of a set $X$ is denoted by $|X|$ and so we have

$|S|=6$.

Things are far more complicated for infinite sets. Consider the set of natural numbers:

$\mathbb{N}=\{1,2,3,\dots\}$,

where the dots signify that there are infinitely many such numbers. It is reasonable to write something like:

$|\mathbb{N}|=\infty$,

however this turns out to give problems when we consider the cardinality of the rational numbers, $|\mathbb{Q}|$, and the cardinality of the real numbers, $|\mathbb{R}|$.

## Subsets

subset of a set $X$, is another set $Y$ such that whenever $y\in Y$ then $y\in X$ also. When this is the case, we write $Y\subseteq X$. For example, the set $A$ of odd numbers (strictly) between two and nine is a subset of the set of numbers (strictly) between two and nine:

$A=\{3,5,7\}\subseteq \{3,4,5,6,7,8\}$.

Note that a set $X$ is always a subset of itself, $X\subseteq X$, because whenever $x\in X$ of course $x\in X$.

A convenient way to think of a subset of a set $X$ is as a choice of elements from $X$. A subset of $X$ is formed by making a choice for each of the elements of $X$ whether to include them or not. For example, for the set $S=\{3,4,5,6,7,8\}$, the subset $\{3,5,7\}=A\subseteq S$ is formed by making the choices:

$3\in A,4\not\in A,5\in A,6\not\in A,7\in A,8\not\in A$.

Under this view, we have, for all sets, $X\subseteq X$, the subset $X$ being formed by choosing all of the elements of $X$.

The subset formed when we choose none of the elements of $X$ is called the empty set. Denoted by $\emptyset$ or $\{\}$, the empty set is a subset of every set:

$\emptyset \subseteq X$.

How many subsets does a finite set have? Recall always that the full choice and empty choice are always subsets. Also if we collect the subsets of a set $X$ as objects we form a set: the set of subsets of $X$.

Let us start with the empty set, $\emptyset=\{\}$. In this case the full and empty choices coincide — as the empty set itself. There are no other choices as there are no elements to choose and so there is only one subset of $\emptyset$:

set of subsets of $\emptyset=\{\emptyset\}$.

Also, $|\text{set of subsets of }\emptyset|=1$.

Consider now the set containing one element, say $\{a\}$. Now we can either include or not include $a$, giving two subsets:

set of subsets of $\{a\}=\{\{a\},\{\}\}$.

We are already weary of writing “set of subsets of” so we introduce the notation $\mathcal{P}(X)$:

$\mathcal{P}(X)=\text{ set of subsets of }X$.

So $\mathcal{P}(\emptyset)=\{\emptyset\}$ (so $|\mathcal{P}(\emptyset)|=1$, and (recalling $\emptyset:=\{\}$) $\mathcal{P}(\{a\})=\{\{a\},\{\}\}$, so $|\mathcal{P}(\{a\})|=2$.

Now consider $\{a,b\}$. We have two choices for $a$: include or not; and two choices for $b$: include or not. We list:

$\mathcal{P}(\{a,b\})=\{\{\},\{a\},\{b\},\{a,b\}\}$.

Note $|\mathcal{P}(\{a,b\})|=4$.

We can keep listing all day, for example with three elements we have the empty set (choose none), singletons (sets with one element: choose one), two element subsets (choose two) and the full subset (choose all):

$\mathcal{P}(\{a,b,c\})=\{\{\},\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$,

and so $|\mathcal{P}(\{a,b,c\})|=8$.

There is a fairly simple relationship between the cardinality of a set $X$ (denoted $|X|$), and the cardinality of the set of subsets of $X$, $\mathcal{P}(X)$ (denoted $|\mathcal{P}(X)|$).

If $X$ is finite, then the cardinality of $X$, $|X|$ is simply the number of elements in $X$ while the cardinality of $\mathcal{P}(X)$, $|\mathcal{P}(X)|$, is therefore the number of subsets of $X$.

### Proposition

For any set $X$,

$|\mathcal{P}(X)|=2^{|X|}$.

Proof using Fundamental Principle of Counting: Let $X=\{a_1,a_2,\dots,a_n\}$ so that $|X|=n$. A subset $S$ of $X$ corresponds to a series of choices:

$a_1\in S$?, $a_2\in S$?,… $a_n\in S$?

This is $n$ tasks and there are two ways of completing each task. By the fundamental principle of counting, there are

$\underbrace{2\times 2\times\cdots\times 2}_{n\text{ tasks}}=2^n=2^{|X|}$

ways of choosing a subset of $X$ $\bullet$

Proof by Induction: Let $P(n)$ be the proposition that $|X|=n\Rightarrow |\mathcal{P}(X)|=2^n=2^{|X|}$.

Consider $X=\emptyset$ so that $|X|=0$, $\mathcal{P}(X)=\{\emptyset\}\Rightarrow |\mathcal{P}(X)|=1=2^0=2^{|X|}$.

Now assume $P(k)$: a set of cardinality $k$ has $2^k$ subsets. Consider $P(k+1)$. Let $X=\{a_1,a_2,\dots,a_k,a_{k+1}\}$. Consider the set $X_k=\{a_1,a_2,\dots,a_k\}$. This set has a cardinality of $k$ and so by assumption has $2^k$ subsets.

Now consider again the subsets of $X=\{a_1,a_2,\dots,a_k,a_{k+1}\}$. A subset of $X$ is a choice of elements from $X$. We can form subsets of $X$ by taking subsets of $X_k=\{a_1,a_2,\dots,a_k\}$ and either including $a_{k+1}$ or not. Where $Y_1,Y_2,\dots,Y_{2^k}$ is an enumeration of $\mathcal{P}(X_k)$, and $Y_i\cup \{a_{k+1}\}$ is the set containing all the elements of $Y_i$ as well as the element $a_{k+1}\in X$, the subsets of $X$ are given by:

$\mathcal{P}(X)=\{\underbrace{Y_1,Y_2,\dots,Y_{2^k}}_{2^k\text{ elements}},\underbrace{Y_1\cup \{a_{k+1}\},Y_2\cup \{a_{k+1}\},\dots, Y_{2^k}\cup\{a_{k+1}\}}_{2^k\text{ elements}}\}$

$\Rightarrow |\mathcal{P}(X)|=2^k+2^k=2\times 2^k=2^{k+1}$,

therefore $P(k+1)$ is true and so by the principle of induction $P(n)$ is true for all $n\in\mathbb{N}$ $\bullet$

It is because of this result that we sometimes call $\mathcal{P}(X)$ the power set of $X$ (even if $X$ is infinite).

Of course, if $X\subseteq Y$, and $Y\subseteq Z$, then $X\subseteq Z$. Why? Well if $X$ is a choice of elements of $Y$, and $Y$ and choice of elements of $Z$, then $X$ is a choice of elements of $Z$. This means that the relationship $\subseteq$ is transitive.

It is also the case that if $X\subseteq Y$, $X\in\mathcal{P}(Y)$, that $\mathcal{P}(X)\subseteq \mathcal{P}(Y)$. A subset of $\mathcal{P}(Y)$ is a selection of some of the subsets of $Y$. Select the subsets of $Y$ that contain only elements of $X$. Subsets of $Y$ (elements of $\mathcal{P}(Y)$) that contain only elements of $X$ are nothing but selections from $X$, i.e. subsets of $X$, in other words elements of $\mathcal{P}(X)$.

As an example, consider the set of real numbers, $\mathbb{R}$. This is all numbers that can be expressed as a decimal. We can represent it graphically using a number line:

It has positive and negative directions, a notional centre (0), and a distance corresponding to one. We can’t list all the real numbers. If we choose some real numbers we get subsets. For example, if we just choose the fractions,

$\mathbb{Q}=\left\{\frac{m}{n}:m,n\in\mathbb{Z}, n\neq 0\right\}$,

we have a subset:

$\mathbb{Q}\subseteq \mathbb{R}\Rightarrow \mathbb{Q}\in\mathcal{P}(\mathbb{R})$.

It isn’t immediately obvious that there are decimals that cannot be written as a fraction, elements of $x\in\mathbb{R}\backslash \mathbb{Q}$ (elements in $\mathbb{R}$ but not in $\mathbb{Q}$ — decimals that are not fractions), but it turns out there are many:

$\sqrt{2}\not\in \mathbb{Q},\,e\not\in\mathbb{Q}$, and $\pi\not\in \mathbb{Q}$

No, $\pi\neq \frac{22}{7}$, that is only an approximation. For a proof that $\sqrt{2}$ is not equal to any fraction see here.

Note that $\mathbb{Q}\subseteq \mathbb{R}$ so we can say that:

$\mathcal{P}(\mathbb{Q})\subseteq \mathcal{P}(\mathbb{R})$.

Now, from the set of fractions, choose just the whole numbers (positive, negative, and zero). Note whole numbers are fractions, for example, $-8=\frac{-8}{1}$. As the set of whole numbers, $\mathbb{Z}$, is a selection from $\mathbb{Q}$, we have

$\mathbb{Z}\subseteq\mathbb{Q}\Rightarrow \mathbb{Z}\in \mathcal{P}(\mathbb{Q})$.

Also, as $\mathbb{Q}\subseteq\mathbb{R}$, we also have that

$\mathbb{Z}\subseteq\mathbb{R}$, so that $\mathbb{Z}\in\mathcal{P}(\mathbb{R})$.

Similarly we have, where $\mathbb{N}=\{1,2,3,\dots\}$, is the natural numbers

$\mathbb{N}\subseteq\mathbb{Z}\subseteq \mathbb{Q}\subseteq \mathbb{R}$,

so we can say things like

$\mathbb{N},\mathbb{Z},\mathbb{Q}\in \mathcal{P}(\mathbb{R})$,

and indeed taking those sets as choices of elements of $\mathcal{P}(\mathbb{R})$, we can form a subset of $\mathcal{P}(\mathbb{R})$. Also including the empty set (choose none of the real numbers), and $\mathbb{R}$ (choose all of the real numbers), and we can say things like:

$\{\emptyset,\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}\}\subseteq \mathcal{P}(\mathcal{P}(\mathbb{R}))$.

## Cartesian Products

Given two sets $X$ and $Y$, we can form their Cartesian product $X\times Y$. This is a set, whose elements are ordered pairsPairs, because they consist of two elements: one from $X$ and one from $Y$, and ordered because we list the element of $X$ first and then the element of $Y$. For example, where $A=\{0,1\}$, and $B=\{a,b,c\}$,

$(1,b)\in A\times B$.

We use the round brackets to emphasise that we have an ordered pair. The ordered pair $(1,b)$ is not the same as the set $\{1,b\}$ because $\{b,1\}=\{1,b\}$ but $(1,b)$ is not the same as $(b,1)$ — order matters.

The Cartesian product is the set of all such ordered pairs:

$X\times Y:=\{(x,y):x\in X,y\in Y\}$.

This is spoken, $X$ times $Y$ is defined as the set of ordered pairs $x,y$, such that $x$ is an element of $X$ and $y$ is an element of $Y$.

For example, if $A=\{0,1\}$ and $B=\{a,b,c\}$, then

$A\times B=\{(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)\}$.

### Exercises

1. Prove that for $|X|=n$ and $|Y|=m$, $|X\times Y|=|X|\times |Y|$.
2. Prove that for finite sets, $|\mathcal{P}(X\times Y)|=2^{|X|\cdot|Y|}$.

A particular cartesian product of interest is the plane, $\Pi$. This is formed by taking the cartesian product of $\mathbb{R}$ with itself:

$\Pi=\mathbb{R}\times\mathbb{R}$.

It is a set of ordered pairs, therefore, such that the first element is a real number and the second is a real number:

$\Pi=\mathbb{R}\times\mathbb{R}=\{(x,y):x,y\in\mathbb{R}\}$.

This is the ordinary plane we are all familiar with. The $x$ is from a horizontal number line (first copy of $\mathbb{R}$), and the $y$ from a vertical number line (second copy of $\mathbb{R}$). Each point corresponds to some pair $(x_0,y_0)\in\mathbb{R}\times\mathbb{R}=\Pi$, and each ordered pair $(x_0,y_0)\in\mathbb{R}\times\mathbb{R}=\Pi$ corresponds to some point on the plane (in the obvious way):

## Relations

relation between sets $X$ and $Y$ is a subset of $X\times Y$; that is an element of $\mathcal{P}(X\times Y)$.

For, example, where $A=\{0,1\}$ and $B=\{a,b\}$, any subset of

$A\times B=\{(0,a),(0,b),(1,a),(1,b)\}$

is a relation. For example,

$R=\{(0,a),(0,b),(1,a)\}$

is a relation. We have $0Ra$ (spoken $0$ is related to $a$), $0Rb$, and $1Ra$.

From exercise two above, this means that there are $2^{|X|\cdot|Y| }$ relations between finite sets $X$ and $Y$.

The full relation between $X$ and $Y$ is selecting all of the ordered pairs, so taking the whole of $X\times Y\in\mathcal{P}(X\times Y)$.

The empty relation between $X$ and $Y$ is selecting none of the ordered pairs, so just the empty set $\emptyset \in \mathcal{P}(X\times Y)$.

When we have a relation $R$ between $X$ and itself, we just say that $R$ is a relation on $X$. So a relation on $X$ is just an element of $\mathcal{P}(X\times X)$.

A relation on $\mathbb{R}$, is a subset of $\mathbb{R}\times\mathbb{R}$, and so just a selection of points on the plane. For example, where the selected points are painted black, the following is a subset of the plane (an element of $\mathcal{P}(\Pi)=\mathcal{P}(\mathbb{R}\times\mathbb{R})$, and so a relation on $\mathbb{R}$:

## Equational Relations

Now suppose that $f(x,y)=0$ is an equation in terms of $x$ and $y$. For example,

$x^2+3y^4+xy=0$.

Using an equation, we can define a relation on $\mathbb{R}$. Recall a relation on $\mathbb{R}$ is a subset of $\mathbb{R}\times\mathbb{R}$, an element of $\mathcal{P}(\mathbb{R}\times\mathbb{R})$… it is a selection of ordered pairs of real numbers.

We use the equation to choose the ordered pairs and we only pick ordered pairs $(x_0,y_0)$ such that $(x_0,y_0)$ solves the equation.

For example, the above equation defines a relation on $\mathbb{R}$, by only choosing the solutions:

$(x,y)\in R$ if and only if $x^2+3y^4+xy=0$.

Now think of solutions $(x_0,y_0)$ as points on the plane, $(x_0,y_0)\in\Pi=\mathbb{R}\times \mathbb{R}$. If we plot all of the solutions of the equation… in other words if we plot all elements of the relation, we have a subset of the plane.

If the equation is particularly nice, we get a nice curve. For example, the above relation, when plotted, gives:

1. Show that $x^2+y^2+1=0$ is the empty relation on $\mathbb{R}$. What does the curve look like?
2. Show that $\cos^2x+\sin^2x+\cos^2y+\sin^2y=2$ is the full relation on $\mathbb{R}$. What does the curve look like?