Define a quotient structure for $(a,b)\sim(c,d)$ iff $a+d=b+c$ in terms of $+$ and $\times$ operators

Question

This is a past paper exam question, I don't really understand how to define this quotient structure.

The relation is on $\Bbb{N}$

In the preceding question I proved that this relation is an equivalence.

The equivalence class of some (a,b), which I will denote $[(a,b)]_\sim$ = {(c,d) | a+d=b+c}

I then worked through a few example classes to determine the pattern and see if I could describe the quotient set:

$[(a,a)]_\sim = \{(c,c) | c \in \Bbb{N}\} $

$[(1,2)]_\sim = \{(c,d) | c \in \Bbb{N} , 1+d = 2+c\} = \{(c,c+1) | c \in \Bbb{N}\}$

$[(1,3)]_\sim = \{(c,d) | c \in \Bbb{N} , 1+d = 3+c\} = \{(c,c+2) | c \in \Bbb{N}\}$

$[(2,1)]_\sim = \{(c,d) | c \in \Bbb{N} , 2+d = 1+c\} = \{(c,c-1) | c \in \Bbb{N}\}$

Clearly, $\forall (a,b) \in \Bbb{N} \times \Bbb{N}, [(a,b)]_\sim = \{(c,c+b-a) | c \in \Bbb{N}\}$

-

I feel like I've understood the relation, but the question asks me "By considering representative members of these classes, or otherwise, describe how operations of $+$ and $\times$ may be defined to form a quotient structure.", and I don't really understand that. Clearly, the quotient set is the set of all possible values of b-a, which is countably infinite. I don't understand how to define that using operations of + and X though.

Answer 1

