Results 1 to 4 of 4

Math Help - Model theory - definiable sets

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    70

    Model theory - definiable sets

    Hi,
    I'm newbie in logic and model theory. I've the following task:

    By exhibiting suitable formulas, show that the set of even numbers is a \sum_0^0 set in \mathbb{N}.
    Show the same for the set of prime numbers.

    How can I solve this? Any advices?
    I'll be grateful for help
    Last edited by Opalg; November 16th 2010 at 12:26 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    What relations and functions are available in the language?

    I understand that \Sigma_0^0 means a set definable by a formula with bounded quantifiers only. A number n is even iff there exists an m <= n such that 2m = n. A number n is prime iff n\ne 1 and for all m < n, if m divides n, then m = 1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    70
    The structure of natural numbers is following:

    \mathbb{N}=(\omega, 0, 1, +, \cdot, <)

    One more definition:

    "The quantifiers \forall (x<y) and \exists (x<y) are said to be bounded"

    Your definitions of even and prime numbers are clear but how can I use this facts to show that mentioned sets are \sum_0^0 in \mathbb{N}? What formulas should I use?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    Replace "there exists an x such that" with " \exists x", "and" with " \land", and "if P, then Q" with " P\to Q". Also, you can express 2 as 1 + 1, and "m divides n", since it is not in the language, has to be written using an existential quantifier: there exists k such that m * k = n.

    To be honest, I don't see where your difficulty is. I wrote English sentences as close as possible to symbolic formulas, so a mechanical search/replace can turn one into the other.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Why providing a model means a theory is consistent?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 29th 2011, 06:58 AM
  2. Model Theory - minimal sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 20th 2010, 01:10 PM
  3. Model Theory - definiable classes
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 19th 2010, 09:21 AM
  4. Model theory - definiable sets 2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2010, 12:08 PM
  5. Set theory, transitive sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 23rd 2009, 06:29 AM

Search Tags


/mathhelpforum @mathhelpforum