Sets, relations, and discrete structures

Three documents have keyword sets: document a has “python,” b has “python” and “ai,” and c has “ai.” A grouping tool calls two documents equivalent when they share a keyword. Then a is equivalent to b, and b to c, but a is not equivalent to c. Grouping each document with an existing representative produces different results when the input order changes. The problem is mathematical before it is an implementation bug: the proposed relationship does not have the properties required of equivalence.

Sets describe collections; relations describe which pairs belong together; functions describe a special kind of relation with exactly one output per input. This module connects those ideas to record identifiers, grouping rules, and dependency orders. You will learn to name the property a rule needs and produce a concrete witness when it fails. An attractive diagram or an intuitive word such as “similar” is insufficient.

Retrieval check: translate “every pair satisfies a property,” negate “every object has a match,” and distinguish a function’s image from its codomain. Review quantifiers and functions as needed. The finite catalogues used below are teaching models; general definitions apply to larger and infinite sets too.

A set is a collection determined by its members. In the elementary sets used here, order and repetition do not matter: $\{a,b,a\}=\{b,a\}$. A list can preserve repetitions and order, so replacing a list with a set may change the problem. If a dataset contains the same observation twice, a set of its distinct values no longer records that multiplicity. The mathematical representation must match the quantity you intend to study.

Write $x\in A$ for membership and $x\notin A$ for nonmembership. The statement $A\subseteq B$ means $\forall x,\ x\in A\Rightarrow x\in B$; it permits equality. A proper subset, written here $A\subsetneq B$, additionally requires $A\ne B$. Membership compares an object with a collection of objects, while inclusion compares two sets by their members. When the members are themselves sets, both questions are possible and should be asked separately.

The empty set $\varnothing$ has no members. It is a subset of every set: no element violates the inclusion implication. It is not automatically an element of every set. For $A=\{a,b\}$, $\varnothing\subseteq A$ is true and $\varnothing\in A$ is false. For $B=\{\varnothing,a\}$, both statements are true. This distinction often prevents errors when using collections of possible subsets.

Union $A\cup B$ contains members of either set; intersection $A\cap B$ contains members of both; difference $A\setminus B$ contains members of $A$ outside $B$. A complement is always relative to a declared universe $U$: $A^c=U\setminus A$, assuming $A\subseteq U$. Without $U$, the word “everything else” is incomplete. A catalogue complement means other catalogue items, not every conceivable object.

The power set $\mathcal{P}(A)$ is the set of every subset of $A$. For $A=\{a,b,c\}$ it contains $\varnothing$, the three singleton sets, the three two-element sets, and $A$ itself: eight members. Each original element either belongs or does not belong to a chosen subset. A finite $n$-element set therefore has $2^n$ subsets; Module 05 develops the counting rule systematically. Note that the power set contains sets as elements, rather than merely repeating the members of $A$.

The Cartesian product $A\times B$ contains ordered pairs $(a,b)$ with $a\in A$ and $b\in B$. Order matters here because the first coordinate has a designated role. For request set $D$ and reviewer set $V$, $D\times V$ is the collection of candidate request–reviewer assignments. The reversed product describes reviewer–request pairs with different coordinate roles. If either factor is empty, there are no pairs and the product is empty.

Python uses set() for the empty set, because {} creates a dictionary. Set elements must be hashable; a mathematical set of sets can be represented using frozenset elements, while a mutable Python set cannot itself be a set member. These representation rules are programming constraints, not changes to membership mathematics. Printed set order is not guaranteed, so the labs sort elements when presenting reproducible outputs.

Two sets are equal exactly when they have the same members. To prove $A=B$, show that an arbitrary object belongs to $A$ if and only if it belongs to $B$. Alternatively, prove both inclusions $A\subseteq B$ and $B\subseteq A$. Checking the number of members alone is insufficient: different sets can have equal cardinality. Checking one chosen member is insufficient unless the entire domain is that one member.

Membership definitions connect set operations to the logic from Module 02. $x\in A\cap B$ means $(x\in A)\land(x\in B)$, while $x\in A\cup B$ means their inclusive disjunction. If $x\in U$, membership in $A^c$ means $x\notin A$. A set identity can therefore follow from a logical equivalence applied to each arbitrary candidate member, without relying on the sets being small enough to list.

