§1 Sets

A set is a group of objects. The objects inside it are called elements.

$$A=\{1,2,3\}$$

Here, $1$, $2$, and $3$ are elements of $A$.

$$1\in A \qquad 4\notin A$$

• $x\in A$ means “$x$ is in $A$.”
• $x\notin A$ means “$x$ is not in $A$.”

The empty set

The empty set has nothing in it. We write it as

$$\varnothing \qquad\text{or}\qquad \{\}.$$

Since it has no elements,

$$x\notin\varnothing$$

no matter what $x$ is. Even the empty set is not inside itself:

$$\varnothing\notin\varnothing.$$

But $\{\varnothing\}$ is different. It is a set with one element, and that element happens to be the empty set:

$$\varnothing\in\{\varnothing\}.$$

Number sets

These symbols show up often:

In these notes, $0$ is included in $\mathbb N$. Some books start $\mathbb N$ at $1$, so it is always worth checking which convention is being used.

Each set fits inside the next one:

$$\mathbb N^+\subseteq\mathbb N\subseteq\mathbb Z\subseteq\mathbb Q\subseteq\mathbb R.$$

$\mathbb N$ and $\mathbb Z$ are discrete: their values come in separate steps. $\mathbb R$ is continuous: there are always more real numbers between any two different real numbers.

Elements and subsets are not the same thing

The symbols $\in$ and $\subseteq$ describe two different relationships.

• $x\in A$ asks whether one object is inside $A$.
• $B\subseteq A$ asks whether every element of $B$ is also in $A$.

For example,

$$\{1,2,3\}\subseteq\mathbb N.$$

This is true because $1$, $2$, and $3$ are all natural numbers.

More generally,

$$A\subseteq B$$

means that anything in $A$ must also be in $B$.

The empty set is a subset of every set:

$$\varnothing\subseteq A.$$

Why? For this to be false, we would need to find something in $\varnothing$ that is missing from $A$. There is nothing in $\varnothing$, so there can be no counterexample.

That does not mean $\varnothing$ is an element of every set:

$$\varnothing\subseteq A \quad\text{is always true, but}\quad \varnothing\in A \quad\text{may be false.}$$

Sometimes both relationships can be true. If

$$A=\{1,2,\{1,2\}\},$$

then

$$\{1,2\}\in A$$

because $\{1,2\}$ appears as one element of $A$. We also have

$$\{1,2\}\subseteq A$$

because both $1$ and $2$ are elements of $A$.

Two ways to write a set

List the elements

The simplest way is to list everything inside braces:

$$A=\{1,2,3\}.$$

Order does not matter, and writing something twice does not add a new element:

$$\{1,2,3\} = \{3,2,1\} = \{1,1,2,3\}.$$

A set only remembers whether an element is there. It does not remember its position or how many times it was written.

Describe a rule

For a large or infinite set, listing everything is not practical. Instead, we can describe which values belong:

$$A=\{x\in U\mid x\text{ follows a certain rule}\}.$$

Read the vertical bar as “such that.” The set $U$ tells us where $x$ is allowed to come from.

For example,

$$\mathbb N=\{x\in\mathbb Z\mid x\ge0\}.$$

This says: take the integers, then keep the ones that are at least zero.

The odd natural numbers can be written as

$$O=\{1,3,5,7,\ldots\}$$

or

$$O=\{2k+1\mid k\in\mathbb N\}.$$

As $k$ runs through $0,1,2,3,\ldots$, the expression $2k+1$ gives $1,3,5,7,\ldots$.

Rational numbers

A rational number is any number that can be written as a fraction of two integers:

$$\mathbb Q= \left\{ \frac ab \;\middle|\; a,b\in\mathbb Z, b\neq0 \right\}.$$

The same number can have many fraction forms:

$$\frac12=\frac24=\frac{-3}{-6}.$$

We usually clean this up by reducing the fraction and keeping the denominator positive. That is why

$$\frac{2}{-3}$$

is normally written as

$$-\frac23.$$

When are two sets equal?

Two sets are equal when they contain exactly the same elements. The way they are written does not matter.

A common way to prove that $A=B$ is to prove both directions:

$$A\subseteq B \qquad\text{and}\qquad B\subseteq A.$$

This works because the first direction says $A$ has nothing extra, while the second says $B$ has nothing extra.

Example: two forms of the odd integers

Consider

$$O=\{2k+1\mid k\in\mathbb Z\}$$

and

$$A=\{2\ell-1\mid \ell\in\mathbb Z\}.$$

They look different, but both produce every odd integer.

First, take any $x\in O$. Then $x=2k+1$ for some integer $k$. We can rewrite it as

$$x=2k+1=2(k+1)-1.$$

Since $k+1$ is still an integer, $x$ has the form used in $A$. Therefore,

$$O\subseteq A.$$

Now go the other way. Take any $x\in A$. Then $x=2\ell-1$ for some integer $\ell$. Rewrite it as

$$x=2\ell-1=2(\ell-1)+1.$$

Since $\ell-1$ is an integer, $x$ has the form used in $O$. Therefore,

$$A\subseteq O.$$

Both directions are true, so

$$O=A.$$

The only real difference is where the integer counter starts. Shifting an integer by $1$ still gives an integer, so neither description misses any odd numbers.

Why a rule does not always create a valid set

It is tempting to think that any rule can define a set. Russell's paradox shows why that causes trouble.

Imagine trying to define

$$R=\{x\mid x\text{ is a set and }x\notin x\}.$$

In words, $R$ contains every set that does not contain itself.

Now ask: does $R$ contain itself?

• Suppose $R\in R$. Then $R$ should satisfy its own rule, which says $R\notin R$.
• Suppose $R\notin R$. Then $R$ does satisfy the rule, so $R\in R$.

Either answer gives the opposite answer:

$$R\in R\iff R\notin R.$$

That contradiction is Russell's paradox.

The safe approach is to start with a set that already exists, then choose some of its elements:

$$\{x\in U\mid x\text{ follows a certain rule}\}.$$

This builds a subset of $U$. It does not try to create a giant “set of everything.”

Keep these straight

• $x\in A$: $x$ is one element of $A$.
• $B\subseteq A$: every element of $B$ is also in $A$.
• $\varnothing\subseteq A$ is always true.
• $\varnothing\in A$ is only true if $A$ actually contains the empty set.
• Sets ignore order and repeated entries.
• To prove $A=B$, prove both $A\subseteq B$ and $B\subseteq A$.
• In set-builder notation, start with a set $U$ and select elements from it.