The tag has no usage guidance.

learn more… | top users | synonyms

14
votes
1answer
673 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 ...
1
vote
5answers
123 views

Inequality problem $\frac 1x + \frac 1y + \frac 1z > 5$ prove

Prove that: $$\frac 1x + \frac 1y + \frac 1z > 5$$ where $x+y+z=1$, $x, y, z$ are real numbers not equal $0$ and $x\neq y \neq z $
2
votes
1answer
21 views

Busy Beaver unprovoable for large inputs?

From Wikipedia on the busy beaver, there is a true-but-unprovable sentence of the form "$Σ(10↑↑10) = n$", and there are infinitely many true-but-unprovable sentences of the form "$Σ(10↑↑10) < ...
1
vote
1answer
47 views

Weak Representability and Derivability Condition 1

Can someone point out the error in the following reasoning? Let K be an axiomatizable, consistent extension of Peano Arithmetic. Let P' denote the Gödel number for P. K is axiomatizable, thus ...
0
votes
0answers
26 views

Why is it impossible to prove absolute consistency of a theory falling prey to Godel's theorems?

Why is it impossible to prove absolute consistency of a theory T falling prey to Godel's theorems? I understand that a theory falling prey to Godel's second incompleteness theorem cannot prove its own ...
0
votes
0answers
18 views

Can there be true but unprovable statements about object other than numbers?

In ZFC, everything is a pure set, and because the necessary amount of arithmetic for the Gödel's incompleteness theorems to go through is interpretable within ZFC, there are undecidable statements ...
0
votes
0answers
22 views

The right way of defining a predicate

My theory contains a definition of lists: L(H,T) is a list, H is the first element (head), T is the list of remaining elements (tail), nil is empty list. So [A,B,C] = L(A,L(B,L(C,nil))). I defined ...
0
votes
1answer
26 views

Show that if GL $\vdash$ X then for all interpretations $\xi_i$ of GL in PA, PA $\vdash \xi_i(X)$

I'm trying to show the above. We define interpretations as follows: For any provability predicate $Pr(v_1)$, and $i$ any mapping from $\{ \bot, p_1, ..., p_n, ...\}$ (where $p_i$ are the sentence ...
0
votes
2answers
53 views

Impossibility of proving a foundation to be consistent

An argument came to my mind that seems really mind-blowing and I haven't found it anywhere. Here's how it goes: We call a formal system F embodied in classical logic a foundation of mathematics when ...
0
votes
1answer
38 views

Unary predicate for finite number of values

I am working with automated prover. I am creating a theory, where an unary predicate PR should be true just for several constants, false otherwise. I made following axioms: ...
1
vote
1answer
46 views

Show that a theory is complete if and only if (B or C is provable) implies (either B is provable or C is provable)

The question: Show that a theory T is complete if and only if for any closed formulas B and C $$if \vdash_T B\ \lor C\ \Rightarrow\ \vdash_TB\ or \vdash_T C $$ Where $\vdash_T$ means that a formula P ...
1
vote
2answers
83 views

How does Gödel's second incompleteness apply to any theory containing arithmetic?

If I understand correctly, there are two facts proven by Gödel's second incompleteness theorem, for a formal theory containing arithmetic 1) It is possible to express the consistency of the theory ...
1
vote
2answers
58 views

Can't prove $2^n > n$ with Mathematical Induction

As the title states, I have a problem with proving $2^n > n$ I can do the basis step fine: Basis step: "n = 1" 2^1 = 2 2 > 1 So it is true for $n$. But ...
0
votes
1answer
154 views

Can you prove that something is provable/unprovable? Give an example [closed]

Also, can something be unprovable by definition?
1
vote
2answers
103 views

Do mathematicians ever prove that something can or can't be proved?

I was just idly thinking about things people have a hard time proving, like P=NP, etc, and wondering if instead it could be proved that it's provable or unprovable. Is that a thing? Does that ever ...
0
votes
1answer
48 views

ZFC,unprovability of existence of a countable model,Skolem construction and paradox

The well-known Skolem construction yields a countable model of ZFC,elemetarily equivalent to the universe of sets $V$.Why this construction is not a proof of existence of models of ZFC,as such proofs ...
1
vote
1answer
101 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 ...
0
votes
1answer
120 views

A few questions about a true but unprovable statement

Can someone explain to me what this comment means: If ZFC is not a sound theory, a true but unprovable statement may be refutable and therefore decidable. What is a sound theory? What is ...
3
votes
1answer
96 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 ...
6
votes
2answers
177 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 ...
1
vote
1answer
31 views

provability of a mathematical statement

Is it possible to prove that a non-axiom statement is not mathematically provable with current accepted axioms of mathematics? Note that this is not a question of proving if it is a true or false ...
1
vote
3answers
103 views

