First order logic: Soundness, Completeness, Decidability

[VazScep]

I'm trying to get a concrete example.
By set defined by a wff, i mean, the wff has one free variable, so any substitution of the free variable by an element of the universe that makes the wff true belongs to the set being defined.

Okay. In that case, the negation will define the complement of the first set, which will have two elements. I'm not sure what this is a concrete example of though.

 

[asdf60]

Okay.
I guess the question is, is it possible that one of the sentences is (that is, the wff substituted with an element) is undecidable, meaning it is neither true or false.
If I understand correctly, it's not possible, because that's not what undecidability says.
So to clarify, given a full model/intepretation, it is always possible to verify whether a given sentence is true in the model. And if it isn't true, then it's negation is.
Is this correct?

 

[VazScep]

Okay.
I guess the question is, is it possible that one of the sentences is (that is, the wff substituted with an element) is undecidable, meaning it is neither true or false.

This is not what undecidable means. As I said earlier in the thread, truth and provability should not be confused. If a sentence is undecidable it means it is unprovable, but it will still be either true or false for a given interpretation. For instance, the undecidable Gödel sentences in theories of arithmetic are always true for the interpretation of natural numbers.

If I understand correctly, it's not possible, because that's not what undecidability says.
So to clarify, given a full model/intepretation, it is always possible to verify whether a given sentence is true in the model. And if it isn't true, then it's negation is.

Is this correct?

It might not always be possible to verify whether a given sentence is true in the model, but the definition of truth for an interpretation states that if any formula is not true then its negation is.

 

[VazScep]

Sorry, but I'm going to have another go at this, since I would like to be able to explain this stuff without making people more confused.

A first-order theory (according to one definition, at least) is a set of wffs closed under logical consequence.

Truth and falsehood are not defined in terms of theories, but in terms of interpretations. We do not say that a wff is true for a theory, only that it belongs to (or is provable) in that theory. We can say that a wff is true for some interpretation though.

If some wff \phi is undecidable in a theory, then there will be an model of that theory (an interpretation which makes all the wffs in the theory true) for which \phi is true and a model for which \phi is false. This follows from the theorem that all consistent theories have models.

In your example, if you have an interpretation consisting of a domain with five elements, and a wff \phi(x) defining a subset of this domain with three elements, then the negation of that wff will define the set's complement. There is no mention of theories here, so it doesn't make sense to talk about the wff being decidable. This is why I didn't see the point of your example.