Notes for 3 September

- You start with a guess, possibly after seeing a pattern.
- A few tests, and the guess becomes a conjecture.
- Once the conjecture is proven, you have a theorem.
- A lemma is a theorem leading to other theorems. Typically a technical result leading to the main theorem.
- A corollary is a subsequent theorem, a simple result after a primary theorem.

Other items:

- Definitions are difficult to define.
- Axioms are fundamental definitions. The classic example:
Two points define a line.

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.

Remember Pascal’s triangle? We proved that the sum of the
n^{th} 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:

# | |||||

0 | 1 | ||||

1 | 1 | 1 | |||

2 | 1 | 2 | 1 | ||

3 | 1 | 3 | 3 | 1 | |

4 | 1 = \mathbf{0} + 1 | 4 = 1 + 3 | 6 = 3 + 3 | 4 = 3 + 1 | 1 = 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.

- Start with verifying a base case.
- Then assume the n
^{th}case. - Use that to prove the (n + 1)
^{st}case.

We want to prove the following:

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

Proof:

Here, the base case is the 0^{th}
line:

# | sum | |||||

0 | 1 | 1 = {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 j^{th}
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}. & &
}

□

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.

- We will cover just enough set theory to use later.
- Cardinalities are important for probability. We don’t have time to cover probability sufficiently well, so we will not explore the sizes of sets deeply.
- This is known as naïve set theory. We do not define absolutely everything, nor do we push set theory’s logical limits. Much.

Goals:

- Impart some of the language necessary for later chapters.
- Practice reasoning in a formal setting.
- One key aspect is what to do in extreme cases like empty sets.

- Set up straight-forward examples for logic.

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

- set
- An unordered collection of unique elements.
- Curly braces: \{A,B,C\} is a set of three elements, A, B, and C.
- Order does not matter: \{\text{cat},\text{dog}\} is the same set as \{\text{dog},\text{cat}\}.
- Repeated elements do not matter: \{1,1,1\} is the same set as \{1\}.
- Can be implicit: \{x\kern 1.66702pt |\kern 1.66702pt x\text{ is an integer},x > 0,x < 3\} is the same set as \{1,2\}.
- Read the implicit form as “the set of elements x such that x is an integer, x > 0, and x < 3”. Or “the set of elements x where \mathop{\mathop{…}}”
- Other symbols that sometimes stand for “such that”: :, ∋ (reversed )
- Implicit (or set-builder) form can include formula or other bits left of the bar. \{3x\kern 1.66702pt |\kern 1.66702pt x\text{ is a positive integer}\} is the set \{3,6,9,\mathop{\mathop{…}}\}.

- element
- Any item in a set, even other sets. (Also entry, member, item,
etc.)
- This is not ambiguous. If something is in a set, it is an item of that set. It doesn’t matter if the item is a number or a grape.
- \{A,\{B,C\}\} is a set of two elements, A and \{B,C\}.
- None of the following are the same: \{A,\{B,C\}\}, \{A,B,C\}, \{\{A,B\},C\}.

- empty set
- Or null set. Denoted by ∅
rather than \{\}.
- This is a set on its own.
- \{∅\} is the set of the empty set, which is not empty.
- Think of sets as bags. An empty bag still is a bag, and if a bag contains an empty bag, the outer bag is not empty.
- Implicit definitions can hide empty sets.
- For example, the set \{x\kern 1.66702pt |\kern 1.66702pt x\text{ is an odd integer divisible by }2\} is ∅.

- singleton
- A set with only one element.
- \{1\} and \{∅\} both are singletons (or sometimes singleton sets).

From English:

- The days of the week:
- \{\text{Monday},\text{Tuesday},\text{Wednesday},\text{Thursday},\text{Friday},\text{Saturday},\text{Sunday}\}
- Of course, we’re using a representation of the days and not the days themselves. That is how we reason about things; we model them and represent them by symbols.

- The days when homework is due:
- \{\text{25
^{th}of August},\text{1^{st}of September},\mathop{\mathop{…}}\} - We could list them all.
- \{
every Monday after the 18
^{th}of August 2008 until after the 1^{st}of December \} - Or: \{x\kern 1.66702pt |\kern 1.66702pt x
is a Monday, x
is after the 18
^{th}of August, and x is on or before the 1^{st}of December \}

- \{\text{25

To English:

- \{2,3,4\}:
- The set containing two, three, and four.

- \{x\kern 1.66702pt |\kern 1.66702pt x\text{ is an integer and }x > 0\}:
- The positive integers, also called the counting numbers or the natural numbers.
- Often written as {J}^{+}. The integers often are written as J (because the “I” form can be difficult to read), rationals as ℚ (for quotients), the reals as .

- \{2x - 1\kern 1.66702pt |\kern 1.66702pt x {J}^{+}\}
- The set whose members have the form 2x - 1 where x is a positive integer.
- Cannot list all the entries; this is an infinite set.
- Here, the odd integers.

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.

- Prove the formula for the sum of the first n
positive integers by mathematical induction. That is, prove 1 + 2 + 3 + \mathrel{⋯} + n = n(n + 1)∕2.
The base case here is n = 1.
Then show that the n
^{th}term transforms into the (n + 1)^{th}term by adding n + 1. - Problem set 2.1 (p83):
- Problems 1, 2, 4, 5, 6, 27

Note that you may email homework. However, I don’t use Microsoft^{TM} 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.