text:
## Is PA consistent? do we know it?

1) (By Goedel's) One can not prove, in PA, a formula that can be interpreted to express the consistency of PA. (Hopefully I said it right. Specialists correct me, please). 2) There are proofs (although for the purpose of this question I should putt it in quotations marks) of the consistency of PA.

The questions are: A) Is it the consistency of PA still a mathematical question that can be considered open? B) Is it a mathematical question? (To this I dare to say that it is a mathematical question. Goedel himself translated it into a specific formula, but then I have question C) C) Is it accepting the proofs of the consistency of PA as conclusive a mathematically justified act or an act of taking a philosophical stance?

Motivation: There is a discussion in the mailing list FOM (Foundations Of Mathematics) about this topic, in part motivated by this talk link text . I thought a discussion about this fundamental matter concerns most mathematicians and wanted to bring it to a wider audience.

Edit: It is simple. Either: 1) Consistency of PA is proved and has a proof (as claimed by some in FOM) as valid as any other theorem in math, or 2) On top of the existing proofs a philosophic choice is needed (which explains the length of the discussions in FOM, justifies closing this question but contradicts what is being claimed emphatically by some in FOM)

But you see. If 1) is the case then there is no need for the lengthy discussions and this is a concrete math question as any other, terminating with a proof.

........................................................................................

Edit 2: Thank you all. Although I had seen some of these arguments at FOM now I think I have my ideas more organized and I can make my question more concrete. I would like to try to put aside what involves 'believes'. In, I think, all the answers shown there has been this action entering the argument quite soon, e.g. In Chow's: (approx.) If you believe in the existence of the naturals then con(PA) follows. In Friedman's (approx.) If you believe in (About a dozen Basic axioms) + (1/n subsequences) then con(PA) follows.

I want to put aside that initial action because (1): It is a philosophical question and that is not what I want to discuss, (2): Because of: If I believe (propositional logic) + (p/-p) then I believe ... for example (everything you can say) and maybe (3): Because I, personally, don't do math to believe what I prove. When I show P->Q, in a sequence of self imposed constrained steps I don't do it with the purpose of showing that, and at the end I don't have a complete conviction that, Q is a property of whatever could be a real world. But that is just philosophy and philosophy allows for any sort of choices. That is why I want to put it aside, at least until the moment in which it is inevitably needed.

My question is: Is any of the systems that prove con(PA) a system that has itself been proven consistent?

Why to ask this question? Regardless of how your feelings are about the ontological nature of what you prove. We can say that, since an inconsistent system proves everything, a consistent system is a bit more interesting for not doing so. At least if it is because there is not always a proof in which you use modus ponens twice (after you have found p/-p) for everything that you want to prove.

I guess that also, to answer the question above, it should be clarified what to accept for a consistency proof. Let's leave it kind of open and just try to delay the need for a philosophic stance as much as possible.

-
Given the rather lengthy debate on FOM, and the fact that MO is not for debates or discussions, I don't know that this question is a good fit. Although if someone posts a contradiction in PA I guess that would give a definite answer... – Steven Gubkin May 26 2011 at 22:42
I have voted to close, even though I think this is an interesting question, because, as Franklin points out, there is extensive and impassioned discussion on a mailing list already, and that is a far better forum than MO for this discussion. – David Roberts May 27 2011 at 0:09
And, in addition, the moderators of FOM has said that he will not post any more mailings about the Con(PA) debate unless they add something new. MO is not the place to continue fruitless discussion. – David Roberts May 27 2011 at 0:23
Especially after reading (Matthew) Emerton's long and cogent message on meta, I've decided to cast the last reopening vote. But I please remind everyone to "keep a civil tongue" -- respond coolly and factually. – Todd Trimble Jun 1 2011 at 11:10
Meta thread is at:  meta.mathoverflow.net/discussion/1057/…  – Will Jagy Jun 1 2011 at 23:15
show 11 more comments

For some reason, this question generates more confusion than it really should. My belief is that if you understand the question properly, then you should be able to answer it yourself.

So let me ask the following question: Suppose $P(n)$ asserts a mathematical property of the nonnegative integer $n$, and suppose we can prove $P(0)$ and we can also prove that for all $n$, $P(n)$ implies $P(n+1)$. Does $P(n)$ hold for all $n$?

This is just mathematical induction, and the answer is so obviously yes that you must wonder if it's a trick question. But I'm not asking a trick question. The answer is yes.

Now let me ask if a first-order formula in the language of arithmetic (e.g., $\exists y: y+y=x$) defines a mathematical property of the integers. Again, the answer is so obviously yes that you must wonder if it's a trick question. But it's not a trick question. The answer is yes.

If you're with me so far, then you have just agreed that PA is consistent. You should now be able to ask yourself, did you make any philosophical assumptions just now? Is the validity of mathematical induction a philosophical question or a mathematical one? If it's a mathematical question, is it still an open problem?

-
The question of whether every formula with one free variable determines a property is exactly what has to be proved. The failure of this is exactly what goes wrong in naive set theory with expressions such as $\{ x: x \not \in x\}$. However, we have two completely different proofs of consistency: Gentzen's and Goedel's. These show that, in fact, formulas of PA do determine sensible predicates, at least in the sense that the axiom scheme of induction is consistent. – Carl Mummert May 27 2011 at 1:45
The failure of formulas to do sensible things is also what enables Curry's paradox that shows that certain type theories stronger than PA are inconsistent. It seems odd, but somehow the second-order induction axiom seems less worrisome in this way than the first-order axiom scheme. – Carl Mummert May 27 2011 at 1:53
@Franklin: Your definition of proof runs counter to normal mathematical standards for proof. E.g., mathematicians regard it as proved (not an open problem) that every differentiable function is continuous, even though there's no way to "experimentally check" an uncountable number of differentiable functions at uncountably many points for continuity. By normal mathematical standards, PA is provably consistent. You can of course introduce unconventional philosophical standards and declare that the consistency of PA is an open problem, but then you shouldn't be surprised if people argue with you. – Timothy Chow May 30 2011 at 22:18
I don't see why I should accept or reject some assertions in an absolute sense. Is it a game you want me to play with you? In fact I don't understand the meaning of your "accept". It's not a mathematical notion but a philosophical one. If you care about my philosophy in this respect, look up "ignosticism" at Wikipedia; you could then ask yourself if the assertion about bounded sequences is falsifiable. I'm far less comfortable with $RCA_0$ and with quantification over all (which all?) bounded sequences than with the induction schema of PA. What Emerton says about it also makes sense to me. – Sergey Melikhov Jun 2 2011 at 9:56
@Sergey: I don't think online forums generally give accurate samples of mathematicians' beliefs. Online discussions routinely overstate the doubt about such things as the consistency of PA, the truth of the axiom of choice, etc. If we examine textbooks, which are written much more deliberately than online discussions, we see that with only very rare exceptions they accept the consistency of PA (and the axiom of choice). For example, I have seen dozens of textbooks prove "there are infinitely many primes" and none phrased it as "if ZFC is consistent then there are infinitely many primes." – Carl Mummert Jun 3 2011 at 13:29
show 32 more comments

Dear Tim, I read your same argument (up to homotopy) on FOM a couple of days ago and I must say: NOT convincing. You may ask why, and I am glad to tell you: the $n$ in the induction formula and the x and y in the ∃y:y+y=x are not integers, but TERMS in the language of PA. I certainly have no problems manipulating terms using PA, but about integers I know nothing, in fact I doubt they actually exist (and by the way, I am not alone: Nelson, for one, doubts them too). And I do not mean I doubt that 2^10^10^100000000 exists -in fact it does, just another fancy term), I mean I doubt that even the NUMBER 5 exists. In fact, let me tell u more: what is 5? Answer: the (infinite) equivalence class of terms in the language of PA which are provably equal to SSSSS0. Do you REALLY know this class? I doubt. Perhaps some incredibly complicated term will eventually be proved equal to SSSSS0, and nobody now knows it, or even fancies about it. Bottom line, your argument is basically this: IF there is such a thing as the integers and I know them, THEN PA is (obviously) consistent. A small IF for you, a gigantic one for me.

Coda: do I believe that PA is inconsistent? I would not bet my house on that. But I would not bet my life on PA being consistent either...

-
Dear Mirco, I don't see the difference between faith in numbers and faith in symbols. The one unique (symbolic) entity that we always refer to when we write down something like "SSSSS0" does not strike me as any less mysterious than the equivalence class of all 5-element sets. If you give numbers to the devil, he's going to take the free semigroup generated by the letters used in mathematical discourse. – SJR May 27 2011 at 2:19
I agree with SJR. If you don't believe in numbers, then I don't see why you believe in PA. You ask me, what is 5? I reply, what is a symbol? – Timothy Chow May 27 2011 at 2:43
To work with PA, one has to be able to tell the difference between SSSS0 and SSSSS0. How are you able to tell the difference? I personally do so by counting the number of symbols and noting that one has 5 symbols and the other doesn't. Since you don't know what 5 is, this technique is unavailable to you. And if you can't keep track of the difference between SSSS0 and SSSSS0 then you certainly can't determine whether an alleged PA-proof is correct, or whether your computer program is debugged. So I don't even know what you mean when you say that "PA might be inconsistent." – Timothy Chow May 27 2011 at 15:39
As for your argument, it is you that seem not to accept the obvious, for instance Andreas Blass above understood immediately my position (read again his answer), though he probably will not agree. But at any rate, I try to explain it to you: certainly I know $0, here it is: I write down 0, then S0, then SS0,.. then SSSSS0, and then SSSSS0. BINGO! Now, as I mentioned above, my laptop can be programmed to do just the same, and even to check whether a sequence is well formed or not. For instance, it would reject SS0SSSS0 as invalid. Now, does my laptop know the natural numbers? I doubt it. – Mirco Mannucci May 30 2011 at 23:10 5 is the number of fingers on my right hand. Now for everybody's sake I should be really careful not to get into a nasty accident involving my fingers, because that would make PA inconsistent. – Andrej Bauer Jun 1 2011 at 14:12 show 15 more comments As Mirco Mannucci's answer suggests, the alternatives labeled 1) and 2) in the question are (for some people) not mutually exclusive. The consistency of PA indeed "has a proof as valid as any other theorem in math" (as Timothy Chow's answer pretty much shows) --- alternative 1. Nevertheless, if one doesn't believe the integers exist, then the bottom drops out from that and also from almost everything else in math. So to be really convinced by the proof, one makes a philosophical choice to accept the existence of integers and the meaningfulness of quantification over them. What strikes me as strange is that people who have made that choice (or at least act as if they had made it) and are perfectly content with theorems that rely on the availability not just of integers but of far more complex entities (real numbers, sets thereof, etc.) suddenly develop philosophical qualms about such reliance when used to prove the consistency of PA. Let me also comment on Gentzen's proof. Note that Timothy didn't invoke that argument but gave instead a much more natural and understandable proof. So what is Gentzen's proof good for? As far as I can see, its primary value from a philosophical point of view is that it can be used if one doesn't accept arbitrary first-order sentences about the integers (with possibly lots of quantifiers) as meaningful. The induction axiom scheme of PA says that such sentences can be proved by induction (ordinary induction on natural numbers), which is true but presupposes that these sentences are meaningful. Gentzen's proof uses induction on ordinal numbers up to $\varepsilon_0$ but only to prove very simple, finitary statements. (His proof can be formalized in the system PRA of primitive recursive arithmetic plus the assumption that there is no primitive recursive decreasing sequence of ordinals below $\varepsilon_0$.) The upshot is that there's a trade-off: If you want to prove the consistency of PA by induction on only extremely simple statements, then you need a long induction, of length $\varepsilon_0$. - Andreas, yes, if someone doubts that natural numbers exist, almost everything else in math also drops out, at least as far as ontological beliefs go. But that does not mean that the skeptic fellow will stop loving and/or doing math, or worse, act as a censor and try to obliterate some of its branches, such as for instance set theory. I do not believe in the number 5, yet I am fascinated by the theory of extremely large cardinals. To me, that is another gorgeous game with precise syntactic rules, and some folks play it well and build excellent works of art in Cantor paradise – Mirco Mannucci May 27 2011 at 12:10 "...suddenly develop philosophical qualms..." So you don't suddenly develop an increased attention to rigor when doing math, as opposed to the rest of your daily life. For this reason you never use any medicine (because its action hasn't been proved), never attend seminars (because it hasn't been proved that the talks will run as scheduled), etc. I see. Well, I'm proving my theorems only to better understand world; so I feel comfortable using induction because I'm confident that it's at least very, very close to being true, and any potential problems with PA will not change my proofs too much. – Sergey Melikhov May 31 2011 at 19:53 @Sergey: The position you seem to be defending, being uncertain about mathematics in the same sense (though less intensely) as about "real life", seems coherent to me. What I consider strange, though, is to accept some parts of mathematics (e.g., real analysis) without expressing any doubts, while expressing doubts, based on ontological issues (doubts whether the integers exist), about statements like Con(PA) that seem to require far less ontological commitment than real analysis. The analog in your real-life examples would be someone who is ... (continued in next comment) – Andreas Blass Jun 1 2011 at 12:51 (continuation of previous comment) confident that next week's seminars will take place as scheduled and that his medicine will continue to work but has serious doubts about whether the sun will rise tomorrow. – Andreas Blass Jun 1 2011 at 12:52 Dear Andreas, Regarding the issue that "strikes [you] as strange": after listening to Voevodsky's lecture, my impression is the following: while he (and most mathematicians) work with concepts much more complex than PA, on the other hand, in practice they only use rather limited examples of comprehension, i.e. the formulas they work with are typically of a very limited kind. Voevodsky's position seems to be a strongly constructivist one, and it is not the level of complexity of objects that he seems to be rejecting, but rather non-constructive assertions about them. I think that ... – Emerton Jun 1 2011 at 13:08 show 3 more comments The following is a (I hope correct) adaption of an argument of H. Friedman made on the FOM list, which I found very instructive. The following statements are esentially equivalent: a. The consistency of PA is proved. b. It is proved that for every bounded sequence of rational numbers there exists a subsequence $q_i$ such that for every$n$one has $$|q_i - q_j| < 1/n$$ for$i,j \ge n$. So, I understand that one can have doubts about b. too, but still I think it clearly demonstrates that if one doubts that the consistency of PA is proved, then one has to doubt all kinds of other classical mathemtical facts. - Dear unknown, I agree with this answer, and my impression, from listening to Voevodsky's lecture, is that he does reject a lot of classical mathematical facts, in so far as he adopts an extremely constructivist stance. (See my answer for a slight elaboration on this). Best wishes, Matthew – Emerton Jun 1 2011 at 13:00 The Friedman correspondence is in cs.nyu.edu/pipermail/fom/2011-May/015506.html – Junkie Jun 1 2011 at 14:02 This is not quite what Friedman said. Firstly, I find your "proved" misleading (proved in what formal system?). Secondly, your b involves quantification over sets of integers, so I don't think that your assertion that a implies b corresponds to any actual theorem. What Friedman said is that RCA_0 + (your b without "proved") is equivalent to a system that interprets PA. Thirdly, and I think most importantly, the system RCA_0 allows induction over formulas involving universal quantification over sets of integers (which PA doesn't). – Sergey Melikhov Jun 1 2011 at 18:24 (cont'd) And this is what I don't buy in Friedman's argument. I don't find the notion of "a set of integers" sufficiently unambiguous to be quantified over. Even in ZFC, what is and what is not a set of integers is a matter depending on additional axioms (e.g. this can be affected by forcing). I do hope that our understanding of what are sets of integers will be clarified by seeing them as types (non-discrete in general) - of course if the univalent foundations program succeeds in explaining how to do it. – Sergey Melikhov Jun 1 2011 at 18:48 Added: I did not see the second comment of Sergey Melikhov before finalizing my comments. However, it seems this does not have to severe consequences, except that I should add (again) that I am not qualified to 'defend' Friedman's argument. As said I tried to 'quote' him. In case, I should misrepresent his views I will of course modify my answer. If this is not so, please consider my answer as more-or-less a (free) quotation that I found instructive. – quid Jun 1 2011 at 19:28 show 7 more comments Here is an attempt to answer the question that I posted on the meta discussion, and which I am reposting here now that the question has been reopened. [Note: I am a non-expert with an interest in foundational issues, and I am doing my best to understand the situation. I hope that my lack of technical expertise in the area has not led to too many stupidities, and welcome any such being pointed out.] The question is asked not in isolation, but in the context of a lecture by Voevodsky. This can (and probably should) inform the answer, and will certainly inform my answer. Now, as Timothy Chow notes in his answer here (and in his posts on the FOM mailing list), if one accepts the existence of the natural numbers, and of arbitrary subsets of the natural numbers, then one can prove that PA is consistent, by exhibiting its standard model, namely the natural numbers. In short, if you believe in the existence of the natural numbers with their usual properties, and you believe that any formula in PA defines in a meaningful way a subset of them, then you will be forced to believe in the consistency of PA. On the other hand, listening to Voevodsky's lecture, it seems clear that while he is not rejecting the existence of the natural numbers (as perhaps some extreme finitists do), he does not believe that a general formula in PA defines a meaningful subset of the natural numbers. Thus the standard model argument does not convince him, and in fact he seriously entertains the idea that PA may be inconsistent. On the FOM list there are various assertions that Voevodsky's position is inconsistent, because he has surely proved, and accepted as proved, more elaborate results than the consistency of PA. This is not clear to me, and it seems that a careful analysis of the situation may be somewhat analogous to the analogous analysis of whether large cardinals are required for the proof of FLT --- see this MO question; that is, what might be deduced by a naive analysis of the theories involved, which would suggest that a lot of strong foundational principles are required for$\mathbb A^1$-homotopy and so on, could be misleading upon a more careful investigation. Indeed, it seems quite possible to me that all the arguments that Voevodksy has ever made or signed off on as a referee involve much less comprehension than is required to believe that an arbitrary formula in PA defines a subset of the natural numbers. (The point being that his mathematics will only ever have involved comprehension for rather particular formulas, which are presumably much more concrete than a "general" formula of PA.) Again, listening to Voevodsky's lecture, it is clear that he makes a careful distinction between mathematical reasoning as carried out by mathematicians, and formal reasoning. Indeed, he seriously entertains the idea that there may not be formally consistent foundations, but at the same time is not rejecting usual mathematics in any sense. Rather, he makes it clear that he believes that the kind of unrestricted nature of constructions required in setting up foundations (e.g. allowing arbitrary formulas in PA to define subsets of the naturals) are likely to always lead to contradictions; but at the same time, he believes that "actual" mathematics will not be affected by this (although a new viewpoint on foundations would be required, a viewpoint that I believe he and his collaborators are actively developing). So he draws a very strong distinction between "practical" or "natural" mathematical reasoning, and its formalization in a formal system such as PA or ZFC. He seems to believe that Russel-type paradoxes arising from unresricted comprehension will appear in essentially any foundational system, and his rejection of comprehension even over arbitrary formulas of PA seems to me to be a very strong constructivist position (and I hope I'm using this adjective in some approximately correct sense). So I think the answer to the question should be something like: the consistency of PA can be easily proved using commonly accepted mathematical notions, but not if one limits oneself to sufficiently constructivist notions (as Voevodsky is doing). [The next part of my answer is based on an exchange with an_mo_user on the meta discussion.] On the FOM mailing list, Friedman posted some correspondence with Voevodsky, in which Friedman explain that the consistency of PA follows from fifteen (if I remember correctly) generally accepted mathematical principles together with the following statement: 1. every bounded sequence of rationals contains a subsequence such that for this subsequence for all$n$one has$|q_i - q_j| < 1/n$for$i,j > n$. He then asks for Voevodsky's reaction to this: does he continue to maintain that PA is inconsistent, and (hence) reject (1), or does he have some different position? At this point I am speculating (since Voevodsky hasn't yet answered Friedman's question), but I presume that he will reject statement (1), or rather, will accept as valid only a more limited, sufficiently constructive version of (1). If one takes a formula of PA which determines a non-constructive subset of the naturals (one whose existence Voevodsky rejects), and then takes the corresponding sequence of rationals, one gets a sequence of rationals tending to zero, which I imagine could arise as a candiate sequence$q_n$in (1). Or alternatively, one could imagine some sequence of rationals such that the subsequence predicted by (1) has indices$i$which are precisely determined by the condition of belonging to this subset. I would guess that some (probably much more sophisticated) version of these sorts of constructions is taking place in Friedman's proof relating (1) to consistency of PA. Note that in the question and answer part of the video, Voevodsky makes it pretty clear that he doesn't really believe in the current formalization of the real numbers (calling them an "overidealization") and so it wouldn't surprise me at all if he rejected (1). - You're right about (1) -- it is a slightly disguised form of the Bolzano-Weierstrass Theorem. Over the base system$RCA_0$of second-order arithmetic, this statement is equivalent to arithmetic comprehension$ACA_0$(i.e. all arithmetical formulas define a set of natural numbers). Another option to completely rejecting (1), is to reject the possibility of iterating (1) arbitrarily often. Indeed, when applied to computable sequences of rationals, (1) only allows the comprehension of sets with Turing degree$\leq 0'$, so one needs to iterate (1) a lot in order to get all arithmetical sets... – François G. Dorais Jun 1 2011 at 14:34 ... However, I have yet to see a sensible formulation of "not being able to iterate" in this and similar contexts. – François G. Dorais Jun 1 2011 at 14:36 I think Harvey Friedman's claim was somewhat stronger, in that he doesn't assume the base theory $RCA_0$. Instead, he says he relies on some very basic mathematical (meaning not looking like logic or set theory) facts. This is an aspect of what he calls strict reverse mathematics, and it may well be relevant in the present context, since Voevodsky might reject $RCA_0$. – Andreas Blass Jun 1 2011 at 15:15 @Andreas: Thanks for the precision. @Sergey: You may find these drafts by Friedman of interest: math.osu.edu/~friedman/pdf/StrictRM012305.pdf math.osu.edu/~friedman/pdf/InevLogStr082907.pdf math.osu.edu/~friedman/pdf/… – François G. Dorais Jun 2 2011 at 22:50 François: thanks for the links. Andreas: It's not clear to me if the role of Strict RM in this context would be to reveal essential "facts" being used or rather to hide those ones revealed by ordinary RM behind a heavy ideology. In François' last link, under "Strict RCA$_0$" there is the following disguised form of second-order induction axiom: "every sequence [of integers] has a term of least magnitude" (and also some obscure "extensionality for sequences"). – Sergey Melikhov Jun 4 2011 at 20:01 show 3 more comments I am a little baffled by some of this discussion. It seems everyone agrees that consistency of PA is a theorem, if you accept some stronger system, such as ZFC. So, PA is consistent relative to ZFC. Just as obviously, you need something to prove consistency of PA; it could be$RCA_0$plus some presumably innocuous-looking axiom, but obviously$Con(PA)$doesn't come for free. Where it gets baffling to me is where the words like "believe", "suspicious", "doubts", etc. enter the discussion; those words properly belong to philosophy. If you take a platonist line, then you may be fairly asked what you "believe", and under those circumstances there is a kind of conventional belief that ZFC is simply true. But if you take a formalist line, then there is no commitment to belief; you just take some set of axioms and merrily apply first-order logic$^1$. (But if you are honest about that, then of course you declare what axiom system your theorems are relative to.) For instance, what Andreas Blass finds "strange, though, is to accept some parts of mathematics (e.g., real analysis) without expressing any doubts, while expressing doubts, based on ontological issues (doubts whether the integers exist), about statements like Con(PA) that seem to require far less ontological commitment than real analysis." It's not clear to me what 'ontological commitment' a skeptic of$Con(PA)$would have to particular statements of analysis$^2$, but a formalist will have none, and as Emerton points out (in his speculations on Voevodsky's likely reaction to one of Friedman's questions), there are plenty of seemingly innocent-looking analytic statements subject to constructivist 'doubt', if 'doubt' is indeed the right word to use here. (A formalist might prefer to say instead, 'constructively invalid'.) I can't see why any of this would be controversial. 1. First-order logic is a kind of bottom line for most formalists. There are some divergences as to whether one uses the principle of the excluded middle, or whether one treats equality as intensional or extensional -- much of Voevodsky's fascinating recent work is in intensional type theory and what might be termed its "homotopical semantics". 2. If someone is observed not to express doubts about certain analytic statements but express doubts about$Con(PA)$-- as has no doubt happened in the history of mathematics -- it doesn't necessarily mean that person is confused. It could simply mean that the person has decided to "go along with" ZFC in one discussion -- maybe he is "suspending disbelief" just for the sake of an interesting discussion -- but in another discussion with manifestly metamathematical overtones, he has decided to "reactivate disbelief". Or, maybe he is just being mum about his having or not having beliefs. - Dear Todd, I think that one reason for your confusion is that while (I want to guess) you are a formalist, many others are platonists. In particular, I think it is at least a priori possible to imagine that mathematics takes place prior to foundations of mathematics (this is at least historically true), and then it is harder to phrase results as being of a relative nature in a formalist nature; they instead are relative to certain basic beliefs. E.g. I believe that the real number as a complete ordered field exists, and then I deduce xyz about them; I believe that the natural numbers ... – Emerton Jun 2 2011 at 22:27 exist, with all their subsets, and so obtain a model of PA. (But not a model in ZFC; a model in some less formal sense, a mental model if you like.) Perhaps what I want to say is that Platonist beliefs can occur prior to foundational beliefs, so that one can admit certain beliefs without (necessarily) believing in ZFC. In fact, I think that this is close to how many practicing mathematicians work (they may say they believe in ZFC, but I'm not sure that that isn't just a social convention) --- I should say that I don't have anything but anecdotal evidence for this, though, so don't take ... – Emerton Jun 2 2011 at 22:30 ... it too seriously as an assertion. So let me close by saying that since I started reading online math forums, and so getting a broader cross-section of mathematical points-of-view than I get in person, I have been surprised at how many formalists there seem to be! (So, while you seem to find the formalist position more natural, and the platonist position perhaps less so, my situation is somewhat the reverse.) Anyway, none of this is meant as any criticism at all of your answer, which I think is very lucid; just as some commentary that might shed light on the aspects of the ... – Emerton Jun 2 2011 at 22:33 Timothy, while I may profess agnosticism about all such matters, I confess that I actually believe Con(PA). :-) I'd not heard the controversy you refer to; do you know some place in the literature where this is discussed? I admit that I'm not too sympathetic to the second of those two positions: it would carry little weight in the disastrous event that a formal deduction in PA of 0 = 1 were actually produced! – Todd Trimble Jun 3 2011 at 1:33 Timothy: (1) I was being serious, and (2) I believe you've made this point several times by now. I'm not sure which formalists you're imputing this behavior to, but I understand the point you're making. At the same time, surely for any theory T, "T is inconsistent" has the direct meaning that there is a deduction of the sequent$\top \vdash \bot$in T. – Todd Trimble Jun 4 2011 at 1:51 show 12 more comments I'd been very interested in foundational questions for a long time so I think I can say something about it. To understand the question I think it is necessary make some comment: mathematical logic is the study of mathematical theories via mathematics itself. To make theorem about theories first you have to define what is a formula, a theory and a proof, so first you need a (meta-)theory in which you make your demonstration about your theory: usually this (meta-)theory is Zermelo Fraenkel set theory without infinite axiom. This means that every proof of a theorem about a theory is valid if the meta-theory is consistent, if that's not the case then we cannot say anything because in a inconsistent theory you can deduce everything (that if you use classical logic). This says that we cannot prove the consistency of a theory in an absolute sense but we can only reduce consistency of a theory to the consistency of another theory: so I think today is pointless wonder if PA is consistent, unless you don't believe in the existence of natural number which satisfy all of the Peano Axioms, such existence is the proof of consistence of PA, because it's well know (or I hope so) that a theory with a model is consistent. (In particular if you accept the consistence of ZFC the you can prove PA consistency in this theory). Just one more thing: if you don accept the existence of natural numbers which satisfy PA (and so of a universe which is a model of ZFC) then you cannot accept lots of mathematics that is derived from it. I hope this answer your question. -  Dear ineff, Regarding "you cannot accept lots of mathematics that [is] derived[d] from it"; it may be that you instead accept some constructivist versions of standard mathematical theorems. I think there are many (or at least some) working mathematicians who go along with ZFC (so to speak) but have something of a constructivist view, in that they believe that their theorems are of a sufficiently constructive nature that it doesn't really matter what the background foundational theory is. Regards, Matthew – Emerton Jun 2 2011 at 22:24 Note that PRA is sufficient for most meta-theoretic purposes. (You can do pretty much everything except model theory.) Also, PRA is considerably weaker than PA. – François G. Dorais♦ Jun 2 2011 at 22:34 @Emerton: thanks for the correction, I edited; @Emerton and F.G. Dorais: I didn't mean that ZFC is the only system we can use, anyway it's well know that a lot of mathematics cannot be derived without those systems or without something with the same deductive power. By the way the point of my discussion was that: 1. a proof of consistence is just a reduction of the consistence of a theory to the consistence of the meta-theory (so in the end we have to accept some theory without any proof of is consistence); 2. if we accept the existence of a model for PA we also have to accept its consistence. – Giorgio Mossa Jun 3 2011 at 7:38 I have already posted an answer but in light of the discussion and the kinds of confusions that have emerged, I believe that this additional answer will be helpful. Let us first note that the consistency of PA, or more precisely a certain formalized version of it that I will call "Con(PA)," is a theorem of Zermelo-Fraenkel set theory (ZF). Conceptually, the simplest ZF proof is obtained by formalizing the easy and almost trivial argument that N, the natural numbers, is a model of PA. ZF is an extremely powerful system, and the full power of ZF is not needed for proving Con(PA). Famously, Gentzen showed that primitive recursive arithmetic (PRA), a very weak system, can prove Con(PA) if you add the ability to do induction up to the countable ordinal$\epsilon_0$. Other ways to prove Con(PA) are available. Let B-W denote the statement that "every bounded sequence of rational numbers contains a subsequence$(q_i)$such that for all$n$,$|q_i - q_j| < 1/n$for all$i, j > n$." Then B-W implies Con(PA), and this implication can certainly be proven in the system RCA$_0$, and (according to Harvey Friedman) actually much less than RCA$_0$is needed. Most mathematical statements are no longer considered "open problems" once a proof has been published or otherwise made widely available, and checked and confirmed by experts to be correct. Note that published proofs, and expert verification, usually make no explicit reference to any particular underlying formal system such as ZF or PRA. Mathematicians are trained to recognize correct proofs when they see them, even if no set of axioms is explicitly specified. If pressed to specify an axiomatic system, a common choice is ZF, or ZFC (ZF plus the axiom of choice). If a proof is available that is explicitly formalizable in ZF, that is normally regarded as more than sufficient for settling an assertion and removing its "open problem" status. In the case of Con(PA), the aforementioned "normal conditions" for removing its "open problem" status have been met, and in fact exceeded. Nevertheless, some debate continues over its status, most likely because Con(PA) is widely perceived to be a somewhat unusual mathematical statement, having connections to philosophical questions in the foundations of mathematics. For example, some people, whom I will loosely call "formalists" or "ultrafinitists," maintain that many ordinary mathematical statements (e.g., "every differentiable function is continuous") have no concrete meaning, and the only concrete thing that can be said about them is whether they can or cannot be proved in this or that formal system; however, a statement such as "PA is consistent" is regarded as having a direct, concrete meaning. Roughly speaking this is because "PA is inconsistent," unlike infinitary mathematical statements, can be assigned a quasi-physical meaning as the existence of a certain finite sequence of symbols that we can physically apprehend. While the formalist agrees with all the above facts about the provability of Con(PA) in this or that formal system, such formal proofs don't necessarily carry any weight with the formalist as far as establishing the consistency of PA (in what I've called the "quasi-physical" sense) goes. Formalists will generally agree that explicitly exhibiting a contradiction in PA will definitively establish its inconsistency, but may differ regarding what, if anything, would definitively establish its consistency. There are others who are not formalists but who reject the commonly accepted standard of ZF(C) and only accept proofs that are formalizable in much weaker systems. For example, someone with strong constructivist leanings might only accept proofs that are formalizable in RCA$_0$. For such a person, the proof of Con(PA) in ZF carries no weight. Roughly speaking, the usual ZF proof, that proceeds by showing that N is a model of the axioms of PA, assumes that any first-order formula defines a set of natural numbers, and this assumption is unprovable on the basis of RCA$_0$alone. In fact, one can prove that Con(PA) is unprovable in RCA$_0$. Such a person might regard the consistency of PA as permanently unknowable (in a way similar to those who regard the continuum hypothesis as permanently unknowable since it has been proved independent of ZFC). Note, by the way, that this person would also regard a sizable portion of generally-accepted mathematics (including Brouwer's fixed-point theorem, the Bolzano-Weierstrass theorem, etc.) as being "unproved" or "unprovable." To summarize, the consistency of PA is not an open problem in the usual sense of the term "open problem." Some people do nevertheless assert that it is an open problem, or that it has not been proven. When you encounter such an assertion, you should be aware that most likely, the person is using the term "open problem" in a somewhat nonstandard fashion, and/or holds to certain standards of proof that are more stringent than those that are commonly accepted in the mathematical community. Finally, to answer the new question that Franklin has asked, about whether the consistency of any of the systems in which Con(PA) has been proved has been proved: The answer is, "not in any sense that you would likely find satisfying." For example, one can "prove" that PRA + induction up to$\epsilon_0$is consistent, in the sense that the consistency proof can be formalized in ZF, which as I said above is the usual standard for settling mathematical questions. If, however, the reason that you're asking the question is that you doubt the consistency of PA, and are hoping that you can settle those doubts by proving the consistency of PA in some "weaker" system that can then be proved consistent using "weaker" assumptions that you don't have any doubts about, then you're basically out of luck. This, roughly speaking, was Hilbert's program for eliminating doubts about the consistency of infinitary set theory. The hope was that one could prove the consistency of (say) ZF on the basis of a weak system such as (say) PRA, about which we had no doubts. But Goedel showed that not only is this impossible, but even if we allow all of ZF into our arsenal, we still can't prove the consistency of ZF. For better or for worse, this tempting road out of skepticism about consistency is intrinsically blocked. - wow! thank you. – Franklin Jun 3 2011 at 3:06 Following up on the last paragraph: this is in no way unique to Con(PA). We know in an informal and somewhat trivial way that "to prove a theorem you have to make assumptions at least as strong as the conclusion." This is reflected formally in the Lindenbaum algebra of each formal theory. It is reflected philosophically in the debate whether mathematical truth is analytic. In this sense every mathematical proof (of a non-logical validity) is circular. This is noticed most often in the context of consistency proofs but I do not see them as special in this way. – Carl Mummert Jun 3 2011 at 12:50 To be specific, I'll focus on the second question of the title, "Is PA consistent? do we know it?" As noted by Noah Snyder on the meta thread, this question itself already uses "philosophical" language like "know". So I think it may be viewed it as$\bullet$a question in mathematics, if you accept a specific philosophical position such a form of platonism, formalism, constructivism, or ultrafinitism; or$\bullet$a question in philosophy of mathematics, if you remain ignostic regarding the meaning of "know". So as to stay on-topic, I will only consider the first possibility, and only those four positions that it explicitly lists. In fact, for a constructivist's view I absolutely support what Emerton said (only I'm not sure about the border between what Voevodsky actually claimed in his talk vs. what he might have meant), and for a formalist's view I agree completely with Todd Trimble's answer. (Indeed, before these two answers appeared I had felt something of those kinds was badly missing from this discussion.) Regarding an ultrafinitist's view, I think Mirco Manucci has a point, and I'll incidentally elaborate on another important point made by Qiaochu Yuan on the meta thread. So I will now pretend that I'm a platonist (which is what I usually do when attacking some problem - but certainly not when writing up a proof) and in doing so I'll try to argue that Timothy Chow's first answer is simply wrong. ("Wrong" in platonist's absolute, undefinable sense.) The problem with Timothy's argument is that it unfairly exploits our subconscious reading of some words in a mathematical text. When I'm stating a theorem, in a paper or in a talk, I almost never put it like "Theorem (ZFC)." or "Assume ZFC. Then ..." because my area of geometric topology is (or at least is commonly thought to be) very far from foundations, and such pronouncements, commonly seen as tautological, would be very distracting. But I do mean it. (Not that I like ZFC too much, especially so with the uncountable "C" which strikes me as really awful in the context of ZF. But I recognize that socially and in terms of the existing literature to refer to, I don't have much choice - so all my results are, alas, meant to be in ZFC by default.) I also don't start papers and talks by saying that everything will be in ZFC, for the same reason that this information is (as long as my field is concerned) obvious and distracting, and hence is likely to be a repelling factor; and moreover because of my personal negative emotions towards ZFC. I did, in fact, on one occasion stated a "theorem (ZFC)" in a talk, but only to emphasize that I'm not assuming CH or PFA like some previous authors did. I'm assuming that other authors may have somewhat similar considerations, so in papers, books and talks in my area, I'm reading every "theorem" as a "theorem (ZFC)", or at least as what could have been meant by the author to be a theorem in ZFC. There seem to exist people who don't read theorems in this way (I'm thinking, in particular, of applied mathematics and mathematical physics; of Vladimir Arnold; and of experimental mathematics and computer science) but certainly N. Bourbaki and his faithful readers do read them in this way; I also suspect some countries including France and Poland to have more of this tradition than some other ones. The same of course applies to lemmas, problems and conjectures. Now the situation is different in foundations. You certainly don't read "Problem. Is PA consistent?" as "Problem (ZFC). Is PA consistent?" - at least if you have ever heard of Hilbert's, Goedel's and Gentzen's work on this subject. In set theory, authors usually make it clear what formal system is assumed in their book, chapter or theorem. In other subjects such as proof theory and model theory I understand that the situation is rather complex, but it seems that the prevalent convention in some areas where PA or the second-order arithmetic are more relevant than ZFC is that by default, a "Theorem" could read as "Theorem (no hypotheses whatsoever)." What exactly "no hypotheses whatsoever" means is a separate question, but for the moment I'd like to note that the linguistic/pshychological issue of the clash of conventions for reading words like "theorem", "problem" and "proof" is not mentioned in Timothy's first answer, yet is central to its understanding. For this reason I dismiss his argument as pure sophistry. This doesn't yet address his conclusion - that Con(PA) is true (in the sense of Plato) because we know (in the sense of Plato) a model of PA. (By the way, this purported knowledge usually turns out to be an implicit hypothesis in the "no hypotheses whatsoever" reading.) But how could we possibly know that what we usually refer to as "1,2,3,..." (I will abbreviate this as$\Bbb N$) is indeed a model of PA? (Note that "1,2,3,..." is only a name, and not a model itself, due to the presence of the undefined/circularly defined symbol "...".) I see only 3 possibilities: 1) by virtue of a religious belief; 2) we could know it from experience, by having a physical model of PA; 3) we could know it from the mind, by demonstrating logically that$\Bbb N$must be a model of PA. In connection with the off-topic possibility (1), which I'm not denying, let me only mention some sources: (a) Poincare has devoted quite a few interesting pages to argue for his view that the axiom of induction is a synthetic a priori judgement, (b) Goedel, and in more detail Roger Penrose used the hypothesis that$\Bbb N$is a model of PA to argue rather convincingly for certain philosophical propositions related to religion. The off-topic possibility (2) would have strong consequences for physics, which have not been established yet: given a physical model of PA, apparently either the "physical universe" (the past light cone) is a non-compact 3-manifold; or there can be an infinite amount information within its bounded region, which would contradict the holographic principle (which holds in some flavors of string theory) and also some rivals of string theory such as loop quantum gravity (which involves a quantized, rather than Euclidean, space-time). Finally, the possibility (3). Parikh and Sazonov have shown (assuming our knowledge of a model of PA) that there exist "truncated" versions of PA which are contradictory due to the truncation, yet the shortest proof of contradiction is too long to fit within the theory; thus the theory doesn't "see" itself as being contradictory. Now imagine a finite computer$X$on which a Peano-Sazonov arithmetic is implemented. If we happen to have a model of PA, or a bigger computer$Y$(without tricks) at hand, we could be able to use$Y$to verify that$X$does not emulate PA correctly, and so$X$could be finite. But without$Y$, I don't see how to do it. So it looks like$X$must seem infinite to its user (unless the user's mind is bigger than$X$). Could our$\Bbb N$be just a kind of the computer$X$? That is, could God have faked Sazonov integers for us, and kept Peano integers for himself? I don't see any reason why this couldn't have happened. Please correct me if I'm wrong. (I can't resist recalling that while most people are aware nowadays that the Earth is not flat, the notion of$3$-manifolds other than$\Bbb R^3$still does not occur to many people outside academia in connection with the physical universe.) The conclusion is that we don't know that$\Bbb N$is a model of PA; it is an open problem (in platonist's sense, no hypotheses whatsoever, in particular no assumptions regarding our knowledge of a model of PA). Hence there's also no known reason why Con(PA) couldn't be an open problem (in the same sense). - As noted by Noah Snyder on the meta thread, this question itself already uses "philosophical" language like "know". This is high in criticism, for Many MO questions do this, with the word Why. As a timely simple example, there is "Why do$H_4$and$M_4\$ have the same virtual Euler characteristic?" and I can't dread the poster wants an answer like "because computation X shows it as -1/1440 for each case". I do not count, but I suspect ~25% or more of MO questions are really aimed more philosophical in nature, as the sense of being explanatory of a fact, than just directly what the fact is. – Junkie Jun 5 2011 at 4:33
Junkie: I didn't intend this as a criticism, but only to point out that the question can have many correct answers. Thank you for clarification. – Sergey Melikhov Jun 5 2011 at 11:06


