Results 1 to 4 of 4

Math Help - Enderton 3.4 Problem 2

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Enderton 3.4 Problem 2

    Prove that

    There is a representable relation Tr such that for a formula \alpha and a v which encodes a truth assignment for \alpha (or more), <\sharp \alpha, v > \in \text{Tr} iff that truth assignment satisfies \alpha.

    http://cs.nyu.edu/courses/fall03/G22...c/lec12_h4.pdf (slide 6-10)

    ======================================
    There are several cases to be considered.

    Case 1. \alpha is an atomic formula.
    There is representable function tr such that for a formula \alpha, tr(\sharp\alpha) = <\sharp B_0, \ldots, \sharp B_n> and v=<<\sharp B_0, e_0>,\ldots, <\sharp B_n, e_n>>, where each B_i is a prime constituents of \alpha and each e_i=0 \text{ or } 1.

    I am trying the first case, but I am stuck here.

    Any help will be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Enderton 3.4 Problem 2

    Is \alpha a propositional formula here?

    Quote Originally Posted by logics View Post
    There are several cases to be considered.

    Case 1. \alpha is an atomic formula.
    There is representable function tr such that for a formula \alpha, tr(\sharp\alpha) = <\sharp B_0, \ldots, \sharp B_n> and v=<<\sharp B_0, e_0>,\ldots, <\sharp B_n, e_n>>, where each B_i is a prime constituents of \alpha and each e_i=0 \text{ or } 1.
    Are "prime constituents" the atomic formulas occurring in \alpha? Then this claim about tr seems to speak not only about the case where \alpha is atomic...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Enderton 3.4 Problem 2

    Quote Originally Posted by emakarov View Post
    Is \alpha a propositional formula here?

    Are "prime constituents" the atomic formulas occurring in \alpha? Then this claim about tr seems to speak not only about the case where \alpha is atomic...
    According to the definition of the book, the prime formulas are the atomic formulas and those of the form \forall x \alpha. I guess \alpha should be a formula instead of an atomic formula to apply the above argument (Enderton page 230).

    I was not able to find the definition of the prime constituents in my textbook. I found an example in the web,

    The prime constituents for the below formula are,
    (A(x) \rightarrow \neg \forall y \neg B(y)) \rightarrow \neg \forall x (C(x) \rightarrow A(x)).

    A(x), \forall y \neg B(y), and  \forall x (C(x) \rightarrow A(x)).

    ==============================
    My attempt is

    Suppose tr is a characteristic function such that \text{tr}(\sharp \alpha, v) = 1 \leftrightarrow <\sharp\alpha, v>\in \text{Tr} and \text{tr}(\sharp \alpha, v) = 0 \leftrightarrow <\sharp\alpha, v>\notin \text{Tr}.

    Case 1: \alpha is a prime formula.
    Then, either v=<\sharp \alpha, 0> or v=<\sharp \alpha, 1> is the truth assignment satisfies \alpha. Therefore, \text{Tr} is representable.

    Case 2: \alpha = (\neg \beta).
    \text{tr}(\sharp\alpha, v) = 1 if \text{ tr }(\sharp\beta, v) = 0,
    \text{tr}(\sharp\alpha, v) = 0 if \text{ tr }(\sharp\beta, v) = 1


    Case 3: \alpha = (\beta \rightarrow \gamma).
    \text{tr}}(\sharp\alpha, v) = 1 \text{if} \text{ tr }(\sharp\beta, v)=0 or  {tr}(\sharp\gamma, v)=1, and 0 otherwise.

    Then, apply the induction using Case 1, 2, and 3.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Enderton 3.4 Problem 2

    The characteristic functions of first-order formulas true in \mathcal{N} is not only not representable, but not even definable (Tarski's theorem). If you want to capture the concept "a formula with the code x is true in the standard model" in one formula True(x), then x has to range over formulas of limited complexity. For example, there are formulas \mathrm{True}_\forall(x) and \mathrm{True}_\exists(x) that are true iff x is (the code of) a true formula of the form \forall z\,A(z) (correspondingly, \exists z\,A(z)) and A is quantifier-free. However, neither \mathrm{True}_\forall(x) nor \mathrm{True}_\exists(x) is representable (because relations representable in A_E are decidable and the sets of true universal and existential formulas are not decidable).

    Besides, if the OP is about first-order logic, then what does "a truth assignment for \alpha" mean?

    Quote Originally Posted by logics View Post
    Case 1: \alpha is a prime formula.
    Then, either v=<\sharp \alpha, 0> or v=<\sharp \alpha, 1> is the truth assignment satisfies \alpha.
    I am not sure I understand this sentence. The truth assignment can be longer and contain other variables. The points is that the function that, given \sharp v and \sharp\alpha for an atomic \alpha, returns the truth value of \alpha in v is representable.

    Quote Originally Posted by logics View Post
    Case 2: \alpha = (\neg \beta).
    \text{tr}(\sharp\alpha, v) = 1 if \text{ tr }(\sharp\beta, v) = 0,
    \text{tr}(\sharp\alpha, v) = 0 if \text{ tr }(\sharp\beta, v) = 1

    Case 3: \alpha = (\beta \rightarrow \gamma).
    \text{tr}}(\sharp\alpha, v) = 1 \text{if} \text{ tr }(\sharp\beta, v)=0 or  {tr}(\sharp\gamma, v)=1, and 0 otherwise.
    Yes, using strong recursion.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Enderton Problem 3.5
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 5th 2012, 11:49 AM
  2. Enderton 3.3 Problem 5
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 19th 2011, 07:34 AM
  3. Enderton 3.3 Problem 8
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 05:46 AM
  4. Enderton 3.1 problem 1 (p.193)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 4th 2011, 10:30 AM
  5. Enderton 3.1 Problem 6 (p. 193)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 3rd 2011, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum