Chapter 12
Notes for 3 September

Notes also available as PDF.

12.1 Proof review

  1. You start with a guess, possibly after seeing a pattern.
  2. A few tests, and the guess becomes a conjecture.
  3. Once the conjecture is proven, you have a theorem.

Other items:

A direct proof takes the given hypotheses and applies rules directly to produce the conclusion. We used a direct proof to show that {n}^{2} is either a multiple of four (can be written as 4k for some k) or one larger than a multiple of four (4k + 1) when n is a non-negative integer.

An indirect proof , often called proof by contradiction or proof by contrapositive, proves that the opposite of the conclusion implies the opposite of the hypothesis. Thus if the hypothesis is true, the conclusion must be true. We used proof by contradiction to show that there are infinitely many primes. We actually proved that if there is a largest prime, then there is a larger number not divisible by any known prime and thus prime itself. The contradiction, constructing a prime larger than the largest prime, proved that there is no largest prime. Along with the known existence of primes, the fact there is no largest prime implies there must be infinitely many primes.

12.2 Inductive proof

Remember Pascal’s triangle? We proved that the sum of the nth row is {2}^{n} if we start counting rows from zero.

Written in rather boring table form, each entry is the sum of the entry directly above and above to the left:

11 1
21 2 1
31 3 3 1
41 = \mathbf{0} + 14 = 1 + 36 = 3 + 34 = 3 + 11 = 1 + \mathbf{0}

We will use our result as an example of mathematical induction. This is a proof technique that formalizes inductive reasoning and using a representative case.

  1. Start with verifying a base case.
  2. Then assume the nth case.
  3. Use that to prove the (n + 1)st case.

We want to prove the following:

Theorem: The sum of the nth line of Pascal’s triangle is {2}^{n}.


Here, the base case is the 0th line:

# sum
011 = {2}^{0}

Then let line n be the sequence

# sum
n{P}_{n,1}{P}_{n,2}{P}_{n,3}\mathrel{⋯}\kern 1.54198pt {P}_{n,n+1}{2}^{n}

Now we need to prove that line (n + 1) holds true. In our notation, item jth on line (n + 1) is formed be {P}_{n+1,j} = {P}_{n,j-1} + {P}_{n,j}, setting the entries outside the table ({P}_{n,0} and {P}_{n,n+2}) to zero.

Then we need to show that {\mathop{\mathop{∑ }}\nolimits }_{j=1}^{n+2}{P}_{n+1,j} = {2}^{n+1}.

\eqalignno{ {\mathop{∑ }}_{j=1}^{n+2}{P}_{ n+1,j} & ={ \mathop{∑ }}_{j=1}^{n+2}\left ({P}_{ n,j-1} + {P}_{n,j}\right ) & & \cr & ={ \mathop{∑ }}_{j=1}^{n+2}{P}_{ n,j-1} +{ \mathop{∑ }}_{j=1}^{n+2}{P}_{ n,j} & & \cr & = \left ({P}_{n,0} +{ \mathop{∑ }}_{j=1}^{n+1}{P}_{ n,j}\right ) + \left ({P}_{n,n+2} +{ \mathop{∑ }}_{j=1}^{n+1}{P}_{ n,j}\right ) & & \cr & ={ \mathop{∑ }}_{j=1}^{n+1}{P}_{ n,j} +{ \mathop{∑ }}_{j=1}^{n+1}{P}_{ n,j} & & \cr & = {2}^{n} + {2}^{n} = 2 ⋅ {2}^{n} = {2}^{n+1}. & & }

12.3 Starting with set theory

Our coverage of set theory mostly will cover definitions. We will use some concepts to work with problem solving and to illustrate proofs. Then we will use sets to build up whole numbers (0, 1, 2, \mathop{\mathop{…}}) and basic arithmetic on those numbers.

12.4 Language of set theory


12.5 Basic definitions

To start, we require unambiguous definitions of terms and items. When a term or item is unambiguously defined, it is called well-defined.

An unordered collection of unique elements.
Any item in a set, even other sets. (Also entry, member, item, etc.)
empty set
Or null set. Denoted by rather than \{\}.
A set with only one element.

12.6 Translating sets into (and from) English

From English:

To English:

12.7 Next time: Relations between and operations on sets

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