0
$\begingroup$

I'm working on a question for a course in mathematical logic.

Prove that if a sentence $\phi$ expresses a truth function $f$ and every connective in $\phi$ is assigned a self-dual truth function, then $\phi$ expresses $f^*$ (the dual of $f$).

My lecture notes say that $\phi$ expresses $f$ iff for all $\mathcal{A}:$ $|\phi|_\mathcal{A}=f(|\alpha_1|_\mathcal{A},...,|\alpha_n|_\mathcal{A})$ for $\alpha_1,...,\alpha_n\in\text{SenLett}(\phi)$ where $\text{SenLett}(\phi)$ is the set of all sentence letters in $\phi$ and $|\phi|_\mathcal{A}$ means the truth value of $\phi$ under the model $\mathcal{A}$.

I've tried to do this by strong induction on the complexity of $\phi$, denoted $\text{NConn}(\phi)$.

Base case: $\text{NConn}(\phi)=0$

$|\phi|_\mathcal{A}=f(|\phi|_\mathcal{A})$ since there are no connectives.

$\therefore |\phi|_\mathcal{A}=1-(1-|\phi|_\mathcal{A})=1-f(1-|\phi|_\mathcal{A}):=f^*(|\phi|_\mathcal{A})$

Inductive step: assume true for $\text{NConn}(\phi)\leq k$

Now I get stuck. $\phi=c(\psi_1,...,\psi_m)=c^*(\psi_1,...,\psi_m)$ for whatever connective $c$ we pick, but I have no idea how to go from some complexity to the next.

I've tried to represent the truth-functions of the connectives: $$ |\phi|_\mathcal{A}=|c(\psi_1,...,\psi_m)|_\mathcal{A}=f_c(|\psi_1|_\mathcal{A},...,|\psi_m|_\mathcal{A})\\\\ =f_{c^*}(|\psi_1|_\mathcal{A},...,|\psi_m|_\mathcal{A})\text{ by self-duality of connective}\\\\ =1-f_c(1-|\psi_1|_\mathcal{A},...,1-|\psi_m|_\mathcal{A})\text{ by definition}\\\\ $$

Now I guess I'd invoke that $|\psi_i|_\mathcal{A}=|c'(\chi_1,...,\chi_n)|_\mathcal{A}$ to make the induction step, but I have no idea how I would do this. I can't recreate the approach from the base case because I don't have in general the ease of manipulation of the case when $\phi$ is a sentence letter itself.

Should I abandon this approach and instead attempt to induct on the number of sentence letters? Or perhaps to prove it for binary connectives and then somehow use expressive adequacy to generalise it for logically equivalent sentences with n-ary connectives? Any advice would be appreciated.

$\endgroup$
2
  • $\begingroup$ Your question uses notation which seems may be particular to the logic text or course in logic it is from. notation like that should be defined in the question. $\endgroup$
    – coffeemath
    Mar 4 at 0:56
  • 1
    $\begingroup$ @coffeemath should be better now - I explained my course's notation for truth value under a model + for duality + for SenLett($\phi$). Let me know if there is any other unclear use of notation. $\endgroup$
    – Amitai
    Mar 4 at 1:01

1 Answer 1

0
$\begingroup$

I'm going to answer my own question after having asked my professor. Here is one approach.

First note that $|\phi|_\mathcal{A}=f_\phi(|\alpha_1|_\mathcal{A},...,|\alpha_n|_\mathcal{A})$ for $\alpha_1,...,\alpha_n\in\text{SenLett}(\phi)$

Claim: $f_\phi=f_{\phi}^*$

Base case: $\text{NConn}(\phi)=0$

$|\phi|_\mathcal{A}=f(|\phi|_\mathcal{A})$ since there are no connectives.

$\therefore |\phi|_\mathcal{A}=1-(1-|\phi|_\mathcal{A})=1-f(1-|\phi|_\mathcal{A}):=f^*(|\phi|_\mathcal{A})$

Inductive step: assume true for $\text{NConn}(\phi_i)\leq k,\ \ 1\leq i\leq m$

$\phi:=c(\phi_1,...,\phi_m)$ for some connective $c$. We see that $\text{NConn}(\phi)\leq mk+1$.

$|\phi|_\mathcal{A}=f_c(|\phi_1|_\mathcal{A},...,|\phi_m|_\mathcal{A})$ where $f_c$ is the truth function for the connective $c$.

$$\begin{align*} |\phi|_\mathcal{A}&=f_{c^*}(|\phi_1|_\mathcal{A},...,|\phi_m|_\mathcal{A}) \text{ by self duality}\\ &=1-f_c(1-|\phi_1|_\mathcal{A},...,1-|\phi_m|_\mathcal{A})\\ &=1-f_c(1-f_{\phi_1}(|\beta_1|_\mathcal{A},...,|\omega_1|_\mathcal{A}),...,f_{\phi_m}(|\beta_m|_\mathcal{A},...,|\omega_m|_\mathcal{A}))\\ \text{s.t. $\beta_i,...,\omega_i\in\text{SenLett}(\phi_i)$}\\ &=1-f_c(1-f^*_{\phi_1}(|\beta_1|_\mathcal{A},...,|\omega_1|_\mathcal{A}),...,f^*_{\phi_m}(|\beta_m|_\mathcal{A},...,|\omega_m|_\mathcal{A}))\\ &=1-f_c(f_{\phi_1}(1-|\beta_1|_\mathcal{A},...,1-|\omega_1|_\mathcal{A}),...,f_{\phi_m}(1-|\beta_m|_\mathcal{A},...,1-|\omega_m|_\mathcal{A}))\\ &=1-f_{\phi}(1-|\alpha_1|_\mathcal{A},...,1-|\alpha_n|_\mathcal{A})\\ &=f^*_\phi(|\alpha_1|_\mathcal{A},...,|\alpha_n|_\mathcal{A})\\ \end{align*}$$ $\blacksquare$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .