FA19:Lecture 3 Set constructions

From CS2800 wiki
Revision as of 14:34, 6 September 2019 by {{GENDER:Mdg39|[math]'"2}} [/math]'"7
(<math>1) </math>2 | <math>3 (</math>4) | <math>5 (</math>6)

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 [math]A [/math] and [math]B [/math] are sets, then the union of [math]A [/math] and [math]B [/math] (written [math]A \href{/cs2800/wiki/index.php/%5Ccup}{\cup} B [/math]) is given by [math]A \cup B \href{/cs2800/wiki/index.php/Definition}{:=} \{x \href{/cs2800/wiki/index.php/%5Cmid}{\mid} x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/Or}{\text{ or }} x \href{/cs2800/wiki/index.php/%5Cin}{\in} B\} [/math].

This means that if you know [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%5Ccup}{\cup} B [/math], you can conclude that 'either' [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] 'or' [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} B [/math], and similarly you can prove [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%5Ccup}{\cup} B [/math] if you can either prove [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] or that [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} B [/math].

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

Venn-union.svg

Intersection

Definition: Intersection
If [math]A [/math] and [math]B [/math] are sets, then the intersection of [math]A [/math] and [math]B [/math] (written [math]A \href{/cs2800/wiki/index.php/%5Ccap}{\cap} B [/math]) is given by [math]A \href{/cs2800/wiki/index.php/%5Ccap}{\cap} B \href{/cs2800/wiki/index.php/Definition}{:=} \{x \href{/cs2800/wiki/index.php/%5Cmid}{\mid} x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/And}{\text{ and }} x \href{/cs2800/wiki/index.php/%5Cin}{\in} B\} [/math].

This means that if you know [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%5Ccap}{\cap} B [/math], you can conclude 'both' that [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] 'and' [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} B [/math], and similarly you must prove both [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] and [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} B [/math] to prove [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%5Ccap}{\cap} B [/math].

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

Venn-intersection.svg

Set difference

Definition: Set difference
If [math]A [/math] and [math]B [/math] are sets, then the set difference [math]A [/math] minus [math]B [/math] (written [math]A \href{/cs2800/wiki/index.php/%5Csetminus}{\setminus} B [/math]) is given by [math]A \href{/cs2800/wiki/index.php/%5Csetminus}{\setminus} B \href{/cs2800/wiki/index.php/Definition}{:=} \{x \href{/cs2800/wiki/index.php/%5Cmid}{\mid} x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/And}{\text{ and }} x \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} B\} [/math].

We use the symbol [math]\href{/cs2800/wiki/index.php/%5Csetminus}{\setminus} [/math] 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 [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%5Csetminus}{\setminus} B [/math], you can conclude 'both' that [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] 'and' [math]x \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} B [/math], and similarly you must prove both [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] and [math]x \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} B [/math] to prove [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%5Csetminus}{\setminus} B [/math].

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

Venn-diff.svg

Power set


Definition: Power set
The power set of a set [math]A [/math] (written [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math])is the set of all subsets of [math]A [/math]. Formally, [math]\href{/cs2800/wiki/index.php/2}{2}^A \href{/cs2800/wiki/index.php/Definition}{:=} \href{/cs2800/wiki/index.php/Set_comprehension}{\{B \mid} B \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A\} [/math].

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 [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math] are the subsets of [math]A [/math]. Here are some examples:

Let [math]A := \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]. Then

  • [math]\href{/cs2800/wiki/index.php/2}{2}^A = \{ \href{/cs2800/wiki/index.php/Empty_set}{\{\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{2\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{3\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,3\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{2,3\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} \} [/math], by inspection. For example, [math]\{1,2,3\} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^A [/math] because [math]\{1,2,3\} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A [/math].
  • [math]1 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} \href{/cs2800/wiki/index.php/2}{2}^A [/math], because 1 is a number but [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math] contains only sets. Put differently, [math]1 \href{/cs2800/wiki/index.php?title=%5Cnsubseteq&action=edit&redlink=1}{\nsubseteq} A [/math].
  • Therefore [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} \href{/cs2800/wiki/index.php?title=%5Cnsubseteq&action=edit&redlink=1}{\nsubseteq} \href{/cs2800/wiki/index.php/2}{2}^A [/math]
  • But note that [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^A [/math].
  • for any set [math]X [/math], we have [math]\href{/cs2800/wiki/index.php/%E2%88%85}{∅} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^A [/math] and [math]X \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^X [/math], because ∅⊆X and X⊆X.

Proofs

We started to prove the following claim:

[math]A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (B \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} C) \href{/cs2800/wiki/index.php/Equality_(sets)}{=} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B) \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} C) [/math]

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.