Proof of a logical theorem

Prove that if for every proposition $$\psi\left(p_{0}, \ldots, p_{n}, p\right)$$ there exists $$\phi\left(p_{0}, \ldots, p_{n}\right)$$ in which $$\psi\left(p_{0}, \ldots, p_{n}, p\right) \rightarrow\left(\phi\left(p_{0}, \ldots, p_{n}\right) \leftrightarrow p\right)$$ is a tautology then $$\phi$$ is a definition of $$p$$ in terms of $$\psi$$ then $$\left(\psi\left(p_{0}, \ldots, p_{n} , p\right) \wedge \psi\left(p_{0}, \ldots, p_{n}, q\right)\right) \rightarrow(p \leftrightarrow q)$$ is a tautology. $$p_{0}, \ldots, p_{n}, p , q$$ are atoms.

I looked it up in two logic books A Mathematical Introduction to Logic and Logic and Structure but couldn't find this theorem. I'm new to logical proofs and I don't know where to begin in proving this theorem. Is there anyone who can name some books that contain this theorem? If not please explain how this logical proof works.

• Oct 23 '21 at 9:44

Let me explain what is going on here by way of an example: $$\psi(p_0,p_1,p) = p \leftrightarrow (p_0 \land p_1).$$ That is, $$\psi(p_0,p_1,p)$$ is true iff $$p = p_0 \land p_1$$.

If you define $$\phi(p_0,p_1) = p_0 \land p_1,$$ then we indeed have $$\psi(p_0,p_1,p) \to (\phi(p_0,p_1) \leftrightarrow p),$$ which means that if $$\psi(p_0,p_1,p)$$ holds then $$p = \phi(p_0,p_1)$$.

Clearly, in this case, if both $$\psi(p_0,p_1,p)$$ and $$\psi(p_0,p_1,q)$$ hold then $$p = q$$, since both are equal to $$\phi(p_0,p_1)$$.

Now for the formal proof. We assume that $$\tag{\ast} \psi(p_0,\ldots,p_n,p) \to (\phi(p_0,\ldots,p_n) \leftrightarrow p),$$ and want to conclude $$(\psi(p_0,\ldots,p_n,p) \land \psi(p_0,\ldots,p_n,q)) \to (p \leftrightarrow q).$$

Assume, therefore, that $$\psi(p_0,\ldots,p_n,p)$$ and $$\psi(p_0,\ldots,p_n,q)$$ both hold. Assumption ($$\ast$$) implies that $$p \leftrightarrow \phi(p_0,\ldots,p_n) \leftrightarrow q,$$ and so $$p \leftrightarrow q$$.

This problem sounds quite abstract and I'll sketch a proof below. To prove the final material conditional is a tautology, we only need to prove $$\psi(p_0, \ldots p_n, p) \wedge \psi(p_0, \ldots p_n, q) \land \lnot (p \leftrightarrow q)$$ is unsatisfiable, which means it can never be the case that $$p,q$$ can have opposite truth values while both $$\psi(p_0, \ldots p_n, p)$$ and $$\psi(p_0, \ldots p_n, q)$$ are true. In general cases this obviouly could be satisfied, for example in the case of a disjunctive normal form, $$\psi(p_0, \ldots p_n, p)=p_0 \lor \ldots \lor p_n \lor p$$.

However, we have the given assumption $$\psi(p_0, \ldots p_n, p) \rightarrow (\phi(p_0, \ldots p_n) \leftrightarrow p)$$ as a tautology, this obviously blocks the previous case as $$\phi$$ now must be truth-functionally dependent on $$p$$, for example, if $$\psi=p_0 \land \ldots \land p_n \land \lnot p$$, then we can have $$\phi=\lnot (p_0 \land \ldots \land p_n)$$. This given tautology (premise) thus ensures us that $$\phi$$ can be thought of as a logically equivalent definition of $$p$$ in terms of $$\psi$$ and therefore $$p$$ must be logically equivalent to $$\phi(p_0, \ldots p_n)$$ alone (nothing else), as a result it can never be the case that $$p,q$$ can have opposite truth values while both $$\psi(p_0, \ldots p_n, p)$$ and $$\psi(p_0, \ldots p_n, q)$$ are true.