Set Operations

Return to Course Outline

Previous Lecture

Misc

Feedback survey. Return by Friday (if you want to return it).

Questions?

Weak vs Strong Induction?

Which principle of induction do you use when, and do you use it in the extended or regular form?

My advice: don’t worry about extended vs regular forms, just start the induction at whatever integer value is appropriate. If it’s not 1, you’re doing an extended form of induction, but the argument you make won’t change because of that.

Strong vs weak: If you prove that P(k+1) must hold just from P(k) holding, it’s weak induction. If you need to use multiple values ≤ k, it’s strong induction and may need multiple base cases.

Set Operations

Section 5.1.

Basic Ideas

Form some sets of people in this room (e.g., by major, other interests, etc.)

A (Capricorns)= { NN, TG }

B (Geminis) = { WJJ, KH, BB }

C (Libras) = { JS, ABo }

D (wearing black shoes) = { CC, JR, MF, JD }

E (wearing brown shoes) = { DB, ABe }

F (wearing green shoes) = ∅

G (wearing white shoes) = { JS, MR, LK, NN, RG }

Some set operations on these examples

Intersection: G ∩ C = { JS }, A ∩ B = ∅, A ∩ G = { NN }

Notice that anything intersected with the empty set is the empty set, kind of like any number times 0 is 0. There’s an algebra of set operations emerging here.

Union: B ∪ E = { WJJ, KH, BB, DB, ABe }

Complement: G^C = { BB, WJJ, .... }, i.e., the set containing everyone in the classroom except those in set G.

Difference: C - G = { ABo }, i.e., the set of all members of C that are not also in G.

Cardinality, i.e., the size of a set. For example card(D) = 4.

Proofs about Sets

Example

A conjecture coming out of our discussion of complement: if U is the universal set, then ∅^C = U.

Proof strategy: show that every element of ∅^C is in U and vice versa. This strategy reflects the definition of set equality.

Every element of ∅^C is in U: Suppose x is an element of ∅^C. Then by the definition of complement, x is in U (and not in ∅). Therefore x is in U.

Every element of U is in ∅^C: Suppose d is an element of U. Since d is not in ∅ it is in ∅^C (the detailed reasoning for this last assertion is that d is in U and d cannot be in ∅, and ∅^C is defined to be elements that are in U but not in ∅).

Another Example

(Not discussed in class, but requested afterwards.)

Prove that { n ∈ ℕ | n > 6 } ⊆ { n ∈ ℕ | n+1 > 6 }.

Proof strategy: following the definition of subset, show that every element of { n ∈ ℕ | n > 6 } is also an element of { n ∈ ℕ | n+1 > 6 }.

Give the sets names to make them easier to talk about, so let S = { n ∈ ℕ | n > 6 } and T = { n ∈ ℕ | n+1 > 6 }. Suppose x is an element of S. Then n > 6, from the definition of S. From algebra, n + 1 > 7, and 7 > 6, so n+1 > 6. But this means n is in T, from the definition of T.

Next

Both of the above proofs followed a pattern of assuming some variable (x or d, depending on what part of what proof you look at) is a member of some set, and showing that it must also be a member of some other set. Look more thoroughly at this tactic and what you can prove about sets with it.

Read section 5.2

Next Lecture