1
$\begingroup$

Can we express the following property of natural numbers as FOL. The property given below is only indicative, I am more interested in knowing how the concepts such as "infinitely many X exists for so and so" can be expressed in FOL. Also these need to be expressed as uninterpreted functions.

"For every natural number n, there are infinitely many other natural numbers such that the greatest common divisor of n and each of these other numbers is 1"

As I said if you can't express this sentence in FOL at least suggest links/material where I can get leads.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

If $f(n)$ is a predicate in the first order language of arithmetic, then "there are infinitely many $n$ such that $f(n)$ holds" can be expressed as $$\forall m\in\mathbb{N}\ \exists k\in\mathbb{N}:f(m+k+1).$$

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Or: For all m there is a k larger than m such that f(k). $\endgroup$
    – Andrés E. Caicedo
    Commented Aug 12, 2010 at 22:18
  • $\begingroup$ Okay. I was a bit confused as per who the "infinitely many.." is represented. $\endgroup$
    – Akshar Prabhu Desai
    Commented Aug 13, 2010 at 5:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .