I am finding difficult to understand the meaning of definitions and would found useful to grasp things by examples, first.
Can you show the concept of interpretation and how to find a counter model of these examples, possibly explaining the passages or the symbols with human language?
1. $ ∃x∃z(p(x) → q(z)), ∃xp(x) → ∃xq(x) \implies ∃x(p(x) ∨ q(x))$
this can be reduced to:
$ ∃x∃z(p(x) → q(z)), ∃x∃y((p(x) → q(y)) \implies ∃x(p(x) ∨ q(x)) $
The way I'd try to prove it is using a resolution method.
I would pick up a universe of elements U = {0,1,2} since there are three variables x, y, z.
Translating the premisess in conjunctions for the resolution method, I would get:
$\lnot pa \lor qb $, $\lnot pa \lor qc$, and the negated conclusion $\lnot px \lor qx $
for x:= a, y:=b, Z:=c
- is the x in the premisess and conclusion assumed to be the same, so that I can substitute x:= a in all, or can it mean a different variable ?
- if the translation is correct, with the resolution method I cannot find a contradiction with the negated conclusion. So there must be a counter model. But how to find it using the universe above ? How should I proceed ?
$ ∀xRxx, ∀x∀y(Rxy ∨ Ryx), ∀x∀y∀z((Rxy∧Ryz)→Rxz) \implies ∀x∀y(Rxy →Ryx) $
Same question as above. A solution for this exercise only points out: Let U = {a,b} and the interpretation Ip = {(a,a),(b,b),(a,b)} and that's it.
But I don't see a countermodel in it..
Also, I would have thought that, given ∀xRxx I would have : (a,a) for x:=a and given Rxy, Ryx I would have (a,b) for y :=b, and given Ryz I would have (b, c) for z:=c
so to have an IP = {(a,a),(a,b),(b,c)} and that is different from the solution.
- Can you explain how to formulate a legit interpretation this second example ?
- How to find a counter-model ?
In general, I understand the difference of ∀x and ∃x, but I struggle to apply to interpretations with implications and compositions of formulas.
I would find useful an example or intuition in how to proceed with interpretations of implications using the ∃ quantifiers:
$ ∃xpx → ∃xqx $ that would reduce to $ ∃x∃y(px → qy) $
$ ∃xpx → ∀xqx $ that would reduce to $ ∀x¬px ∨ ∀xqx $ and I can compose as $ ∀x ( ¬px ∨ qx ) $
$ ∀xpx → ∃xqx $ that would reduce to $ ∃x¬px ∨ ∃xqx $:
- can I compose $ ∃x¬px ∨ ∃xqx $ as $ ∃x( ¬px ∨ qx) $ ?
- Why not $ ∃xpx → ∃xqx $ be composed as $ ∃x( px → qx ) $?
In naif words, I thought that that x does not necessarily represent the same "items" among the possible interpretation of it, but not clear.
Example using a truth table or proofs with resolution method are helpful to check if the above are equivalent, but I am looking for an explanation of the passages for proofs and countermodels in human language as well.
I think you are confusing something in the exercise enunciate. Maybe you can edit your question with the full exercise statement.
I think the exercise ask you to find a unique model that makes the first formula valid and the second one not valid:
$∃x∃z(p(x) → q(z)), ∃xp(x) → ∃xq(x) ⟹ ∃x(p(x) ∨ q(x))$.
If this is the case :
Take a model with domain with just one element $a$, and make $p(a)$ and $q(a)$ false. The $x$ in premise and conclusion of the second formula is not the same, but the model is small and we can test all the possibilities of interpretations (just one in this case, because we have just the element $a$ in the domain). Substituting $a$ for $x$ and $z$ in the first formula, and interpreting it will give us $I(p(a) \to q(a) ) = T$ ($I$ is the interpretation function).
And you can see the second formula will be false, because all elements of the domain (i.e. just $a$) we have
$$(F\to F) \to (F \vee F) = F$$.
In: $∀xRxx, ∀x∀y(Rxy ∨ Ryx), ∀x∀y∀z((Rxy∧Ryz)→Rxz) ⟹ ∀x∀y(Rxy →Ryx)$
Ip = {(a,a),(b,b),(a,b)} probably means all elements of the domain where the predicate $R$ is true. So
$$I(R(a,a)) = T$$ $$I(R(b,b)) = T$$ $$I(R(a,b)) = T$$ $$I(R(b,a)) = F$$
You can see that $∀xRxx$ will be valid in this model (because $I(Raa) = T$ and $I(Rbb) = T$.
You can see also that $∀x∀y(Rxy ∨ Ryx)$ is valid. (Substitute all the possibles $a$ and $b$)
And $∀x∀y∀z((Rxy∧Ryz)→Rxz) ⟹ ∀x∀y(Rxy →Ryx)$ is not valid for $x:=a$, $y:=b$ and $z:=a$.
As for your question: "How to find a counter-model ?" The answer is: construct a model where your formula will be not valid. A formula is valid in a model iff every interpretation of the formula, when we substitute every instance of quantifiers, is true in this model. So to show a counter-model means to find just one interpretation where the substitutions are false. (note that interpretation of $\forall x A$ and $\exists x A$ gives us different kinds of substitution, for the first one interpretation to be valid all the substitutions in the formula $A$ will have to be true, the second one just one.)
I didn't understand what you want to do in the 3o part of your question. The reductions are valid. As for the question:
can I compose $∃x¬px ∨ ∃xqx$ as $∃x( ¬px ∨ qx)$ ?
No. The $x$ could not be the same in the two quantifiers (in the first formula). You must do this instead if you want to put all the quantifiers in front of the formula:
$∃x∃y( ¬px ∨ qy) $
(note that this also possible because $x$ is not free on $q$ and $y$ is not free on $p$)
Actually, every formula has a form equivalent with just existential quantifiers in front of it. It is called the prenex form of the formula. Maybe this help you.