True or false: $\left(\mu\left[a,\bar{a}\right]=\mu\left[b,\bar{b}\right]\iff a+\bar{b}=b+\bar{a}\right)\iff\mu$ is a homomorphism?

64 Views Asked by At

Note: square brackets $\left[\dots\right]$ are use to indicate parameter lists in function signatures. Addition of ordered pairs in the domain is defined by

$$\left<a,\bar{a}\right>+\left<b,\bar{b}\right>=\left<a+b,\bar{a}+\bar{b}\right>.$$

The book I'm reading states without proof or clarification that a mapping of ordered pairs (of natural numbers $\{1,2,\dots\}$) is a homomorphism if and only if

$$\mu\left[a,\bar{a}\right]=\mu\left[b,\bar{b}\right]\iff a+\bar{b}=b+\bar{a}.\tag{1}$$

The codomain will end up being the integers, and $\mu$ will be subtraction. But at this point all we have to work with are that addition is commutative, associative, and obeys a term-wise cancellation law $a+b=a+c\implies{b=c}$.

It is unclear to me if the authors intend the asserted property (1) to hold for all homomorphisms of ordered pairs, or they are talking about the specific case of integer subtraction.

I've tried to prove it for a generic homomorphic mapping of ordered pairs of natural numbers to some unspecified codomain in which there is addition having the stated properties. But I haven't been able to come up with a proof.

Is the stated property (1) held by all homomorphisms with addition in the domain and codomain having the stated properties? I'm not asking for a proof. I'm only asking if the proposition is true.

1

There are 1 best solutions below

1
On BEST ANSWER

Here's a counterexample:

Consider the map $\mu\colon\Bbb N^2\to\Bbb N$ by $\mu(x,y)=y$. Then,

$$\mu(a,\bar a)+\mu(b,\bar b)=\bar a+\bar b=\mu(x,\bar a+\bar b)=\mu(a+b,\bar a+\bar b)$$

So, $\mu$ is a homomorphism, but,

$$\mu(a,\bar a)=\mu(b,\bar b)\implies \bar a=\bar b$$

so $a$ and $b$ can be any natural number, so $a+\bar b=b+\bar a$ doesn't necessarily hold. For example, $\mu(1,2)=\mu(3,2)=2$ but $1+2=3\neq 5=3+2$