# Math Help - formula sets. proof: if Γ subset Σ => Γ = Σ

1. ## formula sets. proof: if Γ subset Σ => Γ = Σ

Γ and Σ are formula sets. Σ is satisfieable., and for every formula θ applies θ $\in$ Γ or $\neg$θ $\in$ Γ. Proof Γ $\subseteq$ Σ => Γ = Σ

I dont know how to proof....

Every help would be appreciated

2. ## Re: formula sets. proof: if Γ subset Σ => Γ = Σ

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.

3. ## Re: formula sets. proof: if Γ subset Σ => Γ = Σ

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.

4. ## Re: formula sets. proof: if Γ subset Σ => Γ = Σ

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

5. ## Re: formula sets. proof: if Γ subset Σ => Γ = Σ

Originally Posted by MoeBlee
I don't know how you bypass it in this proof.
So, $\Gamma\subseteq\Sigma$, $\Sigma$ is satisfiable and $\Gamma$ contains either each formula or its negation. Let $A\in\Sigma$. Then $\neg A\notin\Gamma$ because otherwise $\neg A\in\Sigma$ and $\Sigma$ cannot be satisfiable. Therefore, $A\in\Gamma$.

Originally Posted by MoeBlee
"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 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 $\Gamma\vdash A$; then $\Gamma\cup\{\neg A\}$ is inconsistent. By assumption, it's unsatisfiable, so in every structure where $\Gamma$ is true, $\neg A$ is false, i.e., $\Gamma\models A$.

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.

6. ## Re: formula sets. proof: if Γ subset Σ => Γ = Σ

Originally Posted by emakarov
So, $\Gamma\subseteq\Sigma$, $\Sigma$ is satisfiable and $\Gamma$ contains either each formula or its negation. Let $A\in\Sigma$. Then $\neg A\notin\Gamma$ because otherwise $\neg A\in\Sigma$ and $\Sigma$ cannot be satisfiable. Therefore, $A\in\Gamma$.
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.

Originally Posted by emakarov
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?
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.

Originally Posted by emakarov
Actually, the fact that satisfiability implies consistency (or its contraposition) is equivalent to soundness.
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 "|-".

Originally Posted by emakarov
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.
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.

7. ## Re: formula sets. proof: if Γ subset Σ => Γ = Σ

Perhaps we need to recall the definition of a consistent set. A set $\Gamma$ is called consistent if it is not the case that $\Gamma\vdash A$ and $\Gamma\vdash\neg A$ for some formula $A$. 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 $A$ and $\neg A$ are in $\Sigma$, then $\Sigma$ is unsatisfiable because no model can satisfy both $A$ and $\neg A$. That's it; there is no need to invoke other concepts.

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.
This follows directly from the definition of $\models$. This does not require any special property.

8. ## Re: formula sets. proof: if Γ subset Σ => Γ = Σ

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