Questions tagged [provability]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
29 views

Is there such a function $f(a,b)=k$ where each value of $k$ appears only once for all integer values of $a$ and $b$?

Suppose we have $f(a,b)=k$ such that $k$ is an integer when $a$ and $b$ are integers. Is there such a function where each value of $k$ appears only once for all integer values of $a$ and $b$? e.g ...
1
vote
6answers
131 views

Inverse Functions and their intersection points

Say you have $f(x) $ and $g(x)$ and $g(x) = f^{-1}(x) $. I observed that these two curves need not intersect, for example with $f(x) = e^x$ and $g(x) = \ln x $ never intersecting each other. I also ...
1
vote
2answers
261 views

Example of the property of rational numbers that must be proved using the axioms of real numbers?

According to Godel's incompleteness theorem, some statements about rational numbers are independent from the axioms of the rational numbers given in Wikipedia--an ordered field generated by 1. So can ...
1
vote
1answer
66 views

Is the sign of a real number decidable?

I'm working on the following problem in a class on provability. Consider how $\mathbb{R}$ might be presented. Is the property of being positive decidable? How could the reals possibly be presented ...
0
votes
1answer
38 views

How do I prove that the following function is increasing in $t\geq 1$ for any $1\leq y \leq t$?

I am sorry if I am asking something too specific and not useful to the general public, but I am stuck at proving that the following function is increasing for all $t\geq 1$ at any given $y$ such that $...
7
votes
1answer
505 views

Semantics for minimal logic

Minimal logic is a fragment of intuitionistic logic that rejects not only the classical law of excluded middle (as intuitionistic logic does), but also the principle of explosion (ex falso quodlibet). ...
1
vote
1answer
230 views

How to justify: Proof by contradiction ? (First Order Logic)

How to justify this rule? Proof by contradiction: If a proof of $\Gamma,\lnot B\vdash C\land\lnot C$ involves no application of Gen using a variable free in $B$, then $\Gamma\vdash B.$ I did one ...
6
votes
1answer
109 views

Being not “close” to ZFC and not “far away” from it at the same time

For each formula $\varphi$ we can have a look at the following two properties: $$1) ZFC \not \vdash Con (ZFC) \rightarrow Con (ZFC + \varphi)$$ $$2) ZFC + \varphi \not \vdash Con (ZFC)$$ Intuitively, ...
0
votes
1answer
46 views

Deduction from negation of uniqueness quantifier

The problem is this: By defintion $ \neg(\exists ! y F(x,y))\quad \leftrightarrow \quad \forall y\neg((F(x,y) \wedge \forall z (F(x,z) \rightarrow y=z))) $ I don't see how $\neg F(x,y)\quad \...
0
votes
3answers
74 views

Provability vs. implication?

For any logic we have an is provable from relation denoted by $S \vdash \phi$ where $S$ is a (for the sake of the argument lets say) finite set of sentences and $\...
4
votes
2answers
207 views

Computable extension to $Σ_1$-sound system that is $Σ_2$-unsound?

Recently, I wrote this post showing (if I did not make a mistake) essentially that: For any nice formal system $S$ that is $Σ_1$-sound there exists some extension $S'$ that is $Σ_1$-sound but $Σ_2$-...
8
votes
2answers
193 views

Brutal gaussian integral of death $\int_{\mathbb{R}} x \Phi(x) \phi(Bx-b)$

Ciao, I was making some computation and I've been stucked in this one. Let $B$ and $b$ be positive contant. We call $\phi(x)$ standard gaussian distribution and $\Phi(x)$ its cumulative function, i....
5
votes
1answer
74 views

Equivalence of different consistency sentences

Take any formal system $S$ that has a proof verifier program and interprets TC or PA$^-$. $ \def\imp{\Rightarrow} \def\con{\text{Con}} $ Then the incompleteness theorems show that $S$ does not prove $...
1
vote
1answer
61 views

Squares of relatively prime numbers [duplicate]

How can I mathematically prove that the squares of two relatively prime numbers are also relatively prime? Thanks in advance.
-2
votes
1answer
82 views

Proving $\frac{0}{0} = \infty$ [duplicate]

I once heard my mathematics teacher say that $\frac{0}{0} = \infty$ and she said proving this is difficult. How would I prove this? Then will $1 \times 0 = \infty$ as well or just $0$?
1
vote
1answer
73 views

Does V have a model that looks like V, according to Morse-Kelly set theory?

Let's talk about V, the class of all sets. We can't talk about this in ZFC, of course, so we will use Morse-Kelly set theory instead, which has classes. My question is, can Morse-Kelly set theory ...
2
votes
1answer
221 views

Model of concatenation theory with left-cancellation but no right-cancellation

The theory of concatenation (TC) can be equivalently expressed as the following assumptions: Closure of strings under concatenation $+$. Existence of an empty string $e$, namely $e+x = x = x+e$ for ...
11
votes
2answers
2k views

Were there any proofs of whether or not a statement could be proved true or false before Gödel's Incompleteness Theorems?

I know of the continuum hypothesis (CH) and how it was proven to be unprovable under ZFC, but this was after Gödel's incompleteness theorems. And in fact Gödel (and Paul Cohen) were the ones who ...
0
votes
1answer
269 views

Models of first-order logic and cardinalities of the domain

In first-order logic, it is possible for a sentence $S$ and its negation $\lnot S$ to both be invalid. That is, it is possible for there to not exist a proof of $S$, and also not of $\lnot S$. For ...
2
votes
1answer
52 views

Are any proofs of undecidability in ZFC also proofs of truth for properties of numbers?

Look at statements such as these: All nontrivial zeroes of the Riemann Zeta function lie on the critical line. Every even integer greater than 2 can be expressed as the sum of two primes. Every ...
0
votes
1answer
27 views

Prove if $m \in \mathbb{Z}$ and $n \in \mathbb{Z} \backslash \{ −1, 0 \}$, $\frac{m + 1}{n+1}$>$\frac{m}{n}$

How to prove if $m \in \mathbb{Z}$ and $n \in \mathbb{Z} \backslash \{ −1, 0 \}$ then $\frac{m + 1}{n+1} > \frac{m}{n}$ ? I started by realizing $n \subset m$ and if we choose $x \in n$ it also ...
-1
votes
3answers
239 views

Prove that if numbers $p$ and $8p^2+1$ are prime numbers then $8p^2-1$ is also a prime number. [closed]

How to prove that if numbers $p$ and $8p^2+1$ are prime numbers then $8p^2-1$ is also a prime number?
2
votes
6answers
98 views

Prove that there exist no natural number k such that $3^k+5^k$ is a square of an integer number? [closed]

How to prove that there exist no natural number $k$ such that $3^k+5^k$ is a square of an integer number
2
votes
2answers
69 views

Existence of inaccessible natural number divisible by every standard natural number under PA

Let $P$ be the proposition that there exists a non-zero number that is divisible by every standard natural number. Let $N$ be a non-standard model of PA. Must $P$ be true in $N$?
2
votes
0answers
62 views

Proving $\langle \Bbb R,+ \rangle \cong \langle \Bbb C,+ \rangle$ without choice [duplicate]

In this question, we have proved that $\langle \Bbb R,+ \rangle \cong \langle \Bbb C,+ \rangle$: Pick your favourite Hamel basis $H=\{U_\alpha \mid \alpha \in I\}$ where $I$ is an indexing set. Then, ...
0
votes
1answer
367 views

Property of “provability predicate”

In A Simple Proof of Gödel’s Incompleteness Theorems, the provability predicate $P$ is defined: Let $g$ denote the Gödel number function. Let $\operatorname{Proof}(x,y)$ be a binary predicate that ...
1
vote
1answer
138 views

The existence of unprovably unprovable statements provable in ZFC [duplicate]

I am aware of Gödel's second incompleteness theorem, the proven existence of several unprovable statements (in ZFC), and the possibility that a formal system may include statements that are unprovably ...
1
vote
0answers
75 views

Numbers made from digits 1-9 — proving the exceptions?

Inspired by this paper Introduction In this paper, a sequential representation of a number is a formula that uses the digits 1-9 in order with the mathematical operations +, -, ×, ÷, ^, as well as ...
3
votes
3answers
643 views

Prove that if you chose 8 numbers from the set $\{1,2,3,\ldots,14\}$ , at least one of these numbers divides another? [closed]

Prove that if you choose $8$ numbers from the set $\{1,2,3,\ldots,14\}$, at least one of these numbers divides another? How can I prove this? I don't know if I have to go with pigeonhole principle or ...
0
votes
2answers
44 views

Determine the basis of a subset V in a vector space of R3

I have to determine a basis of a given polinomyal subset. V is defined as: link I don't know how to start, maybe it could be helpfull to know that V is the subset of polynomial in the following ...
2
votes
2answers
161 views

Are provable statements at the bottom of the arithmetical hierarchy?

When I can assign to a statement (of PA) a classification $\Sigma_n^0$ (resp. $\Pi_n^0$) of the arithmetical hierarchy (AH), then this also classifies it as $\Sigma_m^0$ (resp. $\Pi_m^0$) for any $m\...
-1
votes
1answer
222 views

Can you prove a theorem by proving it’s undecidable? (Numberphile question) [duplicate]

Numberphile posted a vid on 5-31-17 about Godel’s Incompleteness Theorem. Near the end of the vid, the professor argues that proving that the Riemann Hypothesis is undecidable would PROVE the Riemann ...
6
votes
2answers
148 views

What portion of mathematical statements are ZFC undecidable?

