The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
2answers
87 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
27 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
95 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
87 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
38 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
996 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
467 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
142 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
43 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
72 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
92 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
173 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
39 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?
48
votes
12answers
5k views

What is a simple example of an unprovable statement?

Most of the systems mathematicians are interested in are consistent, which means, by Godel's incompleteness theorems, that there must be unprovable statements. I've seen a simple natural language ...
1
vote
1answer
64 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
50 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
43 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
192 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 ...
3
votes
1answer
196 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 ...
0
votes
0answers
15 views

proving a fraction with 2 parameters to be small

Hi I have a fraction as below $$\frac{1.623x^4+0.434x^4\sum_iy_iz_i^2+(0.014x^2+0.0027)\sum_iy_iz_i^4}{1.645x^2+(0.083-0.329x^2+0.435x^4)\sum_iy_iz_i^2+0.014\sum_iy_iz_i^4}$$ where $x\in[0, 0.5]$, ...
0
votes
1answer
64 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 ...
2
votes
3answers
98 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
38 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
50 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
157 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
53 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
70 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
65 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
404 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
82 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 ...
1
vote
1answer
118 views

Is the converse of the first Hilbert-Bernays Derivability Condition true?

The first Hilbert-Bernays Derivability Condition is (⊢P) → (⊢◻P). What I'd like to know is, is the converse true? That is, is (⊢◻P) → (⊢P) valid? I know from Löb's Theorem that ⊢(◻P → P) is not valid ...
2
votes
0answers
69 views

Tricking the Second Incompleteness Theorem

On Wiki, the Second Incompleteness Theorem reads as For any formal effectively generated theory T including basic arithmetical truths and also certain truths about formal provability, if T ...
2
votes
1answer
75 views

What is the connection between provability logic & Gödel's first incompleteness theorem?

Ive already asked this qustion on philosophy.SE Provability logic is a modal logic that interprets the modal operator of K as provability and an additional axiom derived from Löb's theorem. Now the ...
6
votes
2answers
355 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 ...
2
votes
1answer
56 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 ...
0
votes
1answer
94 views

Question concerning satisfiability in a certain Kripke model

My question concerns the exercise on p.77 of Boolos, Logic of Provability: True or false: if $A$ is satisfiable in some finite transitive and irreflexive [FIT] model and contains at most one ...
1
vote
2answers
70 views

Can we add to PA a new predicate T such that for every sentence A of the old vocabulary the new theory proves $T(\ulcorner A\urcorner)\equiv A$

I believe this is not a difficult problem, but I am soo confused, and the reason for that is because there are so many gaps in my knowledge or maybe I have overlooked so many "obvious" argument. I ...
2
votes
1answer
75 views

What can we say about a fixed point for a provability predicate in deductively defined theory that satisfies diagonalisation lemma

I am curious and trying to reason about what consequences we get if we use the predicate in the diagonalisation lemma as the provability predicate. I don't think I succeeded, I would appreciate if ...
10
votes
2answers
141 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?
2
votes
2answers
76 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
280 views

reverse direction of modus ponens

Let $\mathit{pvbl}$ is a formalized provability predicate. If a sentence $X$ is decidable, then following is correct? $$ \left(\mathit{pvbl}(X) \to \mathit{pvbl}(Y) \right) \implies \mathit{pvbl}(X ...
5
votes
2answers
151 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.)
3
votes
4answers
4k views

Proving square root of a square is the same as absolute value

Lets say I have a function defined as $f(x) = \sqrt {x^2}$. Common knowledge of square roots tells you to simplify to $f(x) = x$ (we'll call that $g(x)$) which may be the same problem, but it isn't ...
3
votes
1answer
147 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 ...
1
vote
1answer
173 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$), ...
4
votes
1answer
408 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 ...
0
votes
1answer
145 views

Uniqueness of super godel numbers of $\varphi$ and $\neg \varphi$

Let $e_{0},e_{1},...,e_{n}$ be a sequence of wffs or other expressions. Code each $e_{i}$ by a regular godel number $g_{i}$, to yield a sequence of numbers $g_{0},g_{1},...,g_{n}$. Then encode this ...