Here is midterm 2.

Solutions follow.

**Problem 1** introduces a relation on integers by saying that iff the difference between and is at most 3. In symbols, The problem asks to determine whether is transitive.

It is not. For a counterexample, consider We have and but

**Problem 2** lets be the collection of finite subsets of a set and defines a relation on by setting iff is even. The problem is to show that is reflexive and symmetric.

To prove reflexivity, let be an arbitrary finite subset of Then so Since is even, we conclude that

To prove symmetry, let be finite subsets of such that is even. Since we have that is even, and

**Problem 3** informs us that is a property about integers and asks us to choose among a few options for what is needed to do in order to prove that “For every integer there exists an integer such that is true.”

To do this, we need to start with an arbitrary integer and then find an integer that makes true. Of course, if we choose a different it could be that the that now works is different, i.e., it may well be that depends on Of the options listed in the problem, it is (e) that precisely captures this.

Note that if one manages to show (a) or (f), then one also succeeds in proving the required statement. However, both (a) and (f) are too strong in general, i.e., there are cases where the given statement holds but both (a) and (f) fail. None of the other options even guarantees the truth of the statement.

**Problem 4** gives as an erroneous proof, and requires to identify the flaw. The statement being claimed is that all natural numbers are divisible by 3. The argument uses the well-ordering principle, and contradiction. Assuming that the statement is false means that there are natural numbers not divisible by 3. Letting be the set of all these numbers, this means that The well-ordering principle guarantees that there is a least element of and we call it

Clearly, is not divisible by 3, so in particular

The argument then asks to consider Obviously, and therefore is not in If happens to be a natural number, then we are forced to conclude that and therefore since However, there is also the chance that in which case we cannot conclude that Thus, we cannot conclude that The flaw in the argument, of course, is in assuming that which is only assured if

**Problem **5 asks to prove by induction that, for all positive integers we have

To argue by induction, we first prove the base case, when We have on the left hand side and on the right hand side as well. The inequality holds (in fact, it is an equality in this case).

Now we argue the inductive step. Assume that, indeed,

We need to prove that also

To do this, note that

The sum inside the first set of parentheses is at least by the inductive assumption. We are done if we manage to show that the sum within the second set of parentheses is at least

But note that etc, so the second sum is at least

where there are precisely many terms being added, all of them equal to This means that this sum adds up to Since this is what we needed, we have completed the inductive step, and therefore the proof.