nortexoid

Bonjour

2008-01-11T12:54:00.000-08:00

I barely post to this blog anymore, mostly because I'm busier than my lazy neighbor, and also because blogger lacks native LaTeX support. I'm blowin' this pop stand! Wordpress has become my new girlfriend, and I'm going there soon. Probably very soon too since I'll just stick with the default layout or some template, and go from there. What's gonna happen here? I'm gonna blow up this blog.

The new address will be almost the same, but mostly different: nortexoid.wordpress.com.

(This is what happens when you procrastinate as badly as my shady neighbor.)

Modal consequence is STRONG!

2007-11-15T11:35:00.000-08:00

It has been shown that the second-order consequence relation of a second-order language L1 with a single binary predicate constant and unary predicate variables is reducible to the modal consequence relation of a standard propositional modal language L2. One in effect defines a translation t from L1 to L2 and shows that for any formula A of L1 there is a modal formula t(A) of L2 such that

T |= A iff {B} ∪ t(T) |= t(A)

where t(T) = {t(C): C ∈ T} and B is a required fixed modal formula of L2. (It is required in case T is empty. In this very special case modal consequence is recursive, whereas second-order consequence is not.) L1 is quite strong.

I was introduced some time back to what is sometimes called in the literature "definability theory" or "correspondence theory" in the form of guarded (or bounded) fragments of first-order logic, but didn't actually appreciate what was going on until now. (Definability theory studies the relationship between the definability of formulas in one language in another language, e.g. the first-order definability of some class of modal formulas.) I accidentally came across some of this stuff investigating the relationship between monadic operators and generalized quantifiers, and relational structures and (modal) algebras. There's a ton of interesting definability stuff published by van Benthem, Thomason and a few others.

I'll report back with interesting details as I uncover them. So next year or something.

Lactose intolerance

2007-11-10T10:45:00.000-08:00

Somebody once asked me to demonstrate a first-order sentence that is not true in any recursive model. When I offered "Px & ~Px" they got angry and stormed away.

The consistency of pea soup.

2007-11-08T10:26:00.000-08:00

I take it that consistency is important for the following reasons:

(1) to determine triviality
(2) to determine satisfiability
(3) to determine existence

