Results 1 to 5 of 5

Math Help - Basic Logic Question involving proofs

  1. #1
    Junior Member
    Joined
    Dec 2009
    From
    Texas
    Posts
    70
    Awards
    1

    Basic Logic Question involving proofs

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2009
    Posts
    10
    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
    Last edited by Seppel; December 21st 2009 at 01:36 AM. Reason: correcting a spelling mistake
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Dec 2009
    From
    Texas
    Posts
    70
    Awards
    1
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Mar 2009
    Posts
    256
    Thanks
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    Quote Originally Posted by james121515 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Logic proofs
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 21st 2011, 04:39 PM
  2. Logic Proofs
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: February 11th 2011, 01:42 AM
  3. basic predicate logic question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 23rd 2009, 03:55 PM
  4. Logic Proofs
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 21st 2008, 09:02 AM
  5. need help with two (basic?) proofs involving equicontinuity
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: April 18th 2008, 12:26 AM

Search Tags


/mathhelpforum @mathhelpforum