16 - Sets and Logic: the Language of Mathematics

Sooner or later you open a page of a machine learning textbook and find ∀ε>0 ∃δ>0 ...: it feels like reading a foreign language, and for many people it is the point where the course ends. Almost always the problem is not the calculations, which are simple, but the language: a symbol is only an abbreviated sentence, and once you can read the sentence the formula has no secrets left. This lesson opens the mathematics and statistics module and is the dictionary you will use in all the following ones. For every concept I follow the same order: a concrete analogy, the full definition, the Python code that checks it, the trade-off (when it is needed and when it is not) and the traps. The proofs are written out in full, in steps you can follow with a pencil. At the end every symbol has a translation into English and into code, and you can prove the two laws that are used all the time, De Morgan and inclusion-exclusion.

Python 3 with the standard library alone is enough, plus NumPy in a couple of listings. The listings form a single program to be run in the order in which they appear (each one reuses the definitions of the previous one), except the last, the solution of the mini-project, which is self-contained. They were run with Python 3.14.4 and NumPy 2.3.5. If you are not familiar with Python's set type, review the lesson on lists, tuples, dictionaries and sets first.

The dictionary of symbols

The table pairs each symbol of the lesson with the English phrase it means and with the Python expression that computes it. For the union, besides the method A.union(B), Python accepts the operator A | B, which we will use in the code; the documentation of the built-in types specifies that methods such as union() accept any iterable, whereas the operators require two sets.

Keep the table within reach: in the rest of the module every new symbol will be translated in the same way. The symbol to look at most carefully is the complement, because its translation U - A contains an object, U, that in mathematical notation often stays implicit; we will come back to why.

Sets

A set is a bag of tickets. What matters is what is inside: not the order in which you put the tickets in, and not how many times you repeat the same ticket. The bag {red, green, red} and the bag {green, red} are the same bag. This difference from the list is substantial: a list is an ordered row that allows repetitions, a set is a membership. That is why x in a_set does not scan the tickets one by one but asks the bag whether that one is there, thanks to the hash table covered in the lesson on data structures, and for the same reason the documentation warns that sets do not record position or insertion order and support neither indexing nor slicing.

A set is described in two ways. By listing: A = {2, 4, 6, 8}. By property (set-builder): A = {n ∈ ℕ : n is even, 0 < n ≤ 8}, which reads "the set of the natural numbers n such that..." and in Python becomes a set comprehension. The first listing shows the comprehension and three facts not to be confused: repetitions and order do not matter for sets, they do matter for lists, and the empty curly braces {} produce a dictionary, not an empty set.

A = {n for n in range(1, 9) if n % 2 == 0}
print(sorted(A))
print("repetitions and order do not matter:", {3, 1, 3, 2} == {1, 2, 3})
print("a list and a set are different objects:", [3, 1, 3, 2] == [1, 2, 3])
print("`{}` is an empty dictionary, the empty set is set():", type({}).__name__, type(set()).__name__)

Output obtained (Python 3.14.4, NumPy 2.3.5; run twice with identical output):

[2, 4, 6, 8]
repetitions and order do not matter: True
a list and a set are different objects: False
`{}` is an empty dictionary, the empty set is set(): dict set

The standard number sets are ℕ the naturals (0, 1, 2, ...; some textbooks start from 1, so always state the convention), ℤ the integers, ℚ the rationals (fractions) and ℝ the reals, with ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ. An interval such as [0, 1] is the set of the reals between 0 and 1 endpoints included (square brackets); (0, 1) excludes them.

Subsets and the power set

A ⊆ B means that every element of A is also an element of B. The set of all the subsets of A is called the power set, 𝒫(A). How many are there? We build a subset by deciding, for each element, whether it goes in or stays out: two choices per element. With |A| = n elements and independent choices the total is 2 · 2 · … · 2 = 2ⁿ, and this is the multiplication principle that we will formalise in the lesson on combinatorics. The function parti in the listing generates the subsets by construction, one size at a time with itertools.combinations (the itertools documentation defines it as the subsequences of length r of the iterable), and the loop compares the count with 2ⁿ.

from itertools import combinations

def parti(insieme):
    """All the subsets: for each size k, all the combinations of k elements."""
    elementi = list(insieme)
    return [set(c) for k in range(len(elementi) + 1) for c in combinations(elementi, k)]

for n in range(0, 6):
    print(f"|A| = {n}: subsets = {len(parti(range(n)))}  (2^{n} = {2 ** n})")

Output obtained (Python 3.14.4, NumPy 2.3.5; run twice with identical output):

|A| = 0: subsets = 1  (2^0 = 1)
|A| = 1: subsets = 2  (2^1 = 2)
|A| = 2: subsets = 4  (2^2 = 4)
|A| = 3: subsets = 8  (2^3 = 8)
|A| = 4: subsets = 16  (2^4 = 16)
|A| = 5: subsets = 32  (2^5 = 32)

The correspondence is exact for every n from 0 to 5, including the case n = 0, in which the only subset is the empty set. In machine learning this count explains a design choice: with n = 30 features the number of feature subsets to choose from is 2³⁰ ≈ 10⁹, and with 40 features it is 2⁴⁰ ≈ 10¹². Trying them all is unthinkable, which is why feature selection is done with heuristics and not by brute force.

The operations

Imagine a school with three clubs: chess, theatre, robotics, which each student may join in more than one. The union A ∪ B is whoever is in at least one of the two clubs, counted only once even if in both. The intersection A ∩ B is whoever is in both. The difference A ∖ B is whoever is in A but not in B. The complement Aᶜ is whoever is not in A relative to a universe, for example all the students of the school: without a universe the complement makes no sense, because "whoever is not in the chess club" is a sentence that needs to know among whom to look. The listing applies the five operations to a universe of 10 students and two clubs, and adds the symmetric difference (^), that is, whoever is in only one of the two.

U = set(range(1, 11))                 # universe: students numbered from 1 to 10
scacchi = {1, 2, 3, 4, 5}
teatro = {4, 5, 6, 7}

print("union        :", sorted(scacchi | teatro))
print("intersection :", sorted(scacchi & teatro))
print("chess minus theatre:", sorted(scacchi - teatro))
print("complement of chess:", sorted(U - scacchi))
print("symmetric difference (in only one of the two):", sorted(scacchi ^ teatro))

Output obtained (Python 3.14.4, NumPy 2.3.5; run twice with identical output):

union        : [1, 2, 3, 4, 5, 6, 7]
intersection : [4, 5]
chess minus theatre: [1, 2, 3]
complement of chess: [6, 7, 8, 9, 10]
symmetric difference (in only one of the two): [1, 2, 3, 6, 7]

The result can be checked by eye: students 4 and 5 are in both clubs, so they are in the intersection and not in the symmetric difference. The basic properties are remembered by thinking of the clubs: A ∪ B = B ∪ A (commutative), (A ∪ B) ∪ C = A ∪ (B ∪ C) (associative), and the distributive law A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C): "whoever is in chess and (in theatre or robotics)" coincides with "whoever is in chess and theatre, or in chess and robotics".

De Morgan's laws, proved

De Morgan's laws, which the author they are named after set out in his work on logic of 1847, say how the complement "passes through" a union or an intersection: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ. In English: "not (A or B)" is "not A and not B"; "not (A and B)" is "not A or not B". If you are enrolled neither in chess nor in theatre, then you are not enrolled in chess and you are not enrolled in theatre. To prove that two sets are equal you show that an arbitrary element is in one if and only if it is in the other. Let x be an element of the universe; the first law is proved like this, step by step.

1. x ∈ (A ∪ B)ᶜ means (definition of complement) x ∉ A ∪ B.
2. x ∉ A ∪ B means that it is not true that "x ∈ A or x ∈ B", that is (negating an "or") x ∉ A and x ∉ B.
3. x ∉ A and x ∉ B means (definition of complement, twice) x ∈ Aᶜ and x ∈ Bᶜ.
4. That is, x ∈ Aᶜ ∩ Bᶜ.

Every step is an equivalence ("if and only if"), so (A ∪ B)ᶜ and Aᶜ ∩ Bᶜ have the same elements: they are equal. ∎ The order of the steps is not interchangeable: the second uses the meaning of "or" that the first has just written, and the fourth joins the two pieces of the third. The second law is proved in the same way, swapping the roles of "and" and "or".

