SP18:Lecture 2 Sets

From CS2800 wiki


Definition: Set
A set is a collection of things. If [math]A [/math] is a set and [math]x [/math] is a thing, then [math]x [/math] is either in [math]A [/math] (written [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math]) or not in [math]A [/math] (written [math]x \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} A [/math]).

If [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] we say that [math]x [/math] is an element of [math]A [/math].

Two sets are equal if they contain the same set of things (see the definition of set equality for more details).


Here are some useful sets:

  • The set [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/Definition}{:=} \href{/cs2800/wiki/index.php/Enumerated_set}{\{0,1,2,\dots\}} [/math] of natural numbers.
  • The set [math]\href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} \href{/cs2800/wiki/index.php/Definition}{:=} \href{/cs2800/wiki/index.php/Enumerated_set}{\{\dots,-2,-1,0,1,2,\dots\}} [/math] of integers.

Sets can contain things other than numbers:

  • Let [math]A [/math] be the set of people in the room

The defining feature of a set [math]A [/math] is that every object is unambiguously either in [math]A [/math] or not in [math]A [/math]. You don't need an algorithm for determining which is true. For example:

  • Let [math]B [/math] be the set of Java programs that never crash

This is a perfectly good set (assuming you define "Java program" and "crash"), even though there is no algorithm to determine whether a given program crashes or not. It either does or it doesn't, we don't have to know which.

  • The empty set (written [math]\href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math] or [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{\}} [/math]) is a set; [math]x \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math] for all [math]x [/math].

This is an example of a degenerate object. An informal definition of a set would be something that has things in it; the empty set has no things in it, so perhaps we should rule it out. But most proofs work just as well with special cases as they do for the general case, so by default we include the special cases. We do the same thing when we define subset below.

We can list (or enumerate) the elements of a set:

You can think of this as shorthand for the set comprehension [math]\{n \href{/cs2800/wiki/index.php/%5Cmid}{\mid} n = 1\href{/cs2800/wiki/index.php/Or}{\text{ or }n} = 2\href{/cs2800/wiki/index.php/Or}{\text{ or }n}=3\} [/math].

Sometimes we include a $\dots$ in an enumerated set if its meaning is clear (such as in the definition of [math]\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math]). This can be formalized more carefully as an inductively defined set.

Sets can contain other sets:

  • [math]\{\{1,2\}, \{3,4\}\} [/math] is a set containing two elements: the first is the set [math]\{1,2\} [/math]; the second is the set containing [math]\{3,4\} [/math].
  • Note that [math]\{\href{/cs2800/wiki/index.php/%E2%88%85}{∅}\} \href{/cs2800/wiki/index.php?title=Set_equality&action=edit&redlink=1}{\neq} ∅ [/math]; the former contains one thing (the empty set), while the latter contains no things. This is analogous to the difference in python between [] and [[]]:
>>> len([])
>>> len([[]])

One easy way to construct a set is to draw a picture of it. A common way of doing so is a Venn diagram such as this one:


This diagram indicates that the set [math]A [/math] consists of all of the points in the left-hand circle, while set [math]B [/math] consists of the points in the right hand circle.

Be careful: although Venn diagrams are a great way to create examples, they do not provide proofs that work for arbitrary sets. For example, an argument made using the diagram above does not describe the cases where [math]A \href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} B [/math] or when [math]A \href{/cs2800/wiki/index.php/%5Ccap}{\cap} B \href{/cs2800/wiki/index.php/Equality_(sets)}{=} \href{/cs2800/wiki/index.php?title=%5Cemptyset&action=edit&redlink=1}{\emptyset} [/math]. Moreover, it doesn't consider finite sets or sets that are larger than any set of points in the plane. Venn diagrams give intuition (and examples) but not proofs.

Set comprehensions

The notation [math]\{x \mid \text{property of } x\} [/math] denotes the set of all [math]x [/math] that satisfy the property. You should read [math]\href{/cs2800/wiki/index.php/%5Cmid}{\mid} [/math] as "such that". For example,

[math]A \href{/cs2800/wiki/index.php/Definition}{:=} \{x \mid x\href{/cs2800/wiki/index.php/Even}{\text{ is even}}\} [/math]

indicates the set of all even numbers. [math]2 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] because [math]2 [/math] is even, while [math]1 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} A [/math] because [math]1 [/math] is not even.

We may want to specify that we're only interested in natural numbers; we often use notation like [math]\{x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \mid x\href{/cs2800/wiki/index.php/Even}{\text{ is even}}\} [/math]. This should be read as "the set of natural numbers which are even".

We can also have more complicated expressions to the left of the vertical bar, for example [math]B \href{/cs2800/wiki/index.php/Definition}{:=} \{2y \mid y \in \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}\} [/math] also denotes the set of even natural numbers: [math]8 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B [/math] because [math]8 = 2\href{/cs2800/wiki/index.php?title=%5Ccdot&action=edit&redlink=1}{\cdot}4 [/math] and [math]4 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], while [math]7 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} B [/math] because there is no natural number that when multiplied by 2 gives 7.

Set relationships

Set equality

The defining feature of a set is the collections of elements that are in or not in it. This suggests that we should consider two sets to be the same if they contain the same elements. This motivates the definition of equality:

Two sets [math]A [/math] and [math]B [/math] are equal if every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] is in [math]B [/math], and every [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} B [/math] is in [math]A [/math].

This definition tells us that sets "ignore" duplicates and order. For example, [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,1,2,3\}} \href{/cs2800/wiki/index.php/Equality_(sets)}{=} \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]; we can prove this using the definition. First, we check every [math]x [/math] in the left hand side (LHS) is in the right hand side (RHS); by inspection, we see that [math]1 \in \href{/cs2800/wiki/index.php/RHS}{RHS} [/math], [math]1 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math], [math]2 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math], and [math]3 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. Then, we check that every [math]x [/math] in the RHS is in the LHS; which they are, again by inspection.


