CPBS 7620 - Lecture 1 - Sets
Watch on YouTube →
Overview
Nicholas Dwork introduces sets as collections of distinct elements and explains membership, set operations, subset relations, intervals, and ordered sets. He demonstrates proving that the even integers equal the integers whose squares are even, then connects Cartesian products and line segments to the definition of convexity in R^n.
Key takeaways
- Set equality can be established by showing each set is a subset of the other, a method demonstrated for even integers and integers whose squares are even.
- A set ignores element order, but an ordered set preserves it, so (1, 2, 5) differs from (1, 5, 2).
- Interval notation encodes endpoint inclusion: [a, b] includes both endpoints, while (a, b) excludes both; parentheses can also denote ordered pairs, so context must resolve ambiguity.
- The Cartesian product R × R defines R² as ordered pairs of real numbers, and repeating that product n times defines Rⁿ.
- The parameterization (1 − γ)X + γY traces the line segment from X to Y as γ ranges from 0 to 1.
- Convexity requires every line segment connecting two points in a set to remain entirely within the set; boundedness is not required.
Chapters
- Sets use curly braces and contain distinct elements; order does not matter, so {5, 2, 3} equals {2, 3, 5}.
- Membership notation distinguishes elements such as 2 in A from 8 not in A; examples include the empty set and the infinite set of integers.
- Union collects elements in either set, intersection keeps elements shared by both, and complement contains elements outside a set.
- Set-builder notation describes intervals, such as real x satisfying 0 < x < 1.
- A is a subset of B when every element of A belongs to B; equality follows by proving both subset directions.
- Dwork proves that the even integers equal the integers n for which n squared is even, using an even-number representation and a contradiction based on odd integers.
- Proofs should use complete sentences and clear reasoning; symbols such as ∀, ∃, ⇒, and iff abbreviate common logical statements.
- Ordered sets distinguish sequences such as (1, 2, 5) and (1, 5, 2); intervals use brackets for included endpoints and parentheses for excluded endpoints.
- The Cartesian product X × Y contains ordered pairs (x, y) with x in X and y in Y; R² is R × R, and Rⁿ repeats the real-number product n times.
- For X and Y in Rⁿ, the line segment between them consists of (1 − γ)X + γY for γ in the inclusive interval [0, 1].
- A set is convex when the segment between every pair of its points stays inside the set, including unbounded examples.
- Formally, C is convex if for all X and Y in C, the line segment connecting them is a subset of C.
Transcript excerpt
0:00 Hi, my name is Nicholas Towork. This is the first lecture of Mathematical Foundations of Machine Learning and Computation, and today we're going to be talking about sets. A set is the most fundamental mathematical entity. It's definition, a collection of distinct elements. This is a very fuzzy definition. We're going to use our intuition to understand what a set is, and then we'll see how to work with one. So, here's an example of a set. We use the curly braces to denote the elements of a set. This set is named A, capital A. And so, A is equal to the set 2 5 3. So, what can we say about this set? We can say that 2 is it in A. That's what this notation with this epsilon means. And we can say that 8 is not in A. That's what this epsilon with the slash through it means.
0:48 We don't need the same types of elements in a set. Here's another set labeled B, and it has the letter A, the number 18, and the star in it. Here's a special set. It's the empty set. It's the set that has nothing inside of it. And here's an example of an infinite set. It's the set of integers. Order doesn't matter with a set. So, the set 5 2 3 is the same as the set 2 5 3, which is the same as the set 2 3 5. The elements of a set must be distinct. So, here's notation that looks like it's a set. We're labeling it S, and it has the elements 8 2 2 and 1 in it. But, since the elements must be distinct, this thing doesn't exist. This is not a
1:35 valid set. I've shown you two commonly used sets.
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, Nicholas Dwork.