A check with the computer is not a general proof, but here something strong is possible: on a small universe you can test all the pairs of subsets. With a universe of 4 elements there are 16 subsets and therefore 256 pairs; the listing runs through all of them and uses assert for the two laws, so a single exception is enough to stop the program.

U = {0, 1, 2, 3}
tutti = parti(U)                    # the 16 subsets of U
coppie = 0
for A in tutti:
    for B in tutti:
        assert U - (A | B) == (U - A) & (U - B)       # first law
        assert U - (A & B) == (U - A) | (U - B)       # second law
        coppie += 1
print("pairs (A, B) checked:", coppie, "| no exceptions")

Output obtained (Python 3.14.4, NumPy 2.3.5; run twice with identical output):

pairs (A, B) checked: 256 | no exceptions

No assertion failed, so on this universe the two laws hold for all 256 pairs. The advantage of the exhaustive check is that it finds transcription errors by itself: if you wrote U - (A | B) == (U - A) | (U - B) with the "or" in place of the "and", the program would stop at once. The limit is that it says nothing about larger universes: for that you need the proof above.

Where you really meet them

Every time you write a filter with several conditions on a table you are using De Morgan. The listing shows it with NumPy boolean masks (the same syntax works for the columns of Pandas): ~(a | b) and ~a & ~b select the same rows, where ~ is negation.

import numpy as np

eta = np.array([15, 22, 35, 41, 67, 70])
a = eta < 18                                   # under 18
b = eta >= 65                                  # senior
print("outside both (~(a|b))  :", eta[~(a | b)])
print("~a & ~b                :", eta[~a & ~b])
print("same selection:", np.array_equal(~(a | b), ~a & ~b))

Output obtained (Python 3.14.4, NumPy 2.3.5; run twice with identical output):

outside both (~(a|b))  : [22 35 41]
~a & ~b                : [22 35 41]
same selection: True

The day you have to negate a long filter without making mistakes, De Morgan saves you: negate every condition and swap the "and"s with the "or"s. The same holds for the filters on the data of a training pipeline, where an error in the negation removes rows you wanted to keep without anything flagging the problem.

The Cartesian product: the data space and the grid

A restaurant offers 3 first courses and 2 main courses, and a menu is a pair (first, main). The possible menus are all the pairs: 3 · 2 = 6. The Cartesian product A × B is the set of all the ordered pairs (a, b) with a ∈ A and b ∈ B, hence |A × B| = |A| · |B|: for each element of A you have |B| ways of completing the pair. In machine learning it appears twice. The data space is a Cartesian product: an example with d real features is a point of ℝ × ℝ × … × ℝ = ℝᵈ, and saying "the data live in a 30-dimensional space" means that every example is a 30-tuple. The hyperparameter grid is another: trying C ∈ {0.1, 1, 10} and kernel ∈ {linear, rbf} means walking through the product {0.1, 1, 10} × {linear, rbf}, that is 6 combinations, and it is what GridSearchCV does in the lesson on scikit-learn. The listing builds the grid with itertools.product, which the documentation describes as the Cartesian product of the input iterables.

from itertools import product

C = [0.1, 1, 10]
kernel = ["linear", "rbf"]
griglia = list(product(C, kernel))
print(griglia)
print("combinations:", len(griglia), "= |C| · |kernel| =", len(C) * len(kernel))

print("with 5 hyperparameters of 10 values each:", 10 ** 5, "combinations")

Output obtained (Python 3.14.4, NumPy 2.3.5; run twice with identical output):

[(0.1, 'linear'), (0.1, 'rbf'), (1, 'linear'), (1, 'rbf'), (10, 'linear'), (10, 'rbf')]
combinations: 6 = |C| · |kernel| = 6
with 5 hyperparameters of 10 values each: 100000 combinations

The length of the list coincides with the product of the lengths. The trade-off is that the Cartesian product grows multiplicatively: adding a hyperparameter with 10 values multiplies the cost of the search by 10, and with 5 hyperparameters of 10 values each you reach 100,000 combinations, each to be trained several times in cross-validation. It is the "curse" that pushes towards random or adaptive searches instead of the full grid.

