# Introduction to Proofs

Describe the steps in and/or define how to accomplish the following types of proofs:

a. That two sets are equal.

b. That two sets are disjoint.

c. A proof by contra-positive.

d. A proof by contradiction.

e. A proof by Mathematical Induction.

(Question is repeated in attachment)

Â© BrainMass Inc. brainmass.com December 24, 2021, 4:41 pm ad1c9bdddfhttps://brainmass.com/math/basic-algebra/introduction-proofs-types-1993

## SOLUTION This solution is **FREE** courtesy of BrainMass!

a. Proof that two sets are equal:

I'll call the sets A and B. Here, we want to show that the elements of each set are also in the other set, and that there are no extras in either set. So what we need to do is to show that if something is in set A, it's also in set B, and that if something is in set B, it's also in set A. That is, we want to show that if x is in A, that implies that x is in B, and that if y is in B, that implies that y is in A.

b. Proof that two sets are disjoint:

Here we want to show that none of the elements of either set are in the other set (remember that this is what "disjoint" means: the sets have nothing in common). So similarly to above, we want to show that if x is in A, that implies that x is NOT in B, and that if y is in B, that implies that y is NOT in A.

c. Proof by contrapositive:

Now I'll let A be my set of assumptions (the given information) and B be the thing I want to prove. The proof is then supposed to show that A => B (A implies B, our assumptions imply the conclusion).

Recall that the contrapositive of P => Q (P implies Q) is ~Q => ~P (not Q implies not P) and that these are equivalent statements. So if we have a set of assumptions A that we want to use to prove a statement B, equivalently we can show that ~B => ~A. So we assume the opposite of the thing we wanted to prove, and show that that implies the opposite of our assumptions.

d. Proof by contradiction:

This is similar to a proof by contrapositive, but it's not exactly the same. In a proof by contradiction, we take our assumptions A as normal, but we assume that the thing we want to prove, B, is false. Then we take this together (A and ~B) and show that somehow there's a contradiction; that our assumptions and the opposite (negation) of B cause something to be true and false at the same time, that sort of thing. An example of a contradiction is if we could show that A and ~B meant that both x<y and x>y. What this shows is that since we assume that our assumptions are true (they wouldn't be very good assumptions if not), the problem lies not with A but with ~B... ~B must have been false, which means that as long as A was true, B must be true, and this completes the proof.

e. Proof by mathematical induction:

There are three steps to a proof by induction:

i. Show a base case: in general, the thing we're trying to prove by induction is of the form "Show that for all integers n>0, B is true" where B depends on n somehow. We call this induction on n. In that example, our base case is n=1, it's the first number we're supposed to prove B for. If we had "Show that for all integers n>25, B is true" then our base case would be n=26. So the first step is to show that assuming n is that first number, B is true.

ii. Assume that B is true for n=k. This is an easy step, we just have to write down what it means for B to be true when n=k, which is basically just writing down B but replacing all the n's with k's.

iii. With that assumption, prove that B is true for n=k+1. This is the real substance of the proof by induction. What we've done so far is just shown one case, the base case. In this step we show all possible cases, all at once, which is a pretty impressive trick. What we do is write down what we want to show, meaning write down what it would mean for B to be true for n=k+1. Then usually in this statement we can isolate parts that we already know from our assumption that B is true for n=k. So we apply that knowledge and then usually what's left just takes a bit of manipulation and mathematical knowledge to show that B is also true for n=k+1.

What this accomplishes is showing that B is true for n=1 (let's say that's the base case)... but then we've shown that as long as B is true for n=k (k=1 for example), then B is true for n=k+1 (k+1=2 for example). So this logic shows that it's true for n=2, and then from the n=2 case we know the n=3 case, and so on, for all the integers.

Hope this helps you understand these types of proofs better, and be able to write up solutions in your own words. Remember, these types of proofs get used repeatedly in many disciplines (you might be surprised where proofs become important), so it's good to make sure that you could describe to someone else in your own words what these methods entail.

Â© BrainMass Inc. brainmass.com December 24, 2021, 4:41 pm ad1c9bdddf>https://brainmass.com/math/basic-algebra/introduction-proofs-types-1993