Showing a Set of Connectives is Inadequate

Question

I want to show that the set $\left \{ \vee, \wedge, \to, \leftrightarrow \right \}$ of connectives is inadequate. Since $\leftrightarrow$ is defined using $\vee, \wedge, \to$, is it sufficient to show that the subset $\left \{ \vee, \wedge, \to \right \}$ is inadequate?

Answer 1

Short answer. To prove that the set of connectives $\{\lor, \land, \to, \leftrightarrow\}$ is inadequate, it is sufficient to show that the set $\{\lor, \land, \to\}$ is inadequate, essentially because, as you said correctly, the connective $\leftrightarrow$ can be expressed by means of $\to$ and $\land$.

---

Long answer. Let us see why more precisely (and pedantically).

Definition 1. Given a set $X \subseteq \{\bot, \top, \lnot, \lor, \land, \to, \leftrightarrow\}$ of connectives for propositional logic (the constants $\bot$ and $\top$ can be seen as 0-ary connectives), the set of formulas built up from propositional variables by means of the connectives in $X$ is denoted by $\mathcal{F}_X$.

Definition 2. A set $X \subseteq \{\bot, \top, \lnot, \lor, \land, \to, \leftrightarrow\}$ of connectives for propositional logic is inadequate if there is a formula $A \in \mathcal{F}_{\{\bot, \top, \lnot, \lor, \land, \to, \leftrightarrow\}}$ such that every formula in $\mathcal{F}_X$ is not logically equivalent to $A$.

Lemma. Every formula in $\mathcal{F}_{\{\lor, \land, \to, \leftrightarrow\}}$ is logically equivalent to a formula in $\mathcal{F}_{\{\lor, \land, \to\}}$.

Proof. By induction on the structure of the formula in $\mathcal{F}_{\{\lor, \land, \to, \leftrightarrow\}}$. (Hereafter, we will implicitly use that, in formula $A$, if a subformula $B$ of $A$ is replaced by a formula logically equivalent to $B$, the obtained global formula is logically equivalent to $A$). A formula in $\mathcal{F}_{\{\lor, \land, \to, \leftrightarrow}\}$ is:

• either $A \diamond B$ with $\diamond \in \{\lor, \land, \to\}$ and $A, B \in \mathcal{F}_{\{\lor, \land, \to, \leftrightarrow\}}$, and then by induction hypothesis there are formulas $A', B' \in \mathcal{F}_{\{\lor, \land, \to\}}$ logically equivalent to $A,B$, respectively; therefore, $A' \diamond B'$ is a formula in $\mathcal{F}_{\{\lor, \land, \to\}}$ logically equivalent to $ A \diamond B$;

• or $A \leftrightarrow B$ with $A, B \in \mathcal{F}_{\{\lor, \land, \to, \leftrightarrow\}}$, and then by induction hypothesis there are formulas $A', B' \in \mathcal{F}_{\{\lor, \land, \to\}}$ logically equivalent to $A,B$, respectively; therefore, $(A' \to B') \land (B' \to A')$ is a formula in $\mathcal{F}_{\{\lor, \land, \to\}}$ logically equivalent to $ A \leftrightarrow B$. $\square$

You are asking if the following claim holds. The answer is positive.

Claim. If $\{\lor, \land, \to\}$ is inadequate, then $\{\lor, \land, \to, \leftrightarrow\}$ is inadequate.

Proof. Since $\{\lor, \land, \to\}$ is inadequate, there is a formula $A\in \mathcal{F}_{\{\bot, \top, \lnot, \lor, \land, \to, \leftrightarrow\}}$ such that every formula in $\mathcal{F}_{\{\lor, \land, \to\}}$ is not logically equivalent to $A$. But every formula in $\mathcal{F}_{\{\lor, \land, \to, \leftrightarrow\}}$ is logically equivalent to some formula in $\mathcal{F}_{\{\lor, \land, \to\}}$, according to the lemma above. Therefore, every formula in $\mathcal{F}_{\{\lor, \land, \to, \leftrightarrow\}}$ is not logically equivalent to $A$ (otherwise there would be a formula in $\mathcal{F}_{\{\lor, \land, \to\}}$ logically equivalent to $A$, by transitivity of logical equivalence, which is impossible by hypothesis), i.e. $\{\lor, \land, \to, \leftrightarrow\}$ is inadequate. $\square$

---

Remark (beyond your question). Now, you just have to prove that $\{\lor, \land, \to\}$ is inadequate, i.e. to show that there is a formula $A \in \mathcal{F}_{\{\bot, \top, \lnot, \lor, \land, \to, \leftrightarrow\}}$ such that every formula in $\mathcal{F}_{\{\lor, \land, \to\}}$ is not logically equivalent to $A$. It is easy to prove that you can take $A = \lnot p$, for any propositional variable $p$.

Hint (to prove that every formula in $\mathcal{F}_{\{\lor, \land, \to\}}$ is not logically equivalent to $\lnot p $). What is the truth value of a formula in $\mathcal{F}_{\{\lor, \land, \to\}}$ with a valuation assigning true to every propositional variable occurring in it? What is the truth value of $\lnot p$ with a valuation that assigns true to the propositional variable $p$?