Definition: Subset
If [math]A [/math] and [math]B [/math] are sets, then [math]A [/math] is a subset of [math]B [/math] (written [math]A \href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} B [/math]) if every [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] is also in [math]B [/math]

For example, in the following Venn diagram, [math]A [/math] is a subset of [math]B [/math]:


Note the difference between [math]\href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} [/math] and [math]\href{/cs2800/wiki/index.php/%5Cin}{\in} [/math]: [math]A \href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} B [/math] says that [math]A [/math] is a set and that everything in [math]A [/math] is also in [math]B [/math]; [math]A \href{/cs2800/wiki/index.php/%5Cin}{\in} B [/math] means that [math]A [/math] 'itself' is an element of [math]B [/math].

Set operations

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


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:



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:


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:



Now that we have some definitions, we can turn our attention to proving things using those definitions. During the lecture, we listed some general techniques as we went; here we discuss the general techniques first, and then present the two proofs given.

General techniques

A proof is just an argument that something is true. While writing a proof, you will make a series of claims; each claim should be

  • clearly described (all terms have definitions)
  • true (based on the current set of assumptions)
  • obviously true based on what has already been stated.

Separate goals from knowns

While writing a proof (as with any technical writing), it is often helpful to remind the reader where you are going. However, it is important to clearly indicate that this is what you are doing.

I often write "we want to show" (abbreviated WTS) to clearly indicate that I haven't already proved what I'm stating. Failing to do so can lead to a backwards proof. For example, while trying to prove [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math], I shouldn't write something like

  • [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math]
  • every [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] is in [math]A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math]
  • ...

because the reader will believe that you are claiming what you are trying to prove is true on the very first line (remember, every claim should be obvious based on what came before). However, the following solves this problem:

  • We want to show that [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math],
  • i.e. that every [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] is in [math]A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math]

Here, each sentence is obviously true: we obviously do want to prove [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math], and that is obviously the same as saying that every [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] is in [math]A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math] (we consider definitions to be "obvious").

Plug in definitions

It is often helpful to plug in definitions; indeed, this is the whole point of clearly writing down definitions! If you are trying to prove two things are equal, find the appropriate definition of equality and plug it in.

We often indicate that we are using a definition by writing by definition, in other words, or i.e..

You can often save yourself some handwriting by expanding the outermost definitions first. For example, if you are proving [math]\href{/cs2800/wiki/index.php/2}{2}^{A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/2}{2}^A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} \href{/cs2800/wiki/index.php/2}{2}^B [/math], you could choose to expand any of the uses of the definition of the [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math], of [math]A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B [/math], or of . If you reduce [math]A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B [/math] or [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math] first, you will likely have to repeat its defintiion several times. If you expand [math]\href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} [/math] first, on the other hand, you can immediately dive into the proof of [math]\href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} [/math] without having to copy long formulas down.

Do what it says, use what you know

A good way to approach proofs is to "Do what it says, use what you know". In other words, look at the structure of what you've already proved (or assumed) and what you are trying to prove.

Often, this can help you make progress. We will present a table of proof techniques in a future lecture, but we list some of the techniques here.

Case analysis

If you know that "P or Q" is true for some statements P and Q, and you wish to show a third statement R, you can do so by separately considering the cases where P is true and where Q is true. If you are able to prove R in either case, then you know that R is necessarily true.

This technique is often referred to as case analysis.

Proving "for all" statements

If your goal is to prove "for all [math]x\href{/cs2800/wiki/index.php/%E2%88%88}{∈}A [/math], P", you can proceed by choosing an arbitrary value [math]x∈A [/math] and then proving that P holds for that [math]x [/math].

The fact that [math]x [/math] is arbitrary does not mean you get to pick [math]x [/math]; on the contrary, your proof should work no matter what [math]x [/math] you choose. This means you can't use any property of [math]x [/math] other than that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math].

First example proof: A ∩ B ⊆ A

Here is our first proof:

[math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php?title=A&action=edit&redlink=1}{A} [/math]
We want to show that [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B ⊆ \href{/cs2800/wiki/index.php?title=A&action=edit&redlink=1}{A} [/math], i.e. that every [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math] is also in A. Choose an arbitrary [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math]; our new goal is to show that [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math]. But this comes directly from the definition of [math]\href{/cs2800/wiki/index.php/%E2%88%A9}{∩} [/math], since [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math] we know [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math].

Second example proof: A = (A ∩ B) ∪ (A ∖ B)

[math]A \href{/cs2800/wiki/index.php/Equality_(sets)}{=} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%96}{∖} B) [/math]
Let RHS denote the right hand side ([math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%96}{∖} B) [/math]).

In order to show that [math]A \href{/cs2800/wiki/index.php/Equality_(sets)}{=} RHS [/math], we must show both that 1. [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} RHS [/math] and 2. [math]RHS \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A [/math].

1. Choose an arbitrary [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math]. Clearly [math]x [/math] is either in [math]B [/math] or not. In the first case, we have that [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math] so [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} RHS [/math] (by definition of ). In the second case, we have that [math]x \in A \href{/cs2800/wiki/index.php/%E2%88%96}{∖} B [/math], so again [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} RHS [/math]. In either case, we have [math]x \in RHS [/math] as desired.

2. Now we wish to show that [math]\href{/cs2800/wiki/index.php/RHS}{RHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A [/math], so we choose an arbitrary [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. By definition of the union, we know that either [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math] or [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%E2%88%96}{∖} B [/math]. In the first case, we have [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] (by definition of ), while in the second case we have [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] by definition of . In either case we have [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] as