Every time we group objects by some common criterion (the even numbers less than 10, the users registered in a system, the nodes of a graph), we are working with sets. The concept seems trivial, but one detail separates a rigorous mathematical grouping from a vague list: the criterion must be precise enough that any object in the world can be tested against it.
Why Sets? #
Set theory took rigorous shape in the late nineteenth century, mainly with Georg Cantor (1845 to 1918). In discrete mathematics and computer science, sets show up everywhere:
- Propositional logic: the set of truth assignments that satisfy a formula.
- Combinatorics: counting subsets of size \(k\) of a set with \(n\) elements.
- Graphs: a graph is a pair \((V, E)\) where \(V\) is the set of vertices and \(E \subseteq V \times V\) is the set of edges.
- Programming: collections, filters, and searches are set operations disguised as code.
This article presents the fundamental concepts of set theory: what a set is, how to describe it, the relations between sets, and the power set. These concepts form the language we will use in all the other articles of this series.
What a Set Is #
A set is a well-defined collection of objects called elements.
The expression well-defined is the part of the definition that demands care. It means that, given any object, we must be able to decide unambiguously whether or not it belongs to the set. Without that precision, the grouping is not mathematically useful.
By convention, sets are denoted by capital letters (\(A, B, C, \ldots\)) and their elements by lowercase letters (\(a, b, x, \ldots\)). The relation between an object and a set is called the membership relation:
- \(x \in A\): “\(x\) belongs to \(A\)”
- \(x \notin A\): “\(x\) does not belong to \(A\)”
Well-defined collections and ambiguous collections #
Consider the collection \(C\) formed by tall people.
- If a person is \(1.95\) m tall, intuitively they belong to \(C\).
- If they are \(1.50\) m tall, intuitively they do not.
- If they are \(1.75\) m tall, the answer is already ambiguous.
This collection is not well defined because the membership criterion was not specified precisely. The right way to fix this is to replace the vague description with an objective property:
$$C = \{x \mid \text{the height of } x \text{ is greater than } 1.75\text{ m}\}$$Now it works: for any person in the world, we can decide whether or not they belong to \(C\).
The flowchart below summarizes the reasoning for checking whether a collection is well defined:
flowchart TD
A["Membership criterion"] --> B{"Can any object
be tested
without
ambiguity?"}
B -- "Yes" --> C["Well-defined set ✓"]
B -- "No / Depends" --> D["Ambiguous collection ✗"]
D --> E["Rewrite with an
objective property"]
E --> A
Replacing the vague description with an objective property solves the case of tall people. But precision alone does not guarantee a set, and the discovery of this changed the foundations of mathematics:
In 1901, Bertrand Russell considered the collection of all sets that do not belong to themselves:
$$R = \{X \mid X \notin X\}$$There is nothing vague about the criterion. Still, ask whether \(R \in R\): if \(R \in R\), then \(R\) satisfies the criterion \(X \notin X\), that is, \(R \notin R\); if \(R \notin R\), then \(R\) satisfies the criterion and, therefore, \(R \in R\). Both answers lead to a contradiction: for the object \(R\), there is no way to decide membership.
The flaw lies in accepting that any property defines a set, the principle of so-called naive set theory. In a letter from 1902, Russell showed that this principle made the logical system of Gottlob Frege contradictory. The most widely adopted way out was the axiomatic theory of Zermelo-Fraenkel, in which a property only separates elements of a set that already exists, as in \(\{x \in \mathbb{N} \mid x < 10\}\). Describing sets within a known universe, as we will do in this series, avoids the paradox. More at Russell’s paradox.
The classical number sets #
Before moving on, it is useful to keep in mind the number sets that appear frequently:
| Symbol | Name | Description |
|---|---|---|
| \(\mathbb{N}\) | Naturals | \(\{1, 2, 3, \ldots\}\) |
| \(\mathbb{Z}\) | Integers | \(\{\ldots, -1, 0, 1, \ldots\}\) |
| \(\mathbb{Q}\) | Rationals | \( \{ \frac{p}{q} \mid p, q \in \mathbb{Z}, \ q \neq 0 \} \) |
| \(\mathbb{R}\) | Reals | all the rationals and irrationals |
The definition of \(\mathbb{N}\) is not universal. In Brazilian basic education (BNCC), zero belongs to the naturals: \(\mathbb{N} = \{0, 1, 2, \ldots\}\), and \(\mathbb{N}^\ast = \{1, 2, 3, \ldots\}\) is used for the nonzero naturals. In Discrete Mathematics and Computer Science, many authors (Rosen, Knuth) also include zero. In this series we adopt \(\mathbb{N} = \{1, 2, 3, \ldots\}\) because it follows the tradition of mathematical analysis. When the convention matters for a specific result, it will be stated explicitly. For an in-depth discussion of the different conventions, see Natural number: Terminology and notation and Is 0 a natural number? (Mathematics Stack Exchange).
These sets are nested inside one another: \(\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}\). The precise meaning of the symbol \(\subset\) will be formalized in the section Equality and Inclusion, where a figure illustrates this hierarchy.
Examples of membership in \(\mathbb{N}\)
- \(10598 \in \mathbb{N}\): natural number, belongs
- \(-1 \notin \mathbb{N}\): negative, does not belong
- \(\frac{1}{5} \notin \mathbb{N}\): non-integer rational, does not belong
- \(2.5 \notin \mathbb{N}\): decimal, does not belong
Ways to Describe a Set #
There are two ways to specify a set:
In the roster notation, we explicitly list all the elements:
$$B = \{m, t, c, v\}$$In the set-builder notation, we define a property \(P(x)\) that characterizes the elements:
$$C = \{x \mid P(x)\}$$In set-builder notation, the symbol \(\mid\) is read “such that”. We can also restrict the universe of search:
$$C = \{x \in \mathbb{N} \mid x\ \text{is even and}\ x < 10\} = \{2, 4, 6, 8\}$$
Example: same collection, two descriptions
The set of integers with absolute value less than or equal to 2 can be written in two equivalent ways:
- Roster: \(A = \{-2, -1, 0, 1, 2\}\)
- Set-builder: \(A = \{x \in \mathbb{Z} \mid |x| \leq 2\}\)
Both describe exactly the same set.
The empty set #
An important special case is the empty set: the set that contains no elements, denoted \(\emptyset\).
The empty set \(\emptyset\) contains no elements.
$$\emptyset = \{x \mid x \in \mathbb{N},\ x > 5\ \text{and}\ x < 0\}$$(impossible condition: no natural number is both greater than 5 and less than 0)
The empty set is a subset of every set, and we will see why in the next section.
Application: set-builder notation in databases
The SQL WHERE clause is exactly a set-builder description. The query
SELECT * FROM users WHERE age >= 18 describes the set:
The whole table is the universe of search; the WHERE predicate is the property \(P(x)\).
All data filtering is a set-builder description.
Equality and Inclusion #
Two of the most important concepts in set theory are equality and inclusion.
Two sets are equal when they have exactly the same elements:
$$A = B \iff A \text{ and } B \text{ have the same elements}$$A useful equivalence:
$$A = B \iff A \subseteq B \ \text{and}\ B \subseteq A$$Note that sets have no order and no repetition: \(\{1, 2, 3\} = \{3, 1, 2\} = \{1, 1, 2, 3\}\). What matters is which elements are present.
- \(A \subseteq B\) (A is contained in B): every element of \(A\) is also an element of \(B\)
- \(B \supseteq A\) (B contains A): notation equivalent to \(A \subseteq B\), read from the side of the larger set
- \(A \subset B\) (proper inclusion): \(A \subseteq B\) and \(A \neq B\)
A note on notation: in part of the modern literature, \(\subset\) is used as a synonym for \(\subseteq\) (non-strict inclusion). To avoid ambiguity, some authors adopt \(\subsetneq\) exclusively for proper inclusion. In this series, \(\subset\) always denotes proper inclusion, as defined above. See more at Set notation: inclusion and proper inclusion (Mathematics Stack Exchange).
Equivalent readings for \(A \subseteq B\): “\(A\) is contained in \(B\)”, “\(A\) is a subset of \(B\)”, “\(B\) contains \(A\)”, “\(B\) is a superset of \(A\)”.
Properties of inclusion:
| Property | Statement |
|---|---|
| Reflexivity | \(A \subseteq A\) |
| Transitivity | If \(A \subseteq B\) and \(B \subseteq C\), then \(A \subseteq C\) |
| Inclusion of the empty set | \(\emptyset \subseteq A\) for every set \(A\) |
| Proper inclusion of the empty set | \(\emptyset \subset A\) for every \(A \neq \emptyset\) |
The property \(\emptyset \subseteq A\) follows directly from the definition: for \(\emptyset \not\subseteq A\) to hold, there would have to exist some element of \(\emptyset\) that is not in \(A\), but \(\emptyset\) has no elements, so this situation never occurs.
The classical number sets are a direct example of these relations: \(\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}\). The figure below illustrates this hierarchy of inclusions:
The figure uses nested regions to represent inclusion: each set lies geometrically inside the larger one. This way of visualizing sets is usually called a Venn diagram and will be presented formally in the next article of this series, where we will also see that, strictly speaking, a drawing with only nested regions like this one has another name: Euler diagram.
Application: dependency resolution as inclusion
Package managers (pip, apt, npm) decide whether an installation is feasible by checking whether \(A \subseteq B\). A package can be installed when:
$$\text{deps}(\text{package}) \subseteq \text{installed}$$
If some dependency is not in installed, the inclusion fails and the
manager looks for what is missing. “Dependency resolution” is finding the smallest
additional set that makes the inclusion true.
The Power Set #
Given a set \(A\), we can build a new set whose elements are all the possible subsets of \(A\).
The power set of \(A\), denoted \(\mathcal{P}(A)\), is the set of all subsets of \(A\):
$$\mathcal{P}(A) = \{S \mid S \subseteq A\}$$In Portuguese, the name is conjunto das partes (see the Wikipedia entry Power set).
Example: Let \(A = \{1, 2, 3\}\).
$$\mathcal{P}(A) = \{\emptyset,\ \{1\},\ \{2\},\ \{3\},\ \{1,2\},\ \{1,3\},\ \{2,3\},\ \{1,2,3\}\}$$The diagram below is a Hasse diagram that represents the Boolean lattice of P(A) (ordered by the inclusion relation ⊆): each edge goes up from a subset to the one immediately larger (the one that adds exactly one element).
Reading the diagram from bottom to top visually reveals how these subsets nest inside one another.
flowchart BT
E["∅"]
A1["{1}"]
A2["{2}"]
A3["{3}"]
B12["{1,2}"]
B13["{1,3}"]
B23["{2,3}"]
C["{1,2,3}"]
E --> A1
E --> A2
E --> A3
A1 --> B12
A2 --> B12
A1 --> B13
A3 --> B13
A2 --> B23
A3 --> B23
B12 --> C
B13 --> C
B23 --> C
In practical (and visual) terms, it is a perfectly symmetric mathematical structure. It has an absolute “bottom” (the empty set, ∅) and an absolute “top” (the complete original set, A). Between them, the elements are connected in such a way that, if you pick any two subsets, their union and intersection are also guaranteed to be inside the structure.
Example with the diagram above: pick \(\{1,2\}\) and \(\{1,3\}\).
- The union \(\{1,2\} \cup \{1,3\} = \{1,2,3\}\) is the top node.
- The intersection \(\{1,2\} \cap \{1,3\} = \{1\}\) is a node at the middle level.
Both results appear in the diagram: no operation “leaves” the structure.
The cardinality (number of elements) of the power set is given by:
$$|\mathcal{P}(A)| = 2^{|A|}$$Here the vertical bars indicate cardinality (the number of elements of the set), not absolute value, a notation that will be explored further in the future article on cardinality.
For \(A = \{1, 2, 3\}\): \(|\mathcal{P}(A)| = 2^3 = 8\) subsets.
This makes sense combinatorially: for each element of \(A\), we have exactly two choices, include it in the subset or not. With \(n\) elements and 2 choices per element, there are \(2^n\) possible subsets.
The tree below makes this concrete for \(A = \{1, 2, 3\}\): each level represents the decision about one element, and the 8 leaves are exactly the subsets of \(\mathcal{P}(A)\).
flowchart TD
R["A = {1, 2, 3}"]
R -->|"1 ∈ S"| Y1["{1, ?, ?}"]
R -->|"1 ∉ S"| N1["{_, ?, ?}"]
Y1 -->|"2 ∈ S"| Y12["{1, 2, ?}"]
Y1 -->|"2 ∉ S"| N12["{1, _, ?}"]
N1 -->|"2 ∈ S"| Y02["{_, 2, ?}"]
N1 -->|"2 ∉ S"| N02["{_, _, ?}"]
Y12 -->|"3 ∈ S"| L123["{1, 2, 3}"]
Y12 -->|"3 ∉ S"| L12["{1, 2}"]
N12 -->|"3 ∈ S"| L13["{1, 3}"]
N12 -->|"3 ∉ S"| L1["{1}"]
Y02 -->|"3 ∈ S"| L23["{2, 3}"]
Y02 -->|"3 ∉ S"| L2["{2}"]
N02 -->|"3 ∈ S"| L3["{3}"]
N02 -->|"3 ∉ S"| LE["∅"]
The tree makes the three choices one after the other. We can also see them at the same time: if each element becomes an axis (in or out), the subsets of \(\{1, 2, 3\}\) occupy the eight vertices of a cube. The figure below draws the same lattice as the Hasse diagram in three dimensions: each edge adds a single element, the color says which one, and going up from \(\emptyset\) to \(\{1, 2, 3\}\) is adding one element at a time.
Careful: elements of \(\mathcal{P}(A)\) are sets #
A common source of confusion is mixing up membership (\(\in\)) with inclusion (\(\subseteq\)) when working with \(\mathcal{P}(A)\). If \(A = \{1, 2, 3\}\):
- \( \{1 \} \in \mathcal{P}(A)\): the set \(\{1\}\) belongs to \(\mathcal{P}(A)\) (it is one of its elements)
- \(1 \notin \mathcal{P}(A)\): the number \(1\) does not belong to \(\mathcal{P}(A)\) (the number is not a set)
- \(\emptyset \in \mathcal{P}(A)\): the empty set always belongs
- \(\{\{1\}\} \subseteq \mathcal{P}(A)\): the set \(\{\{1\}\}\) is included in \(\mathcal{P}(A)\) because its only element, \(\{1\}\), belongs to \(\mathcal{P}(A)\)
Summary Table #
The concepts and results of the article, gathered for quick reference:
| Concept | Notation | Result |
|---|---|---|
| Membership | \(x \in A\), \(x \notin A\) | relation between an object and a set |
| Roster notation | \(A = \{a, b, c\}\) | lists all the elements |
| Set-builder notation | \(A = \{x \in U \mid P(x)\}\) | elements of \(U\) that satisfy \(P\) |
| Empty set | \(\emptyset\) | \(\emptyset \subseteq A\) for every \(A\) |
| Equality | \(A = B\) | \(A = B \iff A \subseteq B \text{ and } B \subseteq A\) |
| Inclusion | \(A \subseteq B\) | every element of \(A\) is in \(B\); it is reflexive and transitive |
| Proper inclusion | \(A \subset B\) | \(A \subseteq B\) and \(A \neq B\) |
| Power set | \(\mathcal{P}(A) = \{S \mid S \subseteq A\}\) | \(\lvert \mathcal{P}(A) \rvert = 2^{\lvert A \rvert}\) |
| Elements of \(\mathcal{P}(A)\) | \(\{1\} \in \mathcal{P}(A)\) | they are sets: \(1 \notin \mathcal{P}(A)\) and \(\{\{1\}\} \subseteq \mathcal{P}(A)\) |
In the last row, \(A = \{1, 2, 3\}\), as in the article’s example.
Exercises #
Exercise 1: Equality of sets
Determine which of the following sets are equal:
$$A = \{a, b, -1\} \qquad B = \{b, a, -1\} \qquad C = \{b, a, b, -1\} \qquad D = \{a, -1\}$$
Solution
\(A = B = C\). Sets have no order and do not count repetitions: \(A\), \(B\), and \(C\) contain exactly the elements \(a\), \(b\), and \(-1\). \(D\), on the other hand, does not contain \(b\), so \(D \neq A\).
Exercise 2: Sets by roster and set-builder notation
Write the following sets by explicitly listing their elements:
(i) \(A = \{x \in \mathbb{Z} \mid -1 \leq x \leq 4\}\)
(ii) \(B = \{x \in \mathbb{N} \mid x \leq \sqrt{10}\ \text{or}\ x > -2\}\)
(iii) \(C = \{x \in \mathbb{R} \mid 2x + 1 = 5\}\)
(iv) \(D = \{x \in \mathbb{R} \mid x^2 + 1 = 0\}\)
Solutions
(i) \(A = \{-1, 0, 1, 2, 3, 4\}\). These are all the integers between \(-1\) and \(4\) inclusive.
(ii) \(B = \mathbb{N} = \{1, 2, 3, \ldots\}\). The condition \(x > -2\) is satisfied by every \(x \in \mathbb{N}\), so it already covers all of \(\mathbb{N}\). The condition \(x \leq \sqrt{10} \approx 3.16\) gives \(\{1,2,3\} \subset \mathbb{N}\). The union of the two conditions is all of \(\mathbb{N}\).
(iii) \(C = \{2\}\), since \(2x+1=5 \Rightarrow x=2 \in \mathbb{R}\).
(iv) \(D = \emptyset\), since \(x^2+1=0 \Rightarrow x^2=-1\), which has no real solution.
Exercise 3: Membership relations
Determine whether each relation is true or false:
(i) \(\sqrt{2} \in \{x \in \mathbb{R} \mid x \geq 2\}\)
(ii) \(3 \in \{x \in \mathbb{R} \mid |x| \leq 4\}\)
(iii) \(\emptyset \notin \mathcal{P}(A)\) where \(A = \{1, 2\}\)
(iv) \(\{1\} \in \{x \in \mathbb{R} \mid x^2 = 1\}\)
(v) \(\emptyset \in \{\emptyset, \{1\}\}\)
Solutions
(i) False. \(\sqrt{2} \approx 1.41 < 2\), so it does not satisfy \(x \geq 2\).
(ii) True. \(|3| = 3 \leq 4\).
(iii) False. \(\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}\) and \(\emptyset \in \mathcal{P}(A)\).
(iv) False. \(\{x \in \mathbb{R} \mid x^2 = 1\} = \{-1, 1\}\). The elements are the numbers \(-1\) and \(1\), not the set \(\{1\}\).
(v) True. The empty set is explicitly listed as an element of \(\{\emptyset, \{1\}\}\).
Exercise 4: Inclusion relations
Determine whether each relation is true or false:
(i) \(\{-2, 0\} \subseteq \{x \in \mathbb{Z} \mid |x| \leq 2\}\)
(ii) \(\{\pi\} \subset \{1, \{\pi\}, a\}\)
(iii) \(\{\{\pi\}\} \subset \{1, \{\pi\}, a\}\)
(iv) \(\emptyset \not\subseteq \{3, 1, -7\}\)
(v) \(\emptyset \subseteq \{\emptyset, \{1\}\}\)
Solutions
(i) True. \(\{x \in \mathbb{Z} \mid |x| \leq 2\} = \{-2,-1,0,1,2\}\), which contains \(-2\) and \(0\).
(ii) False. The set \(\{1, \{\pi\}, a\}\) contains the set \(\{\pi\}\) as an element, but does not directly contain \(\pi\). Hence \(\{\pi\} \not\subset \{1, \{\pi\}, a\}\).
(iii) True. \(\{\pi\}\) is an element of \(\{1, \{\pi\}, a\}\), so \(\{\{\pi\}\}\) is included in that set.
(iv) False. \(\emptyset \subseteq C\) for every set \(C\), without exception.
(v) True. \(\emptyset\) is a subset of every set.
Exercise 5: Power set
Given \(A = \{x \in \mathbb{Z} \mid |x| \leq 1\}\), determine \(\mathcal{P}(A)\).
Solution
First, \(A = \{-1, 0, 1\}\) (integers with absolute value at most 1).
$$\mathcal{P}(A) = \{\emptyset,\ \{-1\},\ \{0\},\ \{1\},\ \{-1,0\},\ \{-1,1\},\ \{0,1\},\ \{-1,0,1\}\}$$Since \(|A| = 3\), we have \(|\mathcal{P}(A)| = 2^3 = 8\) subsets, all listed above.
Next Steps #
With the notions of set, membership, and inclusion established, the natural next step is to learn to operate on sets: how to combine two sets into one, how to find what they have in common, how to remove elements of one relative to another. That is the subject of the next article, where we will also see Venn diagrams, a visual tool for reasoning about sets.
Later in the series, all this theory gains a practical dimension: we will see how
the concepts of set, membership, inclusion, and operations translate
directly into Python code, with the language’s set and frozenset types.
For an overview of discrete mathematics and the roadmap of this series, see Discrete Mathematics: Introduction and Roadmap.
See you next time!
