# Enderton 3.4 Problem 2

• Dec 21st 2011, 06:12 AM
logics
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.
• Dec 21st 2011, 11:25 AM
emakarov
Re: Enderton 3.4 Problem 2
Is $\alpha$ a propositional formula here?

Quote:

Originally Posted by logics
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...
• Dec 23rd 2011, 06:06 AM
logics
Re: Enderton 3.4 Problem 2
Quote:

Originally Posted by emakarov
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.
• Dec 23rd 2011, 11:42 AM
emakarov
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
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
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.