Counting: inclusion-exclusion

How many students are in at least one club? If you add up the members of the two clubs, those enrolled in both are counted twice. The correction is to subtract the intersection once: |A ∪ B| = |A| + |B| − |A ∩ B|. The proof splits A ∪ B into three disjoint parts: those only in A (A ∖ B), those only in B (B ∖ A) and the common ones (A ∩ B). Then |A ∪ B| = |A∖B| + |B∖A| + |A∩B|. But |A| = |A∖B| + |A∩B| (A is made of the only-A and the common ones), whence |A∖B| = |A| − |A∩B|, and similarly |B∖A| = |B| − |A∩B|. Substituting: |A∪B| = (|A| − |A∩B|) + (|B| − |A∩B|) + |A∩B| = |A| + |B| − |A∩B|. ∎

With three sets one more correction is needed: by subtracting the three pairwise intersections, the triple intersection has been removed too many times and must be added back, |A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. The listing generalises to any number of sets with an alternating sum: for each group size k, a plus sign if k is odd and a minus if it is even, over the intersections of all the groups of that size (built with combinations). It compares the result with the union computed directly, on three sales channels.

from itertools import combinations

def incl_escl(insiemi):
    """Cardinality of the union with the formula: alternating sum over the intersections."""
    totale = 0
    for k in range(1, len(insiemi) + 1):
        segno = 1 if k % 2 == 1 else -1
        for gruppo in combinations(insiemi, k):
            totale += segno * len(set.intersection(*gruppo))
    return totale

web = {1, 2, 3, 4, 5, 6}
app = {4, 5, 6, 7, 8}
negozio = {6, 8, 9, 10}

print("formula          :", incl_escl([web, app, negozio]))
print("direct union     :", len(web | app | negozio))
print("naive sum        :", len(web) + len(app) + len(negozio), "(counts more than once whoever uses several channels)")

Output obtained (Python 3.14.4, NumPy 2.3.5; run twice with identical output):

formula          : 10
direct union     : 10
naive sum        : 15 (counts more than once whoever uses several channels)

The formula and the direct union both give 10, while the naive sum gives 15 because it counts more than once whoever uses several channels. If you have the sets, len(A | B | C) is enough; the formula is needed when you know only the counts, for example from different reports ("12,000 bought online, 8,000 in store, 3,000 in both"), and you have to estimate how many distinct customers you have. In the lesson on probability the same formula will reappear with "number of elements" replaced by "probability".

Functions

A function f : A → B is a vending machine: to every element of A (the domain, what you put in) it assigns exactly one element of B (the codomain, the kind of thing that comes out). The set of values that actually come out is called the image, f(A) ⊆ B. Three properties, each with its own question, are summarised in the table.

A bijective function is invertible: from the output you can go back to the input. When an operation on the data must be reversible (encoding labels, lossless compression) you need a bijection. The listing checks the two properties for functions defined on a finite domain: injectivity checks that the images do not collide (no duplicates in the list of outputs), surjectivity that the set of outputs coincides with the declared codomain.

def iniettiva(f, dominio):
    immagini = [f(x) for x in dominio]
    return len(set(immagini)) == len(immagini)          # no collisions

def suriettiva(f, dominio, codominio):
    return {f(x) for x in dominio} == set(codominio)

D = range(-3, 4)                                    # domain: from -3 to 3
print("x -> x^2 on D        injective:", iniettiva(lambda x: x * x, D))
print("x -> x+10 on D       injective:", iniettiva(lambda x: x + 10, D))
print("x -> max(0, x) (ReLU) injective:", iniettiva(lambda x: max(0, x), D))
print("x -> x % 3 onto the codomain {0,1,2} surjective:", suriettiva(lambda x: x % 3, D, [0, 1, 2]))

Output obtained (Python 3.14.4, NumPy 2.3.5; run twice with identical output):

x -> x^2 on D        injective: False
x -> x+10 on D       injective: True
x -> max(0, x) (ReLU) injective: False
x -> x % 3 onto the codomain {0,1,2} surjective: True

