Tautologies and valuations in a first order language

Question

I have a few questions regarding the three final question. First I have from earlier:

Definition 1: A formula is called prime if it is either atomic or of the form $\forall x \varphi$, for some variable x and formula $\varphi$. Let $PFormula^{\mathcal{L}}_0$ denote the set of prime formulas in the language $\mathcal{L}$. Then we define recursively that $PFormula^{\mathcal{L}}_{n+1}$ consists of all the formulas either of the form $(\neg \psi )$ or of the form $(\psi \to \varphi)$, where $\psi, \varphi \in \bigcup_{i \leq n} PFormula^{\mathcal{L}}_{i}$

In the assignment I have shown that:

a) Show that $\bigcup_{n \geq 0} PFormula^{\mathcal{L}}_n =Formula(\mathcal{L})$

b) Prove the principle of induction on prime formulas: Let $\Gamma$ be a set of formulas such that $PFormula^{\mathcal{L}}_0 \subseteq \Gamma$. Suppose that if $\varphi \in \Gamma$ then $(\neg \varphi ) \in \Gamma$ and if $\psi, \varphi \in \Gamma $ then $( \psi \to \varphi) \in \Gamma$. Then $\Gamma = Formula (\mathcal{L})$

Definition 2: A valuation is a function $v : PFormula^{\mathcal{L}}_0 \to \lbrace 0,1 \rbrace$

c) Show that given a valuation $v$ there is a unique functions $v^*: Formula(\mathcal{L}) \to \lbrace 0,1 \rbrace$ such that $v^* \upharpoonright PFormula^{\mathcal{L}}_0 = $, $v^*((\neg \varphi ))=1-v^*(\varphi)$ and $v^*((\psi \to \varphi))=max \lbrace1-v^*(\psi), v^*(\varphi) \rbrace$

Definition 3:

(1) A tautology is a formula $\varphi$ such that $v^*(\varphi)=1$ for any valuation $v$.

(2) Let $\Gamma $ be a set of formulas and $\varphi$ a formula. We say that $\Gamma$ truth-functionally implies $\varphi$ if whenever $v$ is a valuation such that $v^*(\gamma)=1$ for all $\gamma \in \Gamma $ then $v^*(\phi)=1$. If this is the case we write $\Gamma \vDash_t \phi$

And now I need to do the last parts where:

d)Give an example of a tautology (in some language of your choice). Prove your example is indeed a tautology.

Answer: to this I've just let $\mathcal{L}$ be any first order language and the my example is:

$(\forall x(x=x))\vee (\neg(\forall x(x=x)))$

As $A \vee (\neg A)$ is a tautology in sentinental logic (by Enderton p. 27) then by replacing A with $(\forall x(x=x)$ which is a wff then by Enderton p. 114 my example is indeed a tautology.

Is this correct? I wanted to use the definition but this seemed simpler (but that might be because it is not true). Also, I wanted it to be an explicit language but I am so new to logic that I am not sure which language it could be.

e) Show that if $\Gamma$ is a set of formulas and $\Gamma \vDash_t \varphi $ for some formula $\varphi$ then $\Gamma \vDash \varphi$

Answer: To follow a hint in the assignment I let $U$ be any model of $\mathcal{L}$ and suppose that $\vDash_U \Gamma [s]$ for some $s: V \to \vert U \vert $. I now want to define a valuation $v: PFormula^{\mathcal{L}}_0 \to \lbrace 0,1 \rbrace $ by letting $v(\gamma)=1$ if and only if $\vDash_U \gamma [s]$ and then I want to show that $v^*(\psi)=1 $ if and only if $\vDash_U \gamma [s]$ for any formula $\psi$

My problem here is I am not sure how to prove this and it's not obvious to me how this helps me to prove the statement.

Finally:

f) Give an example of a language $\mathcal{L}$, a set of formulas $\Gamma$ and a formula $\varphi$ such that $\Gamma \vDash \varphi$ yet $\Gamma \nvDash_t \varphi$

Answer: again I am having som trouble coming up with a specific first order language and also I am having some trouble giving an example which is probably due to the fact that the definitions are not clear to me.

Answer 1

We define a valuation $v$ on all the prime formulas of the language such that:

$v(\alpha)= \text T \text { iff } U \vDash \alpha[s]$.

Then we extend it to $\overline v$ such that $\overline v(\varphi) = \text T \text { iff } U \vDash \varphi [s]$, for a formula $\varphi$ whatever of the language.

That such a $\overline v$ exists is proved by induction.

The base case is already in the definition for prime formulas. The induction step needs the basic connectives of the language. Example for $\lnot$: assume that the property hold for $\psi$ and let $\varphi := \lnot \psi$.

We have:

$\overline v(\varphi) = \text T \text { iff } \overline v (\lnot \psi)= \text T \text { iff } \overline v (\psi)= \text F \text { iff } U \nvDash \psi[s] \text { iff } U \vDash \lnot \psi [s] \text { iff } U \vDash \varphi[s].$

Similar for $\to$ and $\lor$, etc. A little bit more tricky the case for $\forall$.

---

Now for the result: assume that $\Gamma \vDash_{\text {Taut}} \varphi$ and $\Gamma \nvDash \varphi$.

This means that, for some $U$ and $s$ we have:

$U \vDash \gamma_i[s]$, for every $\gamma_i \in \Gamma$, and $U \nvDash \varphi [s]$.

But this means that, using the construction above, we can find $v$ such that $\overline v(\gamma_i)= \text T$ and $\overline v (\varphi)= \text F$, contradicting the assumption that $\Gamma \vDash_{\text {Taut}} \varphi$.