## Chapter 17Solutions for fourth week’s assignments

Also available as PDF.

Note: These are my approaches to these problems. There are many ways to tackle each.

### 17.1 Problem set 2.2

#### 17.1.1 Problem 1

• June 13th: nominal, first: ordinal
• eleventh: ordinal, second: ordinal, 6-iron: nominal, 160 yards: cardinal
• 7 pin: nominal, sixth frame: ordinal, 9: cardinal

#### 17.1.2 Problem 2

• There are five letters in the phrase, \{P,A,N,M,B\}, so we can associate 1 ↔ P, 2 ↔ A, etc. The two sets are equivalent.
• The second set has one more element than the first, so the sets are not equivalent.
• We can associate o ↔ t, n ↔ w, and e ↔ o, where the left quantities come from \{o,n,e\} and the right from \{t,w,o\}. The two sets are equivalent.
• \{0\} has in element, and has none, so the sets are not equivalent.

#### 17.1.3 Problem 6

• We can use the function f(w) = w + 1 to construct a bijection between W and N.
• The function f(d) = d + 1 creates a one-to-one mapping between D and E.
• The function f(n) = 1{0}^{n} creates a one-to-one mapping between N and \{10,100,\mathop{\mathop{…}}\}.

#### 17.1.4 Problem 13

The drawing will have

• |B ∩ C|-|A ∩ B ∩ C| = 5 in the unlabeled portion of B ∩ C,
• |B|-|A ∩ B|-|B ∩ C| + |A ∩ B ∩ C| = 28 in the remaining unlabeled portion of B,
• |A ∩ C|-|A ∩ B ∩ C| = 8 in the unlabeled portion of A ∩ C,
• |A|-|A ∩ B|-|A ∩ C| + |A ∩ B ∩ C| = 15 in the remaining unlabeled portion of A,
• |C|-|B ∩ C|-|A ∩ C| + |A ∩ B ∩ C| = 10 in the remaining unlabeled portion of C, and
• |U|- (10 + 7 + 5 + 28 + 8 + 15 + 10) = 17 in U but outside A, B, and C.

#### 17.1.5 Problem 21

• The function f(a) = a is the one-to-one correspondence from A to itself.
• If A ~ B, there is a function f(a) = b where each b B appears for exactly one a A and the function is defined for every b B and a A. The inverse function g(b) = a where b = f(a) shows B ~ A.
• If A ~ B and B ~ C, then there are one-to-one functions f(a) = b and g(b) = c for each mapping. The function h(a) = g(f(a)) then is a one-to-one mapping between A and C.

#### 17.1.6 Problem 23

For (a) and (b), the table is Pascal’s triangle, which we already have in the notes. For (c), we want the entry {P}_{6,3} in our earlier notation. There are 20 such ways.

Wow. Never, ever give someone a list of all your identifying numbers. Identity theft is a serious problem. While quite often all these numbers are available for a little work, at least make a criminal work for them.

### 17.2 Problem set 2.3

#### 17.2.1 Problem 2

Substituting into |A ∪ B| = |A| + |B|-|A ∩ B|, we see that 10 = 5 + 8 -|A ∩ B|, or that |A ∩ B| = 3.

#### 17.2.2 Problem 5

I’m just going to show these as lines. Illustrating them on a “number line” is equivalent. A better diagram for the last would wrap portions of the result in parentheses to show how the line extended.

• 3 + 5 = +
=
= 8
• 5 + 3 =
+
=
= 8
• 4 + 2 =
+
=
= 6
• 0 + 6 =
+
=
= 6
• 3 + (5 + 7) =
+ (∙ + ∙)
= +
=
= 15
• (3 + 5) + 7 =
(∙ + ∙) +
= +
=
= 15

#### 17.2.3 Problem 11

Again, I’m just going to show these as lines. Illustrating them on a “number line” is equivalent.

