2
$\begingroup$

In the book How to prove it, page 102, the following problem is given: Suppose A, B, and C are sets, A \ B ⊆ C, and x is anything at all. If x ∈ A \ C then x ∈ B.

I can prove it the following manner:

x ∈ A \ C $\rightarrow$ (x ∈ A $\wedge$ x not ∈ C)

It is given that

A \ B ⊆ C

x not ∈ C => x not ∈ A \ B

x not ∈ A \ B can be expressed as:

$\neg$ (x ∈ A $\wedge$ x not ∈ B) = (x not ∈ A $\vee$ x ∈ B)

by conditional law:

(x not ∈ A $\vee$ x ∈ B) = (x ∈ A $\rightarrow$ x ∈ B).

It is given that x ∈ A hence x ∈ B.

But the proof is provided by contradiction as follows: Proof. Suppose x ∈ A \ C. This means that x ∈ A and x not ∈ C. Suppose x not ∈ B. Then x ∈ A \ B, so since A \ B ⊆ C, x ∈ C. But this contradicts the fact that x not ∈ C. Therefore x ∈ B. Thus, if x ∈ A \ C then x ∈ B.

Why is proof by contradiction necessary preferred here? Is not the first proof more intuitive and enough?

$\endgroup$
9
  • 3
    $\begingroup$ "$x$ is anything at all"? I'd like to have a chat with the author... $\endgroup$
    – ajotatxe
    Mar 13, 2018 at 13:46
  • $\begingroup$ What's your justification of the line that begins "but we know"? $\endgroup$
    – BallBoy
    Mar 13, 2018 at 14:00
  • $\begingroup$ @Y.Forman x ∈ A, and x not ∈ A \ B can only be true if $\rightarrow$ x ∈ B ? $\endgroup$
    – coder_bro
    Mar 13, 2018 at 14:07
  • $\begingroup$ @Ngm Can you justify that claim? It's the least self-evident step of your proof. $\endgroup$
    – BallBoy
    Mar 13, 2018 at 14:10
  • 1
    $\begingroup$ @Ngm Looks good now. I'd say the advantage of the author's proof over yours is that yours involves more logical manipulations. On the other hand, the author's proof needs contradiction, while yours doesn't. At this point, I'd agree with klirk that "Which one is more intuitive is up to personal taste." $\endgroup$
    – BallBoy
    Mar 13, 2018 at 14:54

1 Answer 1

3
$\begingroup$

Your proof is correct. Which one is more intuitive is up to personal taste.

I like the proof by contradiction, as it allows to dircectly use the assumption $A\setminus B \subset C$.

In comparison, your direct proof assumes $x\in A\setminus C$. So in order to use the assumption, you have to negate it first, i.e. you look at the complements $C^c\subset (A \setminus B)^c$.

As a remark to your proof: Even though you wrote in the beginning that the goal is to prove x ∈ A \ C → (x ∈ A ∧ x not ∈ C), during the proof you should make clear that you consider an $x \in A\setminus C$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .