- #1

- 121

- 0

**Proving the "proof by contradiction" method**

This can get a little bit fundamental or "axiomatic", if you will. Let's say we can describe sets by prescribing a fixed property P on objects of a certain type, and claiming that a set is a collection of objects satisfying P; i.e. [itex]A = \{x : P(x)\}[/itex]. We have the usual notions of subset, union, intersection, set difference, complement, etc.

**Result.**Let S be a set of objects (the "universe") and [itex]A, B \subseteq S[/itex]. Take the convention that neither A nor B are empty. Suppose A and B partition S in the following sense: [itex]A \cup B = S[/itex], and [itex]A \cap B = \emptyset[/itex]. Then if [itex]x \in S[/itex] with [itex]x \notin A[/itex], we

*necessarily*have [itex]x \in B[/itex].

**Remark.**Notice that this will show that we can use the "contradiction" method: let [itex]A = \{x \in S : P(x)\}[/itex] and [itex]B = \{x \in S : \neg P(x)\}[/itex]. Of course, [itex]A \cup B = S[/itex] and [itex]A \cap B = \emptyset[/itex]. If we can show that for all [itex]x \in S[/itex], we have [itex]x \notin B[/itex] (i.e. x cannot satisfy [itex]\neg P(x)[/itex]), then we will necessarily have [itex]x \in A[/itex] (i.e. x satisfies [itex]P(x)[/itex]).

**Proof of result.**First we will show that [itex]A = S \setminus B[/itex] and vice-versa (lemma) -- we will do this by showing mutual inclusion of these sets.

"[itex]\subseteq[/itex]" Let [itex]x \in A[/itex]. Then [itex]x \in S[/itex]. But [itex]x \notin B[/itex] since [itex]A \cap B = \emptyset[/itex]. Thus [itex]x \in S \setminus B[/itex].

"[itex]\supseteq[/itex]" Let [itex]x \in S \setminus B[/itex]. Then [itex]x \in S[/itex], but [itex]x \notin[/itex]. Since [itex]A \cup B = S[/itex], we get [itex]x \in A[/itex].

We will move on to the proof of the main result. Suppose [itex]x \notin A[/itex]. By the lemma, since [itex]B = S \setminus A[/itex], we get [itex]x \in B[/itex]. □

I'm clearly playing around with boolean logic and using loose definitions of set-axiomatic items. I want to be very careful as I am presenting a formal talk on using sets to describe proofs by contradiction, induction and contraposition in the same manner as I have done above. I'm sure about my results for the latter two, but "proving" that proofs by contradiction are valid is tricky and seemingly not possible. I'm not sure if I've done it correctly here so please point out any flaws in this argument. Thanks!

Last edited: