Skip to content

The Rosser trick and other interesting statements

Barkley Rosser Sr. was an impressive mathematician who made seminal contributions to many diverse areas. There is a Rosser sentence in logic, a Rosser sieve in number theory, and a Rosser matrix in numerical analysis. There are not too many others who have made key contributions to such different areas.

Today I want to talk about “unusual” diagonal statements. One is mathematically important and two are just interesting, I hope.

I once spent the summer at University of Wisconsin, Madison as a guest of the Computer Science Department. Rich DeMillo was also there at the same time, and we shared an office—Rosser’s office. Rosser was away for the summer and we had the honor of using his office. There were great vibes that made us want to work on problems in logic, number theory, and numerical analysis. We actually only got to the former two, as we did not know enough to work on numerical analysis. The summer was great fun, and a great honor to use Rosser’s office, which came with a beautiful view of Lake Mendota.

I wish I could say the vibes helped us to prove some terrific theorem, but alas we did not. Well the short version is we did prove a pretty neat theorem in complexity theory. The issue was that we eventually discovered the theorem had been previously proved, and in exactly the same way that we did. Oh well.

Let’s turn now to diagonal statements (DS). The motivations are to try to get stronger results, to find more “relaxed” ways to employ diagonalization, and to recognize statements that are not diagonal after all. Note that we have previously talked about avoiding diagonalization here.

Examples of DS and Non-DS

I have listed them by who created them, or told them to me, or whom I wish to give credit.

${\bullet }$ Rosser: When Kurt Gödel proved his famous Incompleteness Theorem, in 1931, he needed to assume that Peano Arithmetic was more than consistent. He needed what is called ${\omega}$-consistency, which is stronger than regular consistency. A theory is consistent if there is no sentence ${S}$ such that the theory proves both ${S}$ and ${\neg S}$. A theory like Peano is ${\omega}$-inconsistent provided for some formula ${A(x)}$ the theory can prove all these:

$\displaystyle A(0),A(1),\dots$

and it can also prove ${\exists x \neg A(x)}$. It is ${\omega}$-consistent if it is not ${\omega}$-inconsistent.

I have seen summaries of Gödel’s Incompleteness Theorem that either ignore this point or misstate that Gödel could prove his theorem based only the assumption of consistency. But that is not true. Gödel’s achievement is monumental, but he did need more than consistency: he needed ${\omega}$-consistency.

Suppose we try to prove Gödel’s theorem this way: we plan on using the fact that the Halting problem is undecidable to show that Peano Arithmetic cannot be complete and consistent. Consider a machine ${M}$ that we would like to discover whether or not it halts on the blank tape. We can clearly create an arithmetic sentence ${H(t)}$ which means that ${M}$ halts in at most ${t}$ steps. We do the following in parallel:

1. We start running ${M}$ for ${1,2,\dots}$ steps.
2. We start searching for a proof of ${\forall t \neg H(t)}$.

If we discover that the machine halts, then we are done. If we discover that we can prove ${\forall t \neg H(t)}$, then we are also done. But what if the latter is false: there is no proof of this sentence. Then by completeness it must be the case that Peano proves ${\neg \forall t \neg H(t)}$. This is the same as ${\exists t H(t)}$. This is no contradiction with consistency, but is a contradiction with ${\omega}$-consistency.

I find it quite interesting that the great Gödel could “only” prove:

If Peano Arithmetic is ${\omega}$-consistent, then it is incomplete.

He could not prove the theorem that he really wanted:

If Peano Arithmetic is consistent, then it is incomplete.

There is a lesson here for all, I believe. Sometimes when you are stuck in proving some theorem, proving a slightly weaker theorem is fine. Gödel’s brilliant work was just as surprising with the stronger assumption of ${\omega}$-consistency. Plus it allowed others the opportunity to improve his theorem. Which is precisely what Rosser did in 1936 when he improved Gödel’s Theorem so it needed only regular consistency. Recall Gödels theorem is based on this DS:

This sentence is not provable.

Rosser’s DS is a more complex sentence,

If this sentence is provable, there is a shorter proof of its negation.

This is often called Rosser’s Trick, which I think underplays the importance of his DS. But that is just my opinion.

${\bullet }$ Lipton: Not me, but my daughter Jen Lipton O’Connor. I have discussed it before here, but will include it again to save you from having to click. Another free service of GLL.

Jennifer may have invented, when she was about ten years old, a novel type of DS. On a sunny day in the month of May, I was driving her and her older sister, Andrea, to the mall. Andrea was twelve at the time. Jennifer asked if I could take her to Six Flags, a great amusement park, sometime over the summer. Andrea, who was about to go away to camp for the whole summer, immediately complained. Andrea said that it would not be fair if we went when she was away. Andrea loved roller-coasters, and still does, so she really wanted to go too. I answered something non-committal to both of them. But Andrea was clearly upset. Jennifer finally turned to Andrea and said,

Andrea, would it be okay if we went, but we did not tell you?

I almost lost control of the car laughing. Andrea, who was never at a loss for words, just looked at her sister.

${\bullet }$ Hasselblatt: In this March 2011 Math Monthly issue Boris Hasselblatt is a co-author with Keith Burns of an article on dynamical systems of the type I have just discussed. One of the neat features of this journal is authors give short bio’s at the end of their articles. Usually they list their home institution, their main math areas of research, and usually some fun thing about themselves. Hobbies are very popular. Hasselblatt ends his with this DS:

He dedicates this article to all those who do not dedicate their article to themselves.

${\bullet}$ Unknown: Ken Regan is unable to locate correspondence he remembers with Uwe Schöning that took place over twenty years ago in which a diagonal theme came up. It was a quotation by a German author, in German, along the lines of:

The only book that deserves to be banned is the index of all banned books.

This is not a DS—unlike the article-dedication example it can be resolved without contradiction or paradox. Namely, the Index can list itself as its only member. Then it deservedly bans itself.

Open Problems

Ken asks: can we prove Gödel’s Theorem using only consistency and avoid using Rosser’s trick? This is related to an earlier discussion about diagonal arguments here.

Are there some other favorite diagonal statements that you would like to share with the rest of us?

Advertisements
24 Comments leave one →
1. March 4, 2011 7:21 pm

A couple which I am fond of: “It is known that this sentence is false” and “It is false that this sentence is known”.

2. Anonymous Rex permalink
March 4, 2011 7:26 pm

Does the proof of Godel’s theorem using Tarski’s theorem (regarding the undefinability of truth) avoid the mention of omega-consistency?

3. Anonymous permalink
March 4, 2011 8:55 pm

One can avoid using omega-consistency and Rosser’s trick at the same time if the goal is to show that there is true sentence that is not provable. Rosser’s trick is only necessary if one wants to show that the negation (which is a false sentence) is also not provable, and I have doubts if he had even tried to do it, from philosophy of mathematics point of view (at least of that time) a theory that can prove a false sentence is not interesting, therefore he probably didn’t care about using omega-consistency, in which case implying that he tried and failed would be incorrect.

4. March 4, 2011 10:36 pm

“… can we prove Goedel’s Theorem using only consistency and avoid using Rosser’s trick?”

Apparently we cannot.

Reason: Although Goedel explicitly assumed – and believed – that PA (as also ZF and other formal systems that can ‘contain’ Arithmetic) is omega-consistent, Rosser seemed to have assumed this implicitly by presuming that Aristotle’s particularisation holds over the structure of the natural numbers.

The two are equivalent, since it can be shown that if PA is consistent, then it is omega-consistent if, and only if, Aristotle’s particularisation holds over the structure of the natural numbers.

The detailed arguments for this and Rosser’s implicit assumption are given in:

http://alixcomsi.com/25_Aristotlean_particularisation_III_Rosser_Update.pdf

To clarify:

1. Aristotle’s particularisation:

This holds that from an assertion such as:

‘It is not the case that, for any given n, the proposition P*(n) does not hold’

usually denoted symbolically by ‘~(Ax)~P*(x)’, we may always validly infer in the classical, Aristotlean, logic of predicates that:

‘There exists an unspecified n such that P*(n) holds’

usually denoted symbolically by ‘(Ex)P*(x)’.

2. The significance of Aristotle’s particularisation for the first-order predicate calculus:

We note that in a formal language the formula ‘[(Ex)P(x)]’ is an abbreviation for the formula ‘[~(Ax)~P(x)]’. The commonly accepted interpretation of this formula (and a fundamental tenet of classical logic unrestrictedly adopted as intuitively obvious by standard literature that seeks to build upon the formal first-order predicate calculus) tacitly appeals to Aristotlean particularisation.