For complements relative to a common universe, De Morgan’s laws give $(A\cup B)^c=A^c\cap B^c$ and $(A\cap B)^c=A^c\cup B^c$. The common universe is a hypothesis. Comparing a complement over a training catalogue with a complement over all records would change the candidate members and could invalidate the equality. Carrying the universe explicitly is particularly useful in database filtering and data-split descriptions.

Difference satisfies $A\setminus B=A\cap B^c$ within that universe. It is generally not commutative. Symmetric difference $(A\setminus B)\cup(B\setminus A)$ does commute, because it selects members appearing in exactly one set. A report of changed identifiers may need symmetric difference, whereas a report of identifiers removed from A needs only $A\setminus B$. Similar names do not guarantee interchangeable operations.

A diagram can communicate an identity by shading regions, but the diagram alone does not explain every assumption. In a two-set membership table there are four regions: neither, A only, B only, and both. A set expression selects some of these regions. Comparing its selections across all regions provides a finite logical proof for the membership expression; drawing a few sample points merely illustrates it. State which kind of evidence you are giving.

When proving inclusion, a useful writing pattern is “take any $x\in A$; by the definitions and assumptions, it follows that $x\in B$.” The argument should not start by assuming $x\in B$ unless you are proving the reverse direction or an equivalence with reversible steps. An inclusion proof may use extra hypotheses, for example $A\subseteq B$ and $B\subseteq C$ to conclude $A\subseteq C$. Those hypotheses should remain visible.

The labs inspect all subsets of one three-element universe. Their results are a useful check on the implementation and on your prediction. They do not by themselves prove identities for every conceivable set. The arbitrary-member argument above covers the general statement, including infinite sets. A successful computation and a general proof can support each other while answering different questions.

A binary relation from $A$ to $B$ is a subset $R\subseteq A\times B$. It selects which candidate ordered pairs hold. Write $xRy$ as shorthand for $(x,y)\in R$. A relation on $D$ has $R\subseteq D\times D$, allowing properties that compare objects of the same kind. A Boolean table can represent a finite relation: rows are first coordinates, columns are second coordinates, and a true cell records membership in R.

Four properties recur. Reflexive means $\forall x\in D,\ xRx$. Symmetric means $\forall x,y\in D,\ xRy\Rightarrow yRx$. Antisymmetric means $\forall x,y\in D,\ (xRy\land yRx)\Rightarrow x=y$. Transitive means $\forall x,y,z\in D,\ (xRy\land yRz)\Rightarrow xRz$. Each is a quantified conditional or membership requirement, so its failure has a specific witness shape.

A missing diagonal pair witnesses failed reflexivity. A pair present in one direction but absent in the reverse witnesses failed symmetry. Two distinct objects related in both directions witness failed antisymmetry. A chain $xRy$ and $yRz$ with missing $xRz$ witnesses failed transitivity. A property is not disproved by any unusual-looking pair; its exact quantified rule must be violated.

Antisymmetry does not mean “never symmetric.” It permits both directions for the same object, and it does not require any direction between distinct objects. Equality is both symmetric and antisymmetric: whenever two objects are related they are equal, so a distinct mutual pair never occurs. A relation may also have neither property. The names should be learned through their formulas rather than through a loose interpretation of the prefix “anti.”

The keyword rule from the opening is another transitivity failure: a shares with b, b shares with c, and a shares nothing with c. Symmetry alone cannot fix it. Reflexivity also needs care: a document with no keywords would share no keyword even with itself, so the rule is not reflexive on a domain including such a document. A domain restricted to documents with nonempty keyword sets removes that particular failure but leaves the transitivity problem.

Relations can be empty or universal. On a nonempty D, the empty relation is not reflexive, but is symmetric, antisymmetric, and transitive: the relevant antecedents never hold. The universal relation $D\times D$ is reflexive, symmetric, and transitive; it is antisymmetric only when D has at most one member. On an empty D, all four properties hold vacuously. These edge cases are direct applications of quantified logic.

