# Questions tagged [provability]

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

238 questions
Filter by
Sorted by
Tagged with
59 views

• 189
1 vote
41 views

### Is it True: The average distance of points from the diagonals is less than the average distance from circumference of the circle in a rectangular area

My problem is related to proving that the average distance of random distributed points from the diagonals is less than the average distance from the circumference of the circle. The problem is ...
• 23
1 vote
22 views

• 161
100 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 ...
41 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.
71 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 ...
• 57
211 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?
• 13.2k
65 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 ...
• 189
1 vote
81 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 ...
• 3,766
42 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 ...
• 157
1 vote
59 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
105 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 ...
45 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 ...
• 704
1 vote
128 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 \}$
• 213
227 views

### Incompleteness theorem: Peano arithmetic vs. standard model of arithmetic

Context (from https://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic#From_the_incompleteness_theorems): The incompleteness theorems show that a particular sentence G, the Gödel sentence of ...
• 604
1 vote
82 views

### Characterization for unprovable formulas for first-order logic

Is there any existing work on characterizations of the unprovable formulas in (general) first-order logic? i.e. Gödel's incompletness result constructs an explicit formula that is valid but unprovable:...
43 views

### If a statement implies an undecidable statement, does that make it undecidable itself?

Wikipedia writes that in every consistent formal system that satisfies Gödel's first incompleteness theorem there exist statements about natural numbers that are true, but that are unprovable within ...
• 186
45 views

### Can PA prove Cons(PA) under standard model?

We know that PA cannot prove Cons(PA) without being inconsistent. But can PA prove Cons(PA') where PA' is a restricted PA that allows only the standard model (for example by defining PA' to be the ...
75 views

### Is there a chess example of True but Not Provable statement?

I am trying to explain to someone (and also to understand better) Godel's Theorems through a chess example. Indeed I found some examples of True but Not Provable math statements, but they are honestly ...
1 vote
52 views

### Computability and Logic by Boolos et all Problem 17.1

Show that the existence of a semirecursive set that is not recursive implies that any consistent, axiomatizable extension of $\mathbf{Q}$ fails to prove some correct $\forall$-rudimentary sentence. ...
• 2,354
130 views

### "Barely-unprovable" functions

Fix a $\Sigma_1$-sound theory $\mathcal{T}$ containing basic (Robinson) arithmetic. On the one hand, by diagonalizing over the provably total computable functions in $\mathcal{T}$, we can construct a ...
68 views

### Is there a conjecture or result such that if it's proven to be true would automatically prove (the Strong) Goldbach's conjecture? [duplicate]

I'm just wondering if there's any existing conjectures or results such that if they're proven to be true, Goldbach's conjecture would also be proven to be true. Additional Information: I've looked at ...
• 61
67 views

### Is there an uncomputable number between any two real numbers?

I know close to nil about uncomputable numbers, so perhaps it doesn't even make sense to ask this question. All the information I can find about them is unaccessible with my level of education, but I ...
• 81
1 vote
62 views

### Fundamentals of Truth, Provability and Axioms by means of the Continuum Hypothesis

Let S be the structure/language of ZFC (including PL 1). Let CH refer to the well-known continuum hypothesis. My claims are as follows and could u just say if it's true or wrong and why? In S neither ...
• 342
56 views

### provability and theorem

I am studying first order logic and I have a hard time understanding the link between provable formulas and theorem. In the book by Shoenfield, the predicate $Pr_{T}(a,b)$ of is defined as the set of ...
• 35
1 vote