It doesn't seem that there's really any motivation to define addition or multiplication in the quotient structure a certain way (at least, not from what you've posted), so here's a big motivation: $\Bbb N/\sim$ is quite often how the set of integers is defined using $\Bbb N$. The idea is that $(a,b)$ represents $a-b$ (which needn't make any sense if we're dealing only with natural numbers), and that $(a,b)\sim(c,d)$ iff $a-b=c-d$. In the context of integers, this is of course equivalent to $a+d=b+c$, but since we're dealing with natural numbers only, we need to use the "$a+d=b+c$" version.

I will (temporarily) call the addition and multiplication operations on $\Bbb N/\sim$ by $\oplus$ and $\odot$, to distinguish from the operations $+$ and $\cdot$ on $\Bbb N$. The operation $-$ will represent subtraction on the integers as we're used to (that is, as a superset of $\Bbb N$, rather than being derived as a quotient of $\Bbb N$), just to give us an idea of what we need to happen with $\oplus$ and $\odot$. Now, $$(a-b)+(c-d)=(a+c)-(b+d),$$ so we'll need $$[(a,b)]_\sim\oplus[(c,d)]_\sim:=[(a+c,b+d)]_\sim.$$ Also, $$(a-b)\cdot(c-d)=a\cdot c-a\cdot d-b\cdot c+b\cdot d=(a\cdot c+b\cdot d)-(a\cdot d+b\cdot c),$$ so we'll need $$[(a,b)]_\sim\odot[(c,d)]_\sim:=[(a\cdot c+b\cdot d,a\cdot d+b\cdot c)]_\sim.$$

You should be able to show that each $\sim$-equivalence class has a unique representative $(a,b)$ such that $a=1$ or $b=1$ (or $a=b=1$). This should help you to prove that $\oplus$ and $\odot$ are in fact well-defined.

Once we're done with that, we can call $\Bbb N/\sim$ by "$\Bbb Z$", noting that $[(1,1)]_\sim$ is the $\oplus$-identity element of $\Bbb Z$ and that $[(2,1)]_\sim$ is the $\odot$-identity element. Also, for any $[(a,b)]_\sim\in\Bbb Z$, the $\oplus$-inverse of $[(a,b)]_\sim$ is $[(b,a)]_\sim$. Now, we have a natural inclusion $\Bbb N\to\Bbb Z$ given by $n\mapsto[(n+1,1)]_\sim$, and you can see that this inclusion maps $n+m$ to $[(n+1,1)]_\sim\oplus[(m+1,1)]_\sim$ and maps $n\cdot m$ to $[(n+1,1)]_\sim\odot[(m+1,1)]_\sim.$

This inclusion's operational compatibility allows us to simply call $[(n+1,1)]_\sim$ by "$n$" and $[(1,n+1)]_\sim$ by "$-n$" for all (positive) $n\in\Bbb N$, and we call $[(1,1)]_\sim$ by "$0$"; likewise, call $\oplus$ by "$+$" and $\odot$ by "$\cdot$." In this way, we effectively treat $\Bbb N$ as a substructure of this new structure $\Bbb Z$ that we've constructed (and which has all the properties we're used to), while at the same time simplifying the notation we were using in $\Bbb Z$ before.

Answer 2

I think you missed the essence of the relation. Take for example the equivalence class of $\,(1,2)\,$:

$$(a,b)\sim(1,2)\iff a+2=b+1\iff b-a=1$$

So you have a pretty well and nicely defined equiv. class:

$$[(1,2)]:=\{\;(a\,,\,a+1)\;;\;a\in\Bbb N\;\}$$

Also

$$(a,b)\sim (7,3)\iff a+3=7+b\iff b-a=-4\implies$$

$$[(a,b)]=\{\;(a\,,\,a-4)\;;\;a\in\Bbb N\;\}\ldots\text{etc.}$$

Then, assuming that for you $\,\Bbb N:=\{1,2,3,...\}\,$ ,you can take a representative for each equiv. class with say minimal first coordinate, say in the two examples above $\,(1,2)\;,\;(5,1)\,$ , and now you can define, say:

$$(1,2)+(5,1):=(6,3)\;,\;(1,2)\cdot(5,1):=(5,2)$$

or in any other way you want (I really don't understand what you mean by "quotient structure"...)

Answer 3

The idea is that the quotient is just the set of integers. Indeed any class in $\mathbb N\times \mathbb N/_\sim$ will be either equivalent to $(a,0)$ or $(0,a)$ for some non-negative integer $a$ (I am assuming that $0\in\mathbb N$). Then you think of $(a,0)$ as $+a$ and of $(0,a)$ as $-a$. Then you can define addition and multiplication accordingly:

$$(a,b)+(c,d)=(a+c,b+d)$$

$$(a,b)\cdot(c,d)=(ac+bd,bc+ad)$$

Answer 4

It's hard to figure out a big "hint" here that doesn't spell out what this problem is doing, so I'm just going to spell it out:

This problem is defining the integers based on the natural numbers.

Basically, $(a,0)$ means $+a$, a positive integer, and $(0,a)$ means $-a$.

In general if $a<b$ then $(a,b)\sim (0,c)$ for some $c$. If $a=b$ then $(a,b)\sim(0,0)$. If $a>b$ then $(a,b)\sim (c,0)$ for some $c$.

Then, intuitively, $(a,b)$ is "representing" the integer $a-_zb$, where $-_z$ is some unknown binary operation we'd want to have but don't have yet. Then how would you add $(a-_zb)+(c-_zd)$ if you wanted it to be of the form $x-_zy$ with $x,y\in \mathbb N$? How would you multipliy $(a-_zb)\times (c-_zd)$ to get $u-_z v$ with $u,v\in\mathbb N$?

Answer 5

Intuitively, $(a,b)_\sim$ represents the integer $a-b$.

Now, we the relation is $(a,b)\sim (c,d)\iff a+c=b+d$

Note that we might "identify" an integer as the unique solution to $a+x=b$, which we might then start to call $a-b$. Note that if $a+d=b+c$ then $$b+x=a$$

$$b+d+x=a+d$$

$$b+d+x=b+c$$

and since $c$ is a natural, the cancellation law means

$$d+x=c$$

It follows this relation partitions the natural numbers into classes that "preserve" the unique solution to an equation. So $b+x=a$ and $d+x=c$ are equivalent when $(a,b)\sim (c,d)$. Since if $b+x'=a$, $d+x=c$, then $$(b+d)+(x+x')=(c+a)$$ $$(a+c)+x''=(b+d)$$ where $x''$ is our "new" solution, it is but natural to sum these classes as $$(a,b)+(c,d)=(a+c,b+d)$$

So, suppose that $(a,b)$ is "the solution" to $b+x=a$ and $(c,d)$ is "the solution" to $d+x'=c$. Then we'd like to know what $(a,b)\times (c,d)$ is the solution to. Multiplying gives $$(b+x)(d+x')=ac$$

$$ad+bx'+dx+xx'=ac$$

We need to get rid of $bx'$ and $dx'$. The trick is to note that $$db+dx=da$$ and $$bd+bx'=bc$$ so that after adding one more $db$,

$$(db+dx)+(bx'+bd)+xx'=bd+ac$$

$$da+bc+xx'=bd+ac$$

$$(bc+ad)+xx'=(bd+ac)$$

All in all this tells us that it is natural to define $$(a,b)\times (c,d)=(ac+bd,ad+bc)$$

ADD Check that this two newly defined operations are such that

$(0)$ The resulting class ${\bf a }+{\bf b }$ and ${\bf a }\times {\bf b }$ is independent of which element in $x\in {\bf a }$ and which element $y\in {\bf b }$ we pick to carry out the operation.

$(1)$ There exists a class, which we shall denote by $\bf 0$, for which ${\bf a }+{\bf 0 }={\bf 0}+{\bf a }={\bf a }$ for any class $a$.

$(2)$ For any two classes ${\bf a }+{\bf b }={\bf b }+{\bf a }$ and $({\bf a }+{\bf b })+{\bf c}={\bf a }+({\bf b }+{\bf c})$

$(3)$ There exists a class which we shall denote ${\bf 1}$ for which ${\bf 1}\times {\bf b}={\bf b}\times {\bf 1}= {\bf b}$

$(4)$ For each class ${\bf a}$ there exist a class ${\bf b}$ for which ${\bf a}+{\bf b}=\bf 0$. We shall denote this (unique) class by ${\bf -a }$.

BONUS Build $\Bbb Q$ from $\Bbb Z$ by considering the relation $\simeq$ in $\Bbb Z\times\Bbb Z\smallsetminus \{0\}$ for which $(a,b)\simeq (c,d)\iff ad=bc$ and giving $(\Bbb Z\times\Bbb Z\smallsetminus \{0\})/\simeq$ and appropriate structure. In this case, multiplication will be the easy one, and summation will be "strange".

Answer 6

You have for example $$\begin{align}[(1,2)]=[(42,43)]&=\{(a,a+1)\mid a\in\mathbb N\}\\ [(1,1)]=[(42,42)]&=\{(a,a)\mid a\in\mathbb N\}\\ [(7,3)]=[(42,38)]&=\{(a+4,a)\mid a\in\mathbb N\} \end{align}$$ We'd like to define an addtion on $\mathbb N^2$ such that $(a,b)\sim(a',b')$ and $(c,d)\sim(c',d')$ implies $(a,b)+(c,d)\sim(a',b')+(c'd')$. If we can, this allows us to define an addition on $\mathbb N^2/\sim$ by letting $[(a,b)]+[(c,d)]=[(a,b)+(c,d)]$. Fortunately, the straightforward idea of componentwise additon works: If $a+b'=a'+b$ and $c+d'=c'+d$ then $(a+c)+(b'+d')=(a+b')+(c+d')=(a'+b)+(c'+d)=(a'+c')+(b+d)$ i.e. $(a+c,b+d)\sim(a'+c',b'+d')$. It turns out that this makes $\mathbb N^2/\sim$ an abelian group with neutral element $[(1,1)]$ and where the inverse of $[(a,b)]$ is $[(b,a)]$. We have an embedding (an injective monoid homomorphism) $\iota\colon \mathbb N\to\mathbb N^2/\sim$ given by $\iota(n)=[(n+1,1)]$.

With this in mind we note that $[(a,b)]=\iota(a)-\iota(b)$ (where the subtraction is taken in $\mathbb N^2/\!\sim\,$!).

This suggests that we want our multiplication to satisfy $$[(a,b)]\cdot [(c,d)] = (\iota(a)-\iota(b))\cdot(\iota(c)-\iota(d))=\iota(a)\iota(c)+\iota(b)\iota(d)-\iota(a)\iota(d)-\iota(b)\iota(c).$$ This motivates us to try to define $(a,b)\cdot(c,d)=(ac+bd,ad+bc)$. It turns out, this works and ultimately makes $\mathbb N^2/\sim$ a commutative ring with unit, henceforth denoted by $\mathbb Z$.

Answer 7

Below I explain (from scratch) the motivation, since many textbooks omit such. The goal is to construct the ring $\,\Bbb Z\,$ from the semiring $\Bbb N.\,$ (A semiring is that structure obtained from a ring by dropping the hypothesis on existence of additive inverses ("negatives"). So, informally, a semiring is a "ring without negatives", sometimes (jokingly?) called a rig, i.e. "ri$\rm\color{#c00}n$g" without $\rm\color{#c00}n$ = $\rm\color{#c00}n$egatives).

We wish to construct, in the most general way, a ring $\,\Bbb Z\,$ containing the semiring $\,\Bbb N.\:$ Here, "most general" means two things. First, $\rm\,\Bbb Z\,$ should contain no elements other than what are needed for it to be a ring containing $\,\Bbb N.\,$ Note that $\,\Bbb Z\,$ must contain some elements not in $\rm\,\Bbb N,\:$ e.g. an additive inverse of $\,1,\,$ denoted $\,-1.\:$ But, as we shall see, it need not contain a multiplicative inverse of $\,2.\:$ Second, besides minimizing the underlying set, we also seek to minimize the assumptions, to keep the constructed object as general as possible. So we desire that no equalities are true in $\,\Bbb Z\,$ other than those equalities true in $\,\Bbb N,\,$ and those equalities implied by the ring axioms, e.g. $\rm\:-1 + 1 = 0.\:$

Let's consider the first constraint. We seek a set to represent $\,\Bbb Z.\: $ By hypothesis, $\,\Bbb Z\,$ contains $\,\Bbb N.\,$ Being a ring, it must contain an additive inverse $\rm\,-b\,$ for every $\rm\,b\in\Bbb N.\:$ Being closed under addition, $\,\Bbb Z\,$ must contain all elements of the form $\rm\,a + (-b) =: a-b \,$ for all $\rm\,a,b\in\Bbb N.\:$ No further elements are needed, since, using the ring axioms, and consequences (e.g. law of signs), one can easily check that set of element of this form are closed under all ring operations, e.g.

$\begin{eqnarray}\rm (1)\qquad\qquad &&\rm\qquad -(a\! -\! b)&=&\rm b\! -\! a\\ \rm(2)\qquad\qquad &&\rm a\!-\!b\, +\, \hat a\!-\!\hat b&=&\rm a\!+\!\hat a\, -\, (b\!+\!\hat b)\\ \rm(3)\qquad\qquad &&\rm (a\!-\!b)\,\ (\hat a\!-\!\hat b)&\,=\,&\rm a\hat a\!+\!b\hat b\,-\,(a\hat b\!+\!\hat a b) \end{eqnarray}$

To construct $\,\Bbb Z\,$ set-theoretically, we can represent the element $\rm\:a\!-\!b\:$ by a pair $\rm\:(a,b)\in\Bbb N^2.\:$ However, it is not true that $\rm\:(a,b) = (\hat a,\hat b)\iff a=\hat a,\, b=\hat b\:$ since the ring axioms imply various equalities, e.g. $\rm\:a\!-\!a = b\!-\!b,\;$ so $\rm\:(a,a) = (b,b).\:$ Such equalities induce an equivalence relation $\sim$ on our pair representation $\rm\,\Bbb N^2.\ $ Comparing two general elements of this form we find

$\begin{eqnarray}\rm(4)\qquad\quad\ \ a\!-\!b &\,=\,&\rm \hat a\!-\!\hat b &\iff&\rm a+\hat b &=\,&\rm \hat a+b\\ \rm so\ \ \ \ (a,\,b) &\sim&\,\rm (\hat a,\,\hat b) &\iff&\rm a+\hat b &= &\rm \hat a+b\end{eqnarray}$

which is the equivalence relation specified in your exercise. Thus, recalling our second constraint of minimizing equalities, since these equalities are forced by the ring axioms, we must include them in our equivalence relation. It turns out that no other equalities are needed, since we can show that the resulting quotient structure forms a ring. Namely, let the underlying set of $\rm\,\Bbb Z\,$ be the quotient set $\,\Bbb N^2/\sim.\:$ Next, transport the ring structure from the elements $\rm\:a\!-\!b\:$ to the pairs $\rm\:(a,b)\:$ by translating the operations $\,(1),(2),(3)\,$ to pair operations, e.g.

$\qquad\qquad\ \ \begin{eqnarray} \rm (a\!-\!b)\,\ (\hat a\!-\!\hat b)\!\! &\,=\,&\rm a\hat a\!+\!b\hat b-(a\hat b\!+\!\hat a b)\\ \to\quad\rm\ \ (a,\,b) \ (\hat a,\,\hat b)\ &=&\rm (a\hat a\!+\!b\hat b,\ a\hat b\!+\!\hat a b)\end{eqnarray}$

However, since the definitions of these operations employ particular representatives of the equivalence classes, we must check that the definitions are well-defined, i.e. independent of such choices. That is the task presented to you in the exercise. Then you will need to verify the ring axioms, and that $\,\Bbb N\,$ embeds in $\,\Bbb Z.$

Remark $\ $ This is a special case of a general construction: the ring of differences of an additively cancellative semiring. It is a sort of additive analog of the construction of fraction fields and localizations.