Properties should be tested against the declared domain, even when some domain objects never occur in a stored pair. If a table omits an object, checking reflexivity only for objects already present can miss its missing diagonal. The lab receives the domain separately from the pair set. For a general theorem, show why every relevant pair or triple obeys the rule; for a finite table, complete enumeration can establish the properties of that particular relation.

An equivalence relation is reflexive, symmetric, and transitive. It formalises a chosen meaning of “the same for this purpose.” Literal equality is one example, but two distinct records may be equivalent under a declared key. The equivalence statement concerns that key or representation; it does not automatically prove that the underlying people, events, or physical objects are identical.

For an equivalence relation on D, the equivalence class of x is $[x]=\{y\in D:xRy\}$. Reflexivity gives $x\in[x]$, so classes are nonempty. If $y\in[x]$, symmetry and transitivity imply $[y]=[x]$. Thus any member may serve as a representative of the class without changing which objects it contains. Representatives label a class; they do not create a different class each time.

Why can two classes not partially overlap? Suppose $z\in[x]\cap[y]$. Then $xRz$ and $yRz$, so symmetry gives $zRy$ and transitivity gives $xRy$. For any $u\in[x]$, symmetry gives $yRx$ and transitivity with $xRu$ gives $yRu$, so $u\in[y]$. The reverse inclusion follows the same way. Hence overlapping classes are equal. This is the key mathematical protection missing from the keyword grouping rule.

The distinct equivalence classes therefore form a partition of D: nonempty blocks, pairwise disjoint, whose union is D. Every object is in its own class by reflexivity, so the blocks cover the domain. Conversely, a partition defines equivalence by “belongs to the same block.” That relation is reflexive, symmetric, and transitive because block membership is unique. The two descriptions express the same structure from different directions.

The quotient set $D/R$ is the set of distinct equivalence classes. Its elements are classes, not individual representatives, though a program may store a convenient representative label. A computation on representatives is meaningful on the quotient only if changing representative within a class cannot change the result’s class or value as intended. Later modular arithmetic will use this condition to justify operations on residues.

Equality of a deterministic key produces an equivalence relation: $xRy$ when $k(x)=k(y)$. Equality supplies all three axioms. For example, stripping surrounding spaces and case-folding a name groups labels according to an explicit normalisation rule. That rule may merge two different people with the same name or collapse a distinction needed by the application. Mathematical equivalence of labels and suitability of the chosen key are separate questions.

If a similarity rule lacks transitivity, avoid calling its output equivalence classes. You could choose another clustering objective, or use connectivity through chains, but the latter changes the rule: a and c may become connected through b even though they share no keyword. The chosen repair should be declared and evaluated for its purpose. A programmer should not silently take a transitive closure and still describe the result as direct similarity.

A partial order on D is reflexive, antisymmetric, and transitive. Write $x\preceq y$ for it. Unlike equivalence, it describes an ordering relationship rather than interchangeable membership. Comparable means $x\preceq y$ or $y\preceq x$. A total order is a partial order in which every pair is comparable. “Partial” permits incomparable pairs; it does not mean the three axioms hold only sometimes.

Set inclusion is a partial order on a power set. Every set includes itself; mutual inclusion gives equality; inclusion chains compose. On $\mathcal{P}(\{a,b\})$, singleton sets $\{a\}$ and $\{b\}$ are incomparable: neither includes the other. An implementation that assigns both a numerical position in a sorted list has chosen an additional ordering, not discovered an inclusion relation between them.

A Hasse diagram for a finite partial order omits self-loops and edges already implied by transitivity. It draws a cover edge from x upward to y when $x\prec y$ and no domain object lies strictly between them. Upward paths represent the other comparisons. Omitting an edge does not make its comparison false if an upward path still exists. Conversely, objects without an upward path in either direction are incomparable in the diagram.

A least element is below every domain element. A minimal element has no distinct element below it. A least element is necessarily minimal, but a minimal element need not be least when some objects are incomparable. There can be multiple minimal elements, while a least element is unique if it exists: two least elements would be related both ways, so antisymmetry would make them equal. Greatest and maximal are the corresponding reversed notions.

