Proof by induction generally requires 3 steps, as outlined below. The first step, while critical, is often assumed in most definitions you come across, but I point it out here for the sake of being thorough.

Let m ∈ ℤ. To prove that P(n) is true for all integers n ≥ m, perform the following steps... 

1. Clearly define the statement you are trying to prove for all n, P(n). It may simply be a verbal statement, like "n is prime," or it may be a mathematical statement that some recursive function definition, f(n), is equivalent to the calculation you're trying to represent recursively.

2. Prove that P(m) is true. This is equivalent to saying "prove P for all minimal elements in the set" if you're dealing with a well-founded set, or "prove the basis case" if you're dealing with a recursive function. 

3. Make an assumption and use it to prove P(n). Assume that n is an is an arbitrary integer n > m, and assume that P(k) is true for all k in the interval m ≤ k < n. Prove that P(n) is true.

Suppose we are going to use this process to prove that every natural number n ≥ 2 is prime or a product of prime numbers. 

1. Let P(n) be the statement, "n is prime or a product of prime numbers" for every natural number n ≥ 2.

What is step 2?

Which of the following relations are partial orders? Select all that apply.

Suppose A = {a, b} and a precedes b in the alphabet.

Recall that A* (the closure of A), is just all possible strings over A.

The lexicographic ordering on A* is defined as follows: x ≺ y iff either x is a proper prefix of y or x and y have a longest common proper prefix u such that x = uv, y = uw, and head(v) precedes head(w) in A. (This mathematical definition simply describes what we think of as dictionary ordering of strings. For example: a ≺ b, aa ≺ ab, etc.)

Is the lexicographic ordering on A* well-ordered?

Consider the following partially ordered set (poset):

<S, R>, where...

S = {2, 4, 5, 10} ; R = | (divides)

Which element(s) is(are) the minimal element(s) of S? Select all that apply.

True or False?

If every pair of distinct elements in a partial order are comparable, then the order is called a total order (or a linear order).

Proof by induction generally requires 3 steps, as outlined below. The first step, while critical, is often assumed in most definitions you come across, but I point it out here for the sake of being thorough.

Let m ∈ ℤ. To prove that P(n) is true for all integers n ≥ m, perform the following steps... 

1. Clearly define the statement you are trying to prove for all n, P(n). It may simply be a verbal statement, like "n is prime," or it may be a mathematical statement that some recursive function definition, f(n), is equivalent to the calculation you're trying to represent recursively.

2. Prove that P(m) is true. This is equivalent to saying "prove P for all minimal elements in the set" if you're dealing with a well-founded set, or "prove the basis case" if you're dealing with a recursive function. 

3. Make an assumption and use it to prove P(n). Assume that n is an is an arbitrary integer n > m, and assume that P(k) is true for all k in the interval m ≤ k < n. Prove that P(n) is true.

Suppose we came up with the following recursive definition for 2 + 4 + … + 2n.

f(n) = if n = 0 then 0 else f(n-1) + 2n

We would like to show that our recursive function definition is correct using the inductive proof process described above. What is step 1?

Which of the following orders are well-founded? Select all that apply.

(Hint: Recall that a partially ordered set is said to be well-ordered if every descending chain of elements is finite. In this case, the partial order is called a well-founded order.)

Consider the function f : {a, b, c} → {1, 2, 3} defined by f(a) = 1, f(b) = 1, f(c) = 2. What is f^-1({3})?

Suppose f : A → B. What is the codomain of f?

Which of these functions are examples of partial functions? Select all that apply.