Thread: 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!

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 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, 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.

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 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, is equivalent to x + 1 ≠ 1, i.e., x ≠ 0.

But only if ?

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.

Originally Posted by Fumbles

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.

Originally Posted by emakarov

Indeed, is equivalent to x + 1 ≠ 1, i.e., x ≠ 0.

Originally Posted by Fumbles

But only if ?

One can't talk about the formula

(*)

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.

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" "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.

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!

Originally Posted by Fumbles

"I am a martian" "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.

Originally Posted by Fumbles

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 not knowing if means or — 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.