Results 1 to 7 of 7

Math Help - Mathematical Logic

  1. #1
    Newbie
    Joined
    Feb 2013
    From
    UK
    Posts
    10

    Mathematical Logic

    Hello (1st post!).

    I've been having a bit of trouble with this assignment question. I think i've done it right, but when you have 3 questions asking for a "true or false" answer, you'd expect at least one of them to be true!

    It's parts iiia), b) and c). (the parts with F? next to them. I've also posted what N and N** are further down the page)



    My answer to parts a) and b) are:



    (for part b), "curly N" (or N as i'll write) is just the usual addition and multiplication in the natural numbers. N** is similar, but with an alpha and beta added in (ordinals?). Here's what the book says:



    Finally, my answer to part c is:



    As you can see, i've followed a similar method every time. Since the formula is valid "for all x there exists y", it was my plan to find a y for some x so that it isn't true. Unfortunately, it seemed quite easy to find a counter example each time.

    Am I right? It would be stellar for someone to either back me up!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765

    Re: Mathematical Logic

    Welcome to the forum. Problems about mathematical logic should be posted to Discrete Math subforum. In fact, see this post.

    What is the scope of the existential quantifier in iii(a): just the premise \neg(y\cdot x')=y or the whole implication. Please refer to syntactic conventions about omitting parentheses after the description of the syntax of first-order logic in your textbook. My guess is that the scope is the premise only, i.e., ∃ binds stronger than ->. Then the statement is true. Indeed, \exists y\,y\cdot (x+1)\ne y is equivalent to x + 1 ≠ 1, i.e., x ≠ 0. In fact, if the scope of ∃ extends until the end of the implication, the formula is still true. Indeed, for x = 0 we can take any y, e.g., y = 1. Then y(x + 1) ≠ y is false, so the whole implication is true. If x ≠ 0, then again we can take any y, and the implication is true in virtue of the truth of the conclusion.

    I'll look at iii(b) and (c) later.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2013
    From
    UK
    Posts
    10

    Re: Mathematical Logic

    Welcome to the forum. Problems about mathematical logic should be posted to Discrete Math subforum. In fact, see this post.
    Oh, i've only just registered. Apparently, i've come late for the party!

    What is the scope of the existential quantifier in iii(a): just the premise \neg(y\cdot x')=y or the whole implication. Please refer to syntactic conventions about omitting parentheses after the description of the syntax of first-order logic in your textbook. My guess is that the scope is the premise only, i.e., ∃ binds stronger than ->. Then the statement is true.
    I'm afraid I only know as much (or less) as you do.

    Indeed, \exists y\,y\cdot (x+1)\ne y is equivalent to x + 1 ≠ 1, i.e., x ≠ 0.
    But only if y \neq 0?

    In fact, if the scope of ∃ extends until the end of the implication, the formula is still true. Indeed, for x = 0 we can take any y, e.g., y = 1. Then y(x + 1) ≠ y is false, so the whole implication is true. If x ≠ 0, then again we can take any y, and the implication is true in virtue of the truth of the conclusion.

    I'll look at iii(b) and (c) later.
    Ohhhh, I see! I had completely forgotten about that line in the implication truth table. I'll have another look at it tomorrow and post my new thoughts and answers.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765

    Re: Mathematical Logic

    Quote Originally Posted by Fumbles View Post
    I'm afraid I only know as much (or less) as you do.
    Various sources may have different syntactic conventions. There is much less agreement in this area than, say, about the order of the standard arithmetic operators. In fact, mathematical logic is notorious for the amount of details than one can vary while preserving the main results.

    Quote Originally Posted by emakarov View Post
    Indeed, \exists y\,y\cdot (x+1)\ne y is equivalent to x + 1 ≠ 1, i.e., x ≠ 0.
    Quote Originally Posted by Fumbles View Post
    But only if y \neq 0?
    One can't talk about the formula

    \exists y\,y\cdot (x+1)\ne y (*)

    when y ≠ 0, just like one can't talk about x ≠ 0 when y ≠ 0. Both (*) and x ≠ 0 have only one free variable x. It is legitimate to ask about the truth value of (*) when x = 0, but not when y = 0 because y is "not visible from the outside". The property of x encoded by (*) is that x + 1 is not a multiplicative unit, i.e., not every number multiplied by x + 1 stays unchanged. This phrase refers to x, of course, but y is hidden in the inner machinery, and it is not correct to refer to it.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2013
    From
    UK
    Posts
    10

    Re: Mathematical Logic

    I think I understand it. There's a bit I need to get my head around.

    I wanted to ask, with this as an example:

    "I am a martian"  \Rightarrow "My name is fumbles".

    Since i'm not a martian, the LHS is false. My name is indeed fumbles so the right hand side is true. By truth table logic, the entire statement is correct isn't it? It just seems odd since I could put anything that's true on the RHS even if it's seemingly unrelatable to the LHS, but somehow the entire thing is true. It might sound trivial, but i'm trying to contextualise the 1's and 0's that crop up in truth tables.

    I'd also like to hear your musings about the other parts of the question. Expect a post later on (maybe around 6) with new answers.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Feb 2013
    From
    UK
    Posts
    10

    Re: Mathematical Logic

    Here's my new answer to part a).



    That's a lot of work for just 1 mark!

    EDIT: Here's my new answer to part b). I think it's false.



    Finally, I got part c) to be true. This is some rough working, but it's still readable (the missed off first line is just a rewriting of the second):



    So, if these are all right, I think i've grasped this question solidly!
    Last edited by Fumbles; February 24th 2013 at 05:46 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,504
    Thanks
    765

    Re: Mathematical Logic

    Quote Originally Posted by Fumbles View Post
    "I am a martian"  \Rightarrow "My name is fumbles".

    Since i'm not a martian, the LHS is false. My name is indeed fumbles so the right hand side is true. By truth table logic, the entire statement is correct isn't it?
    Yes.

    Quote Originally Posted by Fumbles View Post
    It just seems odd since I could put anything that's true on the RHS even if it's seemingly unrelatable to the LHS, but somehow the entire thing is true.
    Yes, it may seem counterintuitive, but this is how implication is used in mathematics and in most cases in real life. For example, "For all natural numbers n, if n is divisible by 4, then it is divisible by 2" is true, so n can be instantiated with 2 or 3. Thus both False -> True and False -> False have to be True.

    There have been attempts in philosophical and mathematical logic to consider other types of implication (Wikipedia).

    Concerning the problem, I would still recommend finding out (or deciding for yourself) if ∃x P(x) -> Q means (∃x P(x)) -> Q or ∃x (P(x) -> Q) according to the conventions of your source. Otherwise, determining the truth values of formulas is like trying to prove x^{y^z}=x^{yz} not knowing if x^{y^z} means \left(x^y\right)^z or x^{(y^z)} it just does not make sense.

    In the new solution for (a) when x = 0, you say that y ≠ y is false, but you ignore ∃. The same goes for (b) and (c). If the formula says (∃y y ≠ y) -> 0 ≠ 0 (as I think), then you need to say that ∃y y ≠ y is false and so the implication is true. If it says ∃y (y ≠ y -> 0 ≠ 0), then you need to provide an y (here any y will do). When x ≠ 0, there is no need to consider the premise since the conclusion is true.

    For (b) and x = 0, if it says (∃y y * 1 ≠ y) -> 0 ≠ 0, then it is false since (∃y. y * 1 ≠ y) is true for y = α or y = β. If it says ∃y (y * 1 ≠ y -> x ≠ 0), then it is true because for y = 1 the premise is false.

    For (c) and x ≠ 1/2, again, it is not necessary to consider the premise since the conclusion is true. For x = 1/2 the situation is as in (a) (the formula is true) with the same remark.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. What does N.T.A mean in mathematical logic?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 1st 2010, 11:54 AM
  2. derive formulas in mathematical logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2010, 02:25 AM
  3. mathematical logic books
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 9th 2009, 10:03 AM
  4. Replies: 3
    Last Post: July 17th 2009, 10:10 AM
  5. Mathematical Logic Algorithm
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 7th 2009, 07:19 PM

Search Tags


/mathhelpforum @mathhelpforum