Questions tagged [provability]

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

260 questions
Filter by
Sorted by
Tagged with
133 views

Interpretation of Godel's incompleteness theorem [closed]

Godel's incompleteness theorem states "Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e. there are statements of the ...
• 2,280
42 views

Induction on two variables, confused about the induction step

Suppose I want to show For any $n>1$, any $r$, such that whenever $r+1 \leq n$, we have $P(n,r)$. (Geometrically, we have a 'infinite' triangle in the plane) My induction goes as $\forall n >1$ (...
• 654
139 views

Is Gödels second incompleteness theorem provable within peano arithmetic?

All following notation and assumptions follow Gödel's Theorems and Zermelo's Axioms by Halbeisen and Krapf. Exercise 11.4 c) states "Conclude that the Second Incompleteness Theorem is provable ...
• 171
97 views

Are there examples of statements not provable in PA that do not require fast growing (not prf) functions?

Goodstein's theorem is an example of a statement that is not provable in PA. The Goodstein function, $\mathcal {G}:\mathbb {N} \to \mathbb {N}$, defined such that $\mathcal {G}(n)$ is the length of ...
• 1,027
65 views

Does any computable $T\supset PA^-$ have a provability predicate satisfying Hilbert-Berneys conditions?

In the language of arithmetic, fix a computable theory $T\supset PA^-$. Let $P_T(x)$ be the usual $\Sigma_1$ formula: for any sentence $\varphi$, $\mathbb{N}\models P_T(\ulcorner\varphi\urcorner)$ iff ...
221 views

103 views

Is $(\phi\implies\psi) \iff ((\phi\land\psi)\lor \neg\phi)$ provable in the following hilbert calculus without contraposition or reductio?

Is $(\phi\implies \psi) \iff ((\phi\land \psi)\lor \neg \phi)$ in the following hilbert calculus without contraposition or reductio ad absurdum? If so, how would I go about proving it, and if not, ...
1 vote
124 views

Does a Turing machine exist with output 1 if an unprovable statement is true and 0 otherwise?

Suppose there is some statement $X$ that is unprovable in some system, e.g. ZFC. Let $L = \{x : x \in \Sigma^* \land X \text{ is true}\}$. Is there a Turing machine that decides $L$? I have had an ...
• 559
25 views

Proving minimum steps solution for a math quiz [duplicate]

I have the following math quiz: You have 4 Red Balls & 4 Green Balls. You cannot see the color of the balls but you have a machine (or function) which takes 2 balls as input and returns true, when ...
• 19
113 views

Prove $\sqrt{-3+44a} \in N$ can't be a square root of a square of a natural number [closed]

Prove $\sqrt{-3+44a} \in N$ can't be a square root of a square of a natural number. $$\begin{equation*} \begin{cases} a \in N \\ d \in N \\ -3+44a = d^2 \end{cases} \end{equation*}$$
• 11
1 vote
112 views

Is someone trying to solve problems by building all possible proofs using all possible rules of inference? [closed]

We obviously can construct a program that, starting with ZFC (or any other theory) axioms, would use all possible rules of inference to get all possible proofs constructible in ZFC. (There would be ...
214 views

Is there a proposition that cannot be proven to be provable(or not)? [duplicate]

I have been studying mathematical logic and the foundations of formal systems, and I came across the concept of "provability" and "unprovability" of propositions within such ...
• 151
39 views

Estimating Set Size from Sample Data

I encountered a sampling problem and managed to approximate programmatically. However, I'm interested in determining the analytical solution. There are two sets $A$ and $B$. $|A|$ is known, $|B|$ is ...
• 143
1 vote
59 views

• 171
123 views

Ultra-finite math [closed]

Assume our universe is finite in any sense (the information amount was some $10^{120}$ bits, if I remember correct) and deal with the following, slightly (and intendedly) preposterous, scenario: The ...
83 views

How can I encode a proof in PA as a godel number?

It seems straightforward to encode a wff in PA as a number. I can't see how to encode a proof. Could someone please tell me how this is usally done? Thanks.
188 views

Prove or disprove: if Γ ⊢ α and Γ ⊆ ∆ then ∆ ⊢ α

I am trying to solve this question but I am doubting about the answer. Namely: Γ ⊢ α means that there is a derivation with conclusion α and with all hypothesis in Γ. Since Γ ⊆ ∆, we can use the same ...
• 67
278 views

What is the truth value if any for $f(x)=y$ when $x$ is outside of the domain of $f$?

What is the truth value if any for $f(x)=y$ when $x$ is outside of the domain of $f$? Could it be false or undefined?
• 14.8k
87 views

Can we have another set of inference rule which is simplier and equivalent (in the sense that they prove the same formulas)?

I have some questions on inference rules in model theory. Question 1) In (some books of) model theory, $(\psi \rightarrow \phi, \psi \rightarrow \forall x \phi)$ where $x$ is not free in $\psi$ is ...
• 375
1 vote
83 views

Is the set of all provable theorems countable? [duplicate]

I suppose this is not an easy question unless we formally define what counts as a theorem. For the purpose of this question, let us conservatively suppose that we are taking ZFC as our foundation, and ...
• 4,472
75 views

For every $n \in \mathbb {N}$, assume $p_{n}$ is the $n^{th}$ prime number. if $n \gt 1$, prove that $p_{n}\lt 2^{n}$. [duplicate]

I tried to solve this problem using mathematical induction. First, we say that $3 \lt 4$ for $n =2$, which is correct. Then by assuming that it's accurate for $k$, we need to prove it's accurate as ...
• 161
1 vote
123 views

Independent events in Probability theory

Events A, B and C are independent, $\mathbb P (A) = 0.1$; $\mathbb P (B) = 0.4$ and $\mathbb P (C) = 0.9.$ Find the probability of an event $D = (A + B) (A + C) (B + C).$ Find the probability of ...
• 93
1 vote
268 views

Are provable statements true?

I recently started reading an introductory logic textbook, and I haven't got yet to the chapter that talks about completeness theorem, but I just couldn't wait to read about it using shortcuts. I just ...
66 views

Is it possible to obtain a contradiction from provability logic GL + inference rule ($\square P$ ==> $P$)

Is it possible to obtain a contradiction from provability logic GL + inference rule ($\square P$ ==> $P$) ? I suspect that answer is "No". If I am right, then there is a model of such ...
243 views

Does $\mathbf{Z}$ prove existence of transitive closure of every set?

Is Zermelo set theory sufficient to prove the existence of the transitive closure of any set $X$? $TC(X)=\{X, \bigcup X, \bigcup\bigcup X, \ldots \}$
• 253