In this lecture, we introduced some of the basic set operations, and started discussing how to prove things.

Set operations

There are several ways to combine sets together; here we discuss three: the union, intersection and set difference.

Union

Definition: Union

If and are sets, then the union of and (written ) is given by .

This means that if you know , you can conclude that 'either' 'or' , and similarly you can prove if you can either prove or that .

In this Venn diagram, the union of [math]A [/math] and [math]B [/math] is shaded:

Intersection

Definition: Intersection

If and are sets, then the intersection of and (written ) is given by .

This means that if you know , you can conclude 'both' that 'and' , and similarly you must prove both and to prove .

In this Venn diagram, the intersection of [math]A [/math] and [math]B [/math] is shaded:

Set difference

Definition: Set difference

If and are sets, then the set difference minus (written ) is given by .

We use the symbol instead of the normal [math]- [/math] because occasionally we will want to use sets to represent number-like things, and we will want to define subtraction differently for those sets (in particular, we will do this in the section on Category:number theory).

This means that if you know , you can conclude 'both' that 'and' , and similarly you must prove both and to prove .

In this Venn diagram, the set difference [math]A [/math] minus [math]B [/math] is shaded:

Power set

Definition: Power set

The power set of a set (written )is the set of all subsets of . Formally, .

Because the elements of the power set are themselves sets, it is easy to confuse elements and subsets. As with any set comprehension, the elements of are the subsets of [math]A [/math]. Here are some examples:

Let . Then

, by inspection. For example, because .
, because 1 is a number but contains only sets. Put differently, .
Therefore
But note that .
for any set [math]X [/math], we have and , because ∅⊆X and X⊆X.

Proofs

We started to prove the following claim:

Claim (see proof):

We showed two ways not to prove the claim: proof by example (using a picture) and proof by rewriting (using logical equivalences).

Proof by example

This content has not been migrated to the wiki yet. See Media:fa19-lec03-setproofs-slides.pdf.

Sometimes students provide an example when asked for a proof. An especially common way of doing this is by providing a picture (such as a Venn diagram) in place of a proof. This is not sufficient because the proof only works for the specific example given; usually we ask you to prove things about a general situation.

Pictures are still extremely helpful when figuring things out and explaining them! They just usually aren't sufficient to proving a claim in full generality (unless that claim is that something exists, then a picture can be enough to describe the thing exists).

Proof by rewriting

This content has not been migrated to the wiki yet. See Media:fa19-lec03-setproofs-slides.pdf.

Students are often tempted to do proofs about sets by rewriting the logical statements inside the set definitions. Avoid this style for the following reasons:

Proving that the logical rewriting steps are justified is usually just as complicated as the proof that the sets are equal
This technique doesn't work anymore once we get past very simple examples. We want you to build good habits while working on the simple cases.

Doing computations or rewriting is a good proof technique in general, but we would like you to avoid doing logical rewriting for now.

Instead, you should make use of the definitions and proof technique to give a step-by-step argument for why a given relationship holds.

Correct proof

We will develop a good proof together in the next lecture.

FA19:Lecture 3 Set constructions

Contents