Γ 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.
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.
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".