Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

"For Every natural number n, there are infinitly 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 cant express this sentence in FOL at least suggest links/material where I can get leads.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
Or: For all m there is a k larger than m such that f(k). –  Andres Caicedo Aug 12 '10 at 22:18
    
Okay. I was a bit confused as per who the "infinitely many.." is represented. –  Akshar Prabhu Desai Aug 13 '10 at 5:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.