# Hardest logic problem!

1. Nov 13, 2012

### NasuSama

1. The problem statement, all variables and given/known data

A universal (or ∀_1) formula is one of the form ∀x_1∀x_2...∀x_nθ, where θ is quantifi er-free.
An existential (or ∃_1) formula is one of the form ∃_1∃_2...∃x_n θ.
Let A be a substructure of B, and s valuation on A.

a) Show that if ⊨_B ψ and ψ is universal, then ⊨_A ψ . Also show that if ⊨_A ψ and ψ is existential, then ⊨_B ψ .

b) Use part (a) to show that the sentence (∃x Px) is not logically equivalent to any universal formula, and that (∀x Px) is not logically equivalent to any existential formula.

2. Relevant equations

→satisfiability?

3. The attempt at a solution

My professor goes too quickly with satisfiability, and he expects me to solve such problem.

Here are some thoughts I have..

a) Since ψ is universal, we can say that ⊨_B ∀x_1∀x_2...∀x_n θ . I would say that since θ is quantifier free, no matter what type of symbols you have for θ, then, it must be just ∀x_1∀x_2...∀x_n θ = θ. I am thinking that I need to use induction principle for this part.

Seems like I lack some understanding of how the proof should work. -___-

b) I am not sure how to work out part b.