1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How do you interpret $(-1)^{1/2}$? $\endgroup$ – Yuval Filmus Apr 28 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$ – Yuval Filmus Apr 28 at 8:27
  • 1
    $\begingroup$ How do you handle divisions by zero? What about exponentiations of zero? $\endgroup$ – Yuval Filmus Apr 28 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$ – Yuval Filmus Apr 28 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$ – Yuval Filmus Apr 28 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.