CommeUnJeu · L1 MPSI

Sets

⌚ ~323 min ▢ 40 blocks ✓ 128 exercises ➣ Prerequisites : Logic

A set is, intuitively, a bag of marbles --- a collection of objects whose identity is fixed by the list (or rule) of its elements. We have all manipulated sets before, often without naming them: $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$ are sets; an interval $[0, 1]$ is a set; the solutions of an equation form a set; a graph is a set of points. This chapter sharpens the basic vocabulary.
The plan has two parts. The first sets up the language: how to specify a set (by listing its elements, or by a defining property), what it means for one set to be contained in another, and the all-important power set $\mathcal{P}(E)$ of all parts of $E$. The second introduces the operations: union, intersection, difference, complement, Cartesian product. The two De Morgan laws and the distributivity of $\cap$ and $\cup$ are stated and proved here once and for all --- they will be invoked everywhere afterward.
A constant subtext throughout: set theory and logic mirror each other. Each set construction reflects a logical connective ($\cap \leftrightarrow \wedge$, $\cup \leftrightarrow \vee$, $\complement \leftrightarrow \neg$, $\subset \leftrightarrow \Rightarrow$, $= \leftrightarrow \Leftrightarrow$). Every set identity is, ultimately, an identity between propositions on membership. Once that bridge is in place, set proofs become rote applications of the logic chapter.

I Membership and Inclusion

We start by setting up the basic vocabulary: what a set is, how its elements are named, and how two sets relate by inclusion. Three operations on the language itself --- listing the elements (extension), specifying them by a property (comprehension), and considering all possible subsets ($\mathcal{P}(E)$) --- close the section.

I.1 Sets$\virgule$ elements$\virgule$ empty set

The notion of set is taken as primitive: we will not define it from anything more elementary. The intuitive picture --- a sac of marbles, the marbles being the elements --- suffices. What we do define carefully is the relation between an element and the set that contains it.

Definition — Set$\virgule$ element$\virgule$ membership

A set is a collection of objects called its elements. For an element $x$ and a set $E$:

$x \in E$ reads « $x$ belongs to $E$ » or « $x$ is an element of $E$ ».
$x \notin E$ is the negation: « $x$ does not belong to $E$ ».

Two sets $E$ and $F$ are equal, written $E = F$, when they have exactly the same elements: $$ E = F \ \iff \ \forall x, \ (x \in E \iff x \in F). $$

Example

For the set $E = \{1, 2, 3, 4, 5, 6\}$ of dice outcomes: $$ 2 \in E, \qquad 7 \notin E, \qquad \pi \notin E. $$ The order of listed elements does not matter, and repetitions are ignored: $$ \{1, 2, 3\} = \{3, 1, 2\} = \{1, 1, 2, 3\}. $$

Example

A set $E$ can be visualized as a region of the plane, each element drawn as a point inside it. An element $x \in E$ sits inside the region; an element $y \notin E$ sits outside.

Definition — Empty set

There exists a unique set with no element, called the empty set and denoted $\emptyset$ (or $\{\}$). Formally: $$ \forall x, \ x \notin \emptyset. $$

Example

The set of real numbers $x$ such that $x^2 = -1$ is empty: a square is non-negative, so no such $x$ exists. Concretely, $\{ x \in \mathbb{R} \ \mid \ x^2 = -1 \} = \emptyset$. By contrast, $\{ x \in \mathbb{C} \ \mid \ x^2 = -1 \} = \{i, -i\}$ is non-empty.

Skills to practice

Deciding whether $x \in E$
Identifying when a defining set is empty
Recognizing equal sets

I.2 Definition by extension and by comprehension

A set can be specified in two complementary ways. Extension is the explicit list of elements: $\{1, 2, 3\}$. It works only for finite sets. Comprehension specifies the elements by a property they satisfy: $\{x \in \mathbb{R} \ \mid \ x^2 \le 1\}$. This second style is the workhorse of mathematics --- it lets us speak of infinite sets, and it lets us speak of « the set of all $x$ such that $\dots$ » without writing the elements down.

Definition — Definition by extension and by comprehension

Let $E$ be a set and $\mathcal{P}(x)$ a predicate of a variable $x$.

Extension. Listing the elements between braces: $\{a_1, a_2, \dots, a_n\}$ denotes the set whose elements are exactly $a_1, \dots, a_n$. A set of the form $\{a\}$ is a singleton; a set $\{a, b\}$ with $a \ne b$ is a pair.
Comprehension. The notation $$ \{ x \in E \ \mid \ \mathcal{P}(x) \} $$ denotes the set of elements of $E$ that satisfy $\mathcal{P}$. For a family $(x_i)_{i \in I}$ indexed by a set $I$, we also write $\{ x_i \ \mid \ i \in I \}$ for the set of values taken.

