Reading about the property of satisfiability

[EvLer]

I'm not sure where this thread would go, but here it is...

I am reading about the property of satisfiability. And trying to get some things straight.
I saw different kinds of logics (porpositional, relational) being tested for satisfiability. I've read about models and formal systems. The book does define the formal system and says that each system has models that underlie it. But the notion of satisfiability (or consistency) is applied to a formal system.
So then propositional logic, predicate logic, etc. are SYSTEMS and then what is a model? like modus tollens and the like? I looked up wikipedia, but not sure it is the same thing. The thing is that it all is not discussed in one section, but i gathered all this information from different parts of the book.

Here's text from my book:

we now no longer ask whether certain axioms are true in any absolute sense, but what if anything, they might be true of. That question is equivalent to asking what models, if any, the set of axioms has.

That's where I am confused.

ps: if i expressed something unclearly or you need more details to know what I mean, please ask, i really don't know if I provided enough to understand my question.

Thanks!

 

[Hurkyl]

In your formal systems, you generally have several "abstracts". For example, in formal Euclidean geometry, we say that there are things called "points", and things called "lines", and some relations called "incidence", "betweenness", and "congruence", and we have 15 axioms involving these abstracts.

To give a model for a system is to take those abstracts and define them within some other formal system. (typically set theory)


For example, I will provide a model of Euclidean geometry within the theory of real closed fields. (If you don't know what a real closed field is, just pretend I say "the real numbers" instead of "a real closed field")

Let R be a real closed field.

I define the word "point" from Euclidean geometry to mean a pair of numbers in R.

I define the word "line" to mean a polynomial of the form f(x, y) = ax + by - c. Two lines are equal if one is a multiple of the other.¹

I define the word "incidence" as follows: a point P is incident with a line L if and only if L(P) = 0

I define the word "between" as follows: P * Q * R means that there exists a number λ > 0 such that (R - P) = λ (Q - P)

And so on. One can then show that Hilberts 15 axioms for Euclidean geometry are satisfied by these definitions². Thus, I have demonstrated a model of Euclidean geometry within the theory of Real Closed Fields.


Incidentally, this is probably axiomatic set theory's greatest strength: it is extremely good at modelling other theories. Category theory serves very well in this respect as well. This is why the two theories are considered "foundational" -- not only is their language useful in all aspects of mathematics, but everything we generally like to do can be reduced to them as well.



1: There's a subtlety here -- in the first-order theory of real closed fields, a polynomial is really a logical function as opposed to an object of the theory!
2: There's a subtlety here too -- dealing with the completeness axiom properly is a very tricky business.

 

[EvLer]

Thanks for the explanation. Makes a bit more sense now.

I have a related question though:

propositional logic has interpretation defined as a function assigning a truth-value to a sentence, can I assume that all logics have interpretation defined in the same way (i omit fuzzy logic for simplicity)? Does a logic necessarily has to have an interpretation ? If not, could you post/direct me to a counterexample? In the definition of a formal system that I have in the book it does not say that there have to be a truth-value mapping. But logics are formal systems, right?
Am I asking the right question, here :uhh:

Thanks again.

 

[Hurkyl]

I don't follow your question. It might be because you're confused, but it's more likely because I'm confused. What I know on this subject I've picked up from following my various interests, as opposed to trying to learn it in any sort of systematic way, so a lot of the little details I just don't know.


So, I'm not completely sure what you're asking, but I think I can answer in the affirmative:

A logical system is basically a rule for making deductions, right, and for every logic we have a notion of consistency, right?

If the empty set of propositions is consistent, then I assert that, by Zorn's lemma, there exists a maximal set of propositions that is consistent. (You could probably do it via induction instead)

For this to work, you need to prove that if A1 <= A2 <= A3 <= ... are a nested chain of consistent sets (<= is subset), then their union is also consistent.

If we assume the union is not consistent, then there must be a chain of deductions that let's us deduce a contradiction. However, this chain is finite, so there must be some An which contains each statement in that chain, and thus An would be inconsistent!


Then, we can define a truth function v by choosing some maximal consistent set S of propositions, and defining v(P) = T if and only if P is in S, and v(P) = F otherwise. At least I hope v is a truth function!


But as I mentioned, I'm fuzzy in the gritty details of things, so it's your duty to check over this proof and make sure I haven't gotten anything wrong, and fix it if I have.


There's a more naive thing I think you could do too: you could take your set of truth values to simply be equivalence classes of propositions. (Two propositions are in the same class if they are, well, logically equivalent! Each implies the other, I suppose) Then, you can write a truth function that simply maps each proposition to the equivalence class in which it resides.


If I've gotten this all wrong, maybe you could tell me the definitions of the things about which you're asking, and I can give a better answer!

 

[honestrosewater]

propositional logic has interpretation defined as a function assigning a truth-value to a sentence, can I assume that all logics have interpretation defined in the same way (i omit fuzzy logic for simplicity)?

I only know about Propositional and First Order (or predicate) Logic. Yes, they both have functions from sentences (or formulas) to truth-values. But these functions aren't always called interpretations (and interpretation may mean something else). For instance, my book calls them valuations and uses interpretation for something else.
I wouldn't assume anything about definitions. For instance, sentence could have different meanings in PL and FOL- and different meanings in different books. What one person calls a sentence, others call a proposition, formula, or well-formed formula. What one calls a formula, others call an expression or string. What one calls an expression, others call a string, or terms and formulas. What one calls an interpretation, others call a structure or valuation. So you should be sure that you can ignore the words they use and still determine what each person is talking about from the context before you start assuming.

Does a logic necessarily has to have an interpretation ? If not, could you post/direct me to a counterexample? In the definition of a formal system that I have in the book it does not say that there have to be a truth-value mapping. But logics are formal systems, right?

If the interpretation tells you which sentences have which truth-values under which conditions, logic wouldn't mean much without interpretations. The interpretation is part of the semantics. Without functions from sentences to truth-values, a logic (based on a formal language) would be a "meaningless" bunch of symbols being manipulated by seemingly arbitrary rules. Interpretations are also used to define and determine satisfiability.
What is your definition of a formal system? Your definitons of satisfaction and model would help too, if you have them.

 

[EvLer]

Thank you everyone for your replies: put together I got the answer to my question.
Yeah, terminology seems to be the main source of confusion, I have to check sources for their examples to be sure that they mean the same thing.

In my case, if you are interested, formal system is defined as follows:
1. a non-empty set of primitives;
2. a set of statements about the primitives, the axioms;
3. means of deriving further statements from axioms:
i. an explicit set of recursive rules of derivation
ii. appeal to a background logic of language
iii. no explicit derivation: just what follows from axioms;