Thread: Help with questionable FOL translation and a proof based on the same principle

I'm using Fitch-style proofs where ~ denotes negation sign and x shows subproof, xx subproof within subproof et.c. (Sorry about this getting a bit messy, but in lack of better ideas this is how I try to write proofs here).



Exercise:

Translate the following into First Order Language by using predicates Number, Larger, Odd, Prime and the constant symbol 2:

"There is a number which is larger than every other number"

Solution:
"

where Larger(x,y) means x is larger than y."

Is this really correct? I would like to add " ~(x=y)" in front of the conditional. Does the above given answer not imply that x is larger than every other number AND also that it is larger than itself (or at least that some number is larger than itself)?
If it is true for all objects y, then it should also be true when y refers to the same object as x.

To me this principle seems obvious. Applicated:

Another exercise/solution from the same source states that one cannot prove ~ from a set of premises, including ~ . I believe the conclusion is provable using only this premise;


1. ~
2. x assumption towards contradiction
3. xx [a] assumption towards elimination
4. xx R(a,a)
5. xx
6. x )
7. xContradiction Contradiction intro 1,6
8. ~ ~ intro 2-7

Help is much appreciated, I feel quite puzzled about this since the given solutions to the exercises contradict my reasoning and the proof...
Thanks in advance!

Originally Posted by HeadmasterEel

"

where Larger(x,y) means x is larger than y."

Is this really correct?

No.

Originally Posted by HeadmasterEel

I would like to add " ~(x=y)" in front of the conditional. Does the above given answer not imply that x is larger than every other number AND also that it is larger than itself (or at least that some number is larger than itself)?

Right, you need the conjunct that ~x=y, otherwise, you have an x such that x is larger than itself, which is NOT entailed by the mere fact that there is an x that is larger than every OTHER y.

Originally Posted by HeadmasterEel

Another exercise/solution from the same source states that one cannot prove ~ from a set of premises, including ~ . I believe the conclusion is provable using only this premise

Maybe there is a misunderstanding about how the exercise is stated, because you are correct that ~ExRxx does imply ~ExAyRyx.

Thanks very much for your replies MoeBlee! It is appreciated=)

very unsure since these solutions are taken from an old exam why one would expect them to be correct. And usually the exams are correct even though one may have trouble seeing it at first so I will stay humble ...

The exact formulation of the "advanced" exercise is to either give a counter example or a proof of the following:

Premises:
1.
2.
3.~

Conclusion:
~

In the first post in this thread I think I proved this conclusion from only premise 3, then it must also follow when including more premises...

But the solution given to this exercise presents a counter example as follows:

"Let M be a model. The universe of this model is [0,1] = {a REAL : 0 a 1} where REAL is the set of real numbers. The interpretation R = {(a,b): a,b REAL and a<b } , that is R(a,b) a<b. Then the premises are true but the conclusion is false since 1 is the largest element in the model M."

My point is that, sure 1 is the largest element and it is larger than all the other elements. But 1 is not larger than itself. No element is larger than itself.
Hence, also in this model it is true that ~ , that is: it is not true that there is an objct which is larger than every object.

This is very similar to the translation problem in that it does not seem to take into account that x and y can refer to the very same object (which I believe they can? that seems o be the key question here).

Further input is most welcome=)

Originally Posted by HeadmasterEel

give a counter example or a proof

Okay "OR a proof." Yes, and we don't even need the first two premises, indeed, as you observed ~ExRxx proves ~ExAyRyx.

Originally Posted by HeadmasterEel

I proved this conclusion from only premise 3, then it must also follow when including more premises

Yep, and that observation even has a name; it's called the 'monotonic property' of our logic. That is, if a set of formulas G proves a formula P then, if G is a subset of H, then H also proves P.

Originally Posted by HeadmasterEel

in this model it is true that ~ , that is: it is not true that there is an objct which is larger than every object.

Unless I'm overlooking something, you're right. Where did you get these exam "answers"? Given your description of them, unless I'm spacing out right now, they're wrong.

Originally Posted by HeadmasterEel

x and y can refer to the very same object (which I believe they can?

Yep, it very well could be that x=y.

Originally Posted by HeadmasterEel

"There is a number which is larger than every other number"

I agree, I think you were right to catch that requirement. I believe its prenex normal form would be something like:



Using set notation and bounded quantifiers we might shorten it:



As for the proof, I think the statement (when interpreted) makes more sense if you process the negation through (and do quantifier transformations). If we think of R as "less than," for instance, then the first sentence says for each x there is a y that is not less than it (i.e., for each x we can find a larger y). The other says every x is not larger than itself. I think there is something up with that proof, though. I'll think about it later.

Originally Posted by bryangoodrich

I

As for the proof, I think the statement (when interpreted) makes more sense if you process the negation through (and do quantifier transformations). If we think of R as "less than," for instance, then the first sentence says for each x there is a y that is not less than it (i.e., for each x we can find a larger y). The other says every x is not larger than itself. I think there is something up with that proof, though. I'll think about it later.

I'm sorry but my english is not perfect and I feel a bit unsure what you mean here...

But as I try to interpret what you mean;

~ corresponds to ~

and ~ corresponds to ~ ;

still I think the first is readily proven from the second, both formally:
~
~
~ R
~ R

with proper rules, and informally by reasoning:

"

the first sentence says for each x there is a y that is not less than it (i.e., for each x we can find a larger y)

."
here I would like to SAY "for each x we can find a large OR EQUALLY LARGE y", since I think "Not less than" means "equally large or larger".

All objects are not less than itself, hence it is true that we can find an object which is not larger than x for all x, namely x itself is not larger than x.

Maybe this was just what you tried to say?=) Or maybe I made some mistakes in the reasoning.. as usual, input always welcome and appreciated=)

Originally Posted by MoeBlee

Unless I'm overlooking something, you're right. Where did you get these exam "answers"? Given your description of them, unless I'm spacing out right now, they're wrong.

Yep, it very well could be that x=y.

Well, these solutions are "suggested solutions" from the course homepage and usually those are quite correct even when it is first hard to see. That is why I wanted assurances here before I jump to conclusions about the suggested solutions...

Originally Posted by HeadmasterEel

maybe I made some mistakes in the reasoning

I didn't doublecheck the details of the annotation of your proof in your first post, but your reasoning itself is all correct.

Originally Posted by HeadmasterEel

these solutions are "suggested solutions" from the course homepage

What's the URL of that homepage? I'd like to see it myself to verify that it is incorrect.