MHB Well formed formulae in Predicate Calculus

  • Thread starter Thread starter kp100591
  • Start date Start date
  • Tags Tags
    Calculus Formulae
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?
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.

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