text:
# Multirow to combine cells

I'm trying to make a table as shown below with all the horizontal and vertical lines. Please help.

• Welcome to TeX.SX! Your question right now shows no effort and doesn't focus on a specific difficulty you're having in achieving this layout. Can you add a minimal working example (MWE) that shows what you have so far, and mention in the question which part you're having problems with? – Paul Gessler Feb 18 '15 at 20:02

\begin{table}[htbp]
\centering
\begin{tabular}{rr}
\toprule
title 1 & title 2 \\
\midrule
a     & \multicolumn{1}{c}{\multirow{2}[0]{*}{c}} \\
b     & \multicolumn{1}{c}{} \\
d     & \multicolumn{1}{c}{\multirow{2}[0]{*}{f}} \\
e     & \multicolumn{1}{c}{} \\
\bottomrule
\end{tabular}%

• For new users it may not be obvious which packages are required for this code (booktabs and multirow), so if you edit the example to make it a complete, compilable document, it would be more useful. Also, I don't think any of those \multicolumns are necessary. Why not just make the column a c column instead of r? – Torbjørn T. Mar 8 '15 at 8:44

format: plain


text:
$z_0 \equiv (x+k_0)^2-(x+k_0)y \ (mod\ n_0)$
$z_1 \equiv (x+k_1)^2-(x+k_1)y \ (mod\ n_1)$
a $z_m \equiv (x+k_m)^2-(x+k_m)y \ (mod\ n_m)$
I know the values of all the $z_i$, $k_i$, and $n_i$ $\forall i$, and I wish to solve for $x$ and $y$. All $n$s are co-prime if that helps.


text:
# Prove Or Disprove: tr(AB)=tr(A)*tr(B)

$\mathrm{tr}(AB)=\sum\limits_{i=1}^n \sum\limits_{j=1}^n a_{ij}*b_{ji}$
$\mathrm{tr}(A)*\mathrm{tr}(B)=\sum\limits_{i=1}^n a_{ii}*\sum\limits_{i=1}^n b_{ii}$

Therefore $\mathrm{tr}(AB) \neq \mathrm{tr}(A)*\mathrm{tr}(B)$

Is the proof valid?

• $\sum a_i\sum b_i\neq \sum a_ib_i$!!! – Pedro Tamaroff Jul 27 '14 at 4:27
• Is there a question? (If you want your proof validated, say so and include the proof-verifcation tag). – Semiclassical Jul 27 '14 at 4:28
• Done the edit, and now? – gbox Jul 27 '14 at 4:29
• (What is true, however, is that ${\rm tr}(AB)={\rm tr}(BA)$ – Pedro Tamaroff Jul 27 '14 at 4:33
• It is true for $n = 1$... – Ivo Terek Jul 27 '14 at 4:45

It is false. Let's think small. Consider the identity matrix, of order $n > 1$. Then: $$n = \mathrm{tr}(I) = \mathrm{tr}(I \cdot I) \neq \mathrm{tr}(I)~ \mathrm{tr}(I) = n^2$$ It is important to try some silly cases and gain intuition about the affirmation before tackling summations, etc.


text:
# Posterize

The Posterize Node reduces the number of colors that compose the image by converting portions of continuous gradation into abrupt changes from one color to another. This node is useful for generating masks in particular for rotoscoping.

## Inputs

이미지

Standard color input.

Steps

The number of colors per channel; A value of 8 will result is $$3^8 = 512$$ total colors.

## 특성

This node has no properties.

## Outputs

이미지

Standard color output.


text:
# Odd behaviour in LibreOffice Calc SUM function

Ok, i have a weird one here. Calc has always done what was expected, until I ran into a strange calculation.

I am running the standard Ubuntu distributed LibreOffice - Build ID: 1:5.1.6~rc2-0ubuntu1~xenial1

Beginning at A1, going down through A8. (numbers validated for accuracy - no hidden formatting - I initially thought I entered something wrong the first time, so manual entered it into a new sheet with the same result)

 9.99
14.99
775.18
-26.44
-1.13
-280.24
-280.24
-212.11

In Cell A9, I put.

=SUM(A1:A8)

Cell A9 should contain 0, but instead shows

-1.22568621918617E-13

If I change cell A8 to

-212.1

Cell A9 shows 0.01 as expected.

Change it back to -212.11, and you get the weird result again.

Placing it in a single statement like..

=SUM(9.99,14.99,775.18,-26.44,-1.13,-280.24,-280.24,-212.11)

Also results in the correct answer of 0.

Formatting on all cells is "number -> general"

If I force the format to "number -> -1234", the display is correct.

Any ideas what's going on?

Thanks,

Brent

edit retag close merge delete

Sort by » oldest newest most voted

Hi

I reproduce if ToolsOptionsCalcCalculateLimit decimals for general number format unticked

Regards

more
more

How can this be a hardware limitation. This is simple addition/subtraction. Computers get this right all the time. I could see if you did division with a repeating decimal being rounded and being limited by the number of decimal paces that were being calculated leading to a small error, but this is simple stuff you can get 100% right with a pencil and piece of paper.

( 2017-03-25 17:37:15 +0200 )edit

It's just because you presume that numbers are handled by your computes with pencil and paper inside. Actually, they are not. They aren't stored as decimals, that have finite representation as you input them. They are stored as binary numbers, that do have infinite representation, and so have rounding errors here.

To see it, you may use =SUM(A2:A9), and have -9,99000000000013. Excel will show -9,99000000000012. They differ because of opposite direction of computation, but error is there.

( 2017-03-25 18:13:19 +0200 )edit

The following formulas give exactly same results in Calc and Excel:

• =SUM(A8;A7;A6;A5;A4;A3;A2) -> -9,99000000000013
• =SUM(A2;A3;A4;A5;A6;A7;A8) -> -9,99000000000012
• =SUM(A8;A7;A6;A4;A3;A2) -> -8,86000000000014
• =SUM(A8;A7;A6;A3;A2) -> 17,5799999999999
• =SUM(A8;A7;A6;A4;A3) -> -23,8500000000001
• =SUM(A8;A7;A6;A3) -> 2,58999999999992
( 2017-03-25 18:25:12 +0200 )edit

I can't reproduce in Excel 14.0.7177.5000 (32-bit). Is there a setting in excel to make it exhibit the same behavior?

either way, I will change my setting to enabled for

Tools▸Options▸Calc▸Calculate▸Limit decimals for general number format

and call it a day.

If this is the answer, I believe the default should be changed. The results provided are not intuitive and would limit many peoples confidence in LibreOffice to provide accurate results.

Just my 2 cents

( 2017-03-27 19:19:13 +0200 )edit

To see the results above, you'd need to increase number of decimal places.

And you may just enter your data to Excel in reversed order, and see the sum.

( 2017-03-27 19:32:16 +0200 )edit

As a update to @bmclaren 's answer: In my Mac UI the setting was behind File -> Preferences -> LibreOffice Calc -> Calculate

( 2018-04-13 08:10:37 +0200 )edit

Cannot believe, this 'hardware limitation' is still not worked around by default. as software engineer i can say, this is a typical problem, where the devs dont give a damn what users are experiencing. thank you bmclaren, your workaround helped me out.

( 2019-02-10 23:47:32 +0200 )edit

Working around this hardware limitation by default would at least (1) slow down the program manyfold, and (2) break existing documents. So please don't treat not changing this as what you typically do being a software engineer.

( 2019-02-11 06:55:48 +0200 )edit


text:
# An analysis of variance produces SS_(total)=40 and SS_(within)=10. For rhis analysis, what is SS_(between)?a) 30b) 400c) Cannot be determined grom the information givend) 50

An analysis of variance produces $S{S}_{total}=40$ and $S{S}_{within}=10$. For rhis analysis, what is $S{S}_{between}$?
a) 30
b) 400
c) Cannot be determined grom the information given
d) 50

