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.
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: .
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?