## Chapter 18Notes for the fifth week: review

Notes also available as PDF.

### 18.1 Review

Structure of the upcoming test:

• Eight questions. Chose six and solve them.
• Thus expect about seven minutes per question.
• Closed book, etc. Calculators are fine but not necessary.
• Bring scratch paper and paper for writing up your results. Separately.
• Answers and explanations need to be indicated clearly.
• No questions are intended to be “trick” questions.
• Will cover the following topics:
• problem solving,
• set theory,
• operations on whole numbers.
• Remember that solutions for the homework problems are available on-line: //jriedy.users.sonic.net/VI/math202-f08/:http://jriedy.users.sonic.net/VI/math202-f08/.

### 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

One comment about the homeworks: Most people answer only part of any given problem.

• Determine what you have and what you want.

To indicate an answer clearly to someone else (like me), you need to know what the answer is.

• Consider rephrasing the problem, either in English or symbolically.

• Try some examples.

This is close to devising a plan. Sometimes you may stumble upon an answer.

• Look for relationships between the data.

Examples may help find relationships. The relationships may help you decide on a plan. Mathematics is about relationships between different entities; symbolic mathematics helps abstract away the entities themselves.

#### 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:

• Guessing and checking.

Try a few combinations of the data. See what falls out. This is good for finding relationships and understanding the problem.

• Searching using a list.

If you know the answer lies in some range, you can search that range systematically by building a list.

• Finding patterns.

When trying examples, keep an eye open for patterns. Sometimes the patterns lead directly to a solution, and sometimes they help to break a problem into smaller pieces.

• Following dependencies / working backwards.

Be sure to understand what results depend on which data. Look for dependencies in the problem. Sometimes pushing the data you have through all the dependencies will break the problem into simpler sub-problems.

#### 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.

### 18.3 Set theory

#### 18.3.1 Definitions and mappings

set
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\}.

subset
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\}\}.

superset
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.
union
A ∪ B = \{x\kern 1.66702pt |\kern 1.66702pt x A\text{ or }x B\}. The union contains all elements of both sets.
intersection
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

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

closure
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.
commutative
For numbers, x + y = y + x and xy = yx. For sets, A ∩ B = B ∩ A and A ∪ B = B ∪ A.
associative
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.
distributive
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:

 0 ∙ 1 ∙—∙ 2 ∙—∙—∙