Questions tagged [provability]

For questions on provability, the capability of being demonstrated or logically proved.

151 questions
13k views

Is there any conjecture that has been proved to be solvable/provable but whose direct solution/proof is not yet known?

In mathematics, is there any conjecture about the existence of an object that was proven to exist but that has not been explicitly constructed to this day? Here object could be any mathematical object,...
18k views

What is a simple example of an unprovable statement?

Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements. I've seen a simple natural language ...
6k views

Is there any conjecture that we know is provable/disprovable but we haven't found a proof of yet?

I know that there are a lot of unsolved conjectures, but it could possible for them to be independent of ZFC (see Could it be that Goldbach conjecture is undecidable? for example). I was wondering if ...
5k views

BIG LIST: Statements that look obviously false but cannot be disproved

I'm looking for statements that look obviously false but have no disproof (yet). For example The base-10 digits of $\pi$ eventually only include 0s and 1s. To make this question a little objective, ...
2k views

Statement provable for all parameters, but unprovable when quantified

I've been reading a book on Gödel's incompleteness theorems and it makes the following claim regarding provability of statements in Peano arithmetic (paraphrased): There exists a formula $A(x)$ ...
864 views

Can unprovability unprovable? Is there an $\omega$-fold unprovability?

I was just thinking about unprovability. I just wanted to know if it is possible to make a concrete boundary between provable problems and unprovable problems in a certain axiomatic system. We know ...
2k views

Is it really impossible to lose the Hydra game?

In a number of blog posts I found the claim that the game described below cannot be lost, which is to say, every possible strategy is a winning strategy. In each case, a sketch proof is given that ...
302 views

Growth-rate vs totality

How can one prove the statement, "If a function grows fast enough, it cant be proven total in PA, unless PA is inconsistent"? How fast must it grow to be not provably total?
2k views

Were there any proofs of whether or not a statement could be proved true or false before Gödel's Incompleteness Theorems?

I know of the continuum hypothesis (CH) and how it was proven to be unprovable under ZFC, but this was after Gödel's incompleteness theorems. And in fact Gödel (and Paul Cohen) were the ones who ...
1k views

Is every property of the integers provable?

I've been researching provability of properties, and I came across and interesting argument which states that every property of the integers is provable, yet doesn't the incompleteness theorem tell us ...
859 views

A sentence asserting about itself that if it is provable, then it is true

In $\S$II.2 (vol. 1, p. 170) of his book on classical recursion theory, Odifreddi claims that the sentence asserting of itself that if it is provable then it is true "is true and provable." His ...
786 views

What's the difference between “unprovable” and “undecidable”?

It seems to me that there is a difference between an unprovable sentence, and an undecidable sentence, but sometimes I have the impression that some authors use the terms interchangeably. In my ...
890 views

Does a proof by contradiction always exist?

Good day, Usually, proofs by contradictions are the easier, and sometimes, even the only ones available. However, there are cases where the easiest proof is not the proof by contradiction. For ...
910 views

Difference between 'true' and 'provable'

For a long time now I've been confused about the difference between truth and provability. I've also read questions like this but I still don't understand it. A typical example of my confusion is the ...
191 views

Brutal gaussian integral of death $\int_{\mathbb{R}} x \Phi(x) \phi(Bx-b)$

Ciao, I was making some computation and I've been stucked in this one. Let $B$ and $b$ be positive contant. We call $\phi(x)$ standard gaussian distribution and $\Phi(x)$ its cumulative function, i....
449 views

Semantics for minimal logic

Minimal logic is a fragment of intuitionistic logic that rejects not only the classical law of excluded middle (as intuitionistic logic does), but also the principle of explosion (ex falso quodlibet). ...
54 views

How to prove an inequality

$a$, $b$, $c$, $d$ are rational numbers and all $> 0$. $\max \left\{\dfrac{a}{b} , \dfrac{c}{d}\right\} \geq \dfrac{a+c}{b+d}\geq \min \left\{\dfrac{a}{b} , \dfrac{c}{d}\right\}$ Hope someone ...
492 views

Can an unprovable statement be interpreted as being generally true in some cases?

For example, let's say that Goldbach's conjecture turns out to be unprovable. This would mean that a program cannot devise a way to check whether any counterexample exists. This seems to mean that ...
268 views

Is it possible that two theories be equiconsistent, with Peano Arithmetic not able to prove this?

Do there exist first-order theories that are are equiconsistent, but which cannot be proven to be equiconsistent using Peano Arithmetic? (I hope not.)
281 views

Where is my Collatz conjecture proof wrong?

I am amateur and don't have very good understanding of mathematical proving. My proof is so simple i don't believe noone thought of this before. But I am so blinded by the hope it is correct, that I ...
108 views

Being not “close” to ZFC and not “far away” from it at the same time

For each formula $\varphi$ we can have a look at the following two properties: $$1) ZFC \not \vdash Con (ZFC) \rightarrow Con (ZFC + \varphi)$$ $$2) ZFC + \varphi \not \vdash Con (ZFC)$$ Intuitively, ...
80 views

Can the negation of an unprovable true statement be added as an axiom?

Let $S$ be some statement which is unprovable but true in an axiomatic system $T$. If $T$ is consistent, then adding $S$ as an axiom of $T$ keeps the system consistent. But what about adding $\neg S$ ...
145 views

What portion of mathematical statements are ZFC undecidable?

From Godel's Incompleteness Theorem we conclude that for any logically consistent set of a finite number of axioms, there are an infinite number of mathematical statements that are true but can't be ...
689 views

Goldbach's conjecture can't be proved to be undecidable?

Conjectures concerning natural numbers which could be settled by a counterexample can, as far as I understand, not be proved to be undecidable without being proved not having a counterexample at the ...
63 views

148 views

Higher-order Busy Beaver functions and the language of first-order set theory

I have a question, but before asking this question, it is required to ask the preliminary question: is it possible to define a particular higher-order Busy Beaver function by a formula (of finite ...
171 views

Computable extension to $Σ_1$-sound system that is $Σ_2$-unsound?

Recently, I wrote this post showing (if I did not make a mistake) essentially that: For any nice formal system $S$ that is $Σ_1$-sound there exists some extension $S'$ that is $Σ_1$-sound but $Σ_2$-...
154 views

Are provable statements at the bottom of the arithmetical hierarchy?

When I can assign to a statement (of PA) a classification $\Sigma_n^0$ (resp. $\Pi_n^0$) of the arithmetical hierarchy (AH), then this also classifies it as $\Sigma_m^0$ (resp. $\Pi_m^0$) for any \$m\...