Results 1 to 7 of 7

Thread: 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 $\displaystyle \Gamma$ is a maximal consistent set of sentences ($\displaystyle \forall \phi \in \text{Sent}(\mathcal{L}), \Gamma \vdash \phi$ or $\displaystyle \Gamma \vdash \neg \phi$, but not both) is complete ($\displaystyle \forall \phi \in \text{Sent}(\mathcal{L}), \phi \in \Gamma$ or $\displaystyle \neg \phi \in \Gamma$). I've seen another definition for maximal consistency which says that there are no proper consistent extensions of $\displaystyle \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,577
    Thanks
    790
    Wait, I also have an issue with definitions.

    First, I am used to the definition that $\displaystyle \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, "$\displaystyle \Gamma$ is maximal consistent" means that every proper superset of $\displaystyle \Gamma$ is inconsistent, though $\displaystyle \Gamma$ itself is consistent.

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

    (1) or
    (2) $\displaystyle \forall\Gamma'\subseteq\text{Sent}(\mathcal{L})$, $\displaystyle \Gamma\subset\Gamma'$ implies that $\displaystyle \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 $\displaystyle \Gamma$ is consistent and prove (1) => (2) => (1) and (1) => (3). (Below $\displaystyle \bot$ denotes a contradictory formula and I assume that $\displaystyle \phi\to\bot$ is equivalent to $\displaystyle \neg\phi$.)

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

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

    (1) => (3): This is obvious: for every $\displaystyle \phi$, either $\displaystyle \phi\in\Gamma$ or $\displaystyle \neg\phi\in\Gamma$ by (3). Therefore, $\displaystyle \Gamma\vdash\phi$ or $\displaystyle \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,577
    Thanks
    790
    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 $\displaystyle \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 $\displaystyle \Delta$ that generates the whole theory $\displaystyle \Gamma$, i.e., $\displaystyle \Gamma=\{\phi\mid\Delta\vdash\phi\}$. Now, there are such $\displaystyle \Delta$ and $\displaystyle \Gamma$ that $\displaystyle \Gamma$ is complete (in my sense, i.e., $\displaystyle \Gamma\vdash\phi $ or $\displaystyle \Gamma\vdash\neg\phi$ for every $\displaystyle \phi$), and so $\displaystyle \Delta$ is complete. However, $\displaystyle \Delta$ does not have to be maximal.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    470
    Thanks
    6
    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 $\displaystyle \mathcal{L}$ be a first order language, $\displaystyle \Gamma \subseteq \text{Sent}(\mathcal{L})$ be consistent. Then the following statements are equivalent:

    1. $\displaystyle \Gamma$ is complete, as in your definition.
    2. $\displaystyle \exists \mathcal{A}$ an $\displaystyle \mathcal{L}$-structure such that $\displaystyle \Gamma \vDash \text{Th}(\mathcal{A})$.
    3. $\displaystyle \forall \mathcal{A}, \mathcal{B}$ models of $\displaystyle \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
    470
    Thanks
    6
    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: Aug 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: Dec 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: Dec 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 for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum