Exponent function as uninterpreted function in first order logic - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T19:49:49Z http://mathoverflow.net/feeds/question/35203 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35203/exponent-function-as-uninterpreted-function-in-first-order-logic Exponent function as uninterpreted function in first order logic Akshar Prabhu Desai 2010-08-11T09:16:09Z 2010-08-11T09:22:35Z <p>I want to express the following sentence in first order logic. </p> <p>There are naturals numbers that can not be expressed as one natural number raised to the power of another natural number other than one. </p> <p>Under normal circumstances this is very simple. I am wondering if the the exponent function involved here can be expressed as uninterpreted function. Can we use some combination of *,+ as interpreted functions to express exponent function as uninterpreted one ? </p> http://mathoverflow.net/questions/35203/exponent-function-as-uninterpreted-function-in-first-order-logic/35205#35205 Answer by Robin Chapman for Exponent function as uninterpreted function in first order logic Robin Chapman 2010-08-11T09:22:35Z 2010-08-11T09:22:35Z <p>The function \$f(m,n)=m^n\$ is primitive recursive, so expressible in first-order arithmetic: there is a formula in three free variables \$F(m,n,p)\$ over the language of first-order arithmetic which is valid in Peano arithmetic for numerals \$m\$, \$n\$ and \$p\$ iff \$p=m^n\$.</p> <p>Logic texts (e.g. Boolos and Jeffrey) will prove that primitive recursive functions can be expressed in this way, but the general method does not tend to provide nice formulas for concrete examples like this.</p>