Chapter 18
Notes for the fifth week: review

Notes also available as PDF.

18.1 Review

Structure of the upcoming test:

18.2 Problem solving

Pólya’s principles:

  1. Understand the problem.
  2. Devise a plan.
  3. Carry out the plan.
  4. Look back at your solution.

This is not a simple 1-2-3-4 recipe. Understanding the problem may include playing with little plans, or trying to carry out a plan may lead you back to trying to understand the problem.

18.2.1 Understand the problem

18.2.2 Devise a plan

Sometimes plans are “trivial,” or so simple it seems pointless to make them specific. But write it out anyways. Often the act of putting a plan into words helps find flaws in the plan.

Try to devise a plan that you can check along the way. The earlier you detect a problem, the easier you can deal with it.

Some plans we’ve considered:

18.2.3 Carry out the plan

Attention to detail is critial here.

When building a list, be sure to carry out a well-defined procedure. Or when looking for patterns, be systematic in the examples you try. Don’t jump around randomly.

18.2.4 Look back at your solution

Can you check your result? Sometimes trying to check reveals new relationships that could lead to a better solution.

Think about how your solution could help with other problems.

18.3 Set theory

18.3.1 Definitions and mappings

An unordered collection of unique elements.

You can write a set by listing its entries, \{1,2,3,4\}, or through set builder notation, \{x\kern 1.66702pt |\kern 1.66702pt x\text{ is a positive integer},x < 5\}.

empty set
The unique set with no elements: \{\} or . Be sure to know the relations between the empty set and other sets, and also how the empty set behaves in operations.
element of
You write x ∈ A to state that x is an element of A. The symbol is not an “E” but is almost a Greek ϵ. Think of a pitchfork.

Note that 1 ∈\{1,2\} and \{1\} ∈\{\{1\},\{2\}\}, but \{1\}∉\{1,2\}.

Given two sets A and B, A ⊂ B if every element of A is also an element of B.

One implication is that ∅⊂ A for all sets A. This statement is vacuously true.

Here \{1\} ⊂\{1,2\} and \{1\}⊄\{\{1\},\{2\}\}.

Given two sets A and B, B ⊃ A if every element of A is also an element of B.
proper subset or superset
A subset or superset relation is proper if it implies the sets are not equal.
Venn diagram
A blobby diagram useful for illustrating operations and relations between two or three sets.
A ∪ B = \{x\kern 1.66702pt |\kern 1.66702pt x ∈ A\text{ or }x ∈ B\}. The union contains all elements of both sets.
A ∩ B = \{x\kern 1.66702pt |\kern 1.66702pt x ∈ A\text{ and }x ∈ B\}. The intersection contains only those elements that exist in both sets.
set difference
A \ B = \{x\kern 1.66702pt |\kern 1.66702pt x ∈ A\text{ and }x\mathrel{∉}B\}. The set difference contains elements of the first set that are not in the second set. It cannot contain any elements of the second set.

You can write the result of multiple operations in set-builder notation,

\eqalignno{ (A ∩ B) ∪ C & = \{x\kern 1.66702pt |\kern 1.66702pt x ∈ A\text{ and }x ∈ B\} ∪ C & & \cr & = \{x\kern 1.66702pt |\kern 1.66702pt (x ∈ A\text{ and }x ∈ B)\text{ or }x ∈ C\}. & & }

18.3.2 Cardinality and one-to-one correspondence

The cardinality of a set is a count of its elements. So |\{a,b,c\}| = 3. An infinite set like the set of all positive integers has no simple cardinality.

To sets are equivalent, or A ~ B, if there is a one-to-one correspondence between the two sets. With such a correspondence, each element of one set is matched with exactly one element of the other set.

For finite sets, the two sets must be the same size. If they weren’t, there would be at least one unmatched element.

For finite sets, establishing a one-to-one correspondence is straight-forward. You just need to list which entries correspond. For \{1,2,3\} and \{a,b,c\}, such a list might be

1 ↔ c,\quad 2 ↔ a,\quad 3 ↔ b.

Or you could provide a formula. For A = \{1,2,3\} and B = \{2,4,6\}, a mapping could be a ∈ A ↔ f(a) ∈ B where

f(a) = 2a.

For infinite sets, a formula is the most straight-forward way. Consider the extending the above sets to be infinite. For sets A = \{1,2,3,\mathop{\mathop{…}}\} and B = \{2,4,6,\mathop{\mathop{…}}\}. the same mapping as before shows they are equivalent. For the sets A = \{1,2,3,\mathop{\mathop{…}}\} and B = \{2,3,4,\mathop{\mathop{…}}\}, a mapping function would be f(a) = a + 1.

18.4 Operations and whole numbers

For any operation, the result of the operation always lies in the set. For whole numbers, x + y is closed but x - y is not.
For numbers, x + y = y + x and xy = yx. For sets, A ∩ B = B ∩ A and A ∪ B = B ∪ A.
For numbers, x + (y + z) = (x + y) + z and x(yz) = (xy)z. For sets, A ∩ (B ∩ C) = (A ∩ B) ∩ C) and A ∪ (B ∪ C) = (A ∪ B) ∪ C.
For numbers, the only version is the distribution of multiplication over addition or x(y + z) = xy + xz. For sets, both unions and intersections distribute. So A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

There are multiple ways to illustrate addition and multiplication.

For addition, one illustration is “piles of rocks” or symbols. This is somewhat like set unions, except we assume every element of each set is unique. Equivalently, we assume all sets are disjoint. Then |A ∩ B| = |∅| = 0, so |A ∪ B| = |A| + |B|-|A ∩ B|-|A| + |B|.

Another illustration is the number line. Each number is represented by a length:


Then addition appends lines:

1+2 + 3

This makes the commutative and associative properties fairly obvious; the line has the same final length regardless.

This is essentially the same as Peano arithmetic covered earlier, except addition in Peano arithmetic moves a bar from one number to the other until the sum is reached.

Multiplication often is best illustrated by areas or volumes.