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:

If we plot all of the solutions of an equation, we get it’s curve. This is how an equation has a curve.

This wasn’t exactly the question though was it… the question was how does a curve have an equation.

The examples of lines and circles are not that difficult. Each line has an equation whose solutions correspond precisely to the points on the curve and similarly for circles.

Do all possible curves in/subsets of the plane have such an equation? This is a much harder problem!

Exercises

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?