The article doesn’t really explain very much (not that it ought to explain everything, but there’s very little). The proof of the standard claims about ‘expres

The article doesn’t really explain very much (not that it ought to explain everything, but there’s very little). The proof of the standard claims about ‘expressive adequacy’ (=functional completeness) in propositional logic is given in cap. 4 of Button’s Metatheory; forallx:Cambridge uses the same notation and gives a fairly easy (from a skim) introduction to propositional logic.¹ Briefly, however, a simple method of dealing with at least some of the cases is as follows. Consider the connectives of propositional logic (e.g., ¬, ∧, ∨—add more symbols to taste to represent every other possible connective given by a truth table on two variables). A sentence contains various sentence letters (P, Q, R, P₁, Q₁, R₁, P₂…—adjust to taste) and connectives; we define them inductively, with the base ‘atomic’ cases as the sentence letters and the inductive cases - ¬φ where φ is a sentence, - (φ · ψ) where φ and ψ are sentences, and · is some ‘binary connective’ (i.e., it corresponds to a function given by a truth table with two variables: it could be ∧ or ∨ or even the Quine dagger.) Now, let the complexity of a sentence be the number of connectives appearing within it, which is equal to the number of invocations of one of the inductive rules above required to obtain a sentence (one can also think of sentences as trees). We use induction on the complexity of a sentence to prove statements about all sentences. Let us consider, by way of example, or (∨). We can prove that ∨ alone is not expressively adequate. Consider an assignment of truth values such that the truth value of any sentence letter is T(rue). Now, it should be possible to write some sentence the truth value of which is F(alse) solely using ∨, if ∨ is expressively adequate. The difficulty is that one can’t. Informally, ∨ cannot take two true statements and give a false one, but it only has (under this assignment of truth values) true statements. It is easy to fill in the base and inductive cases because propositional logic is truth-functional (i.e., it does not matter what a proposition says, merely whether it is true or false.) Similar strategies to find properties invariant under the use of inductive rules may be used to prove all sorts of metalogical statements, as shown in Button’s book. 0: available at http://www.homepages.ucl.ac.uk/~uctytbu/Metatheory.pdf http://www.homepages.ucl.ac.uk/~uctytbu/Metatheory.pdf 1: http://www.homepages.ucl.ac.uk/~uctytbu/OERs.html http://www.homepages.ucl.ac.uk/~uctytbu/OERs.html