User andrey bovykin - MathOverflow

Answer by andrey bovykin for undecidable sentences of first-order arithmetic whose truth values are unknown

2012-01-31T02:17:58Z

What you want is called [first-order] Arithmetical Splitting. I have spoken and written a lot about it in the last few years. Send me a message and I can show you some drafts about the current state of this most important topic.

Yes, we should not be able to form any preference, like in the case of PH, where it is clear that PH is better than \neg \PH.

Answer by andrey bovykin for Proofs of Gödel's theorem

2011-03-29T10:37:55Z

Dear Sergei and John. There is just too much to say. If I give you 3 pointers - it will not mean that these are good starting points or that these are the most important developments.

The Jones polynomial is from JSL 43 (1978), no 2. but me and De Smet recently enhanced the polynomial a bit (shortened it by 7 symbols)... :)

Friedman's book is on his homepage. The introduction is quite readable, and contains a long list of unprovable statements.

You can also have a look at my "Brief introduction" on my homepage, although I am a bit ashamed of that naive paper of mine written 6 years ago. I am now writing a long better piece, with all motivations and explanations, and the Arithmetical Splitting story.... but it will take some time.

Answer by andrey bovykin for Proofs of Gödel's theorem

2011-03-29T10:19:44Z

This is a comment on a post by Andreas Blass here.

I have not read Kripke's statement, apart from Andreas's sketch above, but it sounds familiar from elsewhere, so let me comment a bit on the family of results and the many discussions about a family of unprovable statements of the form "for every n there is a finite set that approximates a model of your theory T to the degree n" (where "to the degree n" is specified separately each time).

The first such statement found in print belongs to Paris and Harrington (see the original article in the Handbook for Mathematical Logic), and is sometimes referred to as "half-baked Paris-Harrington Principle". It says "for every n there exists a finite sequence of points that acts as diagonal indiscernibles for the first n Delta_0 formulas", where "diagonal indiscernibility" or "Paris indiscernibility" is the condition that for any c_i_0 < c_i_1< ... < c_i_k < c_j_1 < ... < c_j_k in the sequence, we have: for every parameter a < c_i_0, the following holds:

\forall x_1 < c_i_1 \exists x_2 < c_i_2.... \phi(a, x_1, x_2... x_k) < -- > \forall x_1 < c_j_1 \exists x_2 < c_j_2... \phi(a, x_1, x_2, ...x_k).

Since that time statements of this form became routine intermediate steps in unprovability proofs. For example Shelah tried to modify this statement and came up with something that should be of strength Pi_1^1-CA_0 (see "On logical sentences in PA").

The same idea is the core of most of Harvey Friedman's proofs in the last 25 years, but at higher levels of sophistication. For example for Proposition C, Friedman has 9 intermediate statements of this shape ("the Transmutations"), where the notion of indiscernibility changes at each step. And for Proposition B you need perhaps only 6 transmutations.

When I was entering the subject in 2002 -- 2003, I wrote a naive article draft on half-baked PH and beyond, tinkering and trying to generalize. But then I realized that this topic is widely developed and discussed in the unprovability community, so since this piece already entered the unprovability community's knowledge pot long before me, perhaps none of it is publishable.

One more thought: there are two or three ways of dressing unprovability proofs. Paris's original dressing was via cuts in models of arithmetic, but after Harrington's simplification of n-densities, they wrote the proof for the Handbook in the finitistic way, via half-baked Paris-Harrington + compactness as I sketched above. After that Paris and his co-workers returned to thinking in terms of cuts in models of arithmetic. Both ways of dressing the proof are equally good, but each person usually chooses one.

Answer by andrey bovykin for Proofs of Gödel's theorem

2011-03-25T18:30:17Z

Apart from usual proofs with diagonalization, have a look at model-theoretic proofs (Kotlarski's proof, Kreisel's left-branch proof, etc..), then there are some other proofs that formalize paradoxes (Kikuchi's, Boolos's, etc... there are about a dozen, most of them mentioned in Kotlarski's book).

If you don't want full generality ("for every rec. ax. theory T") then of course almost every proof in modern Unprovability Theory does not use any self-reference (you build a model of your theory by hands, using some unprovable combinatorial principle). Have a look at some easy recent accessible model-theoretic proofs of the Paris-Harrington Principle.

At the low end of the consistency strength spectrum (ISigma_n, PA, ATR_0), for theories that already have good classifications of their provably recursive functions, PH and other unprovable statements can also be proved unprovable using ordinal analysis (e.g. Ketonen-Solovay style), without using diagonalization tricks.

For higher ends of the strength spectrum (SMAH, SRP, etc), H. Friedman's highly technical results also don't use any diagonalization. This is a huge powerful machinery, and much new research is happening there.

MDRP theory gives interesting examples: have a look at the Jones polynomial expression: you can indeed substitute numbers into it and hit every consistency statement by its instances. There are similar ones for n-consistency for each n.

There is much more to say: this is a big subject, with huge bibliography. And, yes, much of the body of results in the subject is unpublished. I can give more pointers if necessary.

Comment by andrey bovykin

2011-03-29T15:50:41Z

Instead of downloading my paper with Kaye that is a survey of some parts of my PhD thesis, it is better to download the actual PhD thesis (written 11 years ago) from logic.pdmi.ras.ru/~andrey/research.html As far as I know, nothing new about order-types of models of arithmetic has been proved since then. (Well, there is another article of mine "Resplendent models and definability with an oracle" but this is about a connection between the order-type of models of arithmetic and linear orders that are interpreted in that model, so not exactly relevant to your question).

Comment by andrey bovykin

2011-03-29T11:25:08Z

Smorynski's article in the Handbook for Mathematical Logic is still relevant (at least you can read Kreisel's left-branch proof in there)... Kotlarski's book is still unpublished. As far as I know, Konrad Zdanowski and Zosia Adamowicz are working to have it published asap.