(adsbygoogle = window.adsbygoogle || []).push({}); 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], wenecessarilyhave [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!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Proving the proof by contradiction method

Loading...

Similar Threads for Proving proof contradiction |
---|

I Proof that BB(k) grows faster than any computable function |

I An easy proof of Gödel's first incompleteness theorem? |

I Cantor's decimal proof that (0,1) is uncountable |

A How does it not contradict the Cohen's theorem? |

**Physics Forums | Science Articles, Homework Help, Discussion**