Indexed Families of Sets

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

The “all dogs are the same breed” problem from problem set 8.

We reviewed the proof in the book, and decided that the basis step is correct (all dogs in any set of 1 dog are the same breed, because there’s only 1).

Then we tried to figure out the logic in the induction step, in particular how it splits a set of k+1 dogs up in 2 different ways, each producing a set of only k dogs with 1 dog left out. Since all dogs in any set of k are assumed to be the same breed, and the sets have members in common (at least dog d₂), and each set leaves out a different (k+1)st dog, all k+1 dogs in the larger set must also be the same breed:

This logic actually does work. But there’s a problem in (depending on how you want to look at it) how the induction step is set up, or how it interacts with the basis step: In order for the argument to work about all dogs in a set of k+1 being the same breed, there need to be at least 3 dogs in that set (d₁ to remove first, d_k+1 to remove second, and d₂ to stay in common). Thus the argument works only for k ≥ 2, not for any natural number as needed for the proof.

Equivalently, the facts that the inductive argument only works when k ≥ 2 but that the basis step is k = 1 means that there’s a “disconnect” between the two parts of the proof.

Indexed Families of Sets

Based on section 5.5 in the textbook and this discussion of indexed families of sets.

The Idea

Give some real-world examples of indexed families of sets, including their indexing sets.

Consider people’s favorite songs, where each person might have several. So we could write this as a set containing the first person’s set of favorite songs, the second person’s, etc: { {s₁, s₂, s₃, ...}, {t₁, t₂, ...} , .... }.

Each member set is associated with a person, so it makes sense to label (i.e., index) the members with the person they go with: If the whole family is A, then A = { A_Joe, A_Jane, ... }, and the indexing set is Λ = {Joe, Jane, ... } Note that indices don’t have to be numbers.

Another example might be groups of movies in a series: { {Twilight I, Twilight II, ...}, {Hunger Games I, Hunger Games II, ...}, ... }. Here we have indexing set M = { Twilight, Hunger Games, ... }.

Operations

For each real number x, define A_x = { y ∈ ℝ | -|x/2| ≤ y ≤ |x/2| }

What is ∪_{i ∈ ℝ} A_i?

As with other unions, it’s the set of elements that appear in at least one of the sets involved in the union. In this case,“the sets involved in the union” are all the A_i, so determining the union comes down to figuring out which real numbers are in intervals ±x/2 around the origin, for some x. This illustrates how calculating a union over a family of sets can involve more abstract thinking than taking a union over a small number of finite sets, but the core idea is the same. It turns out that this union includes all real numbers, because any real number y is an element of A_2y.

What about ∩_{i ∈ ℝ} A_i?

Similarly to the union, we now want the real numbers that are in every one of the A_i. Each set in A excludes some real numbers that larger sets contain. More precisely, for all y ≠ 0, y is not in A_y. But this isn’t true of 0, since 0/2 = 0. So of all the real numbers, only 0 is in all of the A_i sets.

Key Ideas

Key ideas we saw in these examples and conversation include

• A “family” of sets is a set of sets.
• “Indexed” means each member set is identified by a label, which might be a number but doesn’t have to be.
• Union, intersection, etc. extend to families, and are often applied over all members of the family.

Next

Start looking at functions.

Please read sections 6.1 and 6.2 in the textbook.

Please also contribute to this discussion of functions.

Next Lecture