Welcome to MathOverflow

Question

0

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.

flag	asked Aug 12 2010 at 20:36 Akshar Prabhu Desai 129●4

Robin Chapman · Accepted Answer · 2010-08-12 20:48:28Z UTC

2

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

answered Aug 12 2010 at 20:48

Robin Chapman
14.5k●2●29●50

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

Natural number properties as uniterpreted functions in first order logic

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.