User gyorgy sereny - MathOverflow

Answer by Gyorgy Sereny for undecidable sentences of first-order arithmetic whose truth values are unknown

2012-01-01T23:22:03Z

If we omit the qualification "natural" from the question, then, of course, the most obvious examples are the arithmetized versions of metamathematical sentences expressing the (absolute) consistency of ZFC, or any axiom-system of set theory far weaker than ZFC within which arithmetic can be developed. Indeed, e.g. Con(ZF) is a sentence of arithmetic that we obtain by Godel-numbering from the metamathematical sentence "there is no proof of 0=1 from ZF." And if ZF is consistent, then Con(ZF) is undecidable in Peano arithmetic with unknown truth value. Actually, on the one hand, Con(ZF) implies Con(PA), and the arithmetical proof of $\lnot$Con(ZF) would yield a direct proof of the inconsistency of ZF.

As far as the "naturalness" condition is concerned, it seems that there will be no easy way to find "natural" sentences of this kind. Indeed, some natural candidates as e.g. the Goldbach conjecture are excluded, since they should be true, if they turn out to be undecidable. More precisely, any $\Pi_1$ sentence $S$ of arithmetic is true whenever $S$ is undecidable. Indeed, if $S$ is false, then its negation is a true $\Sigma_1$ sentence, and Peano arithmetic proves any true $\Sigma_1$ sentence.

Answer by Gyorgy Sereny for Proofs of Gödel's theorem

2011-05-26T20:37:34Z

Gregor Lafitte's short paper: "G\"odel incompleteness revisited" is is a freely downloadable nice and concise overview of different kinds of proofs with a long list of references:

hal.archives-ouvertes.fr/docs/00/27/45/64/PDF/74-89.pdf

Supplement of 11th October 2011:

In a recent paper `The Surprise Examination Paradox and the Second Incompleteness Theorem', Notices of the AMS Volume 57, Number 11 (it can be downloaded from http://www.ams.org/notices/201011/rtx101101454p.pdf), the authors give a new proof for Godel’s second incompleteness theorem, based on Kolmogorov complexity, Chaitin’s incompleteness theorem, and an argument that resembles the surprise examination paradox.

Answer by Gyorgy Sereny for Surprising and Useful Physical Intuition for Mathematical Objects

2011-06-28T21:04:59Z

I think, Elliott Sober gives a nice example (cf. Elliott Sober `Quine's Two Dogmas', Proceedings of the Aristotelian Society, Supplementary Volumes, Vol. 74 (2000), pp. 268-269):

For logic and mathematics to be tested empirically, one logical or mathematical statement would have to be pitted against an alternative and a framework of shared background assumptions would have to be supplied that permits the two statements to make different predictions about observations. It is instructive to examine a case in the history of mathematics in which this actually happened. Plateau was a 19th century French mathematician who wanted to figure out what the surface of least area is that fills various closed curves. A simple example of the type of problem that Plateau had in mind is a curve that has the shape of an ellipse. An elliptical curve can be filled by the ellipse it contains; any other surface that fills the curve will bulge into a third dimension and so must have more surface area. Although the answer to Plateau's question is obvious for this example, the answers aren't at all obvious for more complicated three-dimensional curves. What Plateau did was to dip wires bent in different shapes into soapy water and observe the resulting soap bubbles that adhered to the frames when they were removed from the water (Courant, R. and Robbins, H., 1941, What is Mathematics?, New York: Oxford University Press). Given the physical assumption that soap bubbles take on the surface of least area in this experiment, different mathematical hypotheses ('the surface of least area for curve C is s1' versus 'the surface of least area for curve C is s2', for example) make different predictions. This example is interesting in the history of mathematics precisely because it is so atypical. No such test of '2 + 3 = 5' against alternative arithmetic hypotheses has ever been carried out, nor is it remotely clear what this would be like.

Answer by Gyorgy Sereny for Completeness vs Compactness in logic

2011-06-27T00:25:24Z