The function x → x² on {−3, …, 3} is not injective ((−2)² = 2²): from the output 4 you cannot tell whether the input was 2 or −2. A ReLU (max(0, x)) squashes all the negatives onto the same zero, so it loses information and is not invertible; for this reason a layer with ReLU is not, in general, reversible. Adding 10, instead, is a bijection onto its own codomain. The check in code holds only for small finite domains: for an infinite domain you need proofs.

Functions and machine learning

A model is a function, f : ℝᵈ → ℝ, from the feature space to the values to be predicted. The preimage f⁻¹(S) = {x : f(x) ∈ S} is the set of inputs that produce a certain result: for a classifier, f⁻¹({1}) is the decision region of class 1, a subset of the data space, and classifying means partitioning the space into sets. The composition (g ∘ f)(x) = g(f(x)) is the basis of neural networks, which apply layers in sequence, and of the chain rule of calculus. The indicator function 1_A(x), which is 1 if x ∈ A and 0 otherwise, is the bridge between sets and numbers: the accuracy of a classifier is the mean of indicators, (1/n) Σ 1[predicted_i = true_i]. The listing computes the accuracy this way on six examples and builds the decision region of a tiny classifier, f(x) = [2x − 1 > 0], on nine points.

vero = np.array([1, 0, 1, 1, 0, 1])
pred = np.array([1, 0, 0, 1, 0, 1])
indicatrici = (pred == vero).astype(int)       # 1 where we guessed right
print("indicators:", indicatrici, "| accuracy = mean of the indicators =", indicatrici.mean())

regione_classe_1 = {x for x in np.linspace(-2, 2, 9) if 2 * x - 1 > 0}      # preimage of {1} for f(x) = [2x - 1 > 0]
print("decision region of class 1:", sorted(float(x) for x in regione_classe_1))

Output obtained (Python 3.14.4, NumPy 2.3.5; run twice with identical output):

indicators: [1 1 0 1 1 1] | accuracy = mean of the indicators = 0.8333333333333334
decision region of class 1: [1.0, 1.5, 2.0]

Five predictions out of six are correct, so the mean of the indicators is 5/6 ≈ 0.8333. The decision region contains the points with 2x − 1 > 0, that is x > 0.5, and among the nine chosen points they are 1.0, 1.5 and 2.0. The real model of a future lesson will be more complicated, but the whole idea is already here: a model is a function, and its classification is a subset.

Logic: implication, quantifiers, counterexamples

P ⇒ Q ("if P then Q") is false only in the case where P is true and Q is false. The truth table (V true, F false) surprises whoever has never looked at it.

If P is false the implication is true "vacuously": the promise "if it rains, I'll take the umbrella" is not broken on sunny days. From here come three facts to keep apart. The contrapositive ¬Q ⇒ ¬P is equivalent to the original: "if it rains, the road is wet" is equivalent to "if the road is dry, it is not raining", and it is useful for proving things. The converse Q ⇒ P is not equivalent to the original: "if the road is wet, it rains" is false (there is the car wash), and confusing the two is the fallacy of affirming the consequent. An example from machine learning: "if the model overfits, the error on the test set is greater than the error on the training set"; the converse ("if the test error is greater, there is overfitting") is false, because there could also be just a normal gap. The listing prints the truth table of the implication, of the contrapositive and of the converse for all four combinations.

def implica(p, q):
    return (not p) or q

print("P     Q     | P=>Q  | not-Q => not-P | converse Q=>P")
for P in (True, False):
    for Q in (True, False):
        print(f"{P!s:5} {Q!s:5} | {implica(P, Q)!s:5} | {implica(not Q, not P)!s:14} | {implica(Q, P)!s}")

Output obtained (Python 3.14.4, NumPy 2.3.5; run twice with identical output):

P     Q     | P=>Q  | not-Q => not-P | converse Q=>P
True  True  | True  | True           | True
True  False | False | False          | True
False True  | True  | True           | False
False False | True  | True           | True

In the rows, the implication column and the contrapositive column are identical, while the converse differs in the rows True False and False True. This is the mechanical check of the equivalence: two logical expressions are equivalent if they have the same column in all the rows.

