Prove that
There is a representable relation Tr such that for a formula and a which encodes a truth assignment for (or more), iff that truth assignment satisfies .
http://cs.nyu.edu/courses/fall03/G22...c/lec12_h4.pdf (slide 6-10)
======================================
There are several cases to be considered.
Case 1. is an atomic formula.
There is representable function such that for a formula , and , where each is a prime constituents of and each .
I am trying the first case, but I am stuck here.
Any help will be appreciated.
According to the definition of the book, the prime formulas are the atomic formulas and those of the form . I guess 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,
.
, and .
==============================
My attempt is
Suppose tr is a characteristic function such that and .
Case 1: is a prime formula.
Then, either or is the truth assignment satisfies . Therefore, is representable.
Case 2: .
if ,
if
Case 3: .
or , and 0 otherwise.
Then, apply the induction using Case 1, 2, and 3.
The characteristic functions of first-order formulas true in 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 and that are true iff x is (the code of) a true formula of the form (correspondingly, ) and A is quantifier-free. However, neither nor is representable (because relations representable in 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 " mean?
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 and for an atomic , returns the truth value of in is representable.
Yes, using strong recursion.