Often philosophers, logicians, and mathematicians employ a notion of intended structure when talking about a branch of mathematics. In addition, we know that there are foundational mathematical theories that can find representatives for the objects of informal mathematics. In this paper, we examine how faithfully foundational theories can represent intended structures, and show that this question is closely linked to the decidability of the theory of the intended structure. We argue that this sheds light on the trade-off between expressive power (...) and meta-theoretic properties when comparing first-order and second-order logic. (shrink)

We give a model-theoretic proof of the fact that for all infinite Abelian groups P ≠ NP in the sense of binary nondeterminism. This result has been announced 1994 by Christine Gabner.

We prove that all infinite Boolean rings (algebras) have the property P ≠ NP according to the digital (binary) nondeterminism.

For an arbitrary finite algebra $\g A = (A, f, 0, 1)$ one defines a double sequence $a(i,j)$ by $a(i,0)\!=\!a(0,j)\! =\! 1$ and $a(i,j) \!= \!f( a(i, j-1) , a(i-1,j) )$.The problem if such recurrent double sequences are ultimately zero is undecidable, even if we restrict it to the class of commutative finite algebras.

A structure of finite signature is constructed so that: for all existential formulas $\exists ??\varphi (??,??)$ and for all tuples of elements $??$ of the same length as the tuple $??$, one can decide in a quadratic time depending only on the length of the formula, if $\exists ??\varphi (??,??)$ holds in the structure. In other words, the structure satisfies the relativized model-theoretic version of P=NP in the sense of [4]. This is a model-theoretical approach to results of Hemmerling and (...) Gaßner. (shrink)

We use a new version of the Definability Theorem of Beth in order to unify classical theorems of Yuri Matiyasevich and Jan Denef in one structural statement. We give similar forms for other important definability results from Arithmetic and Number Theory.

Simple observations on diophantine definability over finite commutative rings lead to a characterization of those rings in terms of their diophantine behavior.

Genera connections between quantifier elimination and decidability for first order theories are studied and exemplified.

We prove that all infinite Boolean rings have the property P ≠ NP according to the digital nondeterminism.

We show that the set of natural numbers has an exponential diophantine definition in the rationals. It follows that the corresponding decision problem is undecidable.

Classical results of additive number theory lead to the undecidability of the existence of solutions for diophantine equations in given special sets of integers. Those sets which are images of polynomials are covered by a more general result in the second section. In contrast, restricting diophantine equations to images of exponential functions with natural bases leads to decidable problems, as proved in the third section.