You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Nathalie Redfern

$S{S}_{between}=S{S}_{total}-S{S}_{within}$
$S{S}_{between}=40-10$
$S{S}_{between}=30$


text:
Flexible Signatures: Towards Making Authentication Suitable for Real-Time Environments

Duc Viet Le, Mahimna Kelkar, and Aniket Kate

Abstract

This work introduces the concept of flexible signatures. In a flexible signature scheme, the verification algorithm quantifies the validity of a signature based on the number of computations performed such that the signature's validation (or confidence) level in $[0,1]$ improves as the algorithm performs more computations. Importantly, the definition of flexible signatures does not assume the resource restriction to be known in advance until the verification process is hard stopped by a system interrupt. Although prominent traditional signature schemes such as RSA, (EC)DSA, EdDSA seem unfit towards building flexible signatures, we find updated versions of the Lamport-Diffie one-time signature and Merkle authentication tree to be suitable for building flexible signatures. We present a flexible signature construction based on these hash-based primitives and prove its security with a concrete security analysis. We also perform a thorough validity-level analysis demonstrating an attractive computation-vs-validity trade-off offered by our construction: a security level of $80$ bits can be ensured by performing only around $\frac{2}{3}$rd of the total hash computations for our flexible signature construction with a Merkle tree of height $20$. We see this work as the first step towards realizing flexible-security cryptographic primitives. Beyond flexible signatures, our flexible-security conceptualization offers an interesting opportunity to build similar primitives in the asymmetric as well as symmetric cryptographic domains. Apart from being theoretically interesting, these flexible security primitives can be of particular interest to real-time systems as well as the Internet of things: rigid all-or-nothing guarantees offered by the traditional cryptographic primitives have been particularly unattractive to these unpredictably resource-constrained

