I think you agree that in order to show that § is inadequate, it is enough to show that there is no way to express a tautology with just §.
A tautology is a term $t$ whose value $v(t)$ is true for every assignment of values to the variables of $t$.
If there is any assignment of values to $t$'s variables that results in $t$ having a false value, then $t$ is not a tautology.
In particular, if assigning false values to all the variables of $t$ results in $t$ having a false value also, then $t$ is not a tautology. (This is the crucial point that seems to be giving you trouble.)
But it is the case that if $t$ is made of only §, then assigning false values to all its variables results in $t$ also having a false value. (This is the step that is justified by the induction proof.)
Therefore, any term $t$ made of only § is not a tautology.
Therefore, § is not adequate.
Is this clearer now?
You said you don't understand how to go from step 3 to step 4.
Consider this silly example, which follows the same pattern:
- A paradise is a country where every inhabitant is happy.
- Gaston, who lives in France, is not happy.
- Therefore, France is not a paradise.
“But,” you say, “why don't we have to consider Pierre? Pierre also lives in France!”
Pierre doesn't matter. France is only a paradise if every person in France is happy. To show that France is not a paradise, we only have to find one person in France who is not happy.
- A tautology is a term for which every assignment of values to its variables results in its having a true value.
- Assigning all false values to the variables of the term $t$ results in $t$ having a false value.
- Therefore, $t$ is not a tautology.
“But,” you say, “why don't we have to consider other assignments of values to the variables of $t$? Those are assignments too!”
Those assignments don't matter. $t$ is only a tautology if every assignment results in $t$ having a true value. To show that $t$ is not a tautology, we only have to find one assignment that results in $t$ having a false value.
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.
Best Answer
What you’re suggesting doesn’t quite work as you’ve stated it: a propositional variable has only one True value in its truth table. However, it is true that every $\varphi\in\Phi$ either is a propositional variable or has an even number of True values in its truth table.
The standard approach is to prove it by induction on the complexity of the wff. The basis step is to check that every propositional variable has it; this is clearly true. The induction step is to show that if $\varphi,\psi\in\Phi$, and $\varphi$ and $\psi$ both have the property, then $\varphi\leftrightarrow\psi$ and $\varphi+\psi$ both have the property.
You can see an example of such an argument in my answer to this question.