The same set may admit both descriptions: $\{0, 1\} = \{ n \in \mathbb{N} \ \mid \ n^2 = n \}$.

Example

By extension: $\{ 1, 4, 9, 16, 25 \}$.
By comprehension: $\{ n^2 \ \mid \ n \in \{1, 2, 3, 4, 5\} \}$.
By comprehension: $\{ n \in \mathbb{N}^* \ \mid \ \sqrt{n} \in \mathbb{N} \text{ and } n \le 25 \}$.

The three notations describe the same set. The choice depends on what we want to emphasize: the explicit values, the construction rule, or the defining property.

Skills to practice

Converting from comprehension to extension
Converting from extension to comprehension
Translating set-builder notation in words

I.3 Cardinal of a finite set

Counting the elements of a finite set is the most elementary operation we can perform on it. The number of elements is called the cardinal; it is the bridge between the language of sets and the arithmetic of natural numbers.

Definition — Cardinal of a finite set

A set is finite if it has a finite number of elements. The number of elements is called the cardinal of the set, denoted $|E|$ or $\mathrm{card}(E)$. By convention, $|\emptyset| = 0$.

Example

$|\{a, b, c\}| = 3$.
$|\{0, 1, 2, \dots, 10\}| = 11$.
$|\{ n \in \mathbb{N} \ \mid \ n^2 \le 100 \}| = 11$ (the elements are $0, 1, \dots, 10$).
$\mathbb{N}, \mathbb{Z}, \mathbb{R}$ are not finite, so $|E|$ is not defined here for them (« infinite » will be made precise in another chapter).

Skills to practice

Counting elements directly
Counting elements defined by comprehension
Counting a list with repetitions

I.4 Inclusion and subsets

Two sets relate to each other in two essentially different ways. They can be equal (have the same elements), or one can be contained in the other (every element of the smaller is an element of the larger). The latter relation is inclusion. We will rely on it constantly to prove set equalities, via the slogan « show two inclusions ».

Definition — Inclusion$\virgule$ subset

Let $E$ and $F$ be two sets. We say that $E$ is included in $F$, or that $E$ is a subset (or part) of $F$, and we write $E \subset F$, if every element of $E$ is an element of $F$: $$ E \subset F \ \iff \ \forall x, \ (x \in E \implies x \in F). $$ The negation is denoted $E \not\subset F$ and means $\exists x \in E, \ x \notin F$.

Example

The classical chain of number sets: $$ \mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}. $$

Each integer is a rational ($n = n/1$); each rational is a real; each real is a complex (with zero imaginary part). The inclusions are strict: $-1 \in \mathbb{Z}$ but $-1 \notin \mathbb{N}$; $\tfrac{1}{2} \in \mathbb{Q}$ but $\tfrac{1}{2} \notin \mathbb{Z}$; $\sqrt{2} \in \mathbb{R}$ but $\sqrt{2} \notin \mathbb{Q}$; $i \in \mathbb{C}$ but $i \notin \mathbb{R}$.

Example

$A \subset E$ means every element of $A$ also belongs to $E$. Visually, the region for $A$ sits inside the region for $E$. The point $x$ is in $A$ (hence in $E$); the point $y$ is in $E$ but not in $A$.

Membership $\ne$ Inclusion

The two relations $\in$ and $\subset$ should not be confused. $\in$ links an element to a set; $\subset$ links a set to a set. The picture: $-1 \in \mathbb{Z}$ but $-1 \not\subset \mathbb{Z}$ ($-1$ is a marble in the bag, not a sub-bag); $\mathbb{N} \subset \mathbb{Z}$ but $\mathbb{N} \notin \mathbb{Z}$ ($\mathbb{N}$ is a sub-bag of $\mathbb{Z}$, not a marble in $\mathbb{Z}$).

Proposition — Equality by double inclusion

For any two sets $E$ and $F$: $$ E = F \ \iff \ \big( E \subset F \big) \wedge \big( F \subset E \big). $$ This characterization is the universal technique to prove a set equality: prove $E \subset F$, then prove $F \subset E$.

Proof

By definition, $E = F$ means $\forall x, \ (x \in E \iff x \in F)$. The biconditional $A \iff B$ is by definition $(A \implies B) \wedge (B \implies A)$. Substituting: $$ \begin{aligned} E = F &\iff \forall x, \ \big( (x \in E \implies x \in F) \wedge (x \in F \implies x \in E) \big) && \text{(unfolding $\iff$)} \\ &\iff \big( \forall x, \ x \in E \implies x \in F \big) \wedge \big( \forall x, \ x \in F \implies x \in E \big) && \text{($\forall$ distributes over $\wedge$)} \\ &\iff (E \subset F) \wedge (F \subset E) && \text{(definition of $\subset$)}. \end{aligned} $$

Example

Show that $\{ x \in \mathbb{R} \ \mid \ x^2 = x \} = \{0, 1\}$.

Answer

We prove the two inclusions.

($\subset$) Let $x \in \{ x \in \mathbb{R} \ \mid \ x^2 = x \}$. Then $x^2 = x$, so $x(x - 1) = 0$, hence $x = 0$ or $x = 1$. Thus $x \in \{0, 1\}$.
($\supset$) Let $x \in \{0, 1\}$. If $x = 0$, then $x^2 = 0 = x$, OK. If $x = 1$, then $x^2 = 1 = x$, OK. In either case, $x$ satisfies $x^2 = x$.

By double inclusion, the two sets are equal.

Proposition — Empty set is included in every set

For every set $E$: $$ \emptyset \subset E. $$

Proof

We must show $\forall x, \ x \in \emptyset \implies x \in E$. Let $x$ be arbitrary. The hypothesis $x \in \emptyset$ is false (no element belongs to $\emptyset$), so the implication is automatically true (vacuous truth).

Skills to practice

Deciding whether $A \subset B$
Proving an inclusion by direct argument
Proving equality by double inclusion

I.5 Power set

Given a set $E$, we can form a new set whose elements are the parts (subsets) of $E$. This is the power set $\mathcal{P}(E)$. The construction is one level of abstraction up: the elements of $\mathcal{P}(E)$ are themselves sets. This level distinction --- a part of $E$ is an element of $\mathcal{P}(E)$ --- is the trickiest mental operation in this chapter. Visualize $E$ as a bag of marbles; then $\mathcal{P}(E)$ is a bag of bags, each bag a sub-collection of marbles from $E$.

Definition — Power set

For any set $E$, the power set of $E$ is the set of all subsets of $E$: $$ \mathcal{P}(E) = \{ A \ \mid \ A \subset E \}. $$ For any set $A$: $$ A \in \mathcal{P}(E) \ \iff \ A \subset E. $$

Example

For $E = \{0, 1, 2\}$: $$ \mathcal{P}(E) = \big\{ \, \emptyset, \ \{0\}, \ \{1\}, \ \{2\}, \ \{0, 1\}, \ \{0, 2\}, \ \{1, 2\}, \ \{0, 1, 2\} \, \big\}. $$ $\mathcal{P}(E)$ has $8 = 2^3$ elements: one of cardinal $0$ ($\emptyset$), three of cardinal $1$, three of cardinal $2$, one of cardinal $3$ ($E$ itself). In general, for a finite set $E$ of cardinal $n$, $\mathcal{P}(E)$ has cardinal $2^n$ --- a result we will reprove rigorously in a later chapter on counting.

Example

For every set $E$, both $\emptyset$ and $E$ itself are elements of $\mathcal{P}(E)$: $$ \emptyset \in \mathcal{P}(E) \quad \text{and} \quad E \in \mathcal{P}(E). $$ The first holds because $\emptyset \subset E$ (the previous Proposition). The second holds because $E \subset E$ (every element of $E$ is an element of $E$ --- a tautology).

Example

For $E = \{a, b, c\}$, the power set $\mathcal{P}(E)$ has $2^3 = 8$ elements. They can be arranged by inclusion (an arrow $X \to Y$ means $X \subset Y$ with no intermediate set):

Skills to practice

Listing all elements of $\mathcal{P}(E)$ for small $E$
Computing $|\mathcal{P}(E)|$
Deciding whether $X \in \mathcal{P}(E)$

I.6 Integer intervals

The integers $\{0, 1, 2, \dots, n\}$ form the canonical index set of mathematics --- it indexes sums, products, recurrences, families, $n$-tuples. We give it a dedicated notation and compute its cardinal once and for all. The notation should not be confused with the real interval of the same endpoints: $[0, 3]$ contains $\sqrt{2}$, $\llbracket 0, 3 \rrbracket$ does not.

Definition — Integer interval

For two integers $a, b \in \mathbb{Z}$, the integer interval $\llbracket a, b \rrbracket$ is the set of integers between $a$ and $b$ in the wide sense: $$ \llbracket a, b \rrbracket = \{ n \in \mathbb{Z} \ \mid \ a \leq n \leq b \}. $$ By convention, $\llbracket a, b \rrbracket = \emptyset$ when $a > b$. The half-open and open variants are defined analogously: $\llbracket a, b \llbracket = \{n \in \mathbb{Z} \mid a \leq n < b\}$.

Example

