0.4 Discrete structures set theory  (Page 3/6)

Finding a proof is in general an art. There is no single method that works for all cases. However, at this level the most important thing to remember is to know and understand definitions of concepts involved. The next important thing to keep in mind is to look up relevant facts and try to use them. Even if you don't see the entire path to the goal, if you move one step forward from where you are, you get a new perspective and it often gives you some good ideas to pursue. Needless to say that you must not forget the inference rules. It is not a bad idea to review "Problem Solving" we studied earlier here.

There are also some well used and often very useful proof techniques such as trivial proof, vacuous proof, direct proof, proof by contradiction, proving the contrapositive, and proof by induction. These are explained below with proofs of the theorems on subset relation as examples.

Theorem 1: A ⊆ U.

Proof: By the definition of ⊆ , we need to show that ∀x [x ∈ A → x ∈ U].

For that, what we need is to show that for an arbitrary x, x ∈ A → x ∈ U holds according to the inference rule "universal generalization".

Since x is an object of the universe of discourse, x ∈ U is true for any arbitrary object by the Universal Instantiation. Hence x ∈ A → x ∈ U is true for any arbitrary object x (p→ q is always true if q is true regardless of what p is). Thus by the Universal Generalization ∀x [x ∈ A → x ∈ U], that is, A ⊆ U by the definition of subset.

We say p→ q is trivially true if q is true, and this kind of proof (i.e. showing q is true for p→ q without referring to p) is called a trivial proof.

Theorem 2: ∅ ⊆ A.

Proof: By the definition of ⊆ , we need to show that ∀x [x ∈ ∅ → x ∈ A]. For that, what we need is to show that for an arbitrary x, x ∈ ∅ → x ∈ A holds. Then apply the Universal Generalization.

Since ∀x x ∉ ∅, for any arbitrary x, x ∈ ∅ is false by the Universal Instantiation.

Hence x ∈ ∅ → x ∈ A is true for any arbitrary x (p→ q is always true if p is false regardless of what q is). Hence by the Universal Generalization ∀x [x ∈ ∅ → x ∈ A]. Thus ∅ ⊆ A by the definition of subset.

We say p→ q is vacuously true if p is false, and this kind of proof (i.e. showing p is false for p → q) is called a vacuous proof.

Proof Variations for Theorem 2

Theorem 2, like most others, can be proven in a number of other ways. Here we try to prove it in two other ways.

(1) Proof by Contrapositive:

In this method, to prove p → q we prove its contrapositive, ¬q → ¬p, instead. So to prove x ∈ ∅ → x ∈ A for an arbitrary x, try to prove x ∉ A → x ∉ ∅. In this case since x ∉ ∅ is true for any arbitrary x, x ∉ A → x ∉ ∅ is trivially true. Hence its contrapositive x ∈ ∅ → x ∈ A is also true.

(2) Proof by Contradiction:

In this method, to prove p we assume ¬p and derive a contradiction from that. Then since ¬p implies a contradiction, it can not hold true. Hence p must be true.So to prove ∀x [x ∈ ∅ → x ∈ A] we assume that ¬∀x [x ∈ ∅ → x ∈ A]. ¬∀x [x ∈ ∅ → x ∈ A] is equivalent to ∃x ¬[x ∈ ∅ → x ∈ A]. This in turn is equivalent to ∃x [x ∈ ∅ ⋀ x ∉ A].