Examples of L-structures in First-Order Logic

[rainwyz0706]

1. Homework Statement

Let L = {P } be a first-order language with a binary relation symbol
P as only non-logical symbol. By exhibiting three suitable L-structures prove
(informally) that no two of the following sentences logically implies the other
(i) ∀x∀y∀z(P (x, y) → (P (y, z) → P (x, z))),
(ii) ∀x∀y(P (x, y) → (P (y, x) → x = y)),
(iii) (∀x∃yP (x, y) → ∃y∀xP (x, y)).

I really don't have a clue how to handle this problem. Could anyone please give me some hints of the L-structures? Any help is appreciated!

 

[Martin Rattigan]

An L-structure is a formalisation of an interpretation of a language. If you think first of an interpretation, then constructing the corresponding L-structure is just turning the handle of the sausage machine.

So the first thing to do is to think of interpretations for which each of (i),(ii) and (iii) (in turn) are false while the other two are true. This would then mean that no two of the sentences logically implies the third. You can then construct corresponding L-structures.

You should check exactly how the L-structures are constructed in the exposition you're following, and exactly how the phrase "logically implies" is defined (this may be in terms of the L-structures). If for some reason you can't find this information there's a reasonably straightforward explanation http://www.maths.ed.ac.uk/~s0571100/Logic.pdf , but try not to mix and match definitions because there can be slight differences which don't affect the meaning in general but can affect whether your proof is considered correct.

 

[rainwyz0706]

Thanks a lot for your help. I can only think of <Q, >>, which would make 1,2 true and 3 false. And I'm not sure that I've interpreted 3 correctly. Could you explain it a little bit more please?

 

[Martin Rattigan]

OK that example is correct.

Conditions (i) and (ii) are almost the requirement for P to be a weak partial order. (By weak I mean "$\leq$" type rather than "$<$" type.) But there's something missing - what?

You've chosen a weak partial (actually total) order with no maximum and that makes the third condition false, because it says, "if everything $\leq$ something, then something $\geq$ everything". That is, "if the domain of P is its whole field (that is the whole of the domain of interpretation in this case) then P must have a maximum", which $\mathbb{Q}$ of course doesn't.

If you answer the question in the first paragraph that should give you possible other interpretations to use.

 

[Martin Rattigan]

Correction; I didn't read your answer properly. You chose a strong partial order ("$>$" type, rather than "$\leq$" type).

If you'd said $(\mathbb{Q},\leq)$ what I said would make sense. The changes to make it correspond with what you said are straightforward.

That should give you a further clue. If you're still struggling ask again.

 

[rainwyz0706]

Thanks. What if I change Q into all non-positive rational numbers, then it has a maximum. Would that work?
Also, that's only one l-structure. Could you give me some hints about the other two possible l-structure?

 

[Martin Rattigan]

I said I misread your answer, not your answer was wrong.

With your suggested change it would still be correct. But notice I was talking about a maximum in connection with $(\mathbb{Q},\leq)$, because I'd misread the answer. If I'd talked about $(\mathbb{Q},\geq)$ instead (which is still not quite what you wrote), I'd have talked about a minimum. In fact with a strict order the definitions of maximum and minimum in terms of the ordering relation have to change slightly.

Sorry I obviously confused you there.

So - I'll give you an interpretation to show (ii) is not a logical consequence of (i) and (iii).

The domain of interpretation will be a pair of distinct cabbages and $P(x,y)$ will be interpreted as, "$x$ is a cabbage or $y$ is a cabbage". It should be apparent that with this interpretation (i) and (iii) are true whereas values of $x$ and $y$ can be found so that (ii) is not satisfied, which should also mean that (i) and (iii) don't logically imply (ii) (when you have checked what that means).

I think with that example you'll probably find showing (ii) and (iii) don't logically imply (i) easy enough. (That just leaves the L-structures to be defined.)