Three concrete cases: $$ \llbracket 0, 3 \rrbracket = \{0, 1, 2, 3\}, \qquad \llbracket -2, 1 \rrbracket = \{-2, -1, 0, 1\}, \qquad \llbracket 5, 5 \rrbracket = \{5\}. $$ And one edge case: $\llbracket 7, 4 \rrbracket = \emptyset$ (since $7 > 4$).

Proposition — Cardinal of an integer interval

For all $a, b \in \mathbb{Z}$ with $a \leq b$: $$ |\llbracket a, b \rrbracket| = b - a + 1. $$ In particular, $|\llbracket 1, n \rrbracket| = n$ and $|\llbracket 0, n \rrbracket| = n + 1$.

Proof

The map $\varphi : k \mapsto a + k$ sends $\llbracket 0, b - a \rrbracket$ to $\llbracket a, b \rrbracket$ bijectively (its inverse is $n \mapsto n - a$), so the two sets have the same cardinal. It remains to count $\llbracket 0, b - a \rrbracket = \{0, 1, \dots, b - a\}$, which has $b - a + 1$ elements.
The « $+ 1$ » is the classical fencepost rule: between two posts numbered $a$ and $b$ there are $b - a$ gaps but $b - a + 1$ posts.

Example

Counting tasks become one-liners:

The number of integers from $17$ to $42$ inclusive is $42 - 17 + 1 = 26$.
The number of integers strictly between $a$ and $b$, i.e.\ in $\llbracket a + 1, b - 1 \rrbracket$, is $b - a - 1$ (when $b > a + 1$).
The number of even integers in $\llbracket 1, 2n \rrbracket$ is $n$, since they form the bijective image $\{2, 4, \dots, 2n\}$ of $\llbracket 1, n \rrbracket$ under $k \mapsto 2k$.

Skills to practice

Computing the cardinal of an integer interval
Counting integers under a constraint
Comparing integer and real intervals

II Operations on Sets

We now turn to the constructions that build new sets from old ones: union, intersection, difference, complement, Cartesian product. Each construction mirrors a logical connective, and the algebraic identities one expects (commutativity, associativity, distributivity, De Morgan) all hold. We state and prove the central ones, then close with three more advanced notions: disjoint cover (partition), Cartesian product, and indicator function.

Before listing the operations one by one, here is the at-a-glance summary --- a single picture per relation, all in the same ambient set $E$ (drawn as the rectangle). \renewcommand{\arraystretch}{1.6}

Notation	Meaning	Venn diagram
$\overline{A}$	Complement of $A$ in $E$
$A \subset B$	$A$ is included in $B$
$A \cup B$	Union: in $A$ or in $B$
$A \cap B$	Intersection: in $A$ and in $B$
$A \setminus B$	Difference: in $A$ but not in $B$
$A \cap B = \emptyset$	$A$ and $B$ are disjoint

\renewcommand{\arraystretch}{1} The next subsections give the formal definition of each construction, the membership characterization (which is just the corresponding logical connective on $\in$), and the algebraic laws.

II.1 Union and intersection

The two binary operations $\cup$ and $\cap$ are mirror images of the logical connectives $\vee$ and $\wedge$. They generalize naturally to arbitrary indexed families, leading to $\bigcup$ and $\bigcap$. The associativity, commutativity and distributivity laws follow from the corresponding laws of logic.

Definition — Union and intersection (binary)

Let $A$ and $B$ be two sets.

The union of $A$ and $B$ is the set $$ A \cup B = \{ x \ \mid \ x \in A \ \vee \ x \in B \}. $$
The intersection of $A$ and $B$ is the set $$ A \cap B = \{ x \ \mid \ x \in A \ \wedge \ x \in B \}. $$

The mnemonic: $\cup$ corresponds to « ou » / $\vee$ / $\exists$; $\cap$ corresponds to « et » / $\wedge$ / $\forall$.

Example

$\{1, 2, 3\} \cup \{2, 4\} = \{1, 2, 3, 4\}$ (union).
$\{1, 2, 3\} \cap \{2, 4\} = \{2\}$ (intersection).
$[0, 2] \cup [1, 3] = [0, 3]$ and $[0, 2] \cap [1, 3] = [1, 2]$.
$\mathbb{N} \cup \mathbb{Z} = \mathbb{Z}$ and $\mathbb{N} \cap \mathbb{Z} = \mathbb{N}$ (since $\mathbb{N} \subset \mathbb{Z}$).

Example

The union $A \cup B$ is the entire shaded region; the intersection $A \cap B$ is the central lens. The mnemonic: $\cup$ corresponds to « ou » / $\vee$; $\cap$ corresponds to « et » / $\wedge$.

Definition — Union and intersection of an indexed family

Let $I$ be a non-empty set and, for each $i \in I$, let $A_i$ be a set.

The union of the family is $$ \bigcup_{i \in I} A_i = \{ x \ \mid \ \exists i \in I, \ x \in A_i \}. $$
The intersection of the family is $$ \bigcap_{i \in I} A_i = \{ x \ \mid \ \forall i \in I, \ x \in A_i \}. $$

Example

For each $n \in \mathbb{N}^*$, set $I_n = [-1/n, 1/n] \subset \mathbb{R}$. Then: $$ \bigcup_{n \in \mathbb{N}^*} I_n = [-1, 1] \quad \text{and} \quad \bigcap_{n \in \mathbb{N}^*} I_n = \{0\}. $$ The intersection collapses to a single point because, the larger $n$, the narrower $I_n$ around $0$. Visually, the intervals nest down to $\{0\}$.

Proposition — Distributivity of $\cap$ and $\cup$

For any sets $B$ and any indexed family $(A_i)_{i \in I}$ (with $I$ non-empty): $$ B \cap \bigcup_{i \in I} A_i = \bigcup_{i \in I} (B \cap A_i) \qquad B \cup \bigcap_{i \in I} A_i = \bigcap_{i \in I} (B \cup A_i). $$

Proof

We prove the first identity by direct equivalence on membership; the second is dual. For any $x$: $$ \begin{aligned} x \in B \cap \bigcup_{i \in I} A_i &\iff x \in B \wedge x \in \bigcup_{i \in I} A_i && \text{(definition of $\cap$)} \\ &\iff x \in B \wedge \big( \exists i \in I, \ x \in A_i \big) && \text{(definition of $\bigcup$)} \\ &\iff \exists i \in I, \ \big( x \in B \wedge x \in A_i \big) && \text{($B$ does not depend on $i$, $\wedge$ commutes with $\exists$)} \\ &\iff \exists i \in I, \ x \in B \cap A_i && \text{(definition of $\cap$)} \\ &\iff x \in \bigcup_{i \in I} (B \cap A_i) && \text{(definition of $\bigcup$)}. \end{aligned} $$ The two sets have the same membership characterization, hence are equal.

Example

Distributivity at a glance: the shaded region of $A \cap (B \cup C)$ is exactly the union of $A \cap B$ and $A \cap C$. Reading the picture is a pictorial proof of the identity.

Proposition — Inclusion characterized by union or intersection

For any sets $A$ and $B$, the following are equivalent: $$ A \subset B \quad \iff \quad A \cup B = B \quad \iff \quad A \cap B = A. $$

Proof

We prove a cycle of three implications.

($A \subset B \implies A \cup B = B$). Suppose $A \subset B$. Then for every $x$: $x \in A \cup B \iff x \in A \vee x \in B \iff x \in B$ (because $x \in A$ already implies $x \in B$). Hence $A \cup B = B$.
($A \cup B = B \implies A \cap B = A$). Suppose $A \cup B = B$. Then $A \subset A \cup B = B$ (every element of $A$ is in $A \cup B$). So for every $x$: $x \in A \cap B \iff x \in A \wedge x \in B \iff x \in A$ (because $x \in A$ implies $x \in B$). Hence $A \cap B = A$.
($A \cap B = A \implies A \subset B$). Suppose $A \cap B = A$. Then $A = A \cap B \subset B$.

Skills to practice

Computing $A \cup B$ and $A \cap B$ for small sets
Computing unions and intersections of intervals
Computing indexed unions and intersections
Applying the basic laws of $\cup$ and $\cap$

II.2 Difference and complement

The difference $A \setminus B$ collects what is in $A$ but not in $B$. When $A$ is fixed as an ambient set $E$, the difference $E \setminus A$ is called the complement of $A$ and denoted $\complement A$ or $\overline{A}$. The complement, applied to the operations $\cup$ and $\cap$, satisfies the De Morgan laws --- the set-theoretic image of the De Morgan laws of logic.

Definition — Difference$\virgule$ complement

Let $A$ and $B$ be two sets.

The difference $A$ minus $B$ is $$ A \setminus B = \{ x \ \mid \ x \in A \ \wedge \ x \notin B \}. $$
Let $E$ be a set and $A \subset E$. The complement of $A$ in $E$ is the set $E \setminus A$, denoted $\overline{A}$ or $\complement_E A$ or $A^c$ when $E$ is clear from context.

Example

