Proof by induction, logic

445 Views Asked by At

I'd like you to comment if my following proof by induction is correct ($\mathbb{N} = \{0, 1, 2, \ldots\}).$

Thesis: Every formula constructed from variable $p$ and connectives $\land$, $\lor$, $\top$ (and brackets) is equivalent to either $p$ or $\top$.

Let $\phi_n$ be formula with depth of $n$, constructed only from variable $p$ and connectives $\land$, $\lor$, $\top$ (and brackets).

Let $X = \{n \in \mathbb{N} : \phi_n \equiv p \lor \phi_n \equiv \top \}$

Base case.
For $n=0$ we have $\phi_0=p$ or $\phi_0=\top$, so obviously $\phi_0 \equiv p \lor \phi_0 \equiv \top$ and $0 \in X$.

Inductive step.
Let's assume $k \in X$, where $k < n$, i. e. $\phi_k \equiv p \lor \phi_k \equiv \top$ (this is inductive hypothesis). We will show that $n \in X$. Let's look at the cases for $\phi_n$:

1) $\phi_n = \phi_k \lor \phi'_{n-1-k}$. We know from our inductive hypothesis that $k \in X$ and $n-1-k \in X$, so we get four equivalent formulas $p \lor \top$, $p \lor p$, $\top \lor \top$ and $\top \lor p$. Obviously $p \lor \top \equiv \top \lor p \equiv \top \lor \top \equiv \top$ and $p \lor p \equiv p$.

2) $\phi_n = \phi_k \land \phi'_{n-1-k}$. We know from our inductive hypothesis that $k \in X$ and $n-1-k \in X$, so we get four equivalent formulas $p \land \top$, $p \land p$, $\top \land \top$ and $\top \land p$. Obviously $p \land \top \equiv \top \land p \equiv p \land p \equiv p$ and $\top \land \top \equiv \top$.

Therefore $n \in X$, so by mathematical induction, formula $\phi_n$ of depth $n \geqslant 1$ constructed only from variable $p$ and connectives $\land$, $\lor$, $\top$ (and brackets) is equivalent to either $p$ or $\top$.