Prerequisites for 80-310/610

Mathematical Prerequisites

You should have some familiarity reading and writing rigorous proofs. A course in abstract mathematics or Arguments and Inquiry (80-211) should be sufficient preparation.

Logical Prerequisites

You should be comfortable with propositional and predicate logic and their semantics, and have worked with at least one deductive system.

Self test

Answering the following questions should be routine.

1. Is the propositional formula (A → B) ∨ (B → A) valid? Justify your answer.

2. Put the formula ∃x A(x) ∧ ∀y (B(y) → ∃z C(y, z)) in prenex form, i.e. write down an equivalent formula in which all the quantifiers are in front.

3. Is the formula ∀x ∀y (x < y → ∃z (x < z ∧ z < y)) true in the structure M,

a. if M is the real numbers?

b. if M is the natural numbers?

c. if M is the set of all subsets of the natural numbers, and < is interpreted as proper set inclusion (⊊)?

4. Prove, by induction, that every natural number other than 1 can be factored into primes.

5. Define the sequence a_{n} recursively taking a_{0} = 1 and a_{n+1} = 3a_{n}. Find

a formula for S_{n}, where

S_{n} = Σ_{i=1}^{n}a_{i}

and use induction to prove that your formula is correct. (Hint: try doubling each S_{n}.)

6. Prove that there are infinitely many primes. (Hint: suppose p_{0}, p_{1}, …, p_{k} is a list of all the primes, and consider N = p_{1}p_{2} … p_{k} + 1. Show that N is either prime or is divisible by a prime different from any of the p_{i}.)