# Induction

- https://www.math.utah.edu/mathcircle/notes/induction.pdf (read at least the first 4 pages and take a look at some of the interesting induction problems in section 6)

- https://www.youtube.com/watch?v=9Opap0Z-gbk (part 8, Peano Axioms/Systems and Transitive Sets; if you would like a review of the construction of $\mathbb{N}$, part 7 in the same series is nice).

*Clean Inductive Proof (JRW)*

- Begin any induction proof by stating precisely, and prominently, the statement (“P(n)”) you plan to prove. A good idea is to put the statement in a display and label it (e.g., by an asterisk (∗) as above), so that it is easy to spot, and easy to reference.

- Be sure to properly begin and end the induction step. From a logical point of view, an induction step is a proof of a statement of the form (∀k ∈ N)[P (k) ⇒ P (k + 1)]. To prove such a statement, you need to start out with the “∀k ∈ N” part (“Let k ∈ N be given”), then assume P(k) is true (“Suppose (∗) is true for n = k”), and, after a sequence of logical deductions, derive P (k + 1) (“Therefore (∗) is true for n = k + 1”).

- Use different letters for the general variable appearing in the statement you seek to prove (n in the above example) and the variable used for the induction step (k in the above example). The reason for this distinction is that in the induction step you want to be able to say something like the following: “Let k ∈ N be given, and suppose (∗) is true for n = k. …. [Proof of induction step goes here] … Therefore (∗) is true for n = k + 1.” Without introducing a second variable k, such a statement wouldn’t make sense.

- Always clearly state, at the appropriate place in the induction step, when the induction hypothesis is being used. E.g., say “By the induction hypothesis we have …”, or use a parenthetical note “(by induction hypothesis)” in a chain of equations as in the above example. The induction hypothesis is the case n = k of the statement we seek to prove (i.e., the statement “P (k)”) and it is what you assume at the start of the induction step. The place where this hypothesis is used is the most crucial step in an induction argument, and you must get this hypothesis into play at some point during the proof of the induction step.

# Logic and formal proof systems

http://www.iep.utm.edu/logcon-d/ (a nice article about formal proof systems as well as the semantic side of logic. Sections 2 and 4, especially 4, are the most relevant to our class. The notation is a little different, but the basic ideas are the same)

# Equivalence relations (JRW)

Outline the forms for proving or disproving that a relation ≃ is reflexive, symmetric, or transitive.

Let ≃ be a relation on a set S.

Proving ≃ is reflexive.

To Prove: (∀a∈S) a≃a.

Form of Proof:

- Let a be an arbitrary (variable) element of S.
- Give an argument which concludes that a ≃ a.

Proving ≃ is not reflexive.

To Prove: (∃a∈S)a̸≃a.

Form of Proof:

- Let a be a specific element of S.
- Verify that a ̸≃ a.

Let ≃ be a relation on a set S.

Proving ≃ is symmetric.

To Prove: (∀a,b∈S)a≃b → b≃a.

Form of Proof:

- Let a and b be arbitrary (variable) elements of S.
- Assume that a ≃ b.
- Expand if its helpful. (It usually is.)
- Give an argument which concludes that b ≃ a.

Proving ≃ is not symmetric.

To Prove: (∃a,b∈S)(a≃b) ∧ (b̸≃a).

Form of Proof:

- Let a and b be specific elements of S.
- Verify that a ≃ b.
- Verify that b ̸≃ a.

Let ≃ be a relation on a set S.

Proving ≃ is transitive.

To Prove: (∀a,b,c∈S)(a≃b) ∧ (b≃c) → (a≃c).

Form of Proof:

- Let a, b and c be arbitrary (variable) elements of S.
- Assume that a≃b and b≃c.
- Expand if its helpful. (It usually is.)
- Give an argument which concludes that a ≃ c.

Proving ≃ is not transitive.

To Prove: (∃a,b,c∈S)(a≃b) ∧ (b≃c) ∧ (a̸≃c).

Form of Proof:

- Let a, b, and c be specific elements of S.
- Verify that a ≃ b.
- Verify that b ≃ c.
- Verify that a ̸≃ c.

http://www.math.vt.edu/people/elder/Math3034/book/3034Chap5.pdf

# Survey

https://plato.stanford.edu/entries/set-theory/

"Basic Set Theory": https://plato.stanford.edu/entries/set-theory/basic-set-theory.html

"Zermelo-Fraenkel Set Theory": https://plato.stanford.edu/entries/set-theory/ZF.ht