Results 1 to 4 of 4

Thread: 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 $\displaystyle \alpha$ and a $\displaystyle v$ which encodes a truth assignment for $\displaystyle \alpha$ (or more), $\displaystyle <\sharp \alpha, v > \in \text{Tr}$ iff that truth assignment satisfies $\displaystyle \alpha$.

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

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

    Case 1. $\displaystyle \alpha$ is an atomic formula.
    There is representable function $\displaystyle tr$ such that for a formula $\displaystyle \alpha$, $\displaystyle tr(\sharp\alpha) = <\sharp B_0, \ldots, \sharp B_n>$ and $\displaystyle v=<<\sharp B_0, e_0>,\ldots, <\sharp B_n, e_n>>$, where each $\displaystyle B_i$ is a prime constituents of $\displaystyle \alpha$ and each $\displaystyle 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,577
    Thanks
    790

    Re: Enderton 3.4 Problem 2

    Is $\displaystyle \alpha$ a propositional formula here?

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

    Case 1. $\displaystyle \alpha$ is an atomic formula.
    There is representable function $\displaystyle tr$ such that for a formula $\displaystyle \alpha$, $\displaystyle tr(\sharp\alpha) = <\sharp B_0, \ldots, \sharp B_n>$ and $\displaystyle v=<<\sharp B_0, e_0>,\ldots, <\sharp B_n, e_n>>$, where each $\displaystyle B_i$ is a prime constituents of $\displaystyle \alpha$ and each $\displaystyle e_i=0 \text{ or } 1$.
    Are "prime constituents" the atomic formulas occurring in $\displaystyle \alpha$? Then this claim about $\displaystyle tr$ seems to speak not only about the case where $\displaystyle \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 $\displaystyle \alpha$ a propositional formula here?

    Are "prime constituents" the atomic formulas occurring in $\displaystyle \alpha$? Then this claim about $\displaystyle tr$ seems to speak not only about the case where $\displaystyle \alpha$ is atomic...
    According to the definition of the book, the prime formulas are the atomic formulas and those of the form $\displaystyle \forall x \alpha$. I guess $\displaystyle \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,
    $\displaystyle (A(x) \rightarrow \neg \forall y \neg B(y)) \rightarrow \neg \forall x (C(x) \rightarrow A(x))$.

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

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

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

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

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


    Case 3: $\displaystyle \alpha = (\beta \rightarrow \gamma)$.
    $\displaystyle \text{tr}}(\sharp\alpha, v) = 1 \text{if} \text{ tr }(\sharp\beta, v)=0$ or $\displaystyle {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,577
    Thanks
    790

    Re: Enderton 3.4 Problem 2

    The characteristic functions of first-order formulas true in $\displaystyle \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 $\displaystyle \mathrm{True}_\forall(x)$ and $\displaystyle \mathrm{True}_\exists(x)$ that are true iff x is (the code of) a true formula of the form $\displaystyle \forall z\,A(z)$ (correspondingly, $\displaystyle \exists z\,A(z)$) and A is quantifier-free. However, neither $\displaystyle \mathrm{True}_\forall(x)$ nor $\displaystyle \mathrm{True}_\exists(x)$ is representable (because relations representable in $\displaystyle 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 $\displaystyle \alpha$" mean?

    Quote Originally Posted by logics View Post
    Case 1:$\displaystyle \alpha$ is a prime formula.
    Then, either $\displaystyle v=<\sharp \alpha, 0> $ or$\displaystyle v=<\sharp \alpha, 1>$ is the truth assignment satisfies $\displaystyle \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 $\displaystyle \sharp v$ and $\displaystyle \sharp\alpha$ for an atomic $\displaystyle \alpha$, returns the truth value of $\displaystyle \alpha$ in $\displaystyle v$ is representable.

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

    Case 3: $\displaystyle \alpha = (\beta \rightarrow \gamma)$.
    $\displaystyle \text{tr}}(\sharp\alpha, v) = 1 \text{if} \text{ tr }(\sharp\beta, v)=0$ or $\displaystyle {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: Jan 5th 2012, 11:49 AM
  2. Enderton 3.3 Problem 5
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Dec 19th 2011, 07:34 AM
  3. Enderton 3.3 Problem 8
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 19th 2011, 05:46 AM
  4. Enderton 3.1 problem 1 (p.193)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Dec 4th 2011, 10:30 AM
  5. Enderton 3.1 Problem 6 (p. 193)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Dec 3rd 2011, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum