Greatest Hits on the Midterm

• State the assumptions in a proof by contradiction. Suppose you are trying to show \forall x\in X, A(x)\rightarrow B(x).

  • Correct:

    • Let x\in X.

    • Let A(x) be true.

    • Let B(x) be false.

    Wrong:

    • If for x\in X A(x) is true, then B(x) is false.

    That's simply a wrong statement and has nothing to do with a proof, by contradiction or otherwise.

• In a proof by induction, P is a predicate, and the truth value of P(n) is to be determined as true for every natural number n. In particular, P(n) is not a number, and it is not equal to anything. It can, at best, be equivalent ("\equiv"") to another statement, typically an equality, i.e. P(n)\equiv ( \text{SOMETHING} = \text{SOMETHING ELSE}).

• Sets are always written in braces. The argument of \mathcal P, the power set function, is always a set. The power set always includes the empty set.

  • Correct:

    • A = \{1,2\}

    • \mathcal P(A)=\mathcal P(\{1,2\})=\{\emptyset, \{1\}, \{2\}, \{1,2\}\}

    Wrong:

    • A=1,2

    • A=(1,2)

    • \mathcal P(1,2)

    • P(\{1,2\})=\{\{1\}, \{2\}, \{1,2\}\}

• For the inverse, converse, and contrapositive of \forall x\in X, A(x)\rightarrow B(x), the quantifier on x does not change, it stays \forall.

• Numbers are not truth values: 5\land x=7 makes no sense. Likewise, n \lor 17 is also wrong.