Results 1 to 8 of 8

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

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    7

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    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.
    Last edited by MoeBlee; November 23rd 2011 at 07:52 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

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

    Quote Originally Posted by MoeBlee View Post
    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.

    Quote Originally Posted by MoeBlee View Post
    "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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

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

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

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

    Quote Originally Posted by emakarov View Post
    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 "|-".

    Quote Originally Posted by emakarov View Post
    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.
    Last edited by MoeBlee; November 22nd 2011 at 02:32 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    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".
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Proof that if A is a subset of P(A), P(A) is a subset of P(P(A))
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: May 23rd 2011, 04:26 PM
  2. Proof on Openness of a Subset and a Function of This Subset
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 24th 2010, 09:04 PM
  3. SETS - (k+1)-element subset S
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 11th 2010, 06:41 AM
  4. Replies: 2
    Last Post: October 12th 2009, 09:49 AM
  5. proof about a subset
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 12th 2009, 09:21 AM

Search Tags


/mathhelpforum @mathhelpforum