Sets and membership

A set is a collection of distinct objects. The objects inside it are called elements or members. We write the elements between braces, such as $\{1,2,3\}$.

Example: membership

Let

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

The symbol $\in$ is the membership symbol. Read $x\in A$ as “$x$ is an element of $A$.” The symbol $\notin$ is the non-membership symbol and means “is not an element of.” Therefore,

$$1\in A \qquad\text{and}\qquad 4\notin A.$$

The empty set

The empty set is the set with no elements. Its symbol is $\varnothing$, and it can also be written as empty braces:

$$\varnothing=\{\}.$$

Since the empty set has no elements, $x\notin\varnothing$ for every object $x$. In particular,

$$\varnothing\notin\varnothing.$$

This says the empty set is not an element of itself. It is different from $\{\varnothing\}$, which is a set containing one element—the empty set:

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

Subsets and set inclusion

The symbol $\subseteq$ is the subset symbol. Read

$$A\subseteq B$$

as “$A$ is a subset of $B$” or “$A$ is included in $B$.” This relationship is called set inclusion. It means that every element of $A$ is also an element of $B$.

Equality is allowed, so every set is a subset of itself:

$$A\subseteq A.$$

A proper subset leaves out at least one element. The symbol $\subset$ means “is a proper subset of.” Read

$$A\subset B$$

as “$A$ is a proper subset of $B$.” It means $A\subseteq B$ but $A\neq B$, so the two sets are not equal.

You may also see $A\subsetneq B$. The symbol $\subsetneq$ always makes “subset but not equal” explicit. The symbol $\subset$ is sometimes used differently between books, but in these notes it means proper subset.

Example: comparing two sets

Let

$$A=\{1,2,3\} \qquad\text{and}\qquad B=\{1,2,3,4\}.$$

Then

$$A\subseteq B.$$

This is true because every element of $A$ also appears in $B$. It is a proper subset, $A\subset B$, because $4$ belongs to $B$ but not to $A$.

The empty set is a subset of every set:

$$\varnothing\subseteq A.$$

For this to be false, we would need an element of $\varnothing$ that is missing from $A$. There are no elements in $\varnothing$, so that can never happen. In particular, $\varnothing\subseteq\varnothing$.

Elements and subsets are different

The symbols $\in$ and $\subseteq$ describe different relationships:

That means

$$\varnothing\subseteq A$$

is always true, while

$$\varnothing\in A$$

is true only when the empty set itself appears as an element of $A$.

Sometimes both relationships are 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$.

Common number sets

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

Each number set is a subset of the next one:

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

Viewed as points on the number line, $\mathbb N$ and $\mathbb Z$ are discrete: their values are separated. For example, the integer after $2$ is $3$; there is no integer between them.

The real number line is continuous instead. Between any two different real numbers, there are always more real numbers, so the values do not come in separate steps.

Two ways to define a set

Definition by extension

A definition by extension, also called roster notation, lists the elements between braces:

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

Order does not matter, and writing an element more than once does not change the set:

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

A set only records whether an element belongs to it. It does not record the element's position or how many times it was written.

Definition by comprehension

A definition by comprehension, also called set-builder notation, describes the common property of the elements:

$$A=\{x\in U\mid P(x)\}.$$

Here:

• $x$ represents a possible element;
• $U$ is the universe, or the set from which $x$ is chosen;
• the vertical bar $\mid$ is read as “such that”;
• $P(x)$ is the property or condition that $x$ must satisfy.

Example: natural and odd numbers

The natural numbers can be defined as the nonnegative integers:

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

The condition $x\ge0$ means “$x$ is greater than or equal to zero.” In other words, start with the integers, then keep the nonnegative values.

The odd natural numbers can be written by extension,

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

or by comprehension,

$$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$.

Example: 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 condition $b\neq0$ means the denominator cannot be zero. An integer such as $5$ is rational because $5=\frac51$.

The same rational number can have many fraction forms:

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

We usually write a rational number in reduced form: the denominator is positive, and the numerator and denominator share no positive factor except $1$. In other words, their greatest common divisor (GCD) is $1$. For example,

