MHB Well formed formulae in Predicate Calculus

  • Thread starter Thread starter kp100591
  • Start date Start date
  • Tags Tags
    Calculus Formulae
AI Thread Summary
The discussion centers on proving that any model satisfying the well-formed formulae W1, W2, and W3 in Predicate Calculus must contain at least three elements. The initial proof uses the positive integers with the relation R(x, y) defined as x < y, demonstrating that W1 and W3 hold true. However, the validity of W2 is questioned, suggesting that a model with fewer than three elements cannot satisfy all three formulae simultaneously. The conversation emphasizes the need for a specific three-element model and explores the implications of one- and two-element models in relation to W1, W2, and W3. Ultimately, a thorough examination of models with increasing elements is necessary to establish the required proof.
kp100591
Messages
5
Reaction score
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
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.
 
can you suggest a one-element model for W1 please ?
 
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.
 
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