Note: Minor changes to abstract, implementation, and proofs

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Contact author(s)
le52 @ purdue edu
History
2019-07-10: last of 2 revisions
See all versions
Short URL
https://ia.cr/2018/343

CC BY

BibTeX

@misc{cryptoeprint:2018/343,
author = {Duc Viet Le and Mahimna Kelkar and Aniket Kate},
title = {Flexible Signatures: Towards Making Authentication Suitable for Real-Time Environments},
howpublished = {Cryptology ePrint Archive, Paper 2018/343},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/343}},
url = {https://eprint.iacr.org/2018/343}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.


text:
• MRITUNJAY KUMAR SINGH

Articles written in Journal of Earth System Science

• Longitudinal dispersion with time-dependent source concentration in semi-infinite aquifer

An analytical solution is obtained to predict the contaminant concentration along unsteady ground-water ﬂow in semi-in ﬁnite aquifer. Initially,the aquifer is not supposed to be solute free ,i.e.,aquifer is not clean.A time-dependent source concentration is considered at the origin of the aquifer and at the other end of the aquifer, it is supposed to be zero. The time-dependent forms of unsteady velocities are considered in which one such form ,i.e., sinusoidal form represents the seasonal pattern in a year in tropical regions. The Laplace Transformation Technique (LTT)is used to get an analytical solution and a graphical representation is made through MATLAB.

• Groundwater contamination in mega cities with finite sources

Groundwater contamination due to multiple sources occurring in mega cities was modelled. One constant source contamination was considered at the source boundary, whereas other sources may join in between at various locations at different times. Initially, the aquifer was contamination-free in mega cities and was subsequently contaminated by means of different sources in due course of time. One-dimensional ADE (Advection Dispersion Equation) for modelling groundwater contamination was used and solved analytically in the semi-infinite aquifer domain for a finite number of point sources. A numerical solution wasalso obtained for two sources to compare analytical solutions. Results were examined for different velocity profiles to show the maximum contaminant concentration level with distance. This may be helpful to model the maximum possible number of point sources of contamination (i.e., it represents approximately what happens in the field situation). Some remedial measures may be taken to overcome these kinds of contamination problems in mega cities by treating the sources so that recharge of the aquifer is not affected.

• InCuence of Cuid viscosity and Cow transition over non-linear Bltration through porous media

The present study investigates two important though relatively unexplored aspects of non-linear filtration through porous media. The first aspect is the influence of viscosity variation over the coefficients of the governing equations used for modelling non-linear filtration through porous media. Velocity and hydraulic gradient data obtained for a wide range of fluid viscosities (8.03E-07 to 3.72E-05 N/m$^2$) were studied. An increase in fluid viscosity resulted in an increased pressure loss through packing which can be quantified using the coefficients of the governing equations. Coefficients of Forchheimer equation represent linearly increasing trend with the kinematic viscosity. On the other hand, coefficient of Wilkins equation represents similar values for different Cuid viscosities and remained unaffected by the variation in packing properties. Obtained data were utilized to understand the nature of flow transition in porous media. Behaviour of polynomial and Power-law coefficient with variation in Cow velocity were also examined. Critical Reynolds number corresponding to the deviation of flow from Darcy regime varies with the porous packing and was observed to be in the range of 0–100. Coefficients of polynomial (Forchheimer) model were observed to be independent of the range of flow velocity, whereas the Power law coefficients are extremely sensitive to the data.

• # Journal of Earth System Science

Volume 130, 2021
All articles
Continuous Article Publishing mode

• # Editorial Note on Continuous Article Publication

Posted on July 25, 2019


text:
# A balanced equation for combustion of methane is given below:
 CH_(4(g)) + 2O_(2(g)) to CO_(2(g)) + 2H_2O_(g)
 Which of the following statements is not correct on the basis of the above chemical equation? (A) one mole of CH4 reacts with 2 moles of oxygen to give one mole of CO2 (B) one molecule of CH4 reacts with 2 molecules of oxygen to give one molecule of CO2 and 2 molecules of water (C) 22.4L methane reacts with 44.8L of oxygen to give 44.8L of CO2 and 22.4L of water (D) 16g of methane reacts with 64g of O2 to give 44g of CO2 and 36g of water

Step by step solution by experts to help you in doubt clearance & scoring excellent marks in exams.

Updated On: 4-3-2021

Apne doubts clear karein ab Whatsapp par bhi. Try it now.

One mole of CH_4 reacts with 2 moles of oxygen to give one mole of CO_2 and 2 moles of water.One molecules of CH_4 reacts with 2 molecules of oxygen to give one molecule of CO_2 and 2 molecules of water.22.4 L of methane reacts with 44.8 L of oxygen to give 44.8 L of CO_2 and 22.4 L of water.16 g of methane reacts with 64 g of O_2 to give 44 g of CO_2 and 36 g of water.


text:
# How to interpret shapley force plot for feature importance?

I am trying to practice and learn shapley value approach to explain my predictions on a binary classification problem. However am having difficulty in understanding the below plot.

1) Does it indicate the day_2_balance influences prediction to 1? or does blue values leads to prediction 1