$$\frac{2}{-3}=-\frac23,$$

and the form on the right follows the positive-denominator convention.

Set equality

The principle of extensionality says that two sets are equal when they contain exactly the same elements. Their order and the way they were defined do not matter.

The double-inclusion method proves that $A=B$ by showing both directions:

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

The first direction shows that $A$ has no element missing from $B$. The second shows that $B$ has no element missing from $A$.

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\}.$$

Both descriptions produce all odd integers. To prove $O=A$, we show both inclusions.

Take any $x\in O$. Then $x=2k+1$ for some integer $k$. Rewrite it as

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

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

$$O\subseteq A.$$

Now 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$.

Why not every condition defines a set

The unrestricted comprehension principle would allow any condition $P(x)$ to create a set $\{x\mid P(x)\}$. Russell's paradox shows why this does not work.

Non-example: Russell's paradox

Suppose we try to define

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

In words, $R$ would contain every set that is not an element of itself. Under this proposed rule, $\varnothing$ would qualify because $\varnothing\notin\varnothing$.

For comparison, some versions of set theory allow a self-containing set called a Quine atom, written $Q=\{Q\}$. Since $Q\in Q$, it would not qualify for $R$.

Now ask whether $R$ is an element of itself:

• If $R\in R$, then $R$ must satisfy its own condition, so $R\notin R$.
• If $R\notin R$, then $R$ satisfies the defining condition, so by definition $R\in R$.

Either answer gives the opposite answer. The symbol $\iff$ means “if and only if,” so we can write the contradiction as

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

This is Russell's paradox.

The safe version is restricted comprehension, called separation in formal set theory. Start with an already defined universe $U$, then choose the elements that satisfy $P(x)$:

$$\{x\in U\mid P(x)\}.$$

This creates a subset of $U$ instead of assuming that every condition creates a set. Here, $U$ is the universal set for the current problem—not one set containing every set that exists.

Set operations

Set operations build new sets from sets we already have. Unless stated otherwise, all complements are taken relative to a fixed universe $U$.

Let $A$ and $B$ be subsets of $U$. For a concrete example, take

$$A=\{1,3,5\} \qquad\text{and}\qquad B=\{1,2,3\}.$$

Union

The union contains everything that belongs to at least one of the two sets:

$$A\cup B=\{x\in U\mid x\in A\text{ or }x\in B\}.$$

The word “or” is inclusive here: an element may belong to $A$, to $B$, or to both. In the example,

$$A\cup B=\{1,2,3,5\}.$$

Intersection

The intersection contains only the elements shared by both sets:

$$A\cap B=\{x\in U\mid x\in A\text{ and }x\in B\}.$$

Therefore,

$$A\cap B=\{1,3\}.$$

Difference

The set difference $A\setminus B$ keeps the elements of $A$ that are not in $B$:

$$A\setminus B=\{x\in U\mid x\in A\text{ and }x\notin B\}.$$

Difference depends on the order:

$$A\setminus B=\{5\}, \qquad B\setminus A=\{2\}.$$

Complement

The complement of $A$ contains everything in $U$ that is outside $A$:

$$\overline A=U\setminus A =\{x\in U\mid x\notin A\}.$$

The universe matters. For $A=\{1,3,5\}$ and the convention $\mathbb N=\{0,1,2,\ldots\}$,

$$U=\mathbb N \quad\Longrightarrow\quad \overline A=\{0,2,4,6,7,8,\ldots\}.$$

If the universe is instead $\mathbb R$, then

$$\overline A =(-\infty,1)\cup(1,3)\cup(3,5)\cup(5,\infty).$$

The notation $\overline A$ is not universal. Depending on the course or context, the complement may be written $A^c$ or $U\setminus A$.

Symmetric difference

The symmetric difference contains the elements that belong to exactly one of $A$ and $B$:

$$A\mathbin\triangle B =\{x\in U\mid x\text{ belongs to exactly one of }A\text{ and }B\}.$$

For the example,

$$A\mathbin\triangle B=\{2,5\}.$$

Some sources write symmetric difference as $A\oplus B$. Neither symbol is universal, so its meaning should be stated when the context is unclear.

It has two useful equivalent forms:

$$A\mathbin\triangle B =(A\cup B)\setminus(A\cap B) =(A\setminus B)\cup(B\setminus A).$$

Set identities and Venn diagrams

A set identity is an equality that is true for every allowed choice of its sets. Venn diagrams divide the universe into all possible membership regions. If two expressions shade exactly the same regions, then they contain exactly the same elements, so the expressions are equal.

This is the same double-inclusion idea used earlier. If expressions $X$ and $Y$ shade the same regions, then every $x\in X$ also lies in the region for $Y$, giving $X\subseteq Y$. The same argument in reverse gives $Y\subseteq X$. Therefore, $X=Y$.

Example: a distributive law

Let $A$, $B$, and $C$ be subsets of $U$. Union distributes over intersection:

$$A\cup(B\cap C)=(A\cup B)\cap(A\cup C).$$

On the left, we take all of $A$ together with the part shared by $B$ and $C$. On the right, a point must belong to both $A\cup B$ and $A\cup C$. If it is not in $A$, it must be in both $B$ and $C$. Both sides therefore select the same regions.

A ∪ (B ∩ C)

1. Shade B2. Shade C3. Keep B ∩ C4. Add A5. Take the union

(A ∪ B) ∩ (A ∪ C)

1. Build A ∪ B2. Build A ∪ C3. Overlay both unions4. Keep their common part5. Same final region

Intersection also distributes over union:

$$A\cap(B\cup C)=(A\cap B)\cup(A\cap C).$$

Common set identities

The following identities hold for all sets $A$, $B$, and $C$ inside a fixed universe $U$.

Example: proving an identity algebraically

Set identities can be combined like algebraic rules. To prove

$$\overline{A\cup(B\cap C)} =(\overline C\cup\overline B)\cap\overline A,$$

start with the left-hand side:

$$\begin{aligned} \overline{A\cup(B\cap C)} &=\overline A\cap\overline{(B\cap C)} &&\text{De Morgan's law}\\ &=\overline A\cap(\overline B\cup\overline C) &&\text{De Morgan's law}\\ &=(\overline C\cup\overline B)\cap\overline A &&\text{commutativity.} \end{aligned}$$

A filled square $\blacksquare$, or QED (short for the Latin phrase meaning “which was to be demonstrated”), marks that a proof is complete.

Cartesian products

The Cartesian product is an external operation: its elements are ordered pairs rather than elements of either original set. It changes the universe of discourse.

$$A\times B=\{(a,b)\mid a\in A\text{ and }b\in B\}.$$

Order matters inside each pair, so $A\times B$ is generally different from $B\times A$.

For

$$A=\{1,2,3\} \qquad\text{and}\qquad B=\{6,7\},$$

we pair every element of $A$ with every element of $B$:

$$A\times B =\{(1,6),(1,7),(2,6),(2,7),(3,6),(3,7)\}.$$

There are $3\cdot2=6$ pairs. The notation $|A|$ means the cardinality of $A$, or the number of elements it contains. If $A$ and $B$ are finite, then

$$|A\times B|=|A|\,|B|.$$

The Cartesian plane is the product of the real numbers with themselves:

$$\mathbb R^2=\mathbb R\times\mathbb R =\{(x,y)\mid x,y\in\mathbb R\}.$$

Power sets

The power set of $A$, written $\mathcal P(A)$, is the set of every subset of $A$:

$$\mathcal P(A)=\{X\mid X\subseteq A\}.$$

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

$$\mathcal P(A)= \left\{ \varnothing, \{1\},\{2\},\{3\}, \{1,2\},\{1,3\},\{2,3\}, \{1,2,3\} \right\}.$$

Each element of $A$ has two choices when forming a subset: include it or leave it out. A set with $n$ elements therefore has $2^n$ subsets:

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

The empty set has one subset—itself—so

$$\mathcal P(\varnothing)=\{\varnothing\}.$$

The power set of the empty set is not empty; it contains the empty set as its one element.