SP20:Lecture 3 Set constructions

From CS2800 wiki


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.

The empty set and vacuous truth

Asking questions about subset relationships with the empty set requires the notion of vacuously true statements.

When [math]P [/math] is a false proposition, we say that "if [math]P [/math] then [math]Q [/math]" is vacuously true; the statement is true, but only because it doesn't say anything.

This is a definition that often leads to confusion. Why is "if [math]P [/math] then [math]Q [/math]" true if [math]P [/math] is false? Well, it is not making any claim at all, since it is discussing the world where [math]P [/math] is true, which isn't the world under consideration. It is often useful to consider this statement to be true.

For example, you might write a specification for a program by saying that "if the input is positive, then the output is positive". The following function should satisfy this specification (i.e. we would consider the statement "if the input is positive, then the output of f is positive" to be true):

def f(x):
  return x

The function still satisfies its specification, even if you pass in -5; the specification is making no claims about this case.

A common example of a vacuous truth is "for all [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php?title=%5Cemptyset&action=edit&redlink=1}{\emptyset} [/math], P". This statement is always true (regardless of [math]P [/math]), but only because there are no [math]x [/math] in the empty set.

This lets us conclude various things about the empty set. For example:

for any set [math]X [/math], [math]\href{/cs2800/wiki/index.php/%E2%88%85}{∅} \href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} X [/math]
Proof: ∅ ⊆ A
This claim is vacuously true, since there are no elements of the empty set. Another more convoluted way of saying the same thing: choose an arbitrary element [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php?title=%5Cemptyset&action=edit&redlink=1}{\emptyset} [/math]. Then we have that [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php?title=%5Cemptyset&action=edit&redlink=1}{\emptyset} [/math] (by assumption) and [math]x \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} \href{/cs2800/wiki/index.php?title=%5Cemptyset&action=edit&redlink=1}{\emptyset} [/math] (by definition of [math]\emptyset [/math]). This is a contradiction, which completes this part of the proof (and thus the whole proof).


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. The way to start is by writing down what is known (the assumptions and definitions) and then combining them until you can reach the conclusion.