Mastering Set Theory: From Filters to Functions in PMA3014

Introduction to Set Theory in PMA3014

Set theory forms the backbone of modern mathematics. In the PMA3014 course, you'll encounter powerful concepts like unions over collections, symmetric difference, filters on natural numbers, and function-induced maps. These ideas are not just abstract—they appear in computer science, data analysis, and even AI algorithms. In this tutorial, we'll break down each exercise step by step, using analogies from trending topics like gaming leaderboards and AI training data to make the concepts stick. Whether you're studying for your set theory homework or preparing for exams, this guide will help you understand the logic behind the proofs.

Exercise 11(i): Distributing Cartesian Product Over Union

Let S be a set of sets and X be another set. We need to show that (⋃ S) × X = ⋃ {S × X | S ∈ S}. This is like saying: if you take the union of all sets in S, then pair every element with every element of X, it's the same as first pairing each S with X and then taking the union of those products.

Proof: Let (a, b) ∈ (⋃ S) × X. Then a ∈ ⋃ S, so a ∈ S for some S ∈ S, and b ∈ X. Hence (a, b) ∈ S × X, so (a, b) ∈ ⋃ {S × X | S ∈ S}. Conversely, if (a, b) ∈ ⋃ {S × X | S ∈ S}, then (a, b) ∈ S × X for some S ∈ S, so a ∈ S ⊆ ⋃ S and b ∈ X, so (a, b) ∈ (⋃ S) × X. Thus equality holds.

This property is analogous to how in a gaming tournament, the set of all players (union of teams) paired with their scores (X) equals the union of each team's player-score pairs.

Exercise 11(ii): Symmetric Difference and Intersection

We prove A ∩ (B △ C) = (A ∩ B) △ (A ∩ C). Recall B △ C = (B \ C) ∪ (C \ B). Using element chasing: x ∈ A ∩ (B △ C) iff x ∈ A and (x ∈ B \ C or x ∈ C \ B). This is equivalent to (x ∈ A ∩ B and x ∉ C) or (x ∈ A ∩ C and x ∉ B). But note that when x ∈ A ∩ B and x ∉ C, then x ∈ (A ∩ B) \ (A ∩ C). Similarly, the other case gives x ∈ (A ∩ C) \ (A ∩ B). Hence x ∈ (A ∩ B) △ (A ∩ C). The reverse inclusion is similar.

This identity is useful in probability and data science when you need to compute overlaps and differences in datasets.

Exercise 12: Filters on Natural Numbers

A filter F on X is a collection of subsets of X that is non-empty, does not contain the empty set, is closed under finite intersections, and is upward closed. Here X = N, and we define n≤ = {m ∈ N : n ≤ m} for each n ∈ N. Let F = { Y ⊆ N : ∃ n ∈ N with n≤ ⊆ Y }. We show F is a filter.

• Non-empty: For any n, n≤ ⊆ N, so N ∈ F.
• ∅ ∉ F: Because any n≤ is infinite, so no finite set can contain an n≤; ∅ contains no n≤.
• Closed under intersection: If Y, Z ∈ F, then ∃ n, m such that n≤ ⊆ Y and m≤ ⊆ Z. Let k = max(n, m). Then k≤ ⊆ n≤ ∩ m≤ ⊆ Y ∩ Z, so Y ∩ Z ∈ F.
• Upward closed: If Y ∈ F and Y ⊆ Z, then ∃ n with n≤ ⊆ Y ⊆ Z, so Z ∈ F.

Thus F is a filter, known as the Fréchet filter or cofinite filter. In AI, filters are used to define 'large' sets of data points, similar to how a filter on natural numbers captures 'almost all' numbers.

Exercise 13: Function-Induced Maps

Let f: Z → Y be a function. Define φ: X^Y → X^Z by φ(g) = g ∘ f. This is well-defined because composition of functions yields a function from Z to X.

(ii) If f is surjective, then φ is injective.

Suppose φ(g1) = φ(g2). Then g1 ∘ f = g2 ∘ f. For any y ∈ Y, since f is surjective, ∃ z ∈ Z with f(z) = y. Then g1(y) = g1(f(z)) = g2(f(z)) = g2(y). Hence g1 = g2, so φ is injective.

(iii) If φ is injective, what can we say about f?

We claim that φ injective implies f is surjective. Proof by contrapositive: if f is not surjective, then there exists y0 ∈ Y \ f(Z). Define two functions g1, g2: Y → X that differ only at y0. Then g1 ∘ f = g2 ∘ f because they agree on all points in f(Z). Hence φ(g1) = φ(g2) but g1 ≠ g2, so φ is not injective. Therefore, φ injective ⇒ f surjective.

This result is crucial in category theory and functional programming, where such maps correspond to contravariant functors.

Connecting Set Theory to Current Trends

Set theory isn't just for math majors. In 2026, with the rise of AI agents and large language models, set operations like union, intersection, and filters are used to manage training data, define attention masks, and construct knowledge graphs. For example, the symmetric difference identity helps in comparing two versions of a dataset. Filters appear in machine learning when we consider 'confidence filters' that only keep predictions above a threshold. The function-induced map φ is analogous to how a neural network layer transforms input spaces.

By mastering these exercises, you're not only acing your PMA3014 homework but also building a foundation for advanced topics in computer science and data science.

Study Tips for Set Theory

• Draw Venn diagrams for symmetric difference and intersection.
• Practice element chasing proofs step by step.
• Understand the intuition behind filters: they are like 'large' sets.
• For function-induced maps, think of composition as 'preprocessing'.

Remember, set theory is a language. The more you practice, the more fluent you become.