0.3  Sets

Every object in linear algebra is a set with some extra structure. A vector space is a set on which we can add and scale, a subspace is a subset of it, and a linear map sends elements of one set to elements of another. Before the structure arrives, we need the plain language of sets: how to describe them, when two of them are equal, and how to combine them. The most important move in this section is proving that two sets are equal by proving two inclusions, a move we will use for subspaces, spans, kernels and images throughout the book.

0.3.1. Sets, elements and set-builder notation

A set is a collection of objects, called its elements. We write $x\in A$ for “$x$ is an element of $A$” (also “$x$ belongs to $A$”, “$x$ lies in $A$”), and $x\notin A$ for its negation. A set is determined by its elements and nothing else: it has no order and no repetition. So $\{1,2\}$, $\{2,1\}$ and $\{1,1,2\}$ all describe the same set, whose elements are $1$ and $2$. We make this precise below.

Small sets can be listed between braces. Infinite sets we meet constantly have fixed names.

Books disagree about whether $0\in \mathbb{N}$. With our convention, the Well-Ordering Principle (Theorem 0.2.11) applies to collections that contain $0$, and “$n\in \mathbb{N}$” means $n\ge 0$. When we need positive integers only, we say “$n\ge 1$”. For real numbers $a\le b$ we also use intervals: $[a,b]$ is the set of real $x$ with $a\le x\le b$, $(a,b)$ the set with $a<x<b$, and $[a,b)$, $(a,b]$ are defined in the same way.

Listing elements fails for most sets we care about, such as “the real numbers whose square is less than $4$”. Instead we describe a set by a property, and select from a set we already have.

In words: an object $y$ belongs to $\{x\in S:P(x)\}$ if and only if $y\in S$ and $P(y)$ is true. Both parts matter. The ambient set $S$ says where we are looking, and the predicate says what we keep. The colon is read “such that”; some books use a vertical bar instead. When it is plain which sets the elements come from, as in the unions and intersections below, we sometimes leave the ambient set out and write $\{x:P(x)\}$.

A second form describes the elements by a formula: $\{2k:k\in \mathbb{Z}\}$ is the set of all numbers of the form $2k$ with $k$ an integer. An object $y$ belongs to it exactly when $y=2k$ for some $k\in \mathbb{Z}$. This form will describe sets such as “all combinations of given vectors” in Chapter 1.

What if no element of $S$ satisfies the predicate? We still want a set, and it has no elements.

For example, $\{x\in \mathbb{R}:x^2=-1\}=\varnothing$, since $x^2\ge 0$ for every real $x$ (Example (Quantified statements)). Also $\{n\in \mathbb{Z}:0<n<1\}=\varnothing$. We will see shortly that there is only one empty set, so these two descriptions give the same set.

Statements about all elements of $\varnothing$ are vacuously true: “every element of $\varnothing$ is a prime number” has no element that could fail, just as in the degenerate case discussed after Example (Quantified statements).

0.3.2. Subsets

Most sets in this book live inside a bigger set: the even integers inside $\mathbb{Z}$, a line inside the plane, and later a subspace inside a vector space. The first thing to check about a candidate subspace will be that it sits inside the space at all. We need a word for “sits inside”.

$A$ is a subset of $B$ when everything in $A$ is also in $B$.

In words: $A\subseteq B$ says that every element of $A$ is an element of $B$. It says nothing about elements of $B$; $B$ may contain many more. The definition is an implication inside a “for every”, so the proof template of the previous section applies: to show $A\subseteq B$, let $x\in A$ and show $x\in B$.

By Definition 0.1.4 and Theorem 0.1.2, the negation reads $$A⊈B⟺\mathrm{\exists }x:x\in A\text{ and }x\notin B.$$ So to show $A$ is not a subset of $B$, exhibit one element of $A$ outside $B$.

0.3.3. Equality of sets and double inclusion

We said a set is determined by its elements. Here is the precise version.

So $\{1,2\}=\{2,1\}=\{1,1,2\}$: each object belongs to one of these sets exactly when it is $1$ or $2$. Order and repetition in a list are features of how we write a set, not of the set.

Proving a biconditional for every $x$ at once is awkward. It is much easier to prove two implications separately, and that is exactly what the next result allows.

This is the move “prove set equality by double inclusion”. The proof is written in two labeled halves, $(\subseteq )$ and $(\supseteq )$, each starting “Let $x\in \dots$”. Here is a first consequence.

