mathematical challenge, number theory, A005245, integer complexity, complexity theory, exponentiation, mathematics is inconsistent, arithmetic is inconsistent, inconsistency

My personal page Mathematical Challenge

By Karlis Podnieks

University of Latvia

 Number Theory Consider representing of natural numbers by using 1, +, * and brackets. One can prove easily that the best way of representing the powers of 3 is as follows: 3n = (1+1+1)*(1+1+1)*...*(1+1+1). All the other variants contain more than 3n 1's. Problem 1. Is 2n = (1+1)*(1+1)*...*(1+1) the best way of representing the powers of 2? It is the best way at least for n≤39 – as verified by Janis Iraids. More about the context – see A005245 in the The On-Line Encyclopedia of Integer Sequences. February 26, 2011 Added later: H. Altman, J. Zelinsky. Numbers with Integer Complexity Close to the Lower Bound, INTEGERS, Vol. 12A, 2012 (available online). J. Iraids, K. Balodis, J. Čerņenoks, M. Opmanis, R. Opmanis, K. Podnieks. Integer Complexity: Experimental and Analytical Results. Scientific Papers University of Latvia, Computer Science and Information Technologies, Vol. 787, 2012, pp. 153-179 (available online). Complexity Theory Consider representing of natural numbers by using 1, +, *, ^ and brackets (^ stands for exponentiation), for example: 10^(10^(10^10)). One cannot compute the “value” of this short expression in real time (whatever that means). Problem 2. How complicated is comparing the values of two expressions based on {1, +, *, ^}, the longer expression having the length n? More about the context – see:K. Podnieks. Towards a Real Finitism? December 2005. February 26, 2011 Mathematical Logic Problem 3. Prove that any formal theory of natural numbers allows deriving of contradictions – as predicted in 1908 by Henri Poincare. According to Gödel's First Incompleteness Theorem, any formal theory of natural numbers is either inconsistent, or incomplete. The final step: prove that the second clause can be dropped. More about the context – see the end of Section 6.1 of my book about Goedel's Theorem. Possibly, the first real step towards a solution is announced in: N. V. Belyakin. One \$omega\$-inconsistent formalization of set theory. The 9th Asian Logic Conference, 16-19 August, 2005, Novosibirsk, Russia (online abstract), where the following is announced: "From this fact follows, in particular, that the existence of strongly inaccessible cardinals is refutable in ZF." Note. The English translation of the abstract contains an error: one should remove [in] from the statement “It is not hard to check that T is [in]consistent wrt ZF+(existence of strongly inaccessible cardinals)”. February 26, 2011

mathematical challenge, number theory, A005245, integer complexity, complexity theory, exponentiation, mathematics is inconsistent, arithmetic is inconsistent, inconsistency