From Godel's Incompleteness Theorem we conclude that for any logically consistent set of a finite number of axioms, there are an infinite number of mathematical statements that are true but can't be ...
52
votes
3answers
6k views

Is there any conjecture that we know is provable/disprovable but we haven't found a proof of yet?

I know that there are a lot of unsolved conjectures, but it could possible for them to be independent of ZFC (see Could it be that Goldbach conjecture is undecidable? for example). I was wondering if ...
1
vote
0answers
14 views

When k drawings are made in succession from n balls and every time ball is white then chance that next ball will be white

A bag contains n balls; k drawings are made in succession, and the ball on each occasion is found to be white. Find the chance that the next drawing will give a white ball (i) if balls are replaced (...
0
votes
0answers
108 views

Proving an equation $\displaystyle\lim_{\Delta x \to 0}\sum_{x=0}^{2} [(f'(x)e^{6x}\Delta x] = \int_{0}^{2} e^{14x}dx $

Continuing from this forum here, suppose that $f(x)=\dfrac{e^{8x}}{8}$ and $f'(x) = e^{8x}$. I was told that : $\displaystyle\lim_{\Delta x \to 0}\sum_{x=0}^{2} [(f'(x)e^{6x}\Delta x] = \int_{0}^{2} ...
0
votes
0answers
44 views

Are there any conjectures known not to be independent that have neither been proven true or false?

Are there any known conjectures that have been shown not to be independent of whatever system they target (i.e. provable), but have not yet been shown to be true or false?
1
vote
1answer
55 views

Help with modal logical deduction in K4

The following deduction can be found from the Boolos - The Logic of Provability in the page 59. It is in the proof for arithmetical soundness theorem. Let's assign \begin{align*} &B = \square ( ...
3
votes
1answer
129 views

What is a natural extension of PA that proves the undecidability of the consistency of PA?

Gödel's second incompleteness theorem can be proven in PA + COH, where PA is Peano Arithmetic and COH the consistency statment. By this I mean : $PA+COH\vdash \neg \square COH$ where $\square P$ means ...
0
votes
1answer
119 views

Do problems with a solution, that are proven to be unsolvable by any logic, exist?

I am aware both -my question formulation might be ambiguous -the conversion of my question based on the xy-problem might not logical/inconsistent. Nevertheless here is my attempt: Do problems with ...
3
votes
1answer
89 views

Theorem in ACA that is unprovable in $Π^1_1$-CA$_0$?

Question Is there a (preferably natural combinatorial) theorem in ACA that cannot be proven in $Π^1_1$-CA$_0$? Motivation On reading many introductory materials on reverse mathematics, there seems ...
1
vote
1answer
42 views

Proving a particular inequality between two sums of ceiling

We have an integer $N$ and $k$ integers $n_1 \geq n_2 \geq \ldots \geq n_k$. We also have a random permutation $\pi$ which permutes the indices of $[1, k]$. I would like to prove that we have the ...
1
vote
1answer
36 views

Formalizing consistency implications

Let $T$ be an axiomatizable theory extending minimal arithmetic, and $T'$ an axiomatizable extension of $T'$. Let $\square_{A}$ be the standard provability predicate for $A$. Is it true that $T\...
23
votes
4answers
2k views

Statement provable for all parameters, but unprovable when quantified

I've been reading a book on Gödel's incompleteness theorems and it makes the following claim regarding provability of statements in Peano arithmetic (paraphrased): There exists a formula $A(x)$ ...
2
votes
0answers
44 views

searching for provabiliy logic books

I ve been searching for a while for books about provability logic, though everything that I found yet seems incomprehensible to me. I have read some first year college courses on naive set theory. ...
2
votes
2answers
93 views

How to express the rest of division by three, with very elementary functions?

Is it possible to express $\; "\!n\pmod 3\!"\;$ with combinations of the functions plus, minus, multiplication, division and exponentiation in $\mathbb C$ or preferably in $\mathbb Z[i]$? I'ts not ...
0
votes
1answer
928 views

Linear functions vs Linearithmic functions complexity

Can we say Linear functions complexity is lower than Linearithmic functions? ie: ...
1
vote
1answer
111 views

On the truth of $GLS$ and Löb's theorem

Consider the formal system $GLS$, whose axioms are the theorems of $GL$ plus all sentences of the form $\square A\rightarrow A$. A translation maps a sentence of modal logic to a sentence in the ...
3
votes
1answer
466 views

Why is the proof of Gödel's first incompleteness theorem no contradiction?

I consider the following version of Gödel's first incompleteness theorem: Assume $F$ is a formalized system which contains Robinson arithmetic $ Q$. Then a sentence $G_F$ of the language of $F$ can ...
14
votes
1answer
2k views

Is it really impossible to lose the Hydra game?

In a number of blog posts I found the claim that the game described below cannot be lost, which is to say, every possible strategy is a winning strategy. In each case, a sketch proof is given that ...