$\{1, 2, 3, 4\} \setminus \{2, 4\} = \{1, 3\}$.
$\mathbb{R} \setminus \mathbb{Q}$ is the set of irrational numbers; $\sqrt{2}, \pi, e \in \mathbb{R} \setminus \mathbb{Q}$.
In $E = \mathbb{R}$: $\overline{[0, 1]} = \, ]-\infty, 0[ \, \cup \, ]1, +\infty[$.
For any $E$ and $A \subset E$: $A \cap \overline{A} = \emptyset$ and $A \cup \overline{A} = E$.

Example

On the left, $A \setminus B$ is the part of $A$ that does not belong to $B$. On the right, $\complement_E A$ (also written $E \setminus A$ or $\bar A$) is the part of $E$ outside $A$.

Proposition — Double complement

Let $E$ be a set and $A \subset E$. Then $$ \overline{\overline{A}} = A. $$

Proof

By definition, $x \in \overline{A}$ means $x \in E \wedge x \notin A$. Hence: $$ x \in \overline{\overline{A}} \iff x \in E \wedge \neg(x \in \overline{A}) \iff x \in E \wedge \neg(x \in E \wedge x \notin A). $$ Using De Morgan and double negation: $\neg(x \in E \wedge x \notin A) \iff x \notin E \vee x \in A$. Combined with $x \in E$, the disjunction reduces to $x \in A$. Hence $x \in \overline{\overline{A}} \iff x \in A$, so $\overline{\overline{A}} = A$.

Skills to practice

Computing $A \setminus B$
Computing the complement $\complement_E A$
Using the double complement
Using the identity $A \setminus B \equal A \cap \overline{B}$

II.3 De Morgan's laws for sets

The De Morgan laws of logic translate verbatim into set theory: the complement turns union into intersection, and intersection into union. We state them in the general indexed form so they can be applied directly to families.

Proposition — De Morgan for sets

Let $E$ be a set and $(A_i)_{i \in I}$ a family of subsets of $E$ (with $I$ non-empty). Then: $$ \overline{\bigcup_{i \in I} A_i} = \bigcap_{i \in I} \overline{A_i} \qquad \overline{\bigcap_{i \in I} A_i} = \bigcup_{i \in I} \overline{A_i}. $$ The complement of a union is the intersection of the complements, and conversely.

Proof

We prove the first identity; the second is dual (apply the first to the complements $\overline{A_i}$ and use double complement). For any $x \in E$: $$ \begin{aligned} x \in \overline{\bigcup_{i \in I} A_i} &\iff x \notin \bigcup_{i \in I} A_i && \text{(definition of $\overline{\phantom{X}}$)} \\ &\iff \neg \big( \exists i \in I, \ x \in A_i \big) && \text{(definition of $\bigcup$)} \\ &\iff \forall i \in I, \ x \notin A_i && \text{(negation of $\exists$)} \\ &\iff \forall i \in I, \ x \in \overline{A_i} && \text{(definition of $\overline{\phantom{X}}$)} \\ &\iff x \in \bigcap_{i \in I} \overline{A_i} && \text{(definition of $\bigcap$)}. \end{aligned} $$

Example

In $E = \mathbb{R}$, with $A = \, ]-\infty, 0]$ and $B = [1, +\infty[$: $$ A \cup B = \, ]-\infty, 0] \cup [1, +\infty[, \qquad \overline{A \cup B} = \, ]0, 1[. $$ On the other hand, $\overline{A} = \, ]0, +\infty[$ and $\overline{B} = \, ]-\infty, 1[$, so $\overline{A} \cap \overline{B} = \, ]0, 1[$. The two computations agree, confirming De Morgan.

Example

De Morgan in pictures: the two shaded regions coincide. The complement of a union is the intersection of the complements.

Skills to practice

Applying De Morgan to specific sets
Simplifying expressions using De Morgan
Proving identities mixing distributivity and De Morgan

II.4 Disjoint sets$\virgule$ disjoint cover$\virgule$ partition

Two sets are disjoint when they share no element. A family of pairwise disjoint sets that together fill an ambient set $E$ is called a disjoint cover; if no piece is empty, it is a partition. Partitions are the set-theoretic shape of « splitting a problem into cases »: dividing $E$ into non-overlapping pieces, dealing with each, and recombining.

Definition — Disjoint sets$\virgule$ disjoint cover$\virgule$ partition

Let $E$ be a set.

Two subsets $A, B \subset E$ are disjoint when $A \cap B = \emptyset$. A family $(A_i)_{i \in I}$ of subsets is pairwise disjoint when $\forall i, j \in I, \ i \ne j \implies A_i \cap A_j = \emptyset$. The union of a pairwise disjoint family is sometimes denoted $\bigsqcup_{i \in I} A_i$ to emphasize disjointness.
A family $(A_i)_{i \in I}$ of subsets of $E$ is a disjoint cover of $E$ when: $$ E = \bigsqcup_{i \in I} A_i $$ i.e.\ the $A_i$ are pairwise disjoint and their union is $E$.
A disjoint cover is a partition when, in addition, every $A_i$ is non-empty.

Example

For $A \subset E$, the pair $\{A, \overline{A}\}$ is a disjoint cover of $E$. It is a partition if $A \ne \emptyset$ and $A \ne E$.
In $\mathbb{Z}$, the pair $\{2 \mathbb{Z}, 2 \mathbb{Z} + 1\}$ (even, odd) is a partition.
In $\mathbb{Z}$, the family $\{3 \mathbb{Z}, 3 \mathbb{Z} + 1, 3 \mathbb{Z} + 2\}$ (residues modulo $3$) is a partition with three pieces.
For any set $E$, the family of singletons $\{ \{x\} \ \mid \ x \in E \}$ is a partition of $E$ (the « finest » one).

Example

On the left, two disjoint sets: $A \cap B = \emptyset$. On the right, a partition of $E$ into four pieces $A_1, A_2, A_3, A_4$: pairwise disjoint, all non-empty, and covering $E$.

Skills to practice

Deciding whether two sets are disjoint
Verifying that a family is a partition
Constructing a partition
Using the pointwise characterization
Mixing integer intervals with set operations

II.5 Cartesian product

The Cartesian product of two sets pairs every element of the first with every element of the second. It is the construction behind coordinates in the plane ($\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$) and behind tuples in general. Two distinctions matter at the start: order matters in a tuple ($(1, 2) \ne (2, 1)$), unlike in a set; and a tuple may have repetitions ($(1, 1, 2)$), unlike a set whose elements are listed at most once.

Definition — Cartesian product

Let $E_1, E_2, \dots, E_n$ be sets ($n \ge 1$). The Cartesian product of $E_1, \dots, E_n$ is the set of $n$-tuples whose $i$-th component is in $E_i$: $$ E_1 \times E_2 \times \dots \times E_n = \{ (x_1, x_2, \dots, x_n) \ \mid \ \forall i \in \{1, \dots, n\}, \ x_i \in E_i \}. $$ When all the $E_i$ are equal to a same set $E$, we write $E^n$ instead of $E \times \dots \times E$.

Example

$\{1, 2, 3\} \times \{a, b\} = \{ (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) \}$ --- six pairs.
$\mathbb{R}^2 = \{ (x, y) \ \mid \ x, y \in \mathbb{R} \}$, the points of the plane.
$\mathbb{R}^3 = \{ (x, y, z) \ \mid \ x, y, z \in \mathbb{R} \}$, the points of space.
For finite sets, $|E_1 \times E_2| = |E_1| \times |E_2|$ --- the cardinality multiplies.

Example

For $A = \{1, 2, 3, 4\}$ and $B = \{1, 2, 3\}$, the Cartesian product $A \times B$ is the set of $4 \times 3 = 12$ couples $(a, b)$. Picturing it as a grid is the standard model for proving $|A \times B| = |A| \cdot |B|$.

Tuple $\ne$ Set

A tuple $(x_1, \dots, x_n)$ is not a set $\{x_1, \dots, x_n\}$. Two key differences:

Order. $(1, 2) \ne (2, 1)$ but $\{1, 2\} = \{2, 1\}$.
Repetitions. $(1, 1, 2)$ is a $3$-tuple with two equal first components, whereas $\{1, 1, 2\} = \{1, 2\}$ is a set with $2$ elements.

The Cartesian product builds tuples; the union builds sets. Confusing the two leads to errors --- e.g.\ writing $\{x, y\}$ when one means the pair $(x, y)$.

Skills to practice

Listing elements of $A \times B$
Computing $|A \times B|$
Distinguishing tuples from sets

II.6 Indicator function

The indicator function turns the set-theoretic question « does $x$ belong to $A$? » into a numerical answer ($0$ or $1$). It is the bridge between set algebra and ordinary arithmetic: $\cap$ becomes a product, $\cup$ becomes a sum (almost), $\overline{\phantom{X}}$ becomes $1 - \cdot$. Consequence: every set identity becomes a polynomial identity in $\{0, 1\}$-valued functions, which can be checked mechanically.

Definition — Indicator function

Let $E$ be a set and $A \subset E$. The indicator function of $A$ is the function $$ \mathbf{1}_A : E \longrightarrow \{0, 1\}, \qquad \mathbf{1}_A(x) = \begin{cases} 1 & \text{if } x \in A, \\ 0 & \text{if } x \notin A. \end{cases} $$ We also call $\mathbf{1}_A$ the characteristic function of $A$ in $E$ (notation $\chi_A$ in some books).

Example

With $E = \mathbb{R}$ and $A = [0, 1]$, the indicator function $\mathbf{1}_A$ is the rectangle pulse equal to $1$ on $[0, 1]$ and $0$ elsewhere:

With $E = \mathbb{N}$ and $A = 2\mathbb{N}$ the even integers, $\mathbf{1}_A(n) = 1$ if $n$ is even, $0$ if $n$ is odd. The two extreme cases: $\mathbf{1}_E$ is the constant function $1$, and $\mathbf{1}_{\emptyset}$ is the constant function $0$.

Proposition — Set algebra in indicators

Let $E$ be a set and $A, B \subset E$. As functions from $E$ to $\{0, 1\}$: $$ \begin{aligned} \mathbf{1}_{A \cap B} &= \mathbf{1}_A \cdot \mathbf{1}_B, \\ \mathbf{1}_{\overline{A}} &= 1 - \mathbf{1}_A, \\ \mathbf{1}_{A \cup B} &= \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A \cdot \mathbf{1}_B, \\ \mathbf{1}_{A \setminus B} &= \mathbf{1}_A \cdot (1 - \mathbf{1}_B), \\ \mathbf{1}_A^2 &= \mathbf{1}_A. \end{aligned} $$ And the characterization: $$ A \subset B \iff \mathbf{1}_A \leq \mathbf{1}_B, \qquad A = B \iff \mathbf{1}_A = \mathbf{1}_B. $$

Proof

All identities are checked pointwise: for $x \in E$, both sides take the same value in $\{0, 1\}$.

Intersection. $\mathbf{1}_{A \cap B}(x) = 1 \iff x \in A \wedge x \in B \iff \mathbf{1}_A(x) = 1 \wedge \mathbf{1}_B(x) = 1 \iff \mathbf{1}_A(x) \cdot \mathbf{1}_B(x) = 1$ (since the values are in $\{0, 1\}$).
Complement. $\mathbf{1}_{\overline{A}}(x) = 1 \iff x \notin A \iff \mathbf{1}_A(x) = 0 \iff 1 - \mathbf{1}_A(x) = 1$.
Union. By De Morgan, $A \cup B = \overline{\overline{A} \cap \overline{B}}$, so $$ \mathbf{1}_{A \cup B} = 1 - \mathbf{1}_{\overline{A}} \cdot \mathbf{1}_{\overline{B}} = 1 - (1 - \mathbf{1}_A)(1 - \mathbf{1}_B) = \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A \mathbf{1}_B. $$
Difference. $A \setminus B = A \cap \overline{B}$, so $\mathbf{1}_{A \setminus B} = \mathbf{1}_A \cdot (1 - \mathbf{1}_B)$.
Idempotence. $\mathbf{1}_A^2 = \mathbf{1}_{A \cap A} = \mathbf{1}_A$ --- equivalently, $0^2 = 0$ and $1^2 = 1$.
Inclusion. $A \subset B \iff \forall x, \ (x \in A \Rightarrow x \in B) \iff \forall x, \ \mathbf{1}_A(x) \leq \mathbf{1}_B(x)$ (the only forbidden case is $\mathbf{1}_A(x) = 1$ and $\mathbf{1}_B(x) = 0$).
Equality. Apply the previous point twice, or note that $A = B \iff \forall x, \ (x \in A \iff x \in B) \iff \forall x, \ \mathbf{1}_A(x) = \mathbf{1}_B(x)$.

Example

De Morgan via indicators. The identity $\mathbf{1}_{\overline{A \cup B}} = \mathbf{1}_{\overline{A} \cap \overline{B}}$ becomes a one-line algebraic check: $$ 1 - (\mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A \mathbf{1}_B) = (1 - \mathbf{1}_A)(1 - \mathbf{1}_B), $$ which is just expanding the right-hand side. Compare with the membership-chain proof of De Morgan given earlier --- the indicator approach replaces logic by algebra.

Example

Symmetric difference. The set $A \triangle B = (A \setminus B) \cup (B \setminus A)$ (in $A$ or in $B$ but not in both) has indicator $$ \mathbf{1}_{A \triangle B} = \mathbf{1}_A + \mathbf{1}_B - 2 \mathbf{1}_A \mathbf{1}_B = \mathbf{1}_A + \mathbf{1}_B \pmod{2}. $$ The « $\pmod{2}$ » connection is the reason set theory and Boolean algebra over $\mathbb{F}_2 = \{0, 1\}$ coincide.

Skills to practice

Computing $\mathbf{1}_A$
Proving set identities via indicators
Proving inclusion-exclusion via indicators

Jump to section

Notation	Meaning	Venn diagram
\(\overline{A}\)	Complement of \(A\) in \(E\)
\(A \subset B\)	\(A\) is included in \(B\)
\(A \cup B\)	Union: in \(A\) or in \(B\)
\(A \cap B\)	Intersection: in \(A\) and in \(B\)
\(A \setminus B\)	Difference: in \(A\) but not in \(B\)
\(A \cap B = \emptyset\)	\(A\) and \(B\) are disjoint