CS2050 L09 Set Theory
Watch on YouTube →
Overview
Abrahim Ladha develops the set-theory definitions used throughout CS2050, connecting set-builder notation and membership to logic, then deriving equality, subsets, products, and set operations. Examples include constructing the rationals, representing functions and graphs as sets, proving De Morgan's law by double containment, and showing every integer can be written as 5a + 2b for integers a and b.
Key takeaways
- Extensionality makes two sets equal precisely when they have the same elements, which yields the general double-containment proof method.
- Set-builder notation turns a logical predicate over a specified universe into a set; the rational numbers are characterized by integer fractions a/b with b ≠ 0.
- The empty set is a subset of every set because its defining subset condition is vacuously true, and extensionality proves that the empty set is unique.
- Cartesian products encode order with tuples, enabling formal set representations of the plane, functions, and graph edges.
- Intersection and union correspond to logical AND and inclusive OR, while complement corresponds to negation; these connections support proofs such as De Morgan's law.
- To prove {5a + 2b : a, b ∈ ℤ} = ℤ, use closure for one inclusion and the explicit choice a = x, b = −2x for the other.
Chapters
- A set formalizes a collection of mathematical objects and is conventionally named with a capital letter such as S.
- Curly braces list set elements, while ∈ means “is an element of”; for example, 2 ∈ S can be true while 4 ∈ S is false.
- Sets can contain other sets, so {2} ∈ S and 2 ∈ S are distinct claims.
- Sets contain unique elements and ignore order, properties later derived from the definition of set equality.
- A universe of discourse specifies which objects are under consideration and can be represented as a set.
- Common notation includes ℕ for natural numbers, ℤ for integers, and U or Ω for a generic universe.
- For this course, 0 is treated as a natural number, though conventions vary across mathematical traditions.
- Interpreting “x is a natural number” resembles declaring an object's type in a programming language.
- Set-builder notation defines objects satisfying a predicate within a specified universe: x belongs to the universe such that a condition holds.
- The rationals can be defined as fractions a/b where a and b are integers and b ≠ 0, avoiding an ambiguous ellipsis-based list.
- A rational can have multiple representations, such as −1/−1 and 1, even though they denote the same value.
- Ladha notes that specifying real-number properties does not itself prove the reals exist; a rigorous construction is substantially more involved.
- The axiom of extensionality defines A = B exactly when every object belongs to A if and only if it belongs to B.
- A is a subset of B, written A ⊆ B, when every element of A is also an element of B.
- Set identity depends on elements rather than the set's name or the order in which its elements are listed.
- The same definitions explain why {2, 3} and {3, 2} represent the same set.
- Comprehension constructs the empty set by selecting a predicate that is always false, such as x ≠ x.
- The empty set, written ∅ or with a slashed zero symbol, has no elements and is not the number 0.
- For every set S, ∅ ⊆ S because the subset condition has no counterexample to check; this is vacuous truth.
- The lecture distinguishes having zero elements from being the unique set that has zero elements.
- Extensionality yields a practical equality test: A = B if and only if A ⊆ B and B ⊆ A.
- To prove two sets equal, prove both inclusions separately by taking an arbitrary element from each set.
- Any two empty sets are subsets of one another, so double containment proves they are equal.
- The same reasoning establishes basic facts such as S ⊆ S and that S ⊆ ∅ forces S = ∅.
- A is a strict subset of B when A ⊆ B but A ≠ B.
- If A is a strict subset of B, at least one element belongs to B but not A.
- The familiar hierarchy is ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ ⊆ ℂ, with each inclusion strict.
- Unlike numerical order, subset inclusion does not compare every pair of sets.
- The Cartesian product A × B contains ordered pairs (a, b) with a ∈ A and b ∈ B.
- Unlike ordinary set elements, ordered pairs distinguish position, so (a, b) generally differs from (b, a).
- The Cartesian plane ℝ² is the product ℝ × ℝ, the set of ordered pairs of real numbers.
- Nested Cartesian products are formally sensitive to grouping, so (A × B) × C and A × (B × C) encode differently nested tuples.
- A function such as y = x² can be represented by the set of real pairs (x, y) satisfying y = x².
- A graph can be specified by a vertex set V and an edge set E drawn from V × V.
- The lecture's simple-graph example excludes self-loops and benefits from set membership's uniqueness of elements.
- Ordered pairs support directed edges; an undirected relationship requires care because (u, v) and (v, u) are distinct ordered pairs.
- A ∩ B contains elements that are in both A and B, mirroring logical AND.
- A ∪ B contains elements in A or B, where OR is inclusive, so a shared element appears only once.
- For example, {1, 2, 3} ∩ {3, 4} = {3}, while their union is {1, 2, 3, 4}.
- If A ⊆ B, then A ∪ B = B and A ∩ B = A.
- Set inclusion is a partial order: sets such as {1, 2} and {1, 3} are neither subsets of each other nor disjoint.
- The complement of A contains elements of the universe of discourse that are not in A.
- For any A, A ∪ Aᶜ is the entire universe and A ∩ Aᶜ is empty.
- These identities follow directly from the logical relationships between a predicate and its negation.
- Intervals can be combined through indexed intersections or unions, extending finite set operations to infinite families.
- The intersection of intervals from 0 through 1/i for every positive integer i is {0}: every interval contains 0, while any positive x is eventually excluded.
- An indexed union such as ⋃ᵢ₌₀∞ {i, i + 1} combines the listed two-element sets.
- Unlike an infinite logical conjunction written as one formula, indexed set operations remain defined relative to a specified universe.
- The target identity is (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ.
- For the first inclusion, an element outside A ∪ B must be outside both A and B, placing it in Aᶜ ∩ Bᶜ.
- For the reverse inclusion, an element outside both A and B cannot belong to their union, so it belongs to (A ∪ B)ᶜ.
- The proof uses two element-by-element arguments rather than relying only on a remembered set identity.
- Define S = {5a + 2b : a, b ∈ ℤ}; closure of integer addition and multiplication gives S ⊆ ℤ.
- For the reverse inclusion, take any integer x and choose a = x and b = −2x.
- Then 5a + 2b = 5x − 4x = x, proving every integer belongs to S and therefore S = ℤ.
- The construction provides explicit coefficients for each x; for example, a = 3x and b = −5x is another valid choice.
Transcript excerpt
0:00 All right. So this is CS 2050. The topic of today is set theory. Now what is set theory? So what is a set? Today is basically not going to be full of like uh I would say like the interesting parts of sets or set theory but it will be kind of the definitions we need for the remainder of the class because all of mathematics can be built upon set theory. We'll talk about the power of set theory um next time. for now. Essentially a set every mathematical concept [clears throat] or object models some kind of mental or abstract uh thing. And so like for example we may associate for the intuitive notion of a quantity uh with uh that of a number which is a formal concept.
0:48 A collection may be formalized as that of a set. That's kind of vague and that's exactly what gives set theory its power cuz everything is kind of like a collection, right? If you have a bunch of things, that's now a set. If you change what those things are, that's now a different set. That's basically all what set theory is. Uh notationally, we use this mustache bracket to denote the opening of a set. We list out a sequence of objects and we use uh the closed mustache brackets to denote the ending of the set. So this is a set and sets are commonly denoted with capital letters. So we'll just maybe we'll say S for set. A set is just a box with things in it. That's it. That's the whole concept. Um but I mean again that sounds pretty simple but it it ends up being
1:37 really surprisingly rich. There is a relation we define on a set no for this uh this
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Abrahim Ladha.