2) What about the axis scale? (-4.357 to 5.643)

3) What does base value mean?

4) When I hover around the pink color , I see few more column names with some values. What do they indicate?

5) does the size of features represent their importance? Meaning PEEP_min=5 has a larger size than other features?

6) What does higher to lower and lower to higher indicate?

Can someone help me with this?

I've never practiced this package myself, but I've read a few analyses based on SHAP, so here's what I can say:

1. A day_2_balance of 532 contributes to increase the predicted output. In this area, such a value of day_2_balance would let to higher predictions.
2. The axis scale represents the predicted output value scale. The actually predicted value is in bold font (-2.98). I don't know if the min and max values of the scale represent true min and max of the model predicted values. They more likely result from automatic scaling of the plot.
3. Base value should be the mean value of the estimator over the whole input space.
4. Those indicate the other features of which value influence the prediction to a higher value. Features are sorted by local importance, so those are features that have lower influence than those visible.
5. Yes, but only locally. On some other locations, you could have other contributions
6. higher/lower is a caption. It indicates if each feature value influences the prediction to a higher or lower output value.

From the example plot, you can draw the following interpretation: "sample n°4100 is predicted to be -2.92, which is much lower than the average predicted value (~0.643), mostly due to the specific values of features PEEP_min(5), Fi02_100_max (50), etc., and although day_2_balance is 532".