Is this a valid logical paradox?

In some recent cases, I have noticed some theorems are accepted to be intuitively or logically true if they themselves, as a unit, have no valid proof, but, their statements can be used to prove ...
3
votes
1answer
143 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 ...
5
votes
0answers
67 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 ...
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 ...
11
votes
3answers
537 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 ...
5
votes
1answer
228 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 ...
1
vote
1answer
47 views

Models of H and GL

I've been reading The Logic of Provability by George Boolos, and something he said stumped me for a bit. Let us use H (for Henkin) to refer to the system that results when (YS) is added to K, ...
1
vote
1answer
118 views

is this formula provable in predicate logic? ⊢ (∀x)(∀y)(f(x1) = y1 → ((∀z)g(z) = f(x1) ≡ (∀z)g(z) = y1))

"Can you prove ⊢ (∀x)(∀y)(f(x1) = y1 → ((∀z)g(z) = f(x1) ≡ (∀z)g(z) = y1)) in predicate logic? explain." I'm saying no, but I'm not sure why. Is it because it's not a tautology? and how would Godel's ...
2
votes
1answer
158 views

$\omega$-consistent in Gödel I

In a very accessible form one could state the first incompleteness as follows: Incompleteness Theorem I Assume that $\textbf{PA}$ is consistent. Then there is a sentence $\phi$ such that ...
4
votes
1answer
284 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 ...
1
vote
0answers
63 views

Provably total functions?

I want to know what does it mean when we say for example $$f(x)=2^x$$ is provably total in Peano arithmetic? Also what's the diffrence between provably total and provably recursive?
55
votes
12answers
7k 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 ...
1
vote
1answer
99 views

Theorems of GL in modal logic

So I've been reading George Boolos' "The Logic of Provability" and he's explaining different systems of modal logic. He's taken as his basic symbols → (implication), □ (necessity), ⊥ (falsehood), a ...
1
vote
0answers
61 views

Existence(?) of a set whose cardinality cannot be determined in ZFC

(First, I apologize if I display any fundamental misunderstanding of how set theory works.) I had a question regarding the limitations of ZFC (assuming its consistency, of course.) Is there any ...
1
vote
1answer
76 views

How can Goodstein's theorem be expressed in PA

I understand Goodstein's Theorem and its proof. I'm trying to understand the proof of why Goodstein's Theorem cannot be proved in PA. However, it's not immediately clear to me that Goodstein's Theorem ...
2
votes
1answer
369 views

True but unprovable?

I would like to ask a question about Gödel's Incompleteness Theorems which I've had in the back of my head for some time. Since I'm a student working in a completely different area of maths (my usual ...
11
votes
4answers
439 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 ...
3
votes
1answer
537 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 ...
1
vote
1answer
79 views

What are techniques for proving undecidability or unprovability of a sentence?

I asked a question the other day on how to form logical equivalence between a sentence $\phi$ and two other sentences $\psi$ and $\chi$, such that neither $\psi$ nor $\chi$ were on their own as ...
3
votes
3answers
617 views

Is Riemann Hypothesis provable?

Loosely speaking, there are three kinds of propositions. Those propositions which are true and can be proved to be true. Those propositions which are false and which can be proved to be ...
2
votes
3answers
117 views

can it be proven that something is “difficult” (prime factoring for example)

I understand that the current state of the art suggests that factoring into primes is a difficult problem. I also understand that a large part of public key cryptography seems to be based on that ...
1
vote
2answers
39 views

How to prove $\sum\limits_{k=0}^n\ (3k^2+2k+1) = n^3 + 5 \begin{pmatrix}n+1\\2\end{pmatrix}+1$

$\sum\limits_{k=0}^n\ (3k^2+2k+1) = n^3 + 5 \begin{pmatrix}n+1\\2\end{pmatrix}+1$ How would you go on proving this equation? Doesn't have to be induction..
8
votes
2answers
52 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 ...
3
votes
1answer
201 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 ...
2
votes
2answers
58 views

On provability within minimal logic

In its most naive form my question boils down to this: when is a proposition that is provable "by contradiction" also provable "directly"? IOW, is it possible to know, a priori, that a ...
2
votes
3answers
79 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 ...
1
vote
2answers
67 views

Are there thoughtfully simple concepts that we cannot currently prove?

I was driving and just happened to wonder if there existed some concepts that are simple to grasp, yet are not provable via current mathematical techniques. Does anyone know of concepts that fit this ...
7
votes
3answers
538 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 ...
1
vote
1answer
90 views

Getting into formal logic

I found myself the motivation to translate some statements and either prove them in a specific setting (assumed premises) or at least decide on their provability. However, I have very little ...