Chapter 16
Notes for 12 September

Notes also available as PDF.

16.1 Review

nominal
A number used for indentification, like your student ID.
ordinal
A number used for ordering, as in first, second, etc.
cardinal
A number that counts the number of entries in some set.
one-to-one correspondence
Two sets A and B are in one-to-one correspondence if there is a pairing of elements (a,b) such that each a ∈ A and b ∈ B belongs to exactly one pair. The pairing is also called a bijection.
equivalent sets
Two sets A and B are equivalent if they are in one-to-one correspondence. We write A ~ B for equivalence and A≁B for non-equivalence.
cardinality
Writen |A|, or rarely n(A), the cardinality of A is the number of elements in A. So |\{a,b,7\}| = 3.

We now have a link from the cardinality of sets to cardinal integers ≥ 0. These are the whole numbers. Moreover, now we can construct the whole numbers. Starting from the unique empty set, |∅| = 0.

Define an operation S(x) = x ∪\{x\}. This is the successor function. Then S(∅) = ∅∪\{∅\} = \{∅\}, a set with one element. Continue applying the successor to see:

|∅|0
S(∅)|\{∅\}|1\{0\}
S(S(∅))|\{∅,\{∅\}\}|2\{0,1\}
S(S(S(∅)))|\left \{∅,\{∅\},\{∅,\{∅\}\}\right \}|3\{0,1,2\}

After the association between and 0, we identify the number k with the set of all numbers preceding k. Thus we follow Guiseppe Peano’s construction of the whole numbers from nothing but sets.

finite set
Equivalent to some number of successor applications S() to the empty set.
infinite set
Cannot be equivalent to any number of successor applications, as we could apply once more to obtain a larger set.

16.2 Addition of whole numbers

So how do we define addition? The text has one method that assumes A and B are disjoint. That is, A ∩ B = ∅. Then |A ∪ B| = |A| + |B|, so we could define addition by the cardinality of a union of disjoint sets.

It’s worth a brief detour to discuss what happens to the cardinality when the sets are not disjoint. This is a tool used frequently in probability.

|\{a,b\} ∪\{c,d\}| = |\{a,b,c,d\}| = 4, where |\{a,b\}| = |\{c,d\}| = 2. If they share an element, though, the union’s cardinality still is four. |\{a,b,c\} ∪\{c,d\}| = |\{a,b,c,d\}| = 4. But now |\{a,b,c\}| = 3.

The rule for counting elements for a union of two sets is |A ∪ B| = |A| + |B|-|A ∩ B|. The first two terms count shared elements twice, and the last term removes one of those. For three terms, |A ∪ B ∪ C| = |A| + |B| + |C|-|A ∩ B|-|A ∩ C|-|B ∩ C| + |A ∩ B ∩ C|, where you add back in elements you removed too many times.

But for general addition, we start by defining a + 0 = a using A ∪∅ = A as a guide. Then we define addition for other numbers recursively by

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

So a + 1 = a + S(0) = S(a + 0) = S(a), the successor of a. If we think of S(b) as b + 1, then the second rule is a + (b + 1) = (a + b) + 1.

A small example working through the recursive definition:

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

Obviously, we don’t want to work through many of these.

So we define addition as decomposing one number into its sequence of successors and then applying those successors. For the line model, we extend one line by the length of the other.

Some properties of addition on whole numbers:

closure
If a and b are two whole numbers, a + b is a whole number. Whole numbers are closed over addition.
commutative
a + b = b + a
associative
a + (b + c) = (a + b) + c
identity
a + 0 = a

Each of these is straight-forward to prove using the text’s model of unions of disjoint sets. Working with Peano arithmetic is trickier but possible.

Terminology: The terms being added are called addends or summands.

16.3 Subtraction of whole numbers

Subtraction is the first property we will define implicitly. The difference of a and b, written a - b, is defined to be the whole number c where a = b + c. If no such c exists, then subtraction is not defined. There is no integer c ≥ 0 such that 1 = 5 + c, so 1 - 5 is not defined.

Thus subtraction is not closed over the whole numbers. It also is not commutative and not associative. However, because a + 0 = a, we know that a - 0 = a. Thus subtraction does have an identity on one side. However, 0 - a is not defined unless a = 0. There is no c such that 0 = a + c unless a = c = 0.

Terminology: In a - b, a is the minuend and b is the subtrahend.

16.4 Multiplication of whole numbers

We are accustomed to thinking of multiplication as repeated addition. For example, 4a = a + a + a + a. Or we can rearrange the repeated addition as in 4a = a + 3a = a + (a + 2a) = a + (a + (a + a)). This arrangement provides the recursive definition of multiplication:

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

Again, thinking of S(b) as b + 1, a ⋅ (b + 1) = a + (a ⋅ b). We pull apart one side into a sequence of ones and repeatedly add the other side.

We will jump ahead and assume multiplication is commutative. So write the example of 4a as a ⋅ 4:

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

And with this recursive definition,

\eqalignno{ a ⋅ 1 & = a ⋅ S(0) & & \cr & = a + (a ⋅ 0) & & \cr & = a + 0 = a, & & }

and one is the multiplicative identity.

Defining multiplication in terms of repeated addition lets multiplication inherit the closure property. The product a ⋅ b exists and is a whole number for every pair of whole numbers a and b. And we could push through and show that multiplication is commutative and associative. Another less formal model makes these properties more clear, however.

A quick note on terminology: In 15 = 5 ⋅ 3, 15 is the product, and five and three are factors. The term factor only applies to integers. Two other terms applied to the operands (5 and 3) in the context of repeated addition are multiplicand and multiplier. If you consider 15 = 5 ⋅ 3 = 5 + 5 + 5, then five is the multiplicand and three is the multiplier. These terms still are used when building multiplier circuits. One term, the multiplicand, is shifted and added according to the multiplier. We will return to this later.

But for the less formal models, consider multiplication of two numbers as tracing out areas and volumes.

The drawing can have its axes flipped around without changing the area. Thus, ab = ba and multiplication is commutative.

For the associative property, consider a volume traced out by three numbers. Putting parenthesis in different places is the same as counting in different directions, but the final count always is the same. Thus multiplication is associative.

There is one additional property that combines addition and multiplication: the distributive property. Here a(b + c) = ab + ac. Drawing a box and separating it into two pieces demonstrates the distributive property well. Thinking of repeated addition here also is simple. We have either b + c copies of a, or b copies of a added to c copies.

16.5 Monday: Division and exponentials

I need to cover these still. They provide examples of undefined behavior; it’s worth exploring that a bit.

To be followed by a little review.

16.6 Homework

Groups are fine, turn in your own work. Homework is due in or before class on Mondays.

Write out (briefly) your approach to each problem.

Note that you may email homework. However, I don’t use MicrosoftTM products (e.g. Word), and software packages are notoriously finicky about translating mathematics.

If you’re typing it (which I advise just for practice in whatever tools you use), you likely want to turn in a printout. If you do want to email your submission, please produce a PDF or PostScript document.