In my textbook I am introduced to two ways to prove that a set of connectives is functionally incomplete. The first one is to prove that it has a property that not all truth functions do.
I am stuck at finding one such property for $\{\lnot\}$ (and I can't believe I am so dumb to be stuck…). I have two ideas: first one is to prove that $\lnot$ always returns a $F$ for any true argument (thus rendering a truth function that returns $T$ from a true arugment impossible).
Prove that if $\phi$ is built up using the variable $P$ with $\lnot$, and $v$ is the truth assignment s.t. $v(p)=T$, then $v(\phi)=F$.
Induction on the number $n$ of connectives in $\phi$.
Base case $n=0$: $\phi=P$ – there isn't any $\lnot$ to talk about, so it is vacuously true.
Assume that it holds true for $\le n$, prove that it holds true for $n+1$.
$\phi=\lnot \psi$: Number of connectives within $\psi=n$, thus it holds true for $\psi$. Therefore $v(p)=T\to v(\psi)=F$.
As you can see, if $v(\psi)=F$, then $v(\phi)=v(\lnot \psi)=T$, which is not what we want. This seems to be an instance of double negation; it can flip whatever truth value to the opposite, so it seems futile to try and show that there is a truth function $\{\lnot\}$ cannot show, because with double negation you can always show a $T/F$.
The second idea to show that a negation can only show a truth function with one argument, but not one with more than one. But this seems only to be a syntactical problem: yes, you can't show a formula of $>1$ variables with only negation, but you can still draw a truth table for it nonetheless.
So my first question is,
1) what went wrong with my proof, and how to prove $\{\lnot\}$ is functionally incomplete by showing a property that only this set has?
The second way is to show how many truth functions of $n$ arguments can be represented; if this number is $<2^{2^n}$, then it is not complete; vice versa.
The book showed how to use this approach to prove that $\{\land\}$ is incomplete. The number for this set is $2^n -1$. My question is,
2) how do we know the number for $\{\lnot,\land,\lor\}=2^{2^n}$?
It must be so since it is complete, but I just don't know how to prove it.
(The book equivalated formulas $\phi$ built up using variables in the set $\{p_1, p_2, . . . , p_n\}$ to a normal form where no parenthesis remains and only variables are left, and explained that the number of non-empty subsets of this
set of variables used to build the normal form $=2^n -1$. e.g. $\phi=(p_3\land p_1)\land (p_2\land(p_1\land p_4))$, normal form=$p_1\land p_2 \land p_3 \land p_4$)
Really appreciate any help offered!
Best Answer
Daniil wrote an excellent post, but just to add to that a little bit:
As Daniil pointed out, you can't capture any truth-functions that non-trivially depend on more than $1$ variable, such as $P \land Q$, with only a $\neg$. So, let's restrict ourselves to functions defined over one variable, $P$, and see if maybe we can capture all those using a $\neg$?
Unfortunately, the answer is still no. Again, as Daniil already pointed out, we can't capture any tautology or contradiction. That is, we can't capture the truth-function that always returns true (i.e. the function $f$ such that $f(T)=f(F)=T$), nor can we capture the truth-function that always returns false (i.e. the function $f'$ such that $f'(T)=f'(F)=F$)
So in this post I just wanted to show you how you can prove that result using induction. In particular, let's prove the following:
Claim
For any expression $\phi$ built up from $P$ and $\neg$ alone, it will be true that if $v$ is the valuation that sets $P$ to true (i.e. $v(P)=T$), and $v'$ is the valuation that sets $P$ to false (i.e. $v'(P)=F$), then either $v(\phi)=T$ and $v'(\phi)=F$, or $v'(\phi)=T$ and $v(\phi)=F$ (in other words, $v(\phi)$ and $v'(\phi)$ will always opposite values, meaning that $\phi$ can not be a tautology or contradiction, for that would require that $\phi$ has the same value for any valuation)
Proof
We'll prove the claim by structural induction on the formation of $\phi$:
*Base: *
$\phi=P$. Then $v(\phi)=v(P)=T$, while $v'(\phi)=v'(P)=F$. Check!
Step:
If $\phi$ is not an atomic proposition, then there is only one possibility: $\phi$ is the negation of some other statement $\psi$, i.e. $\phi = \neg \psi$.
Now, by inductive hypothesis we can assume that $v(\psi)=T$ and $v'(\psi)=F$, or $v'(\psi)=T$ and $v(\psi)=F$
Well, if $v(\psi)=T$ and $v'(\psi)=F$, then $v(\phi)=v(\neg \psi)=F$ and $v'(\phi)=v'(\neg \psi) =T$. On the other hand, if $v(\psi)=F$ and $v'(\psi)=T$, then $v(\phi)=v(\neg \psi)=T$ and $v'(\phi)=v'(\neg \psi) =F$. So, we can conclude that $v(\phi)=T$ and $v'(\phi)=F$, or $v'(\phi)=T$ and $v(\phi)=F$, as desired.