Solving an equation “at school” usually produces only the $(\subseteq )$ half: “if $x$ is a solution, then $x$ is $1$ or $2$”. The $(\supseteq )$ half, checking that the candidates really are solutions, is the part that gets forgotten. It matters whenever a step in the solving is not reversible, such as squaring both sides.

0.3.4. Union, intersection and difference

Given two sets, there are three basic ways to form a new one: keep what is in either, keep what is in both, or keep what is in the first but not the second. Each is a set-builder description whose predicate uses a connective from the section on logic.

In words: the union keeps an element that lies in at least one of the sets (the “or” is inclusive, as always); the intersection keeps an element that lies in both; the difference $A\setminus B$ keeps the elements of $A$ that are not in $B$. The complement depends on the choice of $U$: the complement of $\mathbb{N}$ is the set of negative integers inside $\mathbb{Z}$, but a much bigger set inside $\mathbb{R}$.

Unions, intersections and differences interact through laws that mirror those for “or”, “and” and “not”. The first pair is De Morgan’s laws, the set version of Theorem 0.1.2.

The second pair of laws says each of $\cap$ and $\cup$ distributes over the other, like multiplication over addition, except that here both directions hold.

0.3.5. Indexed families of sets

Two sets are not always enough. In Chapter 1 we will need “the intersection of all subspaces that contain a given set”, and there are usually infinitely many of them. So we need unions and intersections of any number of sets at once.

An indexed family is a list of sets with one set for each label; its union keeps what lies in some member, its intersection what lies in every member.

In words: $x$ lies in the union when it lies in at least one $A_i$, and in the intersection when it lies in every $A_i$. When $I=\{1,2\}$, these are $A_1\cup A_2$ and $A_1\cap A_2$. When $I=\{1,2,3,\dots \}$, we also write $\bigcup _{n=1}^{\mathrm{\infty }}{A}_n$ and $\bigcap _{n=1}^{\mathrm{\infty }}{A}_n$.

Why $I$ must be non-empty for the intersection. If $I=\varnothing$, the condition “$\mathrm{\forall }i\in I:x\in A_i$” is vacuously true for every object $x$, so the “intersection” would contain everything, which is not a set we want. (When all sets live inside a fixed $U$, one sometimes defines the empty intersection to be $U$.) The empty union causes no such trouble: “$\mathrm{\exists }i\in \varnothing$” is always false, so $\bigcup _{i\in \varnothing }{A}_i=\varnothing$.

De Morgan’s laws hold for indexed families with the same proofs: for a non-empty index set $I$, $A\setminus \bigcup _i{B}_i=\bigcap _i(A\setminus B_i)$ and $A\setminus \bigcap _i{B}_i=\bigcup _i(A\setminus B_i)$. The “or” of the finite version becomes “there exists”, and the “and” becomes “for every”, exactly as in Definition 0.1.4.

0.3.6. Cartesian products and $n$-tuples

A set forgets order: $\{1,2\}=\{2,1\}$. But a point in the plane is not like that. The point $(1,2)$ is different from $(2,1)$. We need objects that remember order.

An ordered pair $(a,b)$ has a first entry $a$ and a second entry $b$, and two ordered pairs are equal exactly when their entries agree in order: $$(a,b)=(a^{\prime },b^{\prime })⟺a=a^{\prime }\text{ and }b=b^{\prime }.$$

For example, $\{1,2\}\times \{x,y\}=\{(1,x),(1,y),(2,x),(2,y)\}$. The order of the factors matters: $(1,x)\in \{1,2\}\times \{x,y\}$, but $(1,x)\notin \{x,y\}\times \{1,2\}$, whose pairs have a letter first. A degenerate case: $A\times \varnothing =\varnothing$ for every set $A$, since no pair can have a second entry from $\varnothing$.

In Chapter 1, ${\mathbb{R}}^n$ and more generally $F^n$ become the first examples of vector spaces, with $n$-tuples added and scaled entry by entry.

0.3.7. Power sets

Sets can themselves be elements of sets, as the warning about $\{\varnothing \}$ showed. One such set collects every subset of a given set.

So $X\in \mathcal{P}\left(S\right)$ means exactly $X\subseteq S$. For example, $$\mathcal{P}(\{1,2\})=\{\varnothing ,\{1\},\{2\},\{1,2\}\},$$ which has $4$ elements. The degenerate case is instructive: $\mathcal{P}\left(\varnothing \right)=\{\varnothing \}$ has one element, because the empty set has exactly one subset, itself. For a set with $n$ elements the power set has $2^n$ elements; the last exercise proves this by induction.

0.3.8. Exercises

A. Check your understanding

B. Practice

C. Going deeper