Can the non-zero real numbers be classified into equivalence classes, where equivalence of $a$ and $b$ means that there is an algebraic expression containing $b$ exactly once that is equal to $a$? For example, all real algebraic numbers $\mathbb{A}\setminus\{0\}\subset\mathbb{R}$ should be equivalent, and every number $x\in\mathbb{R}\setminus\mathbb{Q}$ should be equivalent to at least the numbers $x+\mathbb{A}$ (and more, for example $\mathbb{A}x+\mathbb{A}$)

I am not 100% sure about the term "algebraic", I want it to mean expressions that can be created using a finite amount of the basic operators, $a+b,a\cdot b,a^b$. I would define them as the set of finite derivations (language) $L^*$ with the rule

$$G::=G+G\mid G\cdot G\mid G^G\mid x\in\mathbb{A}\setminus\{0\}$$ with $G\neq 0$ everywhere and an expression containing $b$ exactly once could be defined by an element of the language $L_b^*$ with the rule

$$G_b::=G_b+G\mid G_b\cdot G\mid G_b^G\mid G^{G_b}\mid b,$$ again with $G\neq 0$ and with real values everywhere ($(-1)^{1/2}$, $0^{-1}$,... would not be allowed in this context-sensitive grammar)

With that definition, we have the relation

$a\equiv b\Leftrightarrow \exists x\in L_b^*: a=\text{eval}(x)$

where $\text{eval}(G_b)$ is the exact numerical evaluation of the expression $G_b$.

In other words, $\pi$ and $\pi+1$ and $2^{\frac{1}{4-\pi^2}}$ etc... are equivalent. (As all can be derivated as $G_\pi$)

Now the first question is technically, is the previous definition OK so far? I would be happy to overwork it, this is written from scratch.

Secondly, how many equivalence classes are there (I would be surprised to see finitely many), Countable or uncountably many? Can things be said about, for example, if $\pi$ and $e$ are equivalent?

I guess the question "are the two arbitrary real numbers a and b equivalent" is undecidable, with respect to the Entscheidungsproblem or simply the equality problem in the reals. Is it?

  • $\begingroup$ you should write $\exists x \in G_b, a = \text{eval}(x)$ though, L is not needed. $\endgroup$ – user58512 Mar 15 '13 at 20:30
  • $\begingroup$ @caveman Aah, yeah the notation is incorrect here, but shouldnt it be $x\in\tilde{L}^*$? EDIT: I changed $\tilde{L}$ to $L_b$ to add the reference to b, and changed the part you noted. $\endgroup$ – CBenni Mar 15 '13 at 20:32
  • 1
    $\begingroup$ I don't understand what the aim is here $\endgroup$ – user58512 Mar 15 '13 at 20:40
  • $\begingroup$ @caveman, it origined from the question "can pi be written as an expression of e; for example, could it be that $\pi=a+b*e^c$ where a,b,c are algebraic". This, generalized, is the question above $\endgroup$ – CBenni Mar 15 '13 at 20:54
  • 2
    $\begingroup$ I do not understand the close votes here. This is a legitimate subject for discussion, and has been the subject of published work in the past. $\endgroup$ – MJD Mar 15 '13 at 20:56

A theorem of Richardson says that it is indeed undecidable whether two expressions from even a fairly limited language represent the same real number. This seems to be quite close to what you are asking.

Note that this is not the Entscheidungsproblem.

  • $\begingroup$ 1. I am aware that is isnt the Entscheidungsproblem, however it is closely related 2. Eventhough it is undecidable for aritrary a,b; Can there be something said about $\pi$ and $e$? 3. What about the number of equivalence classes? At least qualitively? There are more than 2; 1 for the algebraics, and more than 1 for the non-algebraics - else it would be decidable $\endgroup$ – CBenni Mar 15 '13 at 21:00
  • $\begingroup$ Did you read the linked article? $\endgroup$ – MJD Mar 15 '13 at 21:01
  • $\begingroup$ the wikipedia does not really answe the question; And I have yet to read (and understand) the linked pdf $\endgroup$ – CBenni Mar 15 '13 at 21:08

The question might be easier to consider in the abstract.

If you can write down any relation at all that is an equivalence, then the reals can be partitioned into equivalence classes modulo that relation.

If you can write down any relation at all that is not an equivalence relation, then you can consider the equivalence relation it generates.

If you have any function $f : \mathbb{R} \to \mathbb{R}$, then you can define a relation $\sim$ by $x \sim f(x)$. If you have many such functions, then you can consider the relation

  • $x \sim y$ if and only if there is an $f$ such that $x = f(y)$

If your set of functions contains the identity, then $\sim$ is reflexive.

If your set of functions is closed under composition, then $\sim$ is transitive, because

$$ x = f(y) \quad \text{and} \quad y = g(z) \quad \implies \quad x = (f \circ g)(z) $$

If your set of functions furthermore has the property:

  • If $x = f(y)$, then there is a $g$ such that $y = g(x)$

Then $\sim$ is symmetric.

If your set of functions has all of the stated properties, then $\sim$ is an equivalence relation.

  • $\begingroup$ This only states what equivalence relations are - not really an answer? However, it is reflexive (obviously, as b is in the language $L_b$), it is symmetric (not so easy to prove, but possible) and it is transitive, as composition is included per definition. $\endgroup$ – CBenni Mar 15 '13 at 21:06

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.