-1
$\begingroup$

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.

$\endgroup$
1
3
$\begingroup$

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$.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.