Sets and operations

In chapter 2, we spent the whole chapter talking about the “domain of discourse”, the set over which variables range, while settling for an intuitive idea: a collection of objects. The chapter even closed on a promise: "$A \subseteq B$" would be read "$\forall x,\ x \in A \Rightarrow x \in B$". It is time to keep it. But what is a set, exactly? How do we describe one, how do we test that an object belongs to it, how do we build new ones from old?

The answer is lovelier than a mere catalogue of symbols. You are about to discover that set theory is not a new territory to memorise: it is the logic of chapter 1, poured into objects. The “or” becomes union, the “and” becomes intersection, the “not” becomes complement, and the De Morgan laws you already know will reappear, identical, on sets.

Describing a set

A set Set A collection of objects, called its elements, regarded as a single whole. A set is entirely determined by its elements: two sets with exactly the same elements are equal. It is described by extension, listing its elements in braces such as {1, 2, 3}, or by comprehension, giving the property its elements satisfy, such as {x | x > 3}. is a collection of objects, its elements, regarded as a single whole.

The basic gesture, the one everything else flows from, is to ask whether an object is in or out. This relation is called membership Membership The fundamental relation between an object and a set, written ∈. "x ∈ A" reads "x belongs to A" and means that x is one of the elements of A. Its negation is written ∉. Membership is the basic predicate of set theory: everything else, inclusion and operations, is defined from it. and is written $\in$ :

reads ”$x$ belongs to $A$”, that is ”$x$ is one of the elements of $A$”. Its negation is written $x \notin A$. Notice that "$x \in A$" is exactly a predicate in the sense of chapter 2: depending on what we put in place of $x$, it is true or false. The whole of set theory is built on this single predicate.

There are two ways to describe which objects are in a set:

• By extension : we list the elements in braces. $A = \{1, 2, 3\}$. Handy for small sets.
• By comprehension : we give the property the elements satisfy. $A = \{x \mid x > 0 \text{ and } x < 4 \text{ and } x \text{ integer}\}$. Here the bar $\mid$ reads “such that”.

The comprehension description reveals the deep link with chapter 2: a set by comprehension, $\{x \mid P(x)\}$, is nothing but a predicate $P$ turned into an object. The set is the collection of all the witnesses that make $P$ true.

One last principle, quiet but foundational: a set is entirely determined by its elements. Two sets with exactly the same elements are the same set, no matter how they were described. So $\{1, 2, 3\}$, $\{3, 2, 1\}$ and $\{1, 1, 2, 3\}$ are one and the same set: order and repetitions do not count. This principle is called extensionality, and it is what makes everything that follows possible.

Comparing: inclusion and equality

Now that we can test membership, we can compare two sets. The promise of chapter 2 arrives here. Inclusion Inclusion A relation between two sets, written ⊆. "A ⊆ B" reads "A is included in B" or "A is a subset of B", and means that every element of A is also an element of B. Its definition is a quantified statement: A ⊆ B is equivalent to "for all x, x ∈ A implies x ∈ B". Two sets are equal exactly when each is included in the other (double inclusion). , written $\subseteq$, says that every element of the first set is also in the second:

This equation reads: ”$A$ is included in $B$” exactly when “for all $x$, if $x$ belongs to $A$, then $x$ belongs to $B$”. Inclusion is therefore not one more symbol to memorise: it is a universal implication, the “for all” of chapter 2 applied to the membership predicate. We say $A$ is a subset of $B$.

How, then, do we say that two sets are equal? By extensionality, $A = B$ means they have the same elements, that is, each is included in the other:

This split is called double inclusion. It looks harmless, but it is the most used proof tool whenever we want to show two sets are equal: we prove one inclusion, then the other. Keep it in mind, chapter 4 will make it its daily bread.

We can also gather all the subsets of a set $E$ into a new set: the power set Power set The set of all subsets of a set E, written P(E). Its elements are themselves sets: the empty set and E itself always belong to it. If E has n elements, then P(E) has 2 to the power n, because each element of E is either taken or left out of a subset. For example P({a, b}) = {∅, {a}, {b}, {a, b}}. , written $\mathcal{P}(E)$. Its elements are themselves sets. For example:

We always find $\varnothing$ and $E$ itself in it. And a simple count: if $E$ has $n$ elements, $\mathcal{P}(E)$ has $2^n$, because to build a subset, each element of $E$ is either taken or left out, two independent choices repeated $n$ times.

Combining: the operations are the connectives

Here is the heart of the chapter. From two sets, we build new ones with three operations. Each is defined by its membership condition, and that condition is a connective from chapter 1.

Union Union The operation that joins two sets, written ∪. A ∪ B is the set of objects that belong to A or to B (or to both). Its membership condition is a disjunction: x ∈ A ∪ B is equivalent to "x ∈ A or x ∈ B". Union is to the logical "or" what the object is to the connective. , written $\cup$, gathers:

An object is in $A \cup B$ if it is in $A$ or in $B$ (or in both). Union is the logical “or” turned into an object.

Intersection Intersection The operation that keeps only what two sets share, written ∩. A ∩ B is the set of objects that belong to both A and B. Its membership condition is a conjunction: x ∈ A ∩ B is equivalent to "x ∈ A and x ∈ B". When A ∩ B is empty, A and B are said to be disjoint. , written $\cap$, keeps only the common part:

An object is in $A \cap B$ if it is in $A$ and in $B$. Intersection is the “and”. When $A \cap B = \varnothing$, we say $A$ and $B$ are disjoint.

The complement Complement The operation that returns what is not in a set, relative to a reference universe. The complement of A, written Aᶜ (or A bar), is the set of objects of the universe that do not belong to A. Its membership condition is a negation: x ∈ Aᶜ is equivalent to "not (x ∈ A)". The complement depends on the chosen universe: without a fixed universe, it has no meaning. , written $A^c$, returns what is not in $A$, relative to a reference universe $U$ :

This is the “not”. Careful: the complement only makes sense if the universe is fixed. Without saying “not with respect to what”, $A^c$ means nothing. It is the same role as the domain of discourse of chapter 2.

The table fills itself in: to each logical connective corresponds a set operation, because the two are the same idea seen from two sides.

And since the operations are connectives, the laws that govern the connectives become laws on sets. The De Morgan laws of chapter 1, $\lnot(P \lor Q) \equiv \lnot P \land \lnot Q$, transpose word for word:

Read the first one aloud: “the complement of a union is the intersection of the complements”. To not be in $A$ or $B$, you must be neither in $A$ nor in $B$. This is exactly the “not (P or Q) amounts to (not P) and (not Q)” of chapter 1. You are not proving a new truth: you are recognising an old one in a new costume.

Manipulating De Morgan on objects

The component below makes all this tangible. The universe is $U = \{1, 2, 3, 4, 5, 6\}$, starting with $A = \{1, 2, 3\}$ and $B = \{3, 4, 5\}$. You place each element in one of the four regions by clicking on it, and you choose the operation to display: the component shows the matching membership condition and highlights the selected elements.

Your mission : turn on De Morgan mode. On the left, the component computes $(A \cup B)^c$ ; on the right, $A^c \cap B^c$. The two lists are identical, here $\{6\}$, the only element outside both circles. Now move elements from one region to another, as much as you like: the two sides always stay equal. You have not proved anything yet, but you have watched the law resist every attempt.

Three questions to ask yourself while playing:

• Put every element in the “outside A and B” region. What is $A \cup B$ ? And $(A \cup B)^c$ ? Does the De Morgan equality still hold on empty sets?
• Choose the operation “difference $A \setminus B$”. Guess its membership condition before reading it: which connective matches “in $A$ but not in $B$” ?
• Place a single element in the intersection. How many regions does the complement of $A$ cover?

Building anew: the cartesian product

The three previous operations stay inside the starting universe. One last construction truly steps outside, in the literal sense: the cartesian product Cartesian product The operation that builds a set of pairs from two sets, written ×. A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. Order matters: (a, b) is not (b, a). If A has m elements and B has n, then A × B has m × n. It is the starting brick of relations and functions. , written $\times$. It builds pairs:

$A \times B$ is the set of all ordered pairs whose first coordinate comes from $A$ and second from $B$. Order matters: $(a, b)$ is not $(b, a)$. And the count is clear: if $A$ has $m$ elements and $B$ has $n$, then $A \times B$ has $m \times n$, hence the name. With $A = \{1, 2\}$ and $B = \{x, y\}$ :

We will not go further here, but remember where this brick leads: a pair is the seed of a relation, and a well-chosen relation is a function. The whole language of functions, which the following courses will unfold, is built on this simple $\times$.

In one sentence

A set is determined by its elements through membership; inclusion is a universal implication, union an “or”, intersection an “and”, complement a “not”, so the De Morgan laws of chapter 1 still govern sets, word for word.

Towards chapter 4

You have seen, on the component and on examples, that $(A \cup B)^c = A^c \cap B^c$. You tested it, again and again, never catching it out. But to test is not to prove: checking an identity on a universe of six elements does not prove it holds for all sets, exactly as trying a hundred numbers does not prove a universal property (remember Fermat’s counter-example in chapter 2). How do we pass from “it works every time” to “it is true, always, with no exception”?

The key is already in this chapter: to prove $A = B$, we prove $A \subseteq B$ and $B \subseteq A$ ; and each inclusion is a "$\forall x,\ x \in A \Rightarrow x \in B$", hence a universal implication to prove. Chapter 4 gives precisely the techniques to prove such statements, with no example and no drawing: direct proof, contrapositive, proof by contradiction. The double inclusion of this chapter is the proof obligation the next one will teach you to honour.

Exercises

Take a sheet of paper and a pencil. The solutions are right below, look at them only after trying.

Exercise 1: prove an inclusion through membership

Show that $A \subseteq A \cup B$ for all sets $A$ and $B$. Hint: translate the inclusion into a quantified statement, then reason about an arbitrary element.

Exercise 2: check De Morgan on a finite universe

The universe is $U = \{1, 2, 3, 4, 5, 6\}$, with $A = \{1, 2, 3\}$ and $B = \{3, 4, 5\}$. Compute $(A \cup B)^c$ on one side, then $A^c \cap B^c$ on the other, and compare.

Sources

• Halmos, P. (1960). Naive Set Theory. Van Nostrand. The classic reference, short and luminous, on intuitive set theory.
• Cantor, G. (1895). “Beiträge zur Begründung der transfiniten Mengenlehre.” Mathematische Annalen 46. The founding act of set theory.

Going further

• Velleman, D. J. (2019). How to Prove It. Cambridge University Press. Chapter 1 on sets and their operations, in the exact spirit of this course.
• Enderton, H. (1977). Elements of Set Theory. Academic Press. For the axiomatic version, once chapter 4 is digested.