Consider the domain containing only $\{a\},\{b\},\{a,b\}$, ordered by inclusion. Both singletons are minimal; neither is least because each fails to be below the other. The full set is greatest. This example shows why a rule demanding “the smallest eligible item” needs a tie or incomparability policy. A partial order may not supply a unique choice without extra information.

Strict order notation removes equality: $x\prec y$ means $x\preceq y$ and $x\ne y$. For a partial order this strict relation is irreflexive and transitive. It is not itself reflexive, so do not classify $<$ as a non-strict partial order using the three earlier axioms. Conversely, a suitable strict order can be converted to a non-strict one by adding equality. State which convention is being used before checking its properties.

Dependencies often lead to partial orders through reachability: an object precedes another if it is the same object or has a directed path to it. To get antisymmetry for distinct objects, directed cycles must be excluded. Module 07 will develop graphs and topological ordering. For now, distinguish a direct dependency pair from its transitive reachability relation. A direct-edge list need not itself be transitive even when the overall dependency structure has a meaningful order.

Equivalence and order can coexist in an application but answer different questions. Grouping equal labels may give equivalence classes; ordering those groups by a prerequisite relation is another structure. Equality itself is both an equivalence and a partial order, though it is total only on domains of at most one element. This is another reason to read the axioms instead of assuming the categories can never overlap.

A function $f:A\to B$ can be represented by its graph $G_f=\{(x,f(x)):x\in A\}$, a subset of $A\times B$. It is a special relation because for every input in A there is exactly one output in B. A relation may have no output or several outputs for a given input, so not every relation is a function. Declaring A and B remains essential even when a graph is listed.

A function is injective when $f(x)=f(y)$ implies $x=y$ for all inputs. Distinct inputs must have distinct outputs; every attained output identifies at most one input. It is surjective onto B when every $b\in B$ has some $x\in A$ with $f(x)=b$. That property depends on the declared codomain. A function is bijective when both conditions hold, so every codomain member has exactly one preimage.

The inverse relation reverses every pair of $G_f$. It defines a function on B exactly when f is bijective: surjectivity supplies an output for every inverse input, and injectivity ensures uniqueness. An injective function can instead have an inverse defined only on its image. If f is not injective, the reversed relation has multiple outputs for some input, so selecting one would require an extra rule rather than being the unique inverse.

For the real square function, $f(-2)=f(2)=4$, so it is not injective. Restricting the domain to nonnegative reals makes it injective and surjective onto the nonnegative reals, with inverse square root. This restriction is a mathematical choice. A feature mapping that drops an attribute can likewise lose distinctions between records. A later algorithm cannot reconstruct those distinctions uniquely from the feature value alone without extra information or assumptions.

An identifier key intended to identify every stored record uniquely should be injective on the record domain. It need not be surjective onto every possible identifier string: unused identifiers are normal. A label mapping may intentionally be many-to-one, because multiple records belong to the same class. Treating a label as a unique identifier would confuse these two purposes. The required property follows from the specification rather than from the word “mapping.”

Cardinality comparisons can be expressed by mappings. For finite sets, an injection A to B shows A has at most as many members as B; a bijection shows equal size. Equal finite sizes do not make every mapping bijective: a function may collide on two inputs and omit an output. You still need to inspect the actual rule. For infinite sets, a proper subset may have a bijection with the original set, so finite intuitions about “strictly fewer” do not transfer automatically.

A brief countability preview illustrates this. The map $n\mapsto2n$ is a bijection from the natural numbers, including zero, to the even natural numbers, despite the latter being a proper subset. The integers can be listed as $0,1,-1,2,-2,\ldots$, and the rational numbers can be listed by organising integer numerators and positive denominators and skipping duplicates. These sets are countably infinite. The real numbers are uncountable; a full diagonal argument is deferred as further proof practice, not required for the labs here.

The lesson’s practical exit skill is to inspect a declared mapping, state what information it preserves, and determine whether a reversal is unique and total on the intended domain. Relations, equivalence classes, and orders give other ways to represent structure when a single reversible mapping is not appropriate. Choose the object matching the question before choosing an algorithm to process it.

