Γ and Σ are formula sets. Σ is satisfieable., and for every formula θ applies θ Γ or θ Γ. Proof Γ Σ => Γ = Σ
I dont know how to proof....
Every help would be appreciated
The problem is: Suppose S is a satisfiable set of formulas, and G is a subset of S, and for every formula t, either t in G or ~t in G. Show S is a subset of G.
Proof: Since S is satisfiable, we have that S is consistent. Suppose t in S. Since S is consistent and G is a subset of S, we have that ~t not in G. So t in G.
EDIT after I realized (spurred by emakarov) that I didn't mean 'consistent' in the above:
Proof: Since S is satisfiable, we have that there is no formula t such that both t and ~t are in S. Suppose t in S. Since there is no formula t such that both t and ~t are in S, and G is a subset of S, we have that ~t not in G. So t in G.
The original proof is still correct, but the edited version is more economical since it does not require the soundness theorem.
Just to add that one does not need to go from satisfiability to consistency here. The argument works if "consistent" is replaced by "satisfiable."
Edit: This is still true, but, of course, satisfiable => consistent is soundness, not completeness, which is not nearly as complicated.
"satisfiable then consistent" is even more basic than soundness. "satisfiable then consistent" is not much more than the observation that the assignment of "true per structure and assignment for the variables" is a function (i.e., does not assign a formula both true and false).
I don't know how you bypass it in this proof.
So, , is satisfiable and contains either each formula or its negation. Let . Then because otherwise and cannot be satisfiable. Therefore, .
I think the definition of structure ensures that every formula is either true or false in this structure. This has nothing to do with any sets of formulas that can be satisfiable or consistent. Did you have something else in mind?
Actually, the fact that satisfiability implies consistency (or its contraposition) is equivalent to soundness. Indeed, suppose that ; then is inconsistent. By assumption, it's unsatisfiable, so in every structure where is true, is false, i.e., .
The original problem is framed in purely model-theoretic terms, so it's natural to look for a solution that does not involve proof theory.
But the the "cannot be satisfiable" assertion rests on the fact that a satisfiable set cannot have in it a formula and the negation of that formula, which is is just another way of saying that a satisifiable set is consistent.
Not just that a formula is either true or false in a structure (actually, technically, in this case, satisfied by the structure and assignment for the variables) but that a formula is NOT BOTH true and false in a structure/variable-assignment.
The soundness THEOREM is more than the theorem "satisfiable then consistent". The soundness theorem is "If G |- P then G |= P". That takes more proof than merely "If G is satisfiable then G is consistent", especially since the details of the soundness theorem depend on the particulars of whatever proof system is referred to by "|-".
Indeed, and you see that I did not involve any proof theory, and in particular, I did not involve the soundness theorem that relates structures and satisfiablity with proof. I merely noted that if a set of formulas is satisfiable then that set of formulas is consistent. There's no mention of proof theoretic notions there.
Perhaps we need to recall the definition of a consistent set. A set is called consistent if it is not the case that and for some formula . This concept requires a proof calculus (axioms, inference rules, etc.). Wikipedia admits that there is also a semantic version of consistency, which is just a synonym for satisfiability. As I showed above the fact that satisfiability implies syntactic consistency is equivalent to the soundness theorem. The original problem does not need an excursion to proof calculus.
In the proof of the original problem, if both and are in , then is unsatisfiable because no model can satisfy both and . That's it; there is no need to invoke other concepts.
This follows directly from the definition of . This does not require any special property.Not just that a formula is either true or false in a structure (actually, technically, in this case, satisfied by the structure and assignment for the variables) but that a formula is NOT BOTH true and false in a structure/variable-assignment.
My mistake. I don't know why I was saying "S is consistent"' when what I actually meant is that there is no t such that both t and ~t are in S.
We agree now.
My original proof was not incorrect, but it did not need to restort to the soundness theorem equivalent "S is satisfiable so S is consistent". All it needed was "S is satisfiable so there is no formula t such that both t and ~t are in S."
So throughout this thread, my remarks would be rehabilitated by replacing "S is consistent" with "there is no formula t such that both t and ~t are in S".