Quantifiers and their negation

∀x ∈ A : P(x) says that all the elements satisfy P; ∃x ∈ A : P(x) says that at least one does. Negation swaps the two: ¬(∀x : P(x)) ⇔ ∃x : ¬P(x) and ¬(∃x : P(x)) ⇔ ∀x : ¬P(x). They are De Morgan's laws generalised to any number of terms. The negation of "the model is never wrong" (for every example, correct) is "there exists an example where it is wrong". A practical consequence for whoever tests software and models: a single counterexample is enough to refute a ∀, but no finite number of examples is enough to prove it. A thousand green tests do not prove that the code is correct; one red test proves that it is not. In Python the two quantifiers are all and any, and the listing checks that the negation of one is the other on the list of a model's errors.

errori = [False, False, True, False]            # True = the model got that example wrong

mai_sbaglia = all(not e for e in errori)         # ∀ example: it was not wrong
sbaglia_almeno_una_volta = any(errori)           # ∃ example: it was wrong
print("∀ correct:", mai_sbaglia, "| ∃ error:", sbaglia_almeno_una_volta,
      "| negation consistent:", (not mai_sbaglia) == sbaglia_almeno_una_volta)

print("all([]) =", all([]), "| any([]) =", any([]))

Output obtained (Python 3.14.4, NumPy 2.3.5; run twice with identical output):

∀ correct: False | ∃ error: True | negation consistent: True
all([]) = True | any([]) = False

The last line contains a classic trap: all([]) is True. The documentation of all states it explicitly ("or if the iterable is empty"). A ∀ over the empty set is vacuously true: "all green swans are 2 metres long" is true because there are none, so none violates the sentence. If you compute "the model guessed all the predictions" on a group with no examples you get True, and a quality test on a filter that has emptied the data by mistake passes silently. Always check that the set is not empty.

Where you will meet these ideas again

The lesson may seem abstract until you see the use, so I say right away where each idea comes back. Sets and their operations become, in the lesson on probability, events: "an even number comes up and greater than 2" is an intersection, "an even number comes up or greater than 2" is a union, "an even number does not come up" is a complement. Functions are the models: every model is a function from the feature space to the set of answers, and training it means choosing a function in a family. The logic of quantifiers returns with force in the definition of limit (∀ε ∃δ) in the lesson on calculus, and the counterexample is the mental tool for reading every general claim about a model: "it works on all cases" is refuted with a single case. The Cartesian product, finally, is the data space and the hyperparameter grid. Whoever understands these few concepts well already holds half the language of the rest of the module.

Typical mistakes

Three of these rows (the universe, the inclusive "or" and the converse) come from the same habit: reading a formula the way you read an everyday sentence, where context fills the gaps. In mathematics nothing is implicit, and for this reason it is always worth translating the formula into code and running it on a small example.

Mini-project

You have three lists of customer identifiers: newsletter, acquisti, reclami (invent them with 20-30 numbers each, with overlaps). Proceed in four steps.

1. Compute, with operations on sets, the customers who have bought but have never complained and those who are subscribed to the newsletter but have not bought.
2. Check with the inclusion-exclusion formula that |N ∪ A ∪ R| coincides with the direct cardinality.
3. Check De Morgan on these three sets, with a universe that includes all the identifiers.
4. Write a sentence, with a quantifier, that describes the case "every customer who made a complaint also made a purchase", and test it with all. What happens if reclami is empty?

The fourth step brings you back to the trap of vacuous truth, and it is the reason I put it last: if your result with reclami empty is True, you have understood the difference between "everyone follows the rule" and "there is someone who follows it". Try doing it yourself before reading the solution.

The solution puts the whole vocabulary to work on three lists of identifiers generated with a seed (default_rng(4)), so that the result is reproducible. scegli(k) draws k different identifiers between 1 and 40 (with replace=False the documentation of Generator.choice guarantees there are no duplicates) and converts them into Python integers with int(x), because a set of NumPy integers prints in a less readable way. Then each of the four blocks of the listing solves the corresponding step.

import numpy as np
from itertools import combinations

rng = np.random.default_rng(4)
universo = set(range(1, 41))                                  # 40 customers in all
scegli = lambda k: {int(x) + 1 for x in rng.choice(40, size=k, replace=False)}
newsletter, acquisti, reclami = scegli(22), scegli(18), scegli(9)
print("|N| =", len(newsletter), "| |A| =", len(acquisti), "| |R| =", len(reclami))

# 1) operations on sets
print("bought and never complained :", len(acquisti - reclami))
print("newsletter subscribers who did not buy:", len(newsletter - acquisti))

# 2) inclusion-exclusion against the direct cardinality
def incl_escl(insiemi):
    totale = 0
    for k in range(1, len(insiemi) + 1):
        for gruppo in combinations(insiemi, k):
            totale += (-1) ** (k + 1) * len(set.intersection(*gruppo))
    return totale

print("|N ∪ A ∪ R| formula:", incl_escl([newsletter, acquisti, reclami]), "| direct:", len(newsletter | acquisti | reclami))

# 3) De Morgan with an explicit universe
fuori_da_tutti = universo - (newsletter | acquisti | reclami)
print("De Morgan 1:", fuori_da_tutti == (universo - newsletter) & (universo - acquisti) & (universo - reclami))
print("De Morgan 2:", universo - (newsletter & acquisti) == (universo - newsletter) | (universo - acquisti))

# 4) quantifier: "every customer who complained also bought"
print("∀ r ∈ R : r ∈ A  ->", all(r in acquisti for r in reclami), "| counterexamples:", sorted(reclami - acquisti))
print("with R empty:", all(r in acquisti for r in set()), "(vacuously true)")

Output obtained (Python 3.14.4, NumPy 2.3.5; run twice with identical output):

|N| = 22 | |A| = 18 | |R| = 9
bought and never complained : 14
newsletter subscribers who did not buy: 14
|N ∪ A ∪ R| formula: 33 | direct: 33
De Morgan 1: True
De Morgan 2: True
∀ r ∈ R : r ∈ A  -> False | counterexamples: [12, 21, 25, 27, 39]
with R empty: True (vacuously true)

The first block uses only set differences: "bought but not complained" is acquisti - reclami. The second compares the inclusion-exclusion formula with the cardinality of the union computed directly: the two coincide (33), which is a good test of the formula. The third checks the two De Morgan laws, which require a universe to compute the complement (universo - X). The fourth translates the sentence with the quantifier into all(...) and shows the set of counterexamples (reclami - acquisti): not just "false", but which complainants did not buy, which is the information useful to whoever has to intervene. The last line recalls that on an empty set all is always true.

Challenges

• Easy. Prove that A ∖ B = A ∩ Bᶜ and check it in code for all the pairs of subsets of a universe of 4 elements.
• Medium. Prove the second De Morgan law, (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ, with a chain of equivalences, and write the exhaustive test.
• Hard. Prove that for finite sets |A × B| = |A| · |B| and that |𝒫(A)| = 2^{|A|} by induction on |A| (hint: a subset of A ∪ {a} either contains a or it does not).
• Expert. A function f : A → B between finite sets with |A| = |B|: prove that it is injective if and only if it is surjective. Why is the same statement false for infinite sets? Think of n → n + 1 on ℕ.
• Enterprise. Take two exports of the customer registry of your organisation. Using only operations on sets of keys, list the customers present in only one, those present in both and the internal duplicates. Which of these checks become critical before a Pandas merge?

The first two challenges are solved by retracing the proofs of this lesson; the third and the fourth ask for one more idea, induction and counting with a function. In the Expert challenge the surprise is precisely the infinite case: it is worth trying to build the example before looking at the solution.

In the next lesson, combinatorics, you learn to count the elements of these sets without listing them. The lesson on scikit-learn, which precedes this one, already uses these counts for the grid search of hyperparameters.

The same series also includes: 23 - Linear Algebra 1: Vectors, Matrices, Systems (which refers back to this lesson).

Sources

Bibliographic references cited but not opened for this revision: A. De Morgan, Formal Logic, 1847 (the date and the title are those given in the previous version of this article, not re-checked); P. R. Halmos, Naive Set Theory, 1960; D. J. Velleman, How to Prove It, Cambridge University Press.