The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
2answers
75 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
57 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
81 views

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

Also, can something be unprovable by definition?
1
vote
2answers
98 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
44 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
82 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
113 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
92 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
148 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
30 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
122 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
59 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
521 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
198 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
46 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
103 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
130 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
257 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
57 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?
53
votes
12answers
6k 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
87 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
59 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
63 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
304 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
418 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
78 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
109 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
51 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
186 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
57 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
77 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
503 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
88 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
131 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
73 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
87 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
381 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
59 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
100 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
74 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
78 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 ...
11
votes
2answers
176 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
78 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
335 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
167 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.)
5
votes
4answers
7k 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 ...