• Hi, upvoted for the help.but when my output class is 0 or 1 why does it predict it as -2.92? I mean am working on binary classification problem – The Great Dec 27 '19 at 9:08
• Sorry, did not get that at first sight. Explanations above are for regression. I'm not quite sure how it works for multi-output cases (including classification), this should be some kind of score for the selected class, higher score meaning that the prediction tends towards this class. So in that case, the tested class would not be favoured by the model, due to the explanations listed in my original answer. As this is a binary problem, if you try the other class, you should get reversed results, with more red. – Romain Reboulleau Dec 27 '19 at 21:55


text:
# How to ensure that two objects do not intersect before collision?

I am dropping an object on top of another and I'm noticing some odd behavior. The object that falls intersects the object that it falls on top of:

It then proceeds to "wobble":

I have the following properties set for the objects:

What causes this to occur and how can I prevent the two objects from intersecting at all?

Here's a link to the .blend that demonstrates the problem:

• Increase simulation precision and number of steps Mar 6 '18 at 19:17
• @DuarteFarrajotaRamos how would one go about that? Mar 6 '18 at 19:21
• blender.stackexchange.com/questions/99027/… Mar 6 '18 at 19:28
• I would be careful with increasing the simulation quality unless absolutely necessary, as it can often 'mask' other issues and also slow down the simulation significantly. See my answer below for some options to get a better result. Mar 6 '18 at 21:25

Short Answer: Switch the collision shape on each object to Box, and you're good to go.

Poor collisions are generally due to a combination of a few things:

First is the precision of the simulation. Increasing the quality of the simulation should help, but this will slow down the simulation considerably. Usually you can get away without increasing the simulation precision.

Second is the density of the colliding meshes. A subdivided plane has more geometry to work with, and will collide better than a plane. In your file, adding 3 edge loops on the X and Y axes of the floor object gave the simulation enough geometry to run perfectly. This isn't always the best solution of course, as often times dense meshes are undesirable.

Final thing is how the collisions are being calculated. Blender has a number of different collision shapes that can be used. The geometric shapes (box, sphere, etc.) will always be the most stable as they are the most simple. In your case, both your objects are boxes of some form, so using box collisions will be best. Testing this confirms this, as switching both to Box fixes the collisions and the simulation is very stable as well.

The other types of collisions can work as well, and using the Mesh option (which uses the actual shape of the mesh as the collision object) on each object did give decent collisions, but they were far from perfect. Adding some more geometry to the floor object did help significantly though when using Mesh. Convex Hull (which uses a collision object that is always convex while still fitting the object as best it can) doesn't appear to work at all in your case, as it seems to do a poor job of determining a good collision shape for a box like object. Adding a bit of geometry and changing the shape to be slightly rounded made it work great though.