5
votes
1answer
206 views

Showing unique prime factorization in first-order logic?

Suppose I have the symbols $\{\neg, \rightarrow, =, <,\cdot, \leftrightarrow,\land, \lor \}$ and functions $Div(x,y)$ ($x$ divides $y$), $Prime(x)$ true if $x$ is a prime, and domain $\mathbb{N}$. ...
1
vote
2answers
86 views

Problem of Ages (Problema das Idades)

English: Somebody help me with this challenge? It's very confusing: Today, both me and my younger brother are between $10$ and $20$ years old. Also, our ages are expressed by prime numbers and the ...
5
votes
0answers
268 views

Logical consequence of Euclid's theorem

Are there any far reaching non-trivial consequences of Euclid's infinitude of primes where theorems make use of it? Wikipedia does not have the list of applications of this theorem, rather modern ...
1
vote
1answer
48 views

Missing one link in logic of basic unique factorization argument

From page 2 of The Prime Facts : from Euclid to AKS by Scott Aaronson : Thus P/A = R/K. But R is less than P, since it’s a remainder from dividing by P. Okay So P/A can’t be in lowest ...
1
vote
1answer
497 views

Set of numbers pairwise relatively prime

Given a positve integer n, we can find infinitely many positve integers $b$ such that the $n-1$ integers in the set $\{b+1,\,2b+1,\,3b+1,\,...,\,(n-1)b+1\}$ are pairwise relatively prime. I assume ...
8
votes
3answers
432 views

First-order proof that there is no largest prime

Is there a first-order proof on $(\mathbb{N},+,*,\le)$ that there is no upper bound on primes. ie that $$\neg\exists{q}{\forall{p}{(\forall{m,n}\space m*n=p\rightarrow m=1\vee n=1)\rightarrow p\le ...
1
vote
0answers
153 views

Forcing and divisibility

I'm going to bring together a couple of seemingly unrelated questions that I've asked here. This may be silly. Or maybe not? Imagine that $n$ is some sort of infinitely large integer, and thus so ...
5
votes
2answers
681 views

A first order sentence such that the finite Spectrum of that sentence is the prime numbers

The finite spectrum of a theory $T$ is the set of natural numbers such that there exists a model of that size. That is $Fs(T):= \{n \in \mathbb{N} | \exists \mathcal{M}\models T : |\mathcal{M}| =n\}$ ...