# Thread: Enderton 3.4 Problem 2

1. ## 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.

2. ## Re: Enderton 3.4 Problem 2

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

Originally Posted by logics
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...

3. ## Re: Enderton 3.4 Problem 2

Originally Posted by emakarov
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.

4. ## 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?

Originally Posted by logics
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.

Originally Posted by logics
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.