However, L. E. J. Brouwer had noted in his seminal 1908 paper on the unreliability of logical principles that such interpretation is ambiguous if interpretation is intended over an infinite domain. He essentially argued that, even supposing the formula ‘[P(x)]’ of a formal Arithmetical language interprets as an arithmetical relation denoted by ‘P*(x)’, and the formula ‘[~(Ax)~P(x)]’ as the arithmetical proposition denoted by ‘~(Ax)~P*(x)’, the formula ‘[(Ex)P(x)]’ need not interpret as the arithmetical proposition denoted by the usual abbreviation ‘(Ex)P*(x)’; and that such postulation is invalid as a general logical principle in the absence of a means for constructing some putative object n for which the proposition P*(n) holds in the domain of the interpretation.

3. The significance of Aristotle’s particularisation for PA:

Possibly in order to avoid Brouwer-inspired intuitionistic objections to his reasoning, Goedel introduced the syntactic property of omega-consistency as an explicit assumption in his formal reasoning in his seminal 1931 paper on formally undecidable arithmetical propositions.

Goedel explained at some length (in his introduction, where he gave an informal proof of an undecidable arithmetical proposition using diagonalisation) that his reasons for introducing omega-consistency explicitly was to avoid appealing to the semantic concept of classical arithmetical truth in Aristotle’s logic of predicates (which presumes Aristotle’s particularisation).

However the two concepts are meta-mathematically equivalent in the sense that, if PA is consistent, then PA is omega-consistent if, and only if, Aristotle’s particularisation holds in any model of PA over the structure N of the natural numbers.

4. Aristotle’s particularisation in a contemporary context:

Now we may express Aristotle’s particularisation in a contemporary context as:

From an assertion such as:

‘It is not the case that, for any given x, a witness can provide evidence that P*(x) does not hold in N’

usually denoted symbolically by ‘~(Ax)~P*(x)’, we may always validly infer that:

‘There exists an unspecified n such that a witness can provide evidence that P*(n) holds in N’

usually denoted symbolically by ‘(Ex)P*(x)’.

Prima facie, Brouwer’s objection seems valid since Aristotle’s particularisation now does not appear to hold if we take the witness as deciding arithmetical issues on the basis of evidence provided by a Turing machine, since P*(x) may be a Halting-type of number-theoretic relation.

5. March 4, 2011 11:21 pm

It seems to be a time for DS clustering,http://blog.computationalcomplexity.org/2011/02/interesting-math-related-to-unexpected.html

6. March 4, 2011 11:38 pm

“This Statement Does Not Refer To Itself”

Apparently the familiar semantic and logical paradoxes commonly referred to as the paradoxes of ‘self-reference’ (even though not all of them involve self-reference, e.g., the paradox constructed by Yablo) involve – either implicitly or explicitly – quantification over an infinitude.

Where such quantification is not, or cannot be, explicitly defined in formal logical terms – eg. the classical expression of the Liar paradox as ‘This sentence is a lie’ – the paradoxes per se cannot be considered as posing serious linguistic or philosophical concerns.

Of course, it would be a matter of serious concern if the word ‘This’ in the English language sentences, ‘This statement does not refer to itself’ or ‘This sentence is a lie’, could be validly viewed as implicitly implying that:

(i) there is a constructive infinite enumeration of English language sentences;

(ii) to each of which a truth-value can be constructively assigned by the rules of a two-valued logic;

(iii) and in which ‘This’ refers uniquely to a particular sentence in the enumeration.

Apparently Goedel used the above perspective in his seminal 1931 paper on ‘undecidable’ arithmetical propositions:

(a) to show how the infinitude of formulas in a formally defined Peano Arithmetic P could be constructively enumerated and referenced uniquely by natural numbers;

(b) to show how P-provability values could be constructively assigned to P-formulas by the rules of a two-valued logic;

(c) and to construct a P-formula which interprets as an arithmetical proposition that could be viewed as expressing the sentence ‘This P-sentence is P-unprovable’ without inviting a ‘Liar’ type of contradiction.

The practical significance of the semantic and logical paradoxes is, of course, that they illustrate the absurd extent to which languages of common discourse need to tolerate ambiguity; both for ease of expression and for practical – even if not theoretically unambiguous and effective – communication in non-critical cases amongst intelligences capable of a lingua franca.

Such absurdity is highlighted by the universal appreciation of Charles Dickens’ Mr. Bumble’s retort that “The law is an ass”; a quote oft used to refer to the absurdities which sometimes surface (see http://www.shazbot.com/lawass/) in cases when judicial pronouncements attempt to resolve an ambiguity by subjective fiat that appeals to the powers – and duties – bestowed upon the judicial authority (bosses) for the practical resolution of precisely such an ambiguity, even when the ambiguity may be theoretically irresolvable!

Now addressing such ambiguity in critical cases – such as communication between mechanical artefacts, or a putative communication between terrestrial and extra-terrestrial intelligences – is the very raison d’etre of mathematical activity. Such activity is first the construction of richer and richer mathematical languages that can express those of our abstract concepts that can be subjectively addressed unambiguously; and thereafter the study of the ability of the mathematical languages to precisely express and objectively communicate these concepts effectively.

However, even where the quantification can be made explicit – eg. Russell’s paradox or Yablo’s paradox – the question arises whether such quantification is constructive or not.

Russell’s paradox: Define the set S by {Ax: x is in S iff x is not in x}; then S is in S iff S is not in S.

Yablo’s paradox: Defining the proposition S(i) for all i >= 0 as ‘For all j>i, S(j) is not true’ seems to lead to a contradiction.

For instance, in Russell’s case it could be argued that the contradiction itself establishes that the set S cannot be constructively defined over the range of the quantifier. In Yablo’s case it could be argued that truth values cannot be constructively assigned to any sentence covered by the quantification since, in order to decide whether S(i) is true or not for any given i >= 0, we first need to decide whether S(i+1) is true or not.

There are two questions involved here – not necessarily independent.

The first is whether the currently accepted interpretations of formal quantification (essentially as defined by Hilbert in his formalisation of Aristotle’s particularisation in terms of his epsilon-function) over an infinite domain can be treated as constructive or not.

The second is when, and whether, the concept of a completed infinity is consistent with the interpretation of a formal language.

So far as the most intuitively ‘sound’ of our mathematical languages – first-order Peano Arithmetic PA is concerned – the answers to both seem to be negative.

The challenge begins when we attempt to substitute PA with the set theory ZF as a ‘universal’ mathematical language that can express, and consistently prove, all arithmetical truths, since the answers to both the above questions seem to be affirmative.

7. March 5, 2011 1:01 am

“If Peano Arithmetic is consistent, then it is incomplete.”

A possible reason that Goedel did not prove this in 1931 could be that it is not quite true!

Define a PA-formula [R(x)] as algorithmically verifiable if, and only if, for any given natural number n, there is a Turing machine TM that can provide evidence that the interpretation R*(n) of [R(n)] is either true or false under the standard interpretation of PA.

Then it can be seen that – under Tarski’s definitions – a formula under the standard interpretation of PA is true if, and only if, it is algorithmically verifiable as true.

Goedel, of course, showed that there is a PA-formula that interprets as true in the above sense, even though it is not PA-provable.

Now define a PA-formula [R(x)] as algorithmically computable if, and only if, there is a Turing machine TM that, for any given natural number n, can provide evidence that the interpretation R*(n) of [R(n)] is either true or false under the standard interpretation of PA.

Clearly the PA-formulas that – under the standard interpretation of PA – are algorithmically computable as true are a proper subset of those that are algorithmically verifiable as true.

We can now argue that PA is complete in the sense that a PA-formula is provable if, and only if, it is algorithmically provable as true under the standard interpretation of PA.

See Theorem 6 in: http://alixcomsi.com/27_Resolving_PvNP_Update.pdf

8. March 5, 2011 2:21 am

The book “A Digit of the Moon”, written in 1898 by F.W. Bain, concerns a king who falls madly in love with the beautiful and wise princess Anangaraga. The princess has declared that she will only marry a man who can ask her a question she cannot answer; if a suitor fails twenty-one times, he becomes her slave for life instead.

The king’s friend propounds nineteen questions, all of which the wise and clever princess answers without difficulty. On the morning of the twentieth day, the king, after praying to the goddess Saraswarti for help, is inspired with the solution: he will ask the princess to solve his own difficulty, and to tell him what question he should ask her. “And if she tells me, then I will ask her tomorrow what she tells me to-day: and if she does not tell me, then she is mine according to the terms of the agreement, to-day: and so in either alternative, the bird is caged.”

9. March 5, 2011 2:28 am

(1). Mathematics promises all solutions of a computational procedure
at any ordinary point (Strong consistency).

Ordinary solutions may be entire and complete non-polynomials.

(2). Mathematics promises convergent inference or deduction and
even polynomials to reach a simple closure (Regular consistency).

At least, we can solve three and four levels of complexity to obtain polynomials.
In addition, it is possible to solve N+1 level of complexity to obtain polynomials.

A specical note here: Orthogonality relations hold here for the polynomials.

(3). Mathematics promises asymptotic behaviors in case of conflicts (Inconsistency).

These results hold for automorphisms of relations and solutions.
Hence, strong consistency is not required for a theory to be solutions analytic.
A contradiction with strong consistency is possible.

This is what I want to share with Gödel :

If there is strong consistentency, then it is incomplete

—- It is true as stated in (1)

If there is consistentency, then it is incomplete

—- It is true only as polynomials obtained in (2)

—- It is false as convergent non-polynomials obtained in (2).

This is what I want to share with the author:

Can P = NP mathematically true ?

Please check:

http://leibnizengine.wordpress.com/2011/02/23/p-np/

10. Rafee Kamouna permalink
March 5, 2011 3:43 am

Dear Anand,

With these lengthy posts, your reputation will go negative. They will say that you are here and talking about diagonal statements and not yet resolved P vs. NP.

When they ask you for a diagonal sentence, bring them one in a programming language (like the Kleene-Rosser paradox) and not in natural language, you will soon find out: P=NP iff P!=NP.

Once you bring them this diagonal sentence, they will run away.

Best,
Rafee.

• March 5, 2011 4:50 am

That’s a fair observation, thanks.

The idea was merely to share comments on the post from an uncommon perspective of admittedly unguaranteed value. Wish I could express myself more succintly; a goal that seems as elusive as a holy grail!

• Rafee Kamouna permalink
March 5, 2011 5:50 am

Why do they have to run away when they discover the truth? They ask for a diagonal sentence, when they find it renders mathematics inconsistent, they run away.

Is it because they will lose their jobs. Or since mathematics ends in meaninglessness, then their lives are meaningless?

11. Jim Blair permalink
March 5, 2011 8:22 am

The Lipton DS:

Andrea, would it be okay if we went, but we did not tell you?

Translation of sibling code:

1. Dad doesn’t know it yet, but I know, you know I can talk him into taking me to Six
Flags while you are away at camp.
2. You’ll be at camp doing fun stuff and probably won’t care.
3. If it is going to upset you, don’t ask and I won’t tell.

12. March 5, 2011 10:26 am

Andrea’s delightful comment is reminiscent of (one version of) the surprise examination or unexpected hanging paradox: “You will be hanged tomorrow and you will not know about it in advance.” Like Moore’s paradox (“It is raining but I do not know that it is raining”), it appears to be a true but unknowable statement.

13. Varun permalink
March 5, 2011 11:29 am

Here’s something that reminded me of this post: http://www.gocomics.com/inkpen/2011/03/05/

I’m not a mathematician or anything, so please excuse any misplaced analogy!

14. March 5, 2011 5:33 pm

Amusing picture.

I’ve adapted/adopted one from Salvador Dalí as my signature: “Every morning when I wake up, I experience an exquisite joy — the joy of being this signature.”

Really nice quote in general, I think, before my adjustments: http://en.wikiquote.org/wiki/Salvador_Dal%C3%AD

15. Jim Blair permalink
March 6, 2011 10:26 am

The humorous and charming elements of the Lipton DS are elusive:

The junior member of the sibling team is sincerely seeking the advice of the senior member – Is this a way to resolve the problem?

The junior member may also be engaging in a bit of deft diplomacy – I did my due diligence by consulting with you.

Imagine chauffering adult VIP’s around and hearing the following exchange:

Junior VIP: There are things we know and there are things we don’t know and there are things we know we don’t know and then there are things we know that we didn’t know we know.

Senior VIP: Fool me once, shame on you. Fool me twice – and well – er – you better not fool me twice.

There is probably a moral to this story somewhere.

16. Charlie Volkstorf permalink
March 13, 2011 1:27 pm

Rosser’s 1936 theorem is not actually stronger than Godel’s 1931 results, but rather has different requirements of the Logic to be carried out. Godel’s results apply to any system in which provability is expressible. Rosser’s construction requires that provability be representable. It is not correct to say that Godel requires only soundness (short version in intro) or w-consistency (long version in body) while Rosser requires only consistency. Also see http://www.cs.nyu.edu/pipermail/fom/2010-July/014890.html

17. March 13, 2011 5:13 pm

Note that if you go through computability theory you at least don’t directly use Rosser’s trick. Of course it is ultimately equivalent

http://www.andrew.cmu.edu/user/avigad/Teaching/candi_notes.pdf