The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
40 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
45 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 ...
3
votes
0answers
64 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 ...
0
votes
0answers
20 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?
43
votes
11answers
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 ...
0
votes
1answer
28 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
40 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
24 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
114 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
118 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
14 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
50 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
92 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
35 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
49 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
136 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 ...
1
vote
1answer
41 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
67 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
64 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 ...
6
votes
3answers
344 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
78 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
94 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
64 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
64 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
313 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 ...
1
vote
1answer
55 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
84 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
65 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
66 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
126 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
71 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
229 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 ...
4
votes
2answers
136 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.)
1
vote
3answers
2k 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
133 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 ...
0
votes
1answer
157 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
364 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
133 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 ...