Interpretation and satisfaction

[Agaton]

Can anyone help me with the following?

satisfaction and models:

The sentence α : ∀x(odd(x) ⊃ even(s(x))) is not logically implied by the set S of 4 sentences:
even(0) odd(s(0)) ∀x(even(x) ⊃ even(s(s(x)))) ∀x(even(s(x)) ⊃ odd(x))
Prove that this is so by identifying an interpretation which is a model for S but not a model for α.
What should be changed to S such that the sentence α becomes logically implied?

Thanks in advance.

 

[honestrosewater]

You have to let us know what you have done and where you get stuck.

To get started, can you define -2, -1, and 0 to be successors as normal (0 = s(-1), -1 = s(-2)) but make -2 and -1 both odd?

 

[Agaton]

Thanks honestrosewater,

I think we can suppose and domain with any interpretation, such that the interpretation is a model for S, bot not a model for α.

 

[honestrosewater]

The axioms for S generate an infinite alternating sequence of odd and even objects that starts with 0. So every even object is followed by an odd object. To not model a, you need to have an odd object that is not followed by an even one. Since the sequence following 0 alternates infinitely, you have to go before 0 and make 0 a (perhaps distant) successor of your two successive odd objects.

I can't think of another model that would work except defining 0 to be both odd and even. There's nothing that explicitly rules that out, but it's stretching the expectations more, at least to me.

 

[Agaton]

Thanks honestrosewater,

There is a solution which is close to yours i think as below:

We need an interpretation that is a model for S, but not a model for α.


Let Interpretation = {D,I}, // D = domain , I = Interpretation

with D = { N U X}

I [X] = set of all odd integers (disjoint from the odd integers in N).
I [N] = set of natural numbers.

This is a model for S, but not a model for α.


For the second part, if we change ∀x(even(s(x)) ⊃ odd(x)) to ∀x(odd(s(x)) ⊃ even(x)),

then any interpretation that satisfies S, also satisfies α.


Do you think this is correct?

 

[honestrosewater]

So you want the standard interpretation here, with "0" as 0 and "s" as successor? It doesn't hurt to say so.

Can you derive ∀x(odd(x) ⊃ even(s(x))) from your new set? Just state the proof. You only need to know two things.

The easiest way to make a theorem derivable from a set of axioms is to just add it as an axiom.

 

[Agaton]

Yes, that is standard interpretation.
I do not think that we need to derive ∀x(odd(x) ⊃ even(s(x))). What is required, according to the question, is just to make some change to S. Isn't it?

 

[honestrosewater]

What should be changed to S such that the sentence α becomes logically implied?

Your new S needs to imply ∀x(odd(x) ⊃ even(s(x))). You need to prove what you said, that any interpretation that satisfies S also satisfies a. You can do this by deriving ∀x(odd(x) ⊃ even(s(x))) from S.

This would be a simple matter if you also had ∀x[~odd(x) <-> even(x)] and ∀x[~even(x) <-> odd(x)]. Think contrapositives.

 

[Agaton]

Do not we prove it when we check it with our model?!

 

[Bacle]

No; but if your model is sound, then truth implies provability, so you show that
your sentence is provable, if you show that it is sound.

 

[honestrosewater]

Producing one model doesn't prove it for all models. There are structures that satisfy both the original S and α. The nonnegative integers are such a structure. But this doesn't mean that all structures satisfying one will satisfy the other, as you proved with your counterexample.

You need to prove that a counterexample for your new problem (a structure that satisfies the new S but not α) doesn't exist, which you can do by showing that S implies α.

 

[Bacle]

Never mind anyway; my bad. I was confusing completeness with soundness; mixed
up the directions between truth and provable.

 

[Agaton]

I didn't get your points, so to understand it, i repeat the answer again:

Part A:

To prove the sentence α is not logically implied by the set S, we needed an interpretation which is a model for S, but not a model for α.

The intendedinterpretation consists of a domain as:

D={N U X}, in which

I [N] = set of natural numbers.
I [X] = set of all odd integers (disjoint from the odd integers in N).


So D= {...-5,-3,-1,0,1,2,3...}

This is a model for S, since every sentence of S can be satisfied with respect to this model, but α is not satisfied.

Therefore, 'in this model', α in not logically implied.

Part B: What should be changed to S such that the sentence α becomes logically implied?

the question clearly asks some changes to S in order to imply α. So the suggestion is to replace ∀x(even(s(x)) ⊃ odd(x)) with ∀x(odd(s(x)) ⊃ even(x)).

How S logically implies α? Every model that satisfies S also satisfies α, that is there is no model in which S is satisfied and α in not satisfied.

This is the way I see the question.

This is in agreement with the definition of entailment, when we say the sentence P entails the sentence Q, if and only if, in every model in which P is true, Q is also true.

What do you think? Thanks

 

[honestrosewater]

Every model that satisfies S also satisfies α, that is there is no model in which S is satisfied and α in not satisfied.

Yes, correct, this is what you need to prove. Why must every model that satisfies S also satisfy α? You need a proof. You can give a syntactic argument that S syntactically implies α. You can also give a semantic argument that no counterexample can exist. The syntactic argument seems easier.