# Questions tagged [provability]

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

166 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
38 views

74 views

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.
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$?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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
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$?
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
161 views

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?
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 ( ...
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 ...
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 ...
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 ...
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 ...