View Source Document

Chris Pressey.md

Commentary by Chris Pressey

This work is distributed under a CC-BY-ND-4.0 license, with the following explicit exception: the ratings may be freely used for any purpose with no limitations.

Algebraic Logic

Logic as Algebra

This is a good introduction to how logic can be explained algebraically. Very readable. "100% emoji" as they say. Gloss follows.

"What is Logic?" ... Sections 1 to 7.

Contains a metaphor about a typewriter with 4 letters (D, A, E, N) as a logic machine. (A "small logic", a "small language")

"Propositional Calculus" ... Sections 8 to 18.

The usual stuff. Starts with negation and disjunction. Introduces implication as a derived operation. Mentions Polish notation in passing.

11, "Language as an Algebra", begins putting an algebraic spin on it. "Negation and disjunction are in effect operations on the set of sentences of the propositional calculus". There is a "slight abuse of notation" here though.

12, "Concatenation", is trying to deal with the fact that propositions are strings. Free semigroups.

13, "Theorem schemata", deals with substitution.

14, "Formal proofs."

15, "Entailment" returns to an algebraic view, ordering the elements of the algebra by derivability. Then 16 deals with: if two statements are interderivable then they are logically equivalent.

17 introduces conjunction as another derived operation. 18 discusses algebraic identities; where statements are true for any assignment.

"Boolean algebra" ... 19 to 25

19 Equivalence classes. If E is a congruence relation w.r.t the algebraic structure of S, then S/E inherits the algebraic structure of S. If S is the set of propositional sentences and E the "equivalent" relation, we can talk of elements of S/E having relations like S (like equality) and we go towards Boolean algebra. We can find some identities, and lo and behold characterize the algebra with them.

20, "Interpretations".

21, "Consistency and Boolean algebra". The set of all propositions (of the propositional calculus) is a non-trivial Boolean algebra. Therefore that calculus is consistent.

22, "Duality and Commutivity". A Boolean algebra is a lattice. "And" and "or" can be interchanged (just turns the lattice upside-down). There are actually four ways to "quaternality": a proposition can be taken to (a) itself (b) its complement (c) its dual (d) its contradual.

23 to 34, I skipped ahead and would still need to gloss these.

Logic via Algebra ... 35 to 39

Have read up to "pre-Boolean algebras". Just before the "punchline" I think.

Then I skipped ahead again, to lattices.

Lattices and Infinite operations... 40 to 42

The short chapter on lattices. Very interesting thing there, page 96.

"Other" logics, like intuitionistic logic, modal logic, many-valued logic, can be seen as alterations on the lattice (if viewing the boolean algebra as a lattice):

Lattices of intuitionistic logic are obtained by the theory of Boolean algebras by dropping conditions, while the lattices of modal logic are obtained by by adding conditions.

And many-valued logic is some twist I don't quite understand yet.

Monadic Predicate Calculus ... 43 to 52

There's a good quote in "Monadic predicate logic", Section 43, p. 107, about how propositions are like "sackfuls of truth" and the propositional calculus is about tossing these sacks around without ever looking inside the sacks; it is only with predicate logic (that is, first-order logic or FOL) that we consider the contents of the sacks (and the "structural relations among them") having any bearing on their truth value.

(And I would add, it is this content that we need a term language for, to extend the propositional calculus with, to obtain the predicate calculus.)

An Algebraic Introduction to Mathematical Logic

It's a bit heavy. I can grasp the propositional logic part. When it gets to first-order logic, I'm still struggling with that.

Useful preliminaries: Universal algebra, Free algebra, Variety of algebras, Relatively free algebra.

Then they show how a propositional calculus (i.e. a propositional logic with a calculus (rules for deriving)) can be captured in an algebra, which they call propositional algebra. (Chapter II, page 11).

They show that propositional algebra is a kind of boolean algebra(?).

They then go on to tackle first-order logic, which seems to become deeper.

A Formalization of Set Theory without Variables

If "An Algebraic Introduction to Mathematical Logic" is "a bit heavy" then I guess it's fair to say this one is "super heavy". I came across it on the the Wikipedia page for Relation Algebra.

Origins of the Calculus of Binary Relations

I found this interesting but didn't write many coherent notes, just highlighted some paragraphs. The one coherent note I left is a paraphrase of one thing in it:

The question of wether RA completely axiomatizes the equational theory of binary relations was answered in the negative by Lyndon in 1950, but given that the equations that it cannot capture are complicated to describe, one might interpret this as a technicality only, and consider RA to be "pragmatically" complete.

R.C. Lyndon. The representation of relational algebras. Ann. of Math., Ser 2, 51:707–729, 1950.

I would be really interested in understanding the structure of the equations it cannot capture.

The Algebra of Logic Tradition (Stanford Encyclopedia of Philosophy)

.

logic - What are differences between first order structures and algebraic structures - Mathematics Stack Exchange

.

CS 353: Algebraic Logic: Class Notes (Vaughn Pratt)

.