Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [provability]

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

89
votes
11answers
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,...
67
votes
12answers
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 ...
51
votes
3answers
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 ...
28
votes
11answers
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, ...
23
votes
4answers
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)$ ...
14
votes
4answers
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 ...
14
votes
1answer
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 ...
13
votes
2answers
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?
11
votes
2answers
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 ...
11
votes
4answers
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 ...
10
votes
3answers
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 ...
10
votes
1answer
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 ...
8
votes
3answers
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 ...
8
votes
2answers
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 ...
8
votes
2answers
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....
7
votes
1answer
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). ...
7
votes
2answers
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 ...
6
votes
2answers
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 ...
6
votes
2answers
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.)
6
votes
3answers
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 ...
6
votes
1answer
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, ...
6
votes
1answer
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$ ...
6
votes
2answers
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 ...
5
votes
1answer
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 ...
5
votes
1answer
63 views

Equivalence of different consistency sentences

Take any formal system $S$ that has a proof verifier program and interprets TC or PA$^-$. $ \def\imp{\Rightarrow} \def\con{\text{Con}} $ Then the incompleteness theorems show that $S$ does not prove $...
5
votes
0answers
100 views

Proving $\square(\forall v_1\neg\psi(v_1))\rightarrow\forall v_1\neg\psi(v_1)$ for a particular $\psi$.

I have a formula $\psi(v_1)$ that is equivalent in $\mathrm{PA}$ to $$\exists a\exists b\exists c\left[\neg\exists x\overline{\mathrm{Prf}}(x,c)\wedge\mathrm{Neg}(b,c)\wedge\mathrm{Sub}\left(a,\...
4
votes
2answers
107 views

Can ZFC+A and ZFC+negation of A be both inconsistent where A is some conjecture?

So I know that a conjecture/statement or negation of it plus ZFC can both turn out to be consistent, which means that a statement is not provable. But I would like to go opposite way - and let's say ...
4
votes
1answer
757 views

Need help understanding a proof in Boolos's “The Logic of Provability”

I'm currently reading The Logic of Provability by George Boolos and there's a step in a proof that I don't understand. The author has defined a system of modal logic called GL; its language has a ...
4
votes
1answer
527 views

What other unprovable theorems are there? [duplicate]

Gödel's incompleteness theorem presents us with the possibility of having theorems that are neither provable nor disprovable in a given axiomatic set. Already we have the continuum hypothesis which ...
3
votes
3answers
642 views

Prove that if you chose 8 numbers from the set $\{1,2,3,\ldots,14\}$ , at least one of these numbers divides another? [closed]

Prove that if you choose $8$ numbers from the set $\{1,2,3,\ldots,14\}$, at least one of these numbers divides another? How can I prove this? I don't know if I have to go with pigeonhole principle or ...
3
votes
1answer
519 views

On provability of Paris–Harrington theorem

It is said that the Paris–Harrington theorem is true, but not provable in Peano arithmetic. I want to ask: So how do they know that it is true if it has no proof? I cannot imagine someone knows ...
3
votes
1answer
267 views

Why isn't GL system of provability logic reflexive?

Formula $\square p \rightarrow p$ (axiom T; corresponding to reflexive modal frames) is interpreted as "if p is provable, then p", or more precisely: for all realizations (all substitutions for $p$), $...
3
votes
1answer
90 views

What does it mean for a number to be independent of ZFC?

Since the definition of the Busy Beaver function by Radó in 1962, an interesting open question has been what [is] the smallest value of $n$ for which $BB(n)$ is independent of ZFC set theory. Source: ...
3
votes
3answers
88 views

Formal proof of one of De Morgan's laws

How to give a formal proof of $\vdash \neg (p\land q)\to\neg p\lor \neg q$ in the natural deduction proof system? Here is what I have: ...
3
votes
1answer
457 views

Why is the proof of Gödel's first incompleteness theorem no contradiction?

I consider the following version of Gödel's first incompleteness theorem: Assume $F$ is a formalized system which contains Robinson arithmetic $ Q$. Then a sentence $G_F$ of the language of $F$ can ...
3
votes
1answer
87 views

Theorem in ACA that is unprovable in $Π^1_1$-CA$_0$?

Question Is there a (preferably natural combinatorial) theorem in ACA that cannot be proven in $Π^1_1$-CA$_0$? Motivation On reading many introductory materials on reverse mathematics, there seems ...
3
votes
1answer
395 views

Hilbert–Bernays provability conditions

Let "provability formula" ${\rm Prf}(x, y)$ written in the manner that provability operator $\square A$ defined as $\exists x\ {\rm Prf}(x, \overline A)$ satisfying Hilbert–Bernays axioms: If ZF $\...
3
votes
1answer
140 views

Troubling questions about probability

Suppose we have some random phenomena. Is it true that any event concerning the phenomena has a fixed "correct" probability? That is, the correct probability is the relative number of occurrences of ...
3
votes
1answer
1k views

how to prove : there are an infinite number of points on the circle

I think the follow problem is equal to the problem set 1.16.(a) in Principles of Mathematical Analysis (walter ruldin), And we take (a, b) in $R^2$, X in $R^i$ how to prove : there are an infinite ...
3
votes
1answer
303 views

properties of the provability predicate applied to open formulas

Good day! Let $\mathrm{T}$ be a first-order theory which contains the Peano arithmetic and has a recursively enumerable set of axioms. It is well known that one can construct a predicate $\mathrm{Pr}$...
3
votes
0answers
79 views

Godel's theorem incompleteness, truth vs.provability

I know this question has been investigated in other threads, but I would like to pose yet another question on Gödel's theorem incompleteness, and truth in 'the standard model' compared with ...
3
votes
0answers
165 views

Prove that $\left(\sum_{k=1}^n\,\left(\frac{k}{n}\right)^n\right)^{\frac{1}{n}}$ decreases as $n$ increases.

Please help me to prove the following problem with inductive argument $$\left(\left(\frac{1}{n+1}\right)^{n+1}+\dots+\left(\frac{n+1}{n+1}\right)^{n+1}\right)^{\frac{1}{n+1}}<\left(\left(\frac{1}{n}...
2
votes
6answers
96 views

Prove that there exist no natural number k such that $3^k+5^k$ is a square of an integer number? [closed]

How to prove that there exist no natural number $k$ such that $3^k+5^k$ is a square of an integer number
2
votes
2answers
92 views

How to express the rest of division by three, with very elementary functions?

Is it possible to express $\; "\!n\pmod 3\!"\;$ with combinations of the functions plus, minus, multiplication, division and exponentiation in $\mathbb C$ or preferably in $\mathbb Z[i]$? I'ts not ...
2
votes
2answers
157 views

formalized provability predicate and implication relation

$\DeclareMathOperator{\pvbl}{pvbl}$ Let $\pvbl$ be the formalized provability predicate. Sentences $A$, $B$, $C$, $D$ have the following relation. $\pvbl ( A \rightarrow B)$ $\pvbl ( C \rightarrow ...
2
votes
1answer
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 ...
2
votes
2answers
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$-...
2
votes
2answers
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\...
2
votes
3answers
110 views

Proving that there exists something.

When asked to "Prove that there exists such x that y" , is giving such "x" enough as a solution or do you need to find like a general formula or something? For example, if asked to "prove that there ...
2
votes
1answer
52 views

Are any proofs of undecidability in ZFC also proofs of truth for properties of numbers?

Look at statements such as these: All nontrivial zeroes of the Riemann Zeta function lie on the critical line. Every even integer greater than 2 can be expressed as the sum of two primes. Every ...