I think that everything important that can be said about the differences between Compactness and Completeness Theorems and their proofs from the technical point of view has been said. (I also like most the detailed and elucidating answer given by Joel David Hamkins (at http://mathoverflow.net/questions/9309/in-model-theory-does-compactness-easily-imply-completeness)). On the other hand, one of the most important differences between these theorems is a non-technical one, and indeed some previous answers contain hints to this effect. Indeed, Completeness Theorem has an obvious metamathematical (or even philosophical) flavour as opposed to Compactness Theorem. Actually, it is about the relation between the two most important mathematical notions, i.e., those of proof and truth.

And here I would like to argue with those (Carl Mummert and Stefan Geschke) who claim that sometimes Completeness Theorem is used in everyday mathematics. Actually, as I see it, it is about everyday mathematics, but it does not belong to everyday mathematics.

Actually, contrary to what Carl Mummert says, I doubt that, in everyday mathematics, anybody in any time uses completeness theorem in either an explicit or implicit way. Obviously, one can successfully work in any field of mathematics (which are not intimately connected to logic) without any knowledge of mathematical logic. (Clearly she or he has to have a good sense of logic, but this is a completely different matter.) In other words (unlike Carl Mummert), I cannot imagine any `difficulties in an alternate world where mathematicians have to distinguish between "true in all groups" and "provable from the axioms of a group" '. The reason is simple. I do not think that anyone proves "that a group identity is derivable from the axioms of a group by working semantically and showing that the identity holds in every group." Though I am not a group theorist, I think that no group theorist is interested in the statements that are provable from the axioms of group theory alone. (On the other hand, of course, the most important elementary statements needed to begin group theory at all are usually derived directly from the axioms.) Most mathematicians work in intuitive set theory and freely make use of the different possibilities that this rich theory offers (independently of the fact that she or he is aware of the existence of ZFC). (Actually, the notion of a group itself is defined as a model, that is, generally in terms of sets rather than a first order theory. And, of course, this kind of definition is very practical, since otherwise every course on groups have to be preceded by an introduction to logic.) I think that the pure first order theory of groups has only theoretical or didactic significance for being a nice widely known example of a first order theory.

Likewise, I do not agree with Stefan Geschke that "the completeness theorem does explain why we can do mathematics the way we do." Just the other way around. Clearly, metamathematics is the study of real mathematics by exact mathematical means. Therefore, its notions are intended to mimic those of everyday informal mathematics as faithfully as this is possible. So a metamathematical result cannot explain or justify anything. What it can do is to describe in exact terms and clarify the way mathematics is normally done (and, of course, to draw consequences about everyday mathematics from the results of this description). But its results do not affect the way mathematics is normally done. Obviously, we would do everyday mathematics in exactly the same way if the Completeness Theorem did not hold. Just as those mathematicians do who never have heard of this theorem. And indeed, we do arithmetic in exactly the same way as mathematicians before Gödel (who might well think that true arithmetic was recursively axiomatizable) did.

Answer by Gyorgy Sereny for Supervenience in mathematics

2011-06-23T18:56:34Z

I think that an interesting phenomenon analogous to the relation of informal mathematics to its set theoretical foundations described by Joel David Hamkins is the relation between those meta-arithmetical notions, theorems, and proofs that we formulate by the help of Gödel numbering. Actually, it is a perplexing fact that we can establish the truth of arithmetical theorems without having the faintest idea of their arithmetical content. For example, we know that the Gödel sentence of a consistent theory is true. The statement carrying this metamathematical content is actually a sentence of the language of arithmetic. But, obviously, its arithmetical content is incomprehensible by any human being.

Answer by Gyorgy Sereny for Are inference laws consistent?

2011-06-22T18:09:01Z

First, a remark. You formulate both Gödel's theorem and your question in a subjective way "we cannot prove", etc. However, this theorem is a mathematical one, therefore it is not about our ability to do something, but about the nonexistence of a mathematical object, namely a formal proof within the system concerned. You can draw some e.g. philosophical conclusions from this theorem, but this is a completely another matter.

Now, as far as your question concerned, it is almost certain that nothing analogous to Gödel's theorem can even be stated for the pure first order logic itself. The reason is simple. The analogous theorem would claim the unprovability of the formula expressing the the fact that a contradiction is unprovable within the pure first order logic. But, in the absence of the formal provability predicate, this theorem cannot even be stated. Actually, what we would like to show is that there is a formula $Pr(x)$ such that, on the one hand, it can be considered a provability predicate (that is, for any formula $\varphi$, $Pr(\ulcorner \varphi \urcorner)$ is true just in case $\vdash \varphi$ (here, of course, $\ulcorner \varphi \urcorner$ is the Gödel number of $\varphi$), on the other hand, the formula expressing the fact that a contradiction is unprovable is itself unprovable: $\not\vdash \lnot Pr(\ulcorner 0=1\urcorner)$. Now, the proof of the existence of a provability predicate seems to require much more than pure logic.

Answer by Gyorgy Sereny for Complete mathematics

2011-06-06T22:17:54Z

Perhaps it is worth adding some comments to the list of non-trivial complete theories given by Carl Mummert. One remark is that the completeneness of Euclidean geometry is a consequence of that of the real closed ordered fields (exploiting the possibility to "arithmetize" geometry using cartesian coordinates). The other is that the completeness of the theory of dense linear orderings without endpoints is only one in a set consisting of related theories. Actually, all the 4 possible theories of dense linear orderings, that is, those without endpoints, having both first and last elements, having only first, and having only last element are complete. Analogously all the 4 possible theories of discrete linear orderings (with the additional requirement of infiniteness in the case of having both first and last elements) are also complete. Moreover, there is a nice analogy between linear orderings and Boolen algebras (BA's) in this respect: atomless BA's correspond to dense orderings, atomic BA's to discrete orderings. Indeed, both the theory of atomless BA's and the infinite atomic ones are complete.

Answer by Gyorgy Sereny for Examples of theorems misapplied to non-mathematical contexts

2011-05-31T19:09:33Z

In order to baffle the uninitiated, some authors interpret Banach-Tarski paradox (stating that "it is possible to decompose a ball into five pieces which can be reassembled by rigid motions to form two balls of the same size as the original.", cf. http://mathworld.wolfram.com/Banach-TarskiParadox.html) in an obviously false way as if it could be applied to physical objects. E.g. Reuben Hersh writes (Reuben Hersh: "What Is Mathematics, Really?" p.255):

"Stefan Banach and Alfred Tarski proved, using the axiom of choice, that it's possible to divide a pea (or a grape or a marshmallow) into 5 pieces such that the pieces can be moved around (translated and rotated) to have volume greater than the sun."

Clearly, this formulation is very much misleading, since it suggests that the paradox can be applied to a physical objects, which is obviously false. Indeed, the construction is such that the ball is divided into non-measurable parts and, clearly, there is no physical objects corresponding to non-measurable sets.

Answer by Gyorgy Sereny for Arithmetic fixed point theorem

2011-05-29T23:43:01Z

I think that the best way to capture the idea beyond the proof of the fixed point theorem is to mirror it in an ordinary language formulation and then translate it back to the first order language of arithmetic (cf. J.N. Findlay, Goedelian Sentences: A Non-numerical Approach}, Mind, Vol. 51, 1942, pp. 259-65.). Clearly, what we seek is a sentence asserting that it has a given property, that is, a sentence that says "I have the property p". But, in order for it to be formalizable, our sentence should consist of components with easily identifiable formal first-order counterparts. Therefore we cannot use such indexicals as `I'.
In order to circumvent the need for indexicals, we reformulate Grelling's paradox applying it to open sentences instead of adjectives:

(1) "x is heterological" is heterological,

where an open sentence is called autological if the property it attributes to x possessed by the sentence itself, otherwise it is called heterological. For example, "x consists of five words", "x is English", are autological, while "x is long", "x is German", are heterological. On the other hand, both in formal languages and in informal ones, the fact that an object has a property is expressed by a substitution of the name of the object into the open sentence expressing that property. Consequently,

(2) x is heterological just in case the sentence obtained by substituting the name of x for the variable in it is false.

Now (using the convention that he name of linguistic objects are the object itself between quotation marks), if we replace "being false" by "having property p", (1) and (2) together yield:

(3) the sentence obtained by substituting the name of "the sentence obtained by substituting the name of x for the variable in it has property p" for the variable in it has property p.

This is the sentence we need. On the one hand, it does not use indexicals, on the other, it indeed says of itself that it has property p (and says nothing else), since it is built up in such a way that if we perform the substitution described in it, then we obtain the sentence itself, which is stated to have property p.

Now, let s denote the open sentence between the quotation marks in (3), that is, let s be:

(4) the sentence obtained by substituting the name of x for the variable in it has property p.

Then, clearly, the whole sentence (3) is s("s"). In order to obtain the fix point lemma, we should translate it into the language of formal arithmetic. Clearly, the formalization process consists of two main steps. In the first step, we have to find the formal version $\eta$ of s, and then the second step is obvious: the desired sentence $\lambda$ will simply be $\eta(g(\eta))$ (where $g(\varphi)$ is the G\"odel number of $\varphi$ and plays, of course, the formal counterpart of name of $\varphi$, and, for simplicity, I leave out of consideration the difference between numbers and their formal counterparts in the language).

Now, that is all. That is the essence of the proof. What remains to do is simply translate the ordinary language argument into the formal language of arithmetic. That is a completely mechanical task.

Let us recall that what we should show is that, for any arithmetical formula $\varphi$ with at most one free variable (this fact will be denoted by $\varphi=\varphi(x)$), there is a sentence $\lambda$ such that

$Q\vdash \lambda \longleftrightarrow \varphi(g(\lambda)),$

where $Q$ is Robinson arithmetic (essentially Peano arithmetic without induction).

Now, let the formula corresponding to the property p be $\varphi=\varphi(x)$. Then, obviously, the formal version of s is $\varphi(g[x(g(x)])$. In order to continue the formalization process, we should find a formula that can play the role of $\varphi(g[x(g(x))])$, that is, a formula $\eta=\eta(x)$ such that $\eta(g(\psi))$ is provably equivalent to $\varphi(g[\psi(g(\psi))])$ for every $\psi=\psi(x)$, or equivalently (denoting the inverse of $g$ by $g^{-1}$), for any $n \in N$,

$Q\vdash \eta(n)\longleftrightarrow\varphi(g[g^{-1}(n)(n)]). $

In order to find the appropriate formula $\eta$, let us consider the expression substituted into the formula $\varphi$, and define the function $f:\omega\longrightarrow \omega$ accordingly:

$f(n)=g[g^{-1}(n)(n)]$ if $n \in N$ and $f(n)=0$ otherwise.

Since this function is obviously recursive and hence representable, and, up to provable equivalence, the result of substituting a representable function into a formula can also be expressed by a formula, there is a formula $\eta$ such that, for any $n\in N$,

(5) $Q\vdash\eta(n)\longleftrightarrow\varphi(f(n))$

Thus we have obtained what we need, we have shown that there exists an $\eta$ that can be considered to be the formal version of s. Now, all that remains to do is straightforward: it follows from (5) that, for every $\psi$,

$Q\vdash \eta(g(\psi))\longleftrightarrow \varphi\big(g[\psi(g(\psi))])$,

which, in turn, choosing $\psi$ to be $\eta$, yields

$Q\vdash \eta(g(\eta))\longleftrightarrow \varphi(g[\eta(g(\eta))])$,

showing that the sentence $\lambda =\eta(g(\eta))$ indeed has the desired property.

Answer by Gyorgy Sereny for nontrivial theorems with trivial proofs

2011-05-24T22:44:03Z

What about the irrationality of $\sqrt{2}$, the non-triviality of which is witnessed by the fact that the philosophy of the school of Pythagoreans was based on the belief that such numbers do not exist. The proof, on the other hand, is a well-known elementary one.

Answer by Gyorgy Sereny for Demonstrating that rigour is important

2010-09-04T18:26:10Z

I think that the question itself is entirely misleading. It tacitly assumes as if mathematics could be separated into two parts: mathematical results and their proofs. Mathematics is nothing other than the proofs of mathematical results. Mathematical statements lacks any value, they are neither good nor bad. From the mathematical point of view, it is entirely immaterial whether the answer to a mathematical question like `Is there an even integer greater than two that is not the sum of two primes?' is yes or no. Mathematicians simply do not interested in the right answer. What they would like to do is to solve the problem. That is the main difference between natural sciences or engineering on the one hand, and mathematics on the other. A physicist would like to know the right answer to his question and he does not interested in the way it is obtained. An engineer needs a tool that he can use in the course of his work. He does not interested in the way a useful device works. Mathematics is nothing other than a specific set consisting of different solutions to different problems and, of course, some unsolved problems waiting to be solved. Proofs are not important for mathematics, they constitute the body of knowledge we call mathematics.

Comment by Gyorgy Sereny

2011-06-30T15:59:17Z

I do not think that compactness in logic is a purely semantic notion. True, it is its semantic version which is nontrivial. That is why the semantic version is the one that is used widely. On the other hand, in logic, the notion itself, in a sense, is of syntactic origin. Actually, the usual way to infer the Compactness Theorem from the Completeness is to use the (trivial) syntactic version of compactness: a theory is consistent iff its every finite subset is consistent.

Comment by Gyorgy Sereny

2011-06-30T15:40:47Z

Thank you for your answer. As a matter of fact, I take it for granted, that the completeness of a theory is a syntactic property, that is, one formulated in terms of provability rather than in terms of semantic consequence: T is complete just in case $T\vdash\sigma$ or $T\vdash\lnot\sigma$ for all sentences $\sigma$. In this case, the decidability of complete recursively axiomatized theories can be shown without the Completeness Theorem.

Comment by Gyorgy Sereny

2011-06-29T20:07:28Z

Congratulations. I think that this proof is really very original and ingenious. One can appreciate its simplicity and elegance, only if she or he has tried to prove the claim directly.

Comment by Gyorgy Sereny

2011-06-26T17:45:34Z

You write: "Completeness comes into play when proving the decidability of complete recursively axiomatized theories ...". Don't you use here the notion of "completeness" in another sense (namely as a characteristics of a theory as opposed to one that appears in the Completeness Theorem, which characterizes a logic)?

Comment by Gyorgy Sereny

2011-06-23T16:19:30Z

@unknowngoogle: The formulation 'so that nobody is able to "prove"' seemed to suggest that you think that the theorem is DIRECTLY about our possibilities. @SNd: The non-existence of some object DOES NOT imply directly that we cannot do something. This fact depends also on the interpretation of this mathematical result.