3
$\begingroup$

Does a mathematical operation 'op' exist so that there is a unique result for every expression? so:

a op bb op a
a op bc op a
a op bc op d
a op b = a op b

Thanks in advance.

  • 2
    Your property list doesn't stop nonunique results. For example, let $x\circ y := x$. This trivial operation discards the second input, and it satisfies all the listed properties whenever $a,b,c,d$ are distinct, yet $x\circ y$ and $x\circ z$ have the same result even if $y\ne z$. You should add after the second property these two: $$a\circ b\ne a\circ c $$ $$a\circ b\ne c\circ b$$ At any rate, if the set of elements under consideration is $X$ (and is infinite), any [injection](http://en.wikipedia.org/wiki/Injective_function) $X\times X\to X$ will determine such an operation.2011-09-08
  • 1
    Are we to take a, b, c, d distinct from each other?2011-09-08
  • 0
    @Mark Bennet: Unless stated, some of a,b,c,d could match and the requirements must still be met.2011-09-12
  • 0
    @Ross Millikan: If a=b the two sides of the first expression are equal, so my thought was that there was some unstated condition.2011-09-12
  • 0
    @Mark Bennet: good point. Looks like they have to be distinct2011-09-12

4 Answers 4

11

Yes, there are such operations. Apart from trivial examples, we need an infinite set. For instance, work with the set $\mathbb{N}$ of natural numbers, and define the operation $\ast$ by $a \ast b=2^a3^b$ for all natural numbers $a$, $b$.

There are more interesting examples, with additional properties. It is useful from now on to work with $\mathbb{N}_0$, the set of non-negative integers.

On $\mathbb{N}_0$, define the operation $\ast$ by $a\ast b=2^a(2b+1)-1$. Then it turns out not only that $a\ast b \ne c\ast d$ if $(a,b)$ and $(c,d)$ are distinct ordered pairs, but that in addition the operation $\ast$ maps $\mathbb{N}_0\times \mathbb{N}_0$ onto $\mathbb{N}_0$. That means that for every $c \in \mathbb{N}_0$, there is a unique ordered pair $(a,b)$ such that $a\ast b=c$. Verification of this fact is easy. Given any non-negative integer $c$, express $c+1$ as a power of $2$ times an odd number. That uniquely determines $a$ and $b$.

The operation $\ast$ on $\mathbb{N}_0$ defined by $$a\ast b=\frac{(a+b)(a+b+1)}{2}+a$$ also maps $\mathbb{N}_0\times \mathbb{N}_0$ onto $\mathbb{N}_0$, and has the property you seek. These various pairing functions are even useful. You may want to look at this link. This mapping $\ast$ has the nice property of being a polynomial mapping. Verification that it has the required properties takes more effort than in the preceding example.

We can also find operations of the type you seek on the reals, indeed on any infinite set, but the details get more complicated.

  • 0
    +1. By the last sentence, do you mean that if $X$ is an infinite set, then $X \times X$ has the same cardinality as $X$? Is this true in general?2011-09-09
  • 4
    @Srivatsan, I don't know whether that's what Andre means, but it's true.2011-09-09
  • 0
    @Srivatsan Narayanan: I meant that if $X$ is any infinite set, then there is a binary operation $\ast$ on $X$ such that $a\ast b=c\ast d$ implies that $a=c$ and $b=d$. This is an immediate consequence of the fact that $X\times X$ and $X$ have the same cardinality. (Of course we need the Axiom of Choice.) By "the details get more complicated" I meant that though there is a concrete construction on the reals, it is kind of messy, just like Cantor's construction of an explicit one to one (onto) mapping from $\mathbb{R}\times \mathbb{R}$ to $\mathbb{R}$.2011-09-09
4

The Cantor pairing function $(a+b)(a+b+1)/2+b$ is an example on $\mathbb{N}$

1

To give an example on the reals, or at any rate on the reals $x$ such that $0\le x\lt1$, consider $$0.a_1a_2a_3\dots{\rm\quad op\quad }0.b_1b_2b_3\dots=0.a_1b_1a_2b_2a_3b_3\dots$$ where the $a_i$ and $b_i$ are the decimal digits of the two numbers.

  • 0
    And what if your right-hand side is a real with two different expansions?2011-09-12
  • 0
    @GEdgar, I don't know any reals that have two different expansions. If you are alluding to the possibility that the RHS could be all 9s from some point on, it can't, because that would require the reals on the left to be all 9s from some point on, which they aren't.2011-09-12
  • 0
    @Gerry: What GEdgar is saying is that your operation is contingent on the _form_ of the numbers and not just their value. While you can still constrain that form to ensure that reals have unique decimal expansions (as you noted, just require 'no infinite expansion ending in 9s), doing so means that your mapping isn't onto (consider 'splitting' an RHS of .0909090909...). That doesn't matter here, but there are circumstances where a full bijection is useful and this is an easy trap to fall into. (I have more than once myself, even here on math.SE...)2011-09-12
  • 0
    @Steven, thanks. I know very well that the map I give isn't onto, but, as you say, that doesn't matter here; OP didn't ask for an onto op.2011-09-12
0

Your operation is essentially the operation of forming ordered pairs.

  • 0
    These are of course ordered pairs, edited to make that explicit.2011-09-12
  • 0
    aha! Good point.2011-09-12