Basic Logic Question involving proofs

**james121515** · December 20th 2009, 11:01 PM

Hi all,

What is the usual plan of attack if you have a "p -> (q -> r)" kind of statement you want to prove? My GUESS would you assume p and q and show that r is true? does
"(p /\ q) -> r" it have the same truth logic as "p -> (q->r)"? It seems like it would be harder to assume one statement, and then try to somehow prove that (another) conditional statement is true. Do we ever do that in mathematics or do we usually manipulate the logic?

For example, in my foundations level proof course I just finished, we dealt with some simple proofs involving functions, for example:

"Prove that If g o f is one-to-one, then f is one-to-one". Now in this case, the logic of this statement is p-> (q -> r), right? If I recall correctly, the definition of one-to-one is an implication, right? "If f(x1) = f(x2), then x1 = x2." So, in this specific case what would you be assuming and trying to prove?

I know your probably thinking if I just finished the class then I should know this stuff pretty well, well I do know it pretty well, but, this being my first semester taking a real math class, I really want to make sure I have this stuff down since I'm taking Algebra next semester.

Thanks for any help! :-)
james

**Seppel** · December 21st 2009, 12:28 AM

Hello james121515!

To prove a statement of the form p -> (q -> r) you have to use the rule of conditional proof two times. You first assume p and have to prove q -> r. So, you assume q and try to reach the statement r. If you reached it, you discharge your assumption q and can say that q -> r holds. But then you discharge your assumption p and can say that p -> (q -> r) holds which is what you wanted to prove.

Notice that in proving $p\wedge q\Longrightarrow r$ you use the rule of conditional proof only once. You assume $p\wedge q$ and try to reach r. If you reached it, you discharge your assumption $p\wedge q$ and can say that $p\wedge q\Longrightarrow r$ holds which you wanted to prove.

Though the two statements are equivalent, there is a difference how you prove them.

Regarding your example:

We have $f:L\longrightarrow M$ and $g:M\longrightarrow N$ , where L, M and N are sets. Then $g\circ f:L\longrightarrow N$ (be careful, your definition of $g\circ f$ may differ from the one I use, but I think you will understand it).

Now, $g\circ f$ is one-to-one means $\forall x_1\forall x_2[x_1\in L\wedge x_2\in L\Longrightarrow ((g\circ f)(x_1)=(g\circ f)(x_2)\Longrightarrow x_1=x_2)]$ . Besides, $f$ is one-to-one means $\forall x_1\forall x_2[x_1\in L\wedge x_2\in L\Longrightarrow (f(x_1)=f(x_2)\Longrightarrow x_1=x_2)]$ .

So you can see that the statement which is to prove in fact has the form p -> q and not p -> (q -> r). Nevertheless you had the right idea. To prove the statement you assume $\forall x_1\forall x_2[x_1\in L\wedge x_2\in L\Longrightarrow ((g\circ f)(x_1)=(g\circ f)(x_2)\Longrightarrow x_1=x_2)]$ and have to prove $\forall x_1\forall x_2[x_1\in L\wedge x_2\in L\Longrightarrow (f(x_1)=f(x_2)\Longrightarrow x_1=x_2)]$ . So, you have to let $x_1$ and $x_2$ be arbitrary and have to prove the statement $x_1\in L\wedge x_2\in L\Longrightarrow (f(x_1)=f(x_2)\Longrightarrow x_1=x_2)$ . Now you can see that this statement has the form p -> (q -> r). So, your idea that such a statement form occurs in this proof was right. To prove this statement you have to proceed as I mentioned in the beginning of my post. In the whole proof the rule of conditional proof is used three times (why and where?).

I want to add that you do not have to justify why you ask such questions. Indeed they are very good and very important. Do not stop to ask yourself such questions!

Best wishes,
Seppel

**james121515** · December 21st 2009, 07:17 PM

Hi Seppel! Thank you very much for your response! Your post definitely helped but I'm still a little confused. Here is the proof of the statement that my teacher put on the board. (rememebr this was a beginning proof course so he did not quantify the whole proof). This theorem is certainly of the form p -> (q ->r), correct?

THEOREM: Let f : A -> B and g : B -> D. If g o f is one-to-one, [p ->....] then f is one-to-one.[...(q ->r)]

PROOF: Suppose f(a1) = f(a2) = b. [Here we're supposing q] Since g : B ->D there exist d in D such thatg(b) = d. So, g(f(a1)) = g(f(a2)) =d. Equivalently, (g o f)a1 = (g o f)a2. Since g o f is one-to-one, [here we're also supposing p, so p /\ q] a1 = a2, hence, f is one-to-one. [we've proved r]

So, it seems to me like we've converted p -> (q->r) into p /\ q -> r in order to faciliate proving this statement?

Thanks again!
James

**xalk** · December 22nd 2009, 12:56 PM

Hello ,james121515

If you put :

f: A-->B and g : B--> D = P

gof is one to one =Q

f is one to one = R

Then the form of the theorem becomes :

or equivalently.

$P\wedge Q\Longrightarrow R$ .

And as seppel pointed out very correctly,either you use the 1st form and you have to use the rule of conditional proof twice,or you can use the 2nd form and must use the rule of conditional proof once.

But since by definition ,gof is one to one ,if and only if (iff)

for all ,x,yεA : $x\in A\wedge y\in A\Longrightarrow[(gof(x) = gof(y))\Longrightarrow x=y]$ .

If we put :
(xεA and yεA) = $q_{1}$ .................................................. ........................................1

(gof(x) =gof(y)) = $q_{2}$ .................................................. ........................................2

(x=y)= $q_{3}$ , we have that .................................................. .................................................. 3

Q= $[q_{1}\Longrightarrow(q_{2}\Longrightarrow q_{3})]$ .

Also ,since by definition, f is ono to one iff.

for all x,yεA : $x\in A\wedge y\in A\Longrightarrow[(f(x)=f(y))\Longrightarrow x=y]$ .

And if we put:

(f(x)=f(y)) = r ,in combination of (1) and (3) we that :

R = $[q_{1}\Longrightarrow( r\Longrightarrow q_{3})]$ .

Now for the proof we adopt the 1st form for the theorem and so:

1) we assume P

2) we assume Q = $[q_{1}\Longrightarrow(q_{2}\Longrightarrow q_{3})]$

Ans we want to prove R = $[q_{1}\Longrightarrow( r\Longrightarrow q_{3})]$

3) assume also $q_{1}$ = xεA and yεA.

From (2) and (3) we conclude :

4) $(q_{2}\Longrightarrow q_{3})$ = [(f(x)=f(y)) $\Longrightarrow x=y]$ .

5) assume r = (f(x) = f(y))

But since f(x)εB and f(y)εB AND g : B---->D we have :

6) (f(x) = f(y)) $\Longrightarrow g(f(x)) =g(f(y))\Longrightarrow gof(x) = gof(y)$ . or

$r\Longrightarrow q_{2}$ .

This is the central implication of the theorem.

From (5) and (6) we have :

7) $q_{2}$ .

From (4) and (7) we have :

8) $q_{3}$

So we have assumed in (5) r = (f(x) = f(y)) and end up with (8) and according to the rule of conditional proof we have proved so far:

9) $r\Longrightarrow q_{3}$

Also we have ASSUMED in (3) $q_{1}$ = ( xεA and yεA) and end up with (8) , $r\Longrightarrow q_{3}$ ,and according to the rule of conditional proof again we have proved :

10) $q_{1}\longrightarrow(r\Longrightarrow q_{3})$ which is the statement R i.e :

f is one to one.

So you see james121515 geting into the structure of a proof is not an easy matter and can get quite complicated.

On the other hand trying to explain the mechanics of a proof without diving into the depths of it can produce mere nonsenses.

Note also that apart from the rule of conditional proof the law of M.Ponens has been used repeatedly.

Any laws of quantification involved in a proper formal proof have been omitted.

**emakarov** · December 22nd 2009, 01:22 PM

Originally Posted by james121515

THEOREM: Let f : A -> B and g : B -> D. If g o f is one-to-one, [p ->....] then f is one-to-one.[...(q ->r)]

PROOF: Suppose g o f is one-to-one. [Here we're supposing p] Suppose f(a1) = f(a2) = b. [Here we're supposing q] Since g : B ->D there exist d in D such that g(b) = d. So, g(f(a1)) = g(f(a2)) =d. Equivalently, (g o f)a1 = (g o f)a2. Since g o f is one-to-one, [here we're also supposing p, so p /\ q] a1 = a2

I added the text in blue to show where we assume the first premise p.

I am not sure about two things. When you say "here we're also supposing p", you don't mean that this supposition is done by the phrase "Since g o f is one-to-one", do you? We assumed p, which is "g o f is one-to-one", in the beginning of the proof.

Second, why do you say "so p /\ q"? During a proof, we may have multiple assumptions that are separate independent formulas. Suppose that we have three assumptions: P, Q, and R. As a set, they are equivalent to P /\ Q /\ R. Namely, we can prove P /\ Q /\ R from P, Q, R; we also can prove any of P, Q, and R from P /\ Q /\ R. There is relatively little difference between the two, so sometimes it makes sense to identify the set {P, Q, R} with P /\ Q /\ R and move implicitly from one to the other. However, formally they are different: one is a set of three formulas, the other a formula (or a set of one formula); to move from one to the other one has to use the rules called Simplification and Conjunction in this Wikipedia table.

Below I write some fun extension of this that you may ignore.

The universal quantifier behaves very similarly to implication. When we need to probe $P\to Q$ , we assume $P$ and prove $Q$ . When we need to prove $\forall x.\, P(x)$ , we consider an arbitrary $x_0$ and prove $P(x_0)$ . Conversely, when we know $P\to Q$ , we can combine it with $P$ to get $Q$ . Similarly, when we know $\forall x.\,P(x)$ , we can combine it with some concrete $x_0$ to produce $P(x_0)$ . The first two rules, regarding assumption, are called introduction rules: one of implication, and the other of universal quantifier.

The exact form of some theorem depends on how much we unfold definitions. The following are actual snippets from the automated proof assistant program that I used to prove this theorem. The theorem may look like

Code:

injective (g o f) -> injective f

If we unfold the second "injective", we get

Code:

injective (g o f) ->
  forall x1 x2 : A,
    f x1 = f x2 -> x1 = x2       (*)

((*) is a mark for the future.) It's not exactly of the form P -> (Q -> R), but, since forall and -> are very similar, it's close.

Now we can start use the introduction rules. After four rules, our proof state looks as follows:

Code:

H1 : injective (g o f)
x1 : A
x2 : A
H2 : f x1 = f x2
============================
x1 = x2

This means we have two formulas and two objects (x1 and x2) as assumptions.
If, for example, instead of (*) we start with

Code:

forall x1 x2 : A,
  injective (g o f) ->
    f x1 = f x2 -> x1 = x2

and perform all introductions, we end up with the same proof state as above. On the other hand, if we start with

Code:

forall x1 x2 : A,
  injective (g o f) /\ f x1 = f x2 ->
    x1 = x2

we get

Code:

x1 : A
x2 : A
H : injective (g o f) /\ f x1 = f x2
============================
x1 = x2

It's trivial to transform it again to

Code:

x1 : A
x2 : A
H1 : injective (g o f)
H2 : f x1 = f x2
============================
x1 = x2

Note that so far we took the sets A, B, C and functions f, g as fixed. If we quantify over then as well, we get the following theorem:

Code:

forall (A B C : Set) (f : A -> B)
  (g : B -> C),
    injective (g o f) -> injective f

And if, in addition, we unfold "injective", we get a whopping

Code:

 forall (A B C : Set) (f : A -> B)
  (g : B -> C),
    (forall x1 x2 : A, (g o f) x1 = (g o f) x2 -> x1 = x2) ->
      forall x1 x2 : A, f x1 = f x2 -> x1 = x2

If we introduce everything, we get

Code:

A : Set
B : Set
C : Set
f : A -> B
g : B -> C
H1 : forall x1 x2 : A, (g o f) x1 = (g o f) x2 -> x1 = x2
x1 : A
x2 : A
H2 : f x1 = f x2
============================
x1 = x2

Disclaimer: no animal suffered during these experimants. All computations were performed by a computer.

Thread: Basic Logic Question involving proofs

LinkBack

Thread Tools

Display

Basic Logic Question involving proofs

Similar Math Help Forum Discussions

[SOLVED] Logic proofs

Logic Proofs

basic predicate logic question

Logic Proofs

need help with two (basic?) proofs involving equicontinuity

Search Tags