Let's have expressions that are finite-sized trees, with elements of $\mathbb N$ as leaf nodes and the operations {$+,\times,-,/$, ^} with their usual semantics as the internal nodes, with the special note that we allow arbitrary expressions as the right-hand side of the exponentiation operation. Are the equality between such nodes (or, equivalently, comparison to zero) decidable? Is the closure under these operations a subset of algebraic numbers or not? (Turns out, it isn't: https://en.wikipedia.org/wiki/Gelfond%E2%80%93Schneider_theorem, which disallows an easy reduction to solutions about algebraic numbers.)

This question is similar to this: Decidability of Equality of Radical Expressions but with the difference that here the exponentiation operator is symmetric in the type of the base and the exponent. That means that we could have exponents such as $3^\sqrt 2$. It isn't clear to me, whether allowing exponentiation with irrationals retains the algebraic closure.

This question is also similar to Computability of equality to zero for a simple language but the answers to that question focused on the transcendental properties of combinations of $\pi$ and $e$, which I consider out of scope here.

  • 1
    $\begingroup$ How do you interpret $(-1)^{1/2}$? $\endgroup$ Apr 28 '20 at 8:22
  • 1
    $\begingroup$ On the other hand, under every reasonable interpretation (including multiple allowed values per exponentiation operation), the set of numbers produced by your expressions is countable. $\endgroup$ Apr 28 '20 at 8:27
  • 1
    $\begingroup$ How do you handle divisions by zero? What about exponentiations of zero? $\endgroup$ Apr 28 '20 at 8:43
  • 1
    $\begingroup$ You also still haven't responded about the issue of complex exponentiation. What is $i^i$, for example? You can choose a particular branch of the complex logarithm function for definiteness, but so far haven't indicated so. $\endgroup$ Apr 28 '20 at 9:20
  • 1
    $\begingroup$ It seems that this question isn't completely thought out. I suggest taking a few days to reflect on the question, and asking it again when all of these points have been addressed. $\endgroup$ Apr 28 '20 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.