Consider (1) and some theory T that is trivial wrt some language L--i.e. every formula of L is in T. (I'm using 'L' to denote a set of formulas and not a vocabulary. So there are some implicit formation rules on the vocabulary of L under which L is closed.) This might not be at all interesting depending on L. Let T be the theorems of classical logic and L precisely the formulas provable in some complete/consistent deductive system. (One may recursively specify the formation rules on the vocabulary of L to yield precisely the theorems as the wffs of L.) Then T is trivial wrt L. But that doesn't mean that T is uninteresting for precisely that reason. (We could just as well have let L be a truth constant, assuming it is in the language of T.) The choice of L is absolutely crucial. Triviality of a theory T (wrt to a language L) doesn't entail that T is "uninteresting" in some relevant sense of 'uninteresting'.

One might think that in order for triviality results to be interesting the language L has to be interesting and T has to be generated from some interesting deductive system S. Both S and L will likely (perhaps "necessarily") have intended interpretations in order to count as interesting. Then if T is trivial wrt to L, S doesn't given a proper account of the inferences we wish to capture--it overgenerates them.

But is that necessarily a bad thing? Natural languages such as English have their own truth predicates and are hence inconsistent. (I think it makes sense to talk about consistency wrt to natural languages.) But this doesn't make it "deductively worthless". In particular, when people wish to prove some metatheorem p in an English metalanguage, they do not proceed as follows.

Assume q. Then r, so s, whence t...
Hence v follows from u. By hypothesis...
... [impressive smoke screen] ...
We have T (T = the liar sentence) is true iff it is false. So if T is true then T is false and if T is false then T is true. By classical logic we have T and ~T. Thus T v p. By disjunctive syllogism, p. QED.

People are not computers, so where a computer might generate fallacious proofs given an inconsistent theory T, humans might (likely will) not do so without notice. This does not come to an endorsement of inconsistency. It is a denial that inconsistency is necessaril bad.

(One could argue against proofs of the above form by stating that mathematical reasoning is really relevant, or something. But one still gets relevant paradoxes in a suitably rich metalanguage.)

Well how about (2)? If the language is sufficiently strong, e.g. has branching quantifiers or is second-order or the right sort of infinitary language, then consistency might not entail satisfiability. Basically the result holds for any of the usual non-compact languages. Let L be a usual second order language and S a sentence true only on finite sets (e.g. it says "Every complete order-relation has a last element"). Then form the set

A = {S, Ex1x2~x1=x2, Ex1x2x3~(x1=x2 v x1=3 v x2=x3), ...}.

Then A is finintely satisfiable (i.e. every finite subset is satisfiable) and hence consistent, yet A is not satisfiable. So consistency itself doesn't quite give us enough. We need L to have some special model-theoretic properties.

Now even if T is consistent and L has the right properties, it doesn't tell us that T has a model of the right sort--e.g. its intended model if it is thought to have one. It just tells us it has some model or other. If we determined the consistency of ZFC that would not tell us that ZFC has its intended model (whatever that is). So again, consistency doesn't tell us much in that respect, but I suppose it was never meant to.

This post is getting way too huge to get into (3) but there is a view (that some people, famous people (e.g. Hilbert), held) that the consistency of T tells us that whatever objects T describes exist. Of course this view must presume that T is consistent wrt to an appropriate language and deductive system, because trivially T is consistent wrt to some language L' that is a superset of the language L of T. (Of course S might not generate T wrt L' though it does wrt L. But some other system S' might generate T, and trivially some non-recursive S* will.) But this view seems odd if T is not categorical. And even if T is categorical it still seems weird, because it posits the existence of *anything* that satisfies the axioms. The imagination boggles.

I welcome strong opinions of opposition (in the form of blog comments only), because surely most reading this (if that is anyone) will have some.

Electronic resources

2007-10-31T10:11:00.000-07:00

Quick quip: Ever notice that database software at schools may vary for the same databases, and that some of them severely suck and others are quite good? At one school, search entries in the Philosopher's Index would provide a direct link to the source online, if it was so available. At another school, it just gives you the reference and you have to navigate for an additional 5min. or so determining whether or not you can get electronic access. If your fingers and thumbs are very thick, it might take up to 10 to 25min locating the article online. If you have no fingers or thumbs, it could take upwards of 2hrs (two hours!!).

You're fine, how am I?

2007-10-28T11:59:00.000-07:00

I can admit doing x by saying 'I admit doing x'. I can propose that we go to the concert by saying 'I propose that we go to the concert '. But perlocutionary acts resist this mould. In uttering 'You're fine , how am I ?', I may be amusing you; but I couldn't do the same thing by saying 'I amuse you that you're fine, how am I?'. If you were a fastidious and proud cook I might irritate you by saying 'Please pass the salt', but I could not do the same thing (of a perlocutionary sort) by saying 'I irritate you to please pass the salt'. [Alston, Meaning and Use, The Philosophical Quarterly, Vol. 13.]

Lost and found.

2007-10-14T16:06:00.000-07:00

I heard this one long ago but forgot where it came from. I just found it while reading Kneale and Kneale. It's a classic, and tattooed on my throat.

"Even the crows on the roofs caw about the nature of conditionals."

How they do!

Baggy tights

2007-09-10T21:36:00.000-07:00

Hodges' "An Editor Recalls Some Hopeless Papers" is still one of the funniest reads in logic. Even "A Shorter Model Theory" has hilarious moments. Somebody give that man an award.

School starts I think now. They didn't tell us until a week ago. I'm still in Taiwan but leaving in two days to go home (Ontario Canada) for a visit for about a week, and then off to Scotland (St. Andrews). There's a seminar on algebraic logic being offered, and another on parametric conservative extensions of liberally minded orangutans. I look forward to them. I look forward to the future. (It is impossible to look forward to the past.) I look forward to you.

Downward Lowenheim Skolem theorems

2007-07-05T01:12:00.000-07:00

I'm wondering if anybody knows a proof of the downward Lowenheim-Skolem thereom of the following kind. Let M be an uncountable model. Let A_1,..., be an enumeration of the Σ_1 sentences of the language L of M. Set L_0=L and M_0=M. Suppose M_n has been defined. Let

M_{n+1} = M_n ∪ {c_1^M = a_1,...,c_m^M = a_m} if M_n |= A_n[b_1,...,b_n], a_1,...,a_m are all the elements among the b_i that are unnamed by closed terms in the language L_n, and the c_i are all new to L_n;
M_n otherwise.

Then let M' = ∪_{i<ω}M_i. Clearly M ≡ M'|L, since M' just has more named elements that are not names of L. Moreover, M' |= A_i(x_1,...,x_n) iff M' |= B(t_1,...,t_n) for A_i = ∃x_1,...,x_nB(x_1,...,x_n), and each t_j a closed term in L' = ∪_{k<ω}L_k.

Obtain M* from M' by deleting from M' all the elements that are not named by some closed term of L'. We can show that M* ≡ M', whence M*|L ≡ M.

Compactness

2007-07-01T04:13:00.000-07:00

Hodges has a proof of compactness for first-order languages in "A Shorter Model Theory" that can be simplified by proving that the set he constructs is maximal consistent, rather than a Hintikka set (which it also is). (He already proves that it's consistent, so it's just a matter of proving maximality instead of a lemma concerning Hintikka sets and then verifying the existential condition for Hintikka sets, which he does. This alternative proof requires validating the universal condition for Hintikka sets if one wishes to prove that T' (below) is indeed a Hintikka set. Hodges lemma allows him to avoid this.)

(I apologize in advance for the ugly notation. I should get/learn LaTeX to HTML (or whatever they call it) but I'm too lazy.)

Let T be a first-order theory in a language L such that every finite subset of T has a model. Let c_1,... be an enumeration of constants new to L and let L' be obtained from L by adding the c_i to L. Let A_1,... be an enumeration of the sentences of L. We construct a maximal consistent (Hintikka) set T' in L' such that T is a subset of T'. Let T_0 = T and suppose that T_n has been defined. Then

T_{n+1} = {T_n ∪ {A_n} if every finite subset of this set has a model, and T_n otherwise.

If at the jth stage of the construction A_j has the form ExB(x) and every finite subset of T_j ∪ {A_j} has a model, then set T'_{j+1} = T_{j+1} ∪ {B(c_i)} for c_i the first constant new to this set. Otherwise T'_{j+1} = T_{j+1}. Let T' = ∪_{i<\omega}T'_i.

We first note that if T_i ∪ {A} is such that not all finite subsets of it have a model, then for all k > i,

(1) T_k ∪ {A} is such that not every finite subset of it has a model,

since T_i ⊆ T_k. Suppose A_i is not in T'. Then T_i ∪ {A_i} is such that not every finite subset of it has a model. (That is the only place in the construction A_i could be added.) But then there exists a finite W ⊆ T_i such that

(2) W ∪ {A_i} |= ~A_i.

Let ~A_i = A_j, and suppose for reductio that T_j ∪ {A_j} is such that not every finite subset of it has a model. (This is the only place in the construction where A_j could enter T', so it is equivalent to saying that A_j is not in T'.) Then there exists a finite W* ⊆ T_j such that

(3) W* ∪ {A_j} |= ~A_j.

By construction, either W ⊆ W* or W* ⊆ W. It doesn't matter which we assume since they both end up at the same conclusion in an analogous way. Assume the former. Then by (1), (2), and (3) (recalling ~A_j = ~~A_i), both W* ∪ {A_i} |= ~A_i & ~~A_i and W* ∪ {~A_i} |= ~A_i & ~~A_i. Whence W* |= ~A_i & ~~A_i, contra the supposition that every finite subset of T_j has a model. This concludes the proof of maximality. (Consistency is easier and Hodges already proves it.)

Technically, one should verify that every finite subset of T'_i has a model when every finite subset of T_i ∪ {A_i} has a model and A_i is existential. It seems too obvious to mention since c_i is new to T_i ∪ {A_i}, and we're lazy. It's Sunday, remember?

To see that T' has a model, we see that T' |= A iff A ∈ T' by maximality. Thus if T' has no model then T' |= A and T' |= ~A. Whence A, ~A ∈ T' contra the consistency of T'. Hence T &subeq; T' has a model.

Is there a faster *purely model-theoretic* way to prove compactness?