• 7 - 3 =
-
=
= 4
• 7 - 4 =
-
=
= 3
• 7 - 7 =
-
= ∙ = 0
• 7 - 0 =
-
=
= 7

#### 17.2.4 Problem 24

Draw with two shadings and show that the intersection is shaded twice.

### 17.3 Write 2 + 3 using disjoint sets.

If we let 2 ≡\{a,b\} and 3 ≡\{c,d,e\}, then 2 + 3 ≡\{a,b\} ∪\{c,d,e\} = \{a,b,c,d,e\}.

### 17.4 Illustrate 2 + 3 using Peano arithmetic.

\eqalignno{ a + 0 & = a,\text{ and} & & \cr a + S(b) & = S(a + b). & & }

Here, 3 = S(2), so

\eqalignno{ 2 + 3 & = 2 + S(2) & & \cr & = S(2 + 2) & & \cr & = S(2 + S(1)) & & \cr & = S(S(2 + 1)) & & \cr & = S(S(2 + S(0))) & & \cr & = S(S(S(2 + 0))) & & \cr & = S(S(S(2))) & & \cr & = 5. & & }

### 17.5 Problem set 2.4

#### 17.5.1 Problem 5

• Any set that contains only 1 and some other number is closed because 1 is the multiplicative identity.
• Any set that contains only 1 and some other number is closed because 1 is the multiplicative identity.
• 2 ⋅ 4 = 8\mathrel{∉}\{0,2,4\}, so this is not closed.
• The product of even numbers always is even, so this is closed.
• The product of odd numbers cannot be even, so they must be odd and this set is closed.
• {2}^{2} ⋅ {2}^{3} = {2}^{5}\mathrel{∉}\{1,2,{2}^{2},{2}^{3}\}, so this set is not closed.
• The product of powers of two is a power of two, so this set is closed.
• Similarly, the product of powers of seven is a power of seven so this set is closed. Both of these are closed because \{0,1,2,\mathop{\mathop{…}}\} is closed under addition; {a}^{i} ⋅ {a}^{j} = {a}^{i+j}, moving the property up to the superscript.

#### 17.5.2 Problem 10

Each product is equal to the appropriate shaded area, and the sum is equal to the entire rectangle. The letters correspond directly to the positions.

I had completely forgotten about the FOIL mnemonic. After long enough, it’s just a part of what you do.

#### 17.5.3 Problem 26

The operation is closed because no new shapes are introduced in the operator’s table of results.

The operation is commutative because the operation table is symmetric across the diagonal axis. Thus a ⋆ b = b ⋆ a.

Because ∘ ⋆x = x, the symbol is ’s identity.

After the identity, there are only two symbols remaining. Thus the commutative property combined with the identity means that this operator must be associative.

### 17.6 Illustrate 2 ⋅ 3 using Peano arithmetic. You do not need to expand addition.

We defined multiplication with

\eqalignno{ a ⋅ 0 = 0,\text{ and} & & \cr a ⋅ S(b) = a + (a ⋅ b). & & }

So

\eqalignno{ 2 ⋅ 3 & = 2 ⋅ S(2) & & \cr & = 2 + (2 ⋅ 2) & & \cr & = 2 + (2 ⋅ S(1)) & & \cr & = 2 + (2 + (2 ⋅ 1)) & & \cr & = 2 + (2 + (2 ⋅ S(0))) & & \cr & = 2 + (2 + (2 + 2 ⋅ 0)) & & \cr & = 2 + 2 + 2 = 6. & & }

### 17.7 Illustrate (1 ⋅ 2) ⋅ 3 = 1 ⋅ (2 ⋅ 3) using a volume of size six.

Draw two 1 × 2 × 3 boxes made of 1 × 1 × 1 boxes. To illustrate (1 ⋅ 2) ⋅ 3, show that the 1 × 2 portion is stacked 3 times. To illustrate 1 ⋅ (2 ⋅ 3), show that the 2 × 3 portion is stacked across 1 time.