Proving the proof by contradiction method

[Dr. Seafood]

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. $A = \{x : P(x)\}$. We have the usual notions of subset, union, intersection, set difference, complement, etc.

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

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

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

"$\subseteq$" Let $x \in A$. Then $x \in S$. But $x \notin B$ since $A \cap B = \emptyset$. Thus $x \in S \setminus B$.
"$\supseteq$" Let $x \in S \setminus B$. Then $x \in S$, but $x \notin$. Since $A \cup B = S$, we get $x \in A$.

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

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!

 

[camilus]

the part where A intersect B = empty is basically an axiom. That's why this method works, because we use the law of excluded middle.

 

[Hurkyl]

It's a little hard to comment without knowing your precise motivation. Naive set theory and naive logic are more or less synonymous; they only differ in the words (and symbols) used. The form of a proof can vary a lot depending on what your set of axioms are and the level of detail you intend.

e.g. at the most extreme level of detail, you ought to justify why $x \notin B$ and $A \cup B = S$ imply that $x \in A$.



As an editorial note, in your mutual inclusion proof, you proved A=S\B, but the result you use is B=S\A. It's probably to swap A and B so that you instead prove B=S\A, rather than invoke an implied symmetry argument.



That said, I'm not sure this counts as justifying proof by contradiction. What you're really justifying is that complementary propositions are actually negations of each other.


Proof by contradiction would more closely relate to the following fact:

If $A = \emptyset$, then $x \notin A$​

 

[xxxx0xxxx]

I usually observe that:

$$(P \Rightarrow (P \wedge \neg P)) \Rightarrow \neg P$$

is a tautology irrespective of any of the various set theories, and go from there.

 

[Dr. Seafood]

It's a little hard to comment without knowing your precise motivation. Naive set theory and naive logic are more or less synonymous; they only differ in the words (and symbols) used. The form of a proof can vary a lot depending on what your set of axioms are and the level of detail you intend.

e.g. at the most extreme level of detail, you ought to justify why $x \notin B$ and $A \cup B = S$ imply that $x \in A$.

I realize this. I'm presenting to undergrads, from freshman to seniors. Myself, I'm in my 2nd year. The only "axioms" I want to use are just simple intuitive things like that sets exist, that "set membership" is well-defined, that I can take unions, etc. Of course, considering my audience, I will assume everyone is comfortable with basic set notation if not formal set theory. I haven't ever taken a formal set theory course anyway. I just want to use sets as a vehicle of deepening understanding of these proof methods. I hope this gives a better understanding of the level of detail I want to achieve here.

As an editorial note, in your mutual inclusion proof, you proved A=S\B, but the result you use is B=S\A. It's probably to swap A and B so that you instead prove B=S\A, rather than invoke an implied symmetry argument.

The proof of both B = S \ A and A = S \ B are identical for practical purposes -- the difference is just interchanging symbols. For clarity, I should probably prove B = S \ A then.

That said, I'm not sure this counts as justifying proof by contradiction. What you're really justifying is that complementary propositions are actually negations of each other.

Proof by contradiction would more closely relate to the following fact:

If $A = \emptyset$, then $x \notin A$​

Interesting. I will see what I can do with that then!

Alternatively, I'm trying to show that if the negation of a property does not hold, then the property must always hold; i.e. if $B = {x \in S : \not P(x)} = \emptyset$, then $A = {x \in S : P(x)} = S$. I wonder if this is a reasonable approach.

 

[Dr. Seafood]

I will show you what I have prepared on induction. My goal is to give new light on well-understood ideas, especially for freshman and juniors. Everyone learns mathematical induction in first year, so I just want to show a less common characterization of this concept.

Let $\mathbb{N} = \{1, 2, 3, ...\}$ and $S \subseteq \mathbb{N}$ with $S \neq \emptyset$. Then there exists $s \in S$ such that $s \leq x$ for all $x \in S$. This says that every nonempty subset of the natural numbers has a least element. We know this as the well-ordering principle of $\mathbb{N}$.

Induction. Let $S \subseteq \mathbb{N}$ and suppose (i) $1 \in S$ and (ii) whenever $k \in S$, we get $(k + 1) \in S$. Then $S = \mathbb{N}$.

Proof. Suppose that $S \neq \mathbb{N}$ towards contradiction. Then its complement (with respect to $\mathbb{N}$) is nonempty. Let $T = \mathbb{N} \setminus S$. Since T is nonempty, by well-ordering T has a least element, say $t \in T$. Since $1 \in S$ by (i), $1 \notin T$; so we can take $t \neq 1$ so $t > 1$.
$(t - 1) \notin T$ since t is the smallest number in T. Thus $(t - 1) \in S$. But then by (ii), $(t - 1) + 1 = t \in S$, a contradiction. □

This is the type of presentation I want to make for my seminar.

 

[xxxx0xxxx]

I will show you what I have prepared on induction. My goal is to give new light on well-understood ideas, especially for freshman and juniors. Everyone learns mathematical induction in first year, so I just want to show a less common characterization of this concept.

Let $\mathbb{N} = \{1, 2, 3, ...\}$ and $S \subseteq \mathbb{N}$ with $S \neq \emptyset$. Then there exists $s \in S$ such that $s \leq x$ for all $x \in S$. This says that every nonempty subset of the natural numbers has a least element. We know this as the well-ordering principle of $\mathbb{N}$.

Induction. Let $S \subseteq \mathbb{N}$ and suppose (i) $1 \in S$ and (ii) whenever $k \in S$, we get $(k + 1) \in S$. Then $S = \mathbb{N}$.

Proof. Suppose that $S \neq \mathbb{N}$ towards contradiction. Then its complement (with respect to $\mathbb{N}$) is nonempty. Let $T = \mathbb{N} \setminus S$. Since T is nonempty, by well-ordering T has a least element, say $t \in T$. Since $1 \in S$ by (i), $1 \notin T$; so we can take $t \neq 1$ so $t > 1$.
$(t - 1) \notin T$ since t is the smallest number in T. Thus $(t - 1) \in S$. But then by (ii), $(t - 1) + 1 = t \in S$, a contradiction. □

This is the type of presentation I want to make for my seminar.

I think it would be better to avoid all of the complexity, and use something simple like the following set theorem, which makes rich use of proof by contradiction:

$$\forall x (x \not \in \emptyset)$$

 

[micromass]

I will show you what I have prepared on induction. My goal is to give new light on well-understood ideas, especially for freshman and juniors. Everyone learns mathematical induction in first year, so I just want to show a less common characterization of this concept.

Let $\mathbb{N} = \{1, 2, 3, ...\}$ and $S \subseteq \mathbb{N}$ with $S \neq \emptyset$. Then there exists $s \in S$ such that $s \leq x$ for all $x \in S$. This says that every nonempty subset of the natural numbers has a least element. We know this as the well-ordering principle of $\mathbb{N}$.

Induction. Let $S \subseteq \mathbb{N}$ and suppose (i) $1 \in S$ and (ii) whenever $k \in S$, we get $(k + 1) \in S$. Then $S = \mathbb{N}$.

Proof. Suppose that $S \neq \mathbb{N}$ towards contradiction. Then its complement (with respect to $\mathbb{N}$) is nonempty. Let $T = \mathbb{N} \setminus S$. Since T is nonempty, by well-ordering T has a least element, say $t \in T$. Since $1 \in S$ by (i), $1 \notin T$; so we can take $t \neq 1$ so $t > 1$.
$(t - 1) \notin T$ since t is the smallest number in T. Thus $(t - 1) \in S$. But then by (ii), $(t - 1) + 1 = t \in S$, a contradiction. □

This is the type of presentation I want to make for my seminar.

It might be fun to generalize this result to arbitrary well-ordered sets.

A set X is well-ordered if all non-empty subsets of X have a least element. In particular, X has a least element 0.

Now the induction can be defined as:
If $S\subseteq X$ is such that

• 0 is in S
• If y in X has that $\{x\in X~\vert~x\leq y\}\subseteq S$, then y is in S.

Then S=X.

The fun thing is that every set can be well-ordered (using the axiom of choice). So we can do induction on every set! This is called transfinite induction.

 

[Dr. Seafood]

^ Yeah, I know about that stuff! That's a super good idea, thanks a lot. I will upgrade my presentation to discuss transfinite induction. Thanks for the idea!

 

[PatrickPowers]

Proof by contradiction would more closely relate to the following fact:

If $A = \emptyset$, then $x \notin A$​

I have seen "x is an element of the empty set if and only if x is not equal to itself."

I'm told that this can be proved to be always true in any system of logic. There are two possible results: either all elements are not in the empty set, or all elements are. Needless to say, systems of the first type are found to be more useful.