Results 1 to 7 of 7

Math Help - Maximal consistent sets are complete

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    36

    Maximal consistent sets are complete

    I'm stuck on a problem on the theory of structures and essentially boiled it down to this: If \Gamma is a maximal consistent set of sentences ( \forall \phi \in \text{Sent}(\mathcal{L}), \Gamma \vdash \phi or \Gamma \vdash \neg \phi, but not both) is complete ( \forall \phi \in \text{Sent}(\mathcal{L}), \phi \in \Gamma or \neg \phi \in \Gamma). I've seen another definition for maximal consistency which says that there are no proper consistent extensions of \Gamma and that this is equivalent to being complete, but I fail to see an equivalence between these two definitions.


    Please help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    Wait, I also have an issue with definitions.

    First, I am used to the definition that \Gamma is complete if or : see PlanetMath and MathWorld. (I was surprised that Wikipedia defines completeness as maximal consistency.) That's why saying that Peano Arithmetic is incomplete immediately implies that there is an independent sentence, i.e., a sentence that is neither proved nor disproved.

    Second, the phrase "maximal consistent" is not idiomatic. For any strict order <, saying "x is maximal" means that there is no y such that x < y. (As an aside, note that this is different from saying that x is the greatest, which means that y <= x for all y.) Here the order is set inclusion, so a set is maximal (in a family of sets) if it does not have a proper superset. Correspondingly, " \Gamma is maximal consistent" means that every proper superset of \Gamma is inconsistent, though \Gamma itself is consistent.

    Now, of course, when \Gamma is consistent, these things:

    (1) or
    (2) \forall\Gamma'\subseteq\text{Sent}(\mathcal{L}), \Gamma\subset\Gamma' implies that \Gamma' is inconsistent

    are equivalent, and any of them implies

    (3) or

    So one may say that this is arguing about definitions, though I think that distinguishing properties that hold by definition and those that need to be proved is helpful here.

    Let's assume that \Gamma is consistent and prove (1) => (2) => (1) and (1) => (3). (Below \bot denotes a contradictory formula and I assume that \phi\to\bot is equivalent to \neg\phi.)

    (1) => (2): Suppose \Gamma\subset\Gamma'. Take \phi\in\Gamma`\setminus\Gamma. Since \phi\notin\Gamma, \neg\phi\in\Gamma by (1). Therefore, both \phi and \neg\phi are in \Gamma', and so \Gamma' is inconsistent.

    (2) => (1): Assume the contrary, i.e., \phi\notin\Gamma and \neg\phi\notin\Gamma for some formula \phi. Then both \Gamma\cup\{\phi\} and \Gamma\cup\{\neg\phi\} are inconsistent by (2), i.e., \Gamma\cup\{\phi\}\vdash\bot and \Gamma\cup\{\neg\phi\}\vdash\bot. By Deduction Theorem (or by Implication Introduction rule), \Gamma\vdash\phi\to\bot and \Gamma\vdash\neg\phi\to\bot, i.e., \Gamma\vdash\neg\phi and \Gamma\vdash\neg\neg\phi. This means that \Gamma is inconsistent, a contradiction.

    (1) => (3): This is obvious: for every \phi, either \phi\in\Gamma or \neg\phi\in\Gamma by (3). Therefore, \Gamma\vdash\phi or \Gamma\vdash\neg\phi.

    I am not sure what advice to give about how best to appropriate these proofs. Usually, I don't remember every detail, but I have an intuition about a maximal consistent set as something that knows everything, so one cannot add new knowledge to it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    If is a maximal consistent set of sentences ( or , but not both) is complete ( or ).
    By the way, the formula or in the assumption above does not mean that \Gamma is maximal and so it does not imply or . There are axiomatizable complete theories (e.g., dense linear orders). This means that there is a small set of axioms \Delta that generates the whole theory \Gamma, i.e., \Gamma=\{\phi\mid\Delta\vdash\phi\}. Now, there are such \Delta and \Gamma that \Gamma is complete (in my sense, i.e., \Gamma\vdash\phi or \Gamma\vdash\neg\phi for every \phi), and so \Delta is complete. However, \Delta does not have to be maximal.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Giraffro, to answer your question briefly: It is NOT the case that maximally consistent is equivalent to complete (since an inconsistent set of formulas is complete). But there are other equivalences. Which equivalence in particular are you having a hard time proving?

    Definitions:

    A set of formulas G is consistent iff there is not a formula P such that G |- P and G |- ~P.

    A set of formulas G is complete iff for every sentence S we have either G |- S or G |- ~S.

    A set of formulas G is maximally consistent iff (G is consistent & for all sentences S not in G we have Gu{S} is inconsistent).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2010
    Posts
    36
    Quote Originally Posted by MoeBlee View Post
    Giraffro, to answer your question briefly: It is NOT the case that maximally consistent is equivalent to complete (since an inconsistent set of formulas is complete). But there are other equivalences. Which equivalence in particular are you having a hard time proving?

    Definitions:

    A set of formulas G is consistent iff there is not a formula P such that G |- P and G |- ~P.

    A set of formulas G is complete iff for every sentence S we have either G |- S or G |- ~S.

    A set of formulas G is maximally consistent iff (G is consistent & for all sentences S not in G we have Gu{S} is inconsistent).
    I've managed to show the equivalence eventually, but here was what I was stuck on. Let \mathcal{L} be a first order language, \Gamma \subseteq \text{Sent}(\mathcal{L}) be consistent. Then the following statements are equivalent:

    1. \Gamma is complete, as in your definition.
    2. \exists \mathcal{A} an \mathcal{L}-structure such that \Gamma \vDash \text{Th}(\mathcal{A}).
    3. \forall \mathcal{A}, \mathcal{B} models of \Gamma, \text{Th}(\mathcal{A}) = \text{Th}(\mathcal{B}).


    In my lecture course, a set of sentences is defined to be 'maximal consistent' if it is consistent and complete in your definitions, which is where the confusion started. Thanks for clearing that up. I'll bear that in mind in the future.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    So you showed the equaivalences of 1-3 okay? Let me know if you need any help with them (they seemed right to me as I looked at them rather qucikly).

    And yes, it is easy to see that my definition of 'maximally consistent' is equivalent with 'consistent and complete'.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Mar 2010
    Posts
    36
    Yeh it's fine now. Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Complete sets demonstrations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 21st 2011, 08:52 PM
  2. Consistent Estimator
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: May 7th 2011, 10:01 PM
  3. consistent property
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: December 27th 2010, 03:10 PM
  4. which of the following are complete sets, and why?
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: December 9th 2009, 05:46 AM
  5. Consistent Estimator
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: May 5th 2008, 01:34 PM

Search Tags


/mathhelpforum @mathhelpforum