I'm struggling with the following problem:
Let $L_1^*$ be the language obtained from $L_1$ by removing $\to$ and $\leftrightarrow$ from the stock of connectives (leaving it with $\neg, ∧, ∨, \top,$ and $\bot$). And let $\phi^*$ be the formula obtained from a formula $\phi$ of $L_1^*$ by replacing any occurrence of $∧$ by $∨$, any occurrence of $∨$ by $∧$, any occurrence of $\bot$ by $\top$, and any occurrence of $\top$ by $\bot$.
$(a)$Give a recursive definition of $\phi^*$ — i.e. of the function $\phi \mapsto \phi^*$.
$(b)$ Given a structure $A$, define $A^∗$ by stipulating that $A^∗(P) = f_{\neg}(A(P))$ — in other words, $A^∗(P) = \top(\bot)$ if and only if $A(P) = \bot(\top)$. Show, by induction on the complexity of formulae, that, for any $\phi$ and any $A$, $|\phi^∗|_A = f_{\neg}(|\phi|_{A^∗} )$ — in other words, $|\phi^∗|_A = \top(\bot)$ if and only if $|\phi|_{A^∗} = \bot(\bot)$.
$(c)$ Deduce that $\phi \models \psi$ if and only if $\psi^∗ \models \phi^∗$, and that $\phi$ is tautologous if and only if $\phi^∗$ is unsatisfiable.
Looks like (a) is solved:
1) $P^* = P$, for any atomic formulae $P$
$[$1b) $\top^* = \bot$
1c) $\bot^* = \top]$
2a) $(\phi ∧ \psi)^* = (\phi^* ∨ \psi^*)$
2b) $(\phi ∨ \psi)^* = (\phi^* ∧ \psi^*)$
My attempt at (b):
I assume that the directions to "define $A^*$" mean to provide a recursive definition. I am guessing this would look similar to part (a), so that:
1) $|\phi^*|_A = f_{\neg}(|\neg\phi|_{A^*})$, for any sentence $\phi$
$[$1b) $|\top|_A = |\bot|_{A^*}$
1c) $|\bot|_A = |\top|_{A^*}]$
2a) $|(\phi ∧ \psi)^*|_A = f_{∨}(|(\neg\phi ∨ \neg\psi)|_{A^*})$
2b) $|(\phi ∨ \psi)^*|_A = f_{∧}(|(\neg\phi ∧ \neg\psi)|_{A^*})$
My attempt at (c):
(i) $\phi \models \psi$
By contraposition: $\neg\psi \models \neg\phi$
(ii) By the definition of $A^*$, which stipulates $A^*(P) = f_{\neg}(A(P))$:
$|\neg\phi|_A = f_{\neg}(|\phi^*|_{A^*})$
$|\neg\psi|_A = f_{\neg}(|\psi^*|_{A^*})$
(iii) Thus, if $\phi \models \psi$ (under $A$), then under $A^*$: $\psi^*\models\phi*$