Directory:Jon Awbrey/MathJax Problems

Computation and inference as semiosis

Equational reasoning, as distinguished from implicational reasoning, is well-evolved in mathematics today but grievously short-schrifted in contemporary logic textbooks. Consequently, it may be advisable for me to draw out and place in relief some of the more distinctive characters of equational inference that may have passed beneath the notice of a casual reading of these notes.

By way of a very preliminary orientation, let us consider the distinction between information reducing inferences and information preserving inferences. It is prudent to make make our first acquaintance with this distinction in the medium of some concrete and simple examples.

•	Example 1. Modus Ponens
		Information Reducing Inference
			\(\begin{array}{l} ~ p \Rightarrow q \\ ~ p \\ \overline{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~} \\ ~ q \end{array}\)
		Information Preserving Inference
			\(\begin{array}{l} ~ p \Rightarrow q \\ ~ p \\ \overline{\underline{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~}} \\ ~ p ~ q \end{array}\)

Let us examine these two types of inference in a little more detail. A rule of inference is stated in the followed form:

\(\begin{array}{l} ~ \textit{Expression 1} \\ ~ \textit{Expression 2} \\ \overline{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~} \\ ~ \textit{Expression 3} \end{array}\)

The expressions above the line are called premisses and the expression below the line is called a conclusion. If the rule of inference is simple enough, the proof-theoretic turnstile symbol \({}^{\backprime\backprime} \vdash {}^{\prime\prime}\!\) may be used to write the rule on a single line, as follows:

\(\textit{Premiss 1}, \textit{Premiss 2} ~\vdash~ \textit{Conclusion}.\!\)

Either way, one reads such a rule of inference in the following manner:

From   \({\textit{Expression 1}}\!\)   and   \({\textit{Expression 2}}\!\)   infer   \({\textit{Expression 3}}.\!\)

Looking to Example 1, the rule of inference known as modus ponens says the following: From the premiss \(p \Rightarrow q\!\) and the premiss \(p\!\) one may logically infer the conclusion \(q.\!\)

Modus ponens is an illative or implicational rule. Passage through its turnstile incurs the toll of some information loss, and thus from a fact of \(q\!\) alone one cannot infer with any degree of certainty that \(p \Rightarrow q\!\) and \(p\!\) are the reasons why \(q\!\) happens to be true.

Further considerations along these lines may lead us to appreciate the difference between implicational rules of inference and equational rules of inference, the latter indicated by an equational line of inference or a 2-way turnstile \({}^{\backprime\backprime} \Vdash {}^{\prime\prime}.\!\)

Variations on a theme of transitivity

The next Example is extremely important, and for reasons that reach well beyond the level of propositional calculus as it is ordinarily conceived. But it's slightly tricky to get all of the details right, so it will be worth taking the trouble to look at it from several different angles and as it appears in diverse frames, genres, or styles of representation.

In discussing this Example, it is useful to observe that the implication relation indicated by the propositional form \(x \Rightarrow y\!\) is equivalent to an order relation \(x \le y\!\) on the boolean values \(0, 1 \in \mathbb{B},\!\) where \(0\!\) is taken to be less than \(1.\!\)

•	Example 2. Transitivity
		Information Reducing Inference
			\(\begin{array}{l} ~ p \le q \\ ~ q \le r \\ \overline{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~} \\ ~ p \le r \end{array}\)
		Information Preserving Inference
			\(\begin{array}{l} ~ p \le q \\ ~ q \le r \\ \overline{\underline{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~}} \\ ~ p \le q \le r \end{array}\)

In stating the information-preserving analogue of transitivity, I have taken advantage of a common idiom in the use of order relation symbols, one that represents their logical conjunction by way of a concatenated syntax. Thus, \(p \le q \le r\!\) means \(p \le q ~\mathrm{and}~ q \le r.\!\) The claim that this 3-adic order relation holds among the three propositions \(p, q, r\!\) is a stronger claim — conveys more information — than the claim that the 2-adic relation \(p \le r\!\) holds between the two propositions \(p\!\) and \(r.\!\)