Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Are there any ordered equivalence classes that can be used to distinguish 1+1 and 2 , On one side there is an operation and on the other side just a single number.

This becomes more obvious when dealing with factoring and multiplication , e.g. 17.19 = 323 , LHS contains more information than RHS but how to put an order on them?

share|cite|improve this question
up vote 3 down vote accepted

An equivalence relation on a set $S$ partitions $S$ into disjoint subsets. What is $S$ in your case?

If $S$ is a set of standard numbers, like $\mathbb R$ or $\mathbb N$, then you can't put $1+1$ and $2$ into separate equivalence classes, because they are the same element (of $\mathbb R$ or $\mathbb N$ or whatever).

But if your set $S$ is the set of strings that represent well-formed arithmetic expressions, then you can define an equivalence relation according to (for example) the number of arithmetic operations in the string. Then "$2$" is equivalent to "$323$", and "$1+1$" is equivalent to "$17 \times 19$".

share|cite|improve this answer
I suppose you could define two strings to be equivalent if they represent the same number and have the same number of arithmetic operations. Then $5\times6$ would be equivalent to $3\times10$ but not to $2\times3\times5$, nor to $5\times7$. – Gerry Myerson Oct 27 '11 at 11:26
But what their computational complexity? 1+1 can supposedly be calculated in 1 step , where as 2 is calculated in 0 steps. so 1+1 and 2 end up being in different computational complexity classes. Maybe I should have not used the equivalance classes. – Arjang Oct 27 '11 at 11:36

You could look at the set $\mathbb N\times\mathbb N$ of ordered pairs of natural numbers with equality as equivalence relation. The single number $2$ should then be written as $(2,0)$. For this equivalence relation, $(1,1)$ and $(2,0)$ are not equivalent.

On the set $\mathbb N\times\mathbb N$, there is then a weaker equivalence relation defined by: $(a,b)\sim (c,d)$ if and only if $a+b=c+d$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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