Well formed formulae in Predicate Calculus

  • #1
kp100591
5
0
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.
 
Physics news on Phys.org
  • #2
kp100591 said:
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.
 
  • #3
can you suggest a one-element model for W1 please ?
 
  • #4
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.
 
  • #5
Ask yourself, if the set on which the relation $R$ is defined has just one element, how can W1 be true?
 

Similar threads

Replies
1
Views
2K
Replies
1
Views
2K
Replies
5
Views
2K
Replies
3
Views
2K
Replies
12
Views
2K
Replies
1
Views
1K
Replies
6
Views
3K
Replies
11
Views
4K
Replies
1
Views
2K
Back
Top