Wednesday, February 2, 2011

Propositional logic

As a hobby, from time to time I am thinking about the best way to think about logic, knowing full well that much of what I am thinking about duplicates what other people have done, but since it's just a hobby, that's fine. One of my convictions is that logic should be developed in such a way that it works not only with simple artificial languages like First Order Logic as the target language. Logic concerns truthbearers, and it should be developed in a way that is agnostic as what the truthbearers are—they might be sentences of First Order Logic, sentences of English or propositions.

More generally than truthbearers, logic concerns schemata. Schemata when operated on by sufficiently many quantifiers yield propositions (I think of a name as a kind of quantifier). I don't yet have a clear picture of how I want to characterize schemata.

So what do I have? Well, I have a pretty good picture of how to start thinking about propositional logic—the logic of truthbearers. Let B be the collection of all truthbearers. Let V={T,F} be the truth values. Let V0 be any set with only one element. Let Vn be the set of all n-tuples of members of V; let Bn be the set of all n-tuples of members of B. Let On be all functions from Vn to V. Let O be the union of all the sets On. We call the members of O "truth-tables". Now, for any truth-table f in On, there is an (n+1)-ary relation Cf on B, and we read Cf(b1,...,bn,bn+1) "as bn+1 f-connects b1,...,bn". If there exists b1,...,bn such that bn+1 f-connects b1,...,bn, then we say that bn+1's main connective is f. A nice axiom to have, but one that I would ultimately want to do without, is:

  1. Unique connective parseability: Each truthbearer has at most one main connective.
A related axiom, also too strong in my opinion, is:
  1. Unique component parseability: For any truthbearer b and any truth-table f, there is at most one sequence of truthbearers that b f-connects.
If we're really lucky, we have:
  1. Unique parseability: Both unique connective parseability and unique component parseability hold.
Many artificial languages, but certainly not English, satisfy:
  1. Unique compositionality: For any truth-table f and any sequence b1,...,bn of truthbearers, there is at most one truthbearer that f-connects the sequence.
For instance, in English, there is more than one way of expressing a conjunction, and hence unique compositionality fails. Say that b* is a direct subtruthbearer of b provided that b f-connects some sequence containing b*. Say that b* is a subtruthbearer of b if and only if there is a finite chain of direct subtruthbearer relations from b* to b. Many nice collections of truthbearers will satisfy:
  1. Well-foundedness: The subtruthbearer relation is a partial well-ordering (i.e., there are no infinite decreasing chains of subtruthbearers).
We can say that a truthbearer is atomic provided it has no subtruthbearers.

If f is a truth-table in On, say that the system is f-compositional provided that for any sequence b1,...,bn there is a truthbearer bn+1 that f-connects the sequence. For instance, English is negation, finite-conjunction and finite-disjunction compositional, as can be seen by the fact that for any sentence, we can form a negation of it by prefixing with "It is not the case that", for any finite collection of sentences we can form a conjunction by prefixing with "All of the following are the case" and then stringing the sentences with appropriate punctuation, and a disjunction by prefixing with "At least one of the following is the case".

For a proof theory, we specify bunches of rules, such as standard introduction and elimination rules. We specify them using f-connectedness. For instance, if f is binary conjunction (i.e., the function that takes (T,T) to T and all other pairs in V2 to F), then a reasonable rule says that at if at some point in a proof you have b1 and b2 accessible, then you may write down anything that f-connects them.

That's the start, on the side of syntax. The start on the side of semantics is straightforward. A truth assignment is a function v from truthbearers to V such that whenever bn+1 f-connects b1,...,bn, then v(bn+1)=f(v(b1),...,v(bn)) (if n=0 then v(b1) is equal to the value of v at the unique point of V0).

One can now easily prove this: If well-foundedness and unique parseability hold, then any function from atomic truthbearers to V can be uniquely extended to a truth assignment.

But in the end I'd like to work with logics that aren't uniquely parseable. For instance, English probably isn't uniquely parseable. "The sky is blue and the sea is blue and snow is white" can be parsed as a ternary conjunction, but it may also be parsed as a binary conjunction of "The sky is blue and the sea is blue" and "Snow is white". A nice replacement semantic property is:

  1. Weak (strong) truth-definability: Any function from atomic truthbearers to V can be (uniquely) extended to a truth assignment.
There are all sorts of other cool properties one can define. The payoff of all of that is that one will get to do logic with natural languages or directly at the level of propositions.

Like I said, I know a lot of this stuff has been worked out by real logicians (I think someone once even told me what real logicians call what I called "unique parseability"). But just as it's fun to build a telescope focuser yourself rather than buying one online, so too it's fun to develop logic rather than getting one from the library, as long as one is only doing this as a hobby.

at

3 comments:

  1. Alexander R PrussFebruary 3, 2011 at 8:36 AM

    Here's a fun language, inspired by a brief remark by Ramsey. The language is like standard first order logic, except negation is represented differently. We "express negation not by inserting a word 'not', but by writing what we negate upside down." A cool thing about this language is that there is no way to represent intuitionist logic. We have unique component parseability, but lack unique connective pareseability. We lack well-foundedness, because each sentence negation-connects its upside-down version, and so there are cycles of direct subtruthbearers. In particular, there are no atomic truthbearers in my sense.

    Nonetheless, this language satisfies a nice truth-definability property. Say that a truthbearer is a literal provided that for no f other than negation does it f-connect any truthbearers. Then for any maximal set S of literals with the property that no pair of literals in the set negation-connects another, any function from S to V uniquely extends to a truth assignment on the system as a whole.

    This suggests the following definition. A subbasis B for the system is a collection of truthbearers with the property that any function from B to V extends to a truth assignment on the system as a whole. A basis is a subbasis where the extension is unique.

    There are systems with no subbases. For instance, consider the system where each truthbearer counts as negation-connecting itself. :-)

    Then my weak and strong truth-definability properties should probably be respectively replaced by the claims that the system contains a subbasis or a basis.

    Here is a curious bias I suffer from. I am very happy to give logic extreme flexibility on the side of the system of truthbearers. But I am unhappy to depart from classical logic on the side of the rules of inference.

    ReplyDelete
  2. Alexander R PrussFebruary 3, 2011 at 9:05 AM

    This comment has been removed by the author.

    ReplyDelete
  3. Alexander R PrussFebruary 3, 2011 at 9:06 AM

    I forgot to define consequence. That's straightforward: Q is a consequence of a collection C of truthbearers iff every truth assignment that assigns T to every member of C assigns T to Q.

    A system is connective-inconsistent iff it has no truth assignment (this holds iff the empty collection is not a subbasis). In a connective-inconsistent system, everything is a consequence of everything.

    Here's another system where one lacks all the parseability conditions. Let the truthbearers be Lewisian propositions, i.e., sets of worlds. Then we say that U3 and-connects U1 and U2 iff U3 is the intersection of U1 and U2, and U2 not-connects U1 iff U2 is the complement of U1, and so on. Since most sets of worlds are the intersections of many, many pairs and all sets of worlds are complements of their complements, we don't have either parseability condition. We don't have well-foundedness.

    Q is a consequence of P1,...,Pn iff the intersection of P1,...,Pn is a subset of Q.

    There are subbases. For instance, if w is any world, then {{w}} is a subbasis--it contains one Lewisian proposition which says that w is actual. Off-hand, I don't know if there is a basis, and since I need to go to class, I can't sit and think about it.

    I'd like to have some notion generalizing that of a basis on which {{w}:w is a world} will qualify, but as I said, I need to go to class.

    ReplyDelete