Use Python 3.11 or later and the Python primer if needed. No packages are required. &, |, and - on sets mean intersection, union, and difference; they are not scalar arithmetic in these expressions. Explain predicted results, observed structure, and a fault or variation for each lab. Allocate ten explanation points per lab: 3 for prediction, 4 for interpretation, 3 for diagnosis.

Forty minutes: list the eight subsets of {0,1,2}, predict the number of ordered triples of subsets, and run the script. It compares distributivity and a complement identity on every triple in this one universe. Explain why there are 512 triples, why the output sorts elements, and why the general proof still needs an arbitrary-member argument. Replace the right-hand intersection in De Morgan’s law with union; preserve a failing A,B pair and repair it.

Download lab1_set_identities.py

"""Exhaustive checks over one small universe, not a general set-theoretic proof."""
from itertools import combinations, product


def subsets(items):
    return [set(part) for k in range(len(items) + 1) for part in combinations(items, k)]


def main():
    universe = {0, 1, 2}
    choices = subsets(sorted(universe))
    print("Power set:", [sorted(s) for s in choices])
    checks = 0
    for a, b, c in product(choices, repeat=3):
        assert a & (b | c) == (a & b) | (a & c)
        assert universe - (a | b) == (universe - a) & (universe - b)
        checks += 1
    print("Distributivity and De Morgan agree for", checks, "triples in this universe.")
    a, b = {0, 1}, {1, 2}
    print("A union B:", sorted(a | b), "intersection:", sorted(a & b))
    print("A minus B:", sorted(a - b), "B minus A:", sorted(b - a))
    print("{} is a dict; set() is an empty set.")
    print("General identities still require a proof for arbitrary membership.")


if __name__ == "__main__":
    main()

Power set: [[], [0], [1], [2], [0, 1], [0, 2], [1, 2], [0, 1, 2]]
Distributivity and De Morgan agree for 512 triples in this universe.
A union B: [0, 1, 2] intersection: [1]
A minus B: [0] B minus A: [2]
{} is a dict; set() is an empty set.
General identities still require a proof for arbitrary membership.

Forty minutes: predict all four properties for equal parity, distance at most one, $\le$, and $<$. Run the classifier and read each returned witness against the exact definition. Modify the domain to (0,1,2,3) and predict a new witness before execution. The identity relation’s final check demonstrates that symmetry and antisymmetry can coexist. The explorer above lets you create missing diagonal, reverse-pair, and transitivity failures directly.

Download lab2_relations.py

"""Return one explicit witness for each failed property on a finite domain."""
from itertools import product


def failures(domain, relation):
    pairs = list(product(domain, repeat=2))
    triples = product(domain, repeat=3)
    return {
        "reflexive": next(((x, x) for x in domain if (x, x) not in relation), None),
        "symmetric": next(((x, y) for x, y in pairs if (x, y) in relation and (y, x) not in relation), None),
        "antisymmetric": next(((x, y) for x, y in pairs if x != y and (x, y) in relation and (y, x) in relation), None),
        "transitive": next(((x, y, z) for x, y, z in triples if (x, y) in relation and (y, z) in relation and (x, z) not in relation), None),
    }


def main():
    domain = (0, 1, 2)
    rules = {
        "same parity": lambda x, y: x % 2 == y % 2,
        "distance at most one": lambda x, y: abs(x - y) <= 1,
        "less than or equal": lambda x, y: x <= y,
        "strictly less": lambda x, y: x < y,
    }
    for name, rule in rules.items():
        relation = {(x, y) for x, y in product(domain, repeat=2) if rule(x, y)}
        result = failures(domain, relation)
        print(name)
        for property_name, witness in result.items():
            print(" ", property_name + ":", "holds" if witness is None else f"fails at {witness}")
    identity = {(x, x) for x in domain}
    assert all(witness is None for witness in failures(domain, identity).values())
    print("Identity is both symmetric and antisymmetric.")


if __name__ == "__main__":
    main()

same parity
  reflexive: holds
  symmetric: holds
  antisymmetric: fails at (0, 2)
  transitive: holds
distance at most one
  reflexive: holds
  symmetric: holds
  antisymmetric: fails at (0, 1)
  transitive: fails at (0, 1, 2)
