1
$\begingroup$

(Using the infinite set Z, because modulo addition lacks positive and negative values.)

We could find identity $0$, for if we see $a+b=a$ or $b+a=a$, $(a\neq b)$, we know either $a$ or $b$ is $0$, and need only find another $a+c=c$ or $b+c=c$ ($c\neq a, c\neq b$) to determine which.

We could use identity to determine pairs of integers, one positive and one negative $i+j=0$, but not which is which.

It seems the distinction is that a sum of positives is always positive; but sums including a negative can be positive or negative. But how to test, when you don't know which is which in the first place?

Perhaps grow a subset, until an inverse of an existing member is added?

Wait, maybe: using inverses, we can establish the two subsets, just not which is which. Then, we can test each for closure. The one that's closed under addition is the positives; the one that isn't is the negatives. No, that doesn't work, because we don't know which of the inverses are in the same set. e.g. $a+b=0, c+d=0$, but we don't know if $a$ and $c$ are the same sign, or if $a$ and $d$ are.

$\endgroup$
  • 2
    $\begingroup$ The negatives are also closed under addition. There is no way to distinguish positive from negative using only addition. You need to either fix an element (and require that element to be positive/negative), or use multiplication. $\endgroup$ – Tobias Kildetoft Jan 30 '18 at 7:13
  • $\begingroup$ OK, thanks! I was thinking that taking the inverse of the second operand gave subtraction, but so does taking the inverse of the first operand, and just combines the two closed subsets. $\endgroup$ – hyperpallium Jan 30 '18 at 7:21
  • $\begingroup$ In any case I don't really understand the question, because algorithms are not allowed to have infinite input. $\endgroup$ – Derek Holt Jan 30 '18 at 8:46
2
$\begingroup$

I will assume that we have a set containing elements with arbitrary names, but that it is possible to identify, for given elements $a$, $b$, the element $c$ such that $a+c=b$ and the element $d$ such that $a+b=d$.

Pick an arbitrary element $a$. Identify the element $b$ such that $a+b=a$. The element $b$ is $0$.

Now pick an arbitrary element $a\ne 0$. Identify the element $\overline{a}$ such that $a+\overline{a}=0$.

Given two distinct non-zero elements $a$, $b$, begin building three sets, \begin{align*} S(a)&=\{a,a+a,a+a+a,\ldots\}\\ S(b)&=\{b,b+b,b+b+b,\ldots\}\\ S(\overline{b})&=\{\overline{b},\overline{b}+\overline{b},\overline{b}+\overline{b}+\overline{b},\ldots\}. \end{align*} We do not need to imagine that these sets have been constructed in their entirety, but by simultaneously building up the three sets, we will eventually find that $S(a)$ has non-empty overlap with exactly one of $S(b)$ or $S(\overline{b})$. If $S(a)\cap S(b)\ne\emptyset$, we say that $a$ and $b$ have the same sign; if $S(a)\cap S(\overline{b})\ne\emptyset$, we say that $a$ and $b$ have opposite sign.

Although it is possible to determine whether two nonzero elements have the same sign, absolute sign determinations are not possible. This is because the map that sends $a$ to $\overline{a}$ is an automorphism of the group of integers under addition. In other words, since $a+b=c$ implies $\overline{a}+\overline{b}=\overline{c}$, the group obtained by sending every element to the corresponding element of opposite sign is isomorphic to the original group.

Note, however, that it is possible to perform magnitude comparisons. Given two distinct nonzero elements $a$ and $b$ of the same sign, identify the element $c$ such that $a+c=b$. If $c$ has the same sign as $a$ and $b$, we say that $b$ has greater magnitude than $a$; otherwise we say that $b$ as lesser magnitude than $a$.

With magnitude comparisons in hand, we may run the Euclidean algorithm on two nonzero elements of the same sign to determine their greatest common divisor of the same sign. If $g=\gcd(a,b)$, then $S(a)$ and $S(b)$ are subsets of $S(g)$.

Note that for any nonzero element $a$, the set $S(a)\cup\{0\}\cup S(\overline{a})$ under addition is isomorphic to the integers under addition, and that there are two homomorphisms of the integers onto this set, one that sends $1$ to $a$, the other that sends $1$ to $\overline{a}$.

$\endgroup$

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.