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