Re: Enderton 3.4 Problem 2

Is a propositional formula here?

Quote:

Originally Posted by

**logics** 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

.

Are "prime constituents" the atomic formulas occurring in ? Then this claim about seems to speak not only about the case where is atomic...

Re: Enderton 3.4 Problem 2

Quote:

Originally Posted by

**emakarov** Is

a propositional formula here?

Are "prime constituents" the atomic formulas occurring in

? Then this claim about

seems to speak not only about the case where

is atomic...

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.

Re: Enderton 3.4 Problem 2

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?

Quote:

Originally Posted by

**logics** Case 1:

is a prime formula.

Then, either

or

is the truth assignment satisfies

.

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.

Quote:

Originally Posted by

**logics** Case 2:

.

if

,

if

Case 3:

.

or

, and 0 otherwise.

Yes, using strong recursion.