Well formed formulae in Predicate Calculus

[kp100591]

Consider the following well-formed formulae in the Predicate Calculus:
W1 = (∃x)(∃y) R(x, y)
W2 = (∀x)(∀y) [R(x, y) ⇒ ∼ R(y, x)]
W3 = (∀x)(∀y) [R(x, y) ⇒ (∃z)(R(z, x) ∧ R(y, z))]
Prove that any model in which W1, W2 and W3 are all true must have at least 3 elements. Find one such model with 3 elements.

Proof:
Let U = Z+, and for some x, y ∈ Z+, interpret R(x, y) to mean x < y. Certainly, for some x ∈ Z+, y /<(is not less than) x, so that W1 holds in U.
Furthermore, < is transitive, that is, for all x,y,z ∈ Z+,
x<y<z ⇒ x<z, so that W3 holds in U.
not sure about W2

Please help me with the rest of the working,
and also, suggestions for how to find such a model.

thank you very much.

 

[Evgeny.Makarov]

Proof:
Let U = Z+, and for some x, y ∈ Z+, interpret R(x, y) to mean x < y. Certainly, for some x ∈ Z+, y /<(is not less than) x, so that W1 holds in U.
Furthermore, < is transitive, that is, for all x,y,z ∈ Z+,
x<y<z ⇒ x<z, so that W3 holds in U.

Two remarks. First, finding a single infinite model does not help solve this problem. You need to show that every model has at least three elements, and you need a three-element model. Second, W3 does not mean transitivity of R. Its converse (∃z)(R(z, x) ∧ R(y, z)) ⇒ R(x, y) is almost transitivity, but the conclusion has x, y in the wrong order.

I suggest finding a one-element model of W1. Is it a model of W2? Find a two-element model of W1, W2. Are there other two-element models? Is it a model of W3? Let's start here.

 

[kp100591]

can you suggest a one-element model for W1 please ?

 

[Evgeny.Makarov]

Well, there are not too many candidates there. There is a single element in the universe, and it's either related to itself by R or it's not. Exactly one of these candidates is a model of W1.

 

[Deveno]

Ask yourself, if the set on which the relation $R$ is defined has just one element, how can W1 be true?