# Difference between revisions of "FA19:Lecture 3 Set constructions"

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 and 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 and 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 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 minus 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 . 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 , we have and , because ∅⊆X and X⊆X.

# Proofs

We started to prove the following claim:

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.