Thread: Help with logic formulas

Consider a first-order language with ternary predicate P and equality predicate =. We define the formulas F1, F2, F3 as follows.
F1: ∀x∀y∃zP(x,y,z).
F2: ∀x∀y∀z∀u∀v∀w∀t (P(x,y,u) ∧ P(u,z,w) ∧ P(y,z,v) ∧ P(x,v,t) → =(w,t))
F3: ∀x∀y∀z∀w (∃u(P(x,y,u) ∧ P(u,z,w)) ↔ ∃v(P(y,z,v) ∧ P(x,v,w)))

a) Prove F1 ∧ F2 logically implies F3
b) Prove F2 does not logically imply F3

For B I got
Let the domain be {0,1}
Let P(x,y,z): x+y>z
Set x=0 y=1 u=0 z=1 w=0 v=0 t=0
Then F2 does not logically imply F3

Is this ok?

And how do I start with a) ?

Let the domain be {0,1}
Let P(x,y,z): x+y>z
Set x=0 y=1 u=0 z=1 w=0 v=0 t=0
Then F2 does not logically imply F3

Strictly speaking, it is not clear how your described interpretation relates to the fact that F2 does not logically imply F3. The latter fact says that there exists an interpretation where F2 is true and F3 is false. Did you describe that alleged interpretation? Then say directly that it is in the interpretation just describes that F2 is true and F3 is false.

First, you may need to clarify what is 1 + 1 since the domain is {0,1}. Since + is not in the formula vocabulary, it does not have to be interpreted by a function from {0,1} to {0,1}; so I assumed that you mean regular addition. I agree that F2 is true because its premise, namely P(x,v,t) is false. However, both sides of F3 are true: take u = 0 and v = 1.

Assuming F1, it is easy to show -> implication in F3. Indeed, assume P(x,y,u) and P(u,z,w) for some u. By F1, there exist v and y such that P(y,z,v) and P(x,v,t). Then by F2, w = t, so P(x,v,w) and thus ∃v(P(y,z,v) ∧ P(x,v,w)). At the moment I am not sure about the converse implication. Are you sure it is an equivalence?

I am deeply lost here
"Assuming F1, it is easy to show -> implication in F3. Indeed, assume P(x,y,u) and P(u,z,w) for some u. By F1, there exist v and y such that P(y,z,v) and P(x,v,t). Then by F2, w = t, so P(x,v,w) and thus ∃v(P(y,z,v) ∧ P(x,v,w)). At the moment I am not sure about the converse implication. Are you sure it is an equivalence?"
Can you explain it more?

Also by "Are you sure it is an equivalence?" do you mean that there shouldn't be a <--> in F3, actually there is, which is making it harder to show F2 !=> F3...

To prove ∀x∀y∀z∀w (∃u(P(x,y,u) ∧ P(u,z,w)) -> ∃v(P(y,z,v) ∧ P(x,v,w))) from F1 and F2:

Fix x, y, z, w and assume ∃u(P(x,y,u) ∧ P(u,z,w)). Take u that makes P(x,y,u) ∧ P(u,z,w) true. By F1, there exists a v such that P(y,z,v) and there exists a t such that and P(x,v,t). (My post above incorrectly said y instead of t.) Thus, we have P(x,y,u) ∧ P(u,z,w) ∧ P(y,z,v) ∧ P(x,v,t). By F2, w = t, so from P(x,v,t) we get P(x,v,w). So, ∃v(P(y,z,v) ∧ P(x,v,w)).

Why are you using -> instead of <--> in F3?

But since ∃u(P(x,y,u) ∧ P(u,z,w)) is true and ∃v(P(y,z,v) ∧ P(x,v,w))

F3 will be true, so then F1 and F2 => F3

Originally Posted by Sneaky

Why are you using -> instead of <--> in F3?

Originally Posted by emakarov

At the moment I am not sure about the converse implication.

Originally Posted by Sneaky

But since ∃u(P(x,y,u) ∧ P(u,z,w)) is true and ∃v(P(y,z,v) ∧ P(x,v,w))

F3 will be true

∃u(P(x,y,u) ∧ P(u,z,w)) is not true (true in which interpretation? none was specified); it is by assuming that it is true in some interpretation we can show that ∃v(P(y,z,v) ∧ P(x,v,w)) is also true there.

I cant figure out how to show F2 !=> F3, I tried
P(x,y,z): x<z<y or y<z<x
with domain {0,1,2,3,4,5}
with x=0 u=1 z=3 y=5 w=2 v=4 t=2
but it's not working...