less than or equal
  reflexive: holds
  symmetric: fails at (0, 1)
  antisymmetric: holds
  transitive: holds
strictly less
  reflexive: fails at (0, 0)
  symmetric: fails at (0, 1)
  antisymmetric: holds
  transitive: holds
Identity is both symmetric and antisymmetric.

Forty minutes: predict the normalised-name groups and the two greedy keyword groupings. Run and explain the different results. Equality of a fixed key forms equivalence classes, while direct shared-keyword similarity does not. Do not describe normalised names as verified personal identity. As a variation, add a fifth record with name “Ada” but representing another person; explain why the code remains mathematically correct for its key and unsuitable for identifying people.

Download lab3_grouping.py

"""Equality of a declared key is an equivalence; shared keywords need not be."""


def main():
    records = (("r1", "Ada"), ("r2", " ADA "), ("r3", "Lin"), ("r4", "LIN"))
    groups = {}
    for identifier, name in records:
        key = name.strip().casefold()
        groups.setdefault(key, []).append(identifier)
    print("Groups by stripped, case-folded name:", groups)
    print("This key defines equality of labels, not proof of personal identity.")
    keywords = {"a": {"python"}, "b": {"python", "ai"}, "c": {"ai"}}

    def related(x, y):
        return bool(keywords[x] & keywords[y])

    print("a~b:", related("a", "b"), "b~c:", related("b", "c"), "a~c:", related("a", "c"))
    assert related("a", "b") and related("b", "c") and not related("a", "c")

    def greedy(order):
        result = []
        for item in order:
            for group in result:
                if related(item, group[0]):
                    group.append(item)
                    break
            else:
                result.append([item])
        return result

    print("Representative grouping, order a,b,c:", greedy(("a", "b", "c")))
    print("Representative grouping, order b,a,c:", greedy(("b", "a", "c")))
    print("Repair: use an explicit equivalence key or declare a different clustering objective.")


if __name__ == "__main__":
    main()

Groups by stripped, case-folded name: {'ada': ['r1', 'r2'], 'lin': ['r3', 'r4']}
This key defines equality of labels, not proof of personal identity.
a~b: True b~c: True a~c: False
Representative grouping, order a,b,c: [['a', 'b'], ['c']]
Representative grouping, order b,a,c: [['b', 'a', 'c']]
Repair: use an explicit equivalence key or declare a different clustering objective.

Exercises 1–12 have a 110-minute budget and five points each. The optional pair adds 25 minutes. For a failed property, give inputs satisfying the premise and violating the conclusion. For a proof, state the domain and use an arbitrary member or complete logical argument.

Complete nine automatically checked choices and one written explanation. Review the definitions when feedback identifies a confusion; a familiar name does not replace its quantified rule.

Required, 15 minutes: in the textbook linked by MIT Mathematics for Computer Science, read the elementary set and binary-relation definitions. Rewrite one membership identity using logical connectives and compare the use of subset notation.

Required, 20 minutes: read its equivalence-relation and partial-order discussions. Write their axiom lists side by side and explain which axiom changes the purpose. Draw the four-object inclusion diagram yourself. Advanced countability is optional here.

Optional: use the official Python set documentation to compare mutable sets with frozenset and to distinguish empty-set construction from an empty dictionary. All diagrams and teaching examples here are original.

Membership gives set operations; arbitrary-member arguments establish identities. Relations select pairs, and quantified axioms determine which structures they represent. Equivalence gives partitions into interchangeable blocks. Partial orders give comparisons that may leave some objects incomparable. Functions add unique outputs; bijections permit unique reversal on the whole codomain.

Exit task: prove one complement identity, classify a three-object relation with concrete failure witnesses, draw a Hasse diagram with an incomparable pair, and determine whether a listed function has a total inverse. Use exercises 60, lab explanations 30, and quiz 10 including the reviewed written point. Explain any failed prerequisite after correction.

Module 04 develops direct proofs, contradiction, induction, and program invariants. Its starting skill is to take an arbitrary object, use the relevant definitions, and state a conclusion whose scope matches the argument. Keep the membership and parity proofs as examples of that pattern.