BASIC GROUP & RING LAWS

F Richard Singer III http://www.conceptualstudy.org

Edition Date: 1/2009

SECTION 1: BASIC GROUP LAWS

Jo: Does anyone recall the concept of a commutative group (which we also called an abelian group)?

Roy: An abelian group has a binary operation that is commutative and associative. It has an identity element for this operation. It also has a unary operation giving inverses for this operation.

Bob: Depending on whether we use additive or multiplicative notation we can state the basic laws defining a group as indicted below.

(x+y)+z = x+(y+z) (x·y)·z = x·(y·z) associative

0+x = x x+0 = x 1·x = x x·1 = x identity

-x+x = 0, x+-x = 0 /x·x = 1 x·/x = 1 inverse

x+y = y+x x·y = y·x commutative

Kay: There are groups involving the composition of functions. These structures were called transformation groups. For many transformation groups, composition is not commutative. However the symmetry group for the rectangle was commutative.

Jan: The cyclic groups we looked at were commutative. So were the bit string groups. In fact the symmetry group for the rectangle is the bit string group with stings of length 2.

Jo: We shall deduce some propositional laws that are satisfied by commutative groups. Then we will consider which of these are also satisfied by non-commutative groups. We begin with commutative groups because they occur in ordinary algebra. The rational numbers form a commutative additive group. The non-zero rational numbers also form a commutative multiplicative group. The laws defining a commutative group express what addition and multiplication have in common.

Kay: The same can be said about the real numbers and about the complex numbers.

Bob: The integers form an additive group, but the non-zero integers do not form a multiplicative group. Most multiplicative inverses are missing.

Jo: Let a and b denote any terms. For an additive language, we abbreviate a+-b as a-b. We often call this subtraction, but you should be able to think of what is said in terms of the unabbreviated language of addition and additive inverses. See if you can deduce the laws below.

Th1: 1. (x+y)-y = x 2. -x+(x+y) = y 3. x+(-x+y) = y 4. (x-y)+y = x

Th2: 1. x = y Û x+z = y+z 1a. x = y Û z+x = z+y

2. x+z = y Û x = y-z 2a. x+z = y Û z = -x+y

3. x+z = x Û z = 0 3a. z+x = x Û z = 0

4. x+y = 0 Û x = -y 4a. x+y = 0 Û y = -x

Th3: 1. -0 = 0 2. -(-x) = x 3. -(x+y) = -y+-x

Th4: 1. -(x+y) = -x+-y 2. -(x-y) = y-x 3. (x+z)-(y+z) = x-y

Roy: For each part o Th1, start with the associative law. Then use the inverse law and the identity law.

Bob: I agree. Part 1 says: (x+y)+-y = x. Below is the deduction that Roy indicated.

(1) (x+y)+-y = x+(y+-y) associative

(2) (x+y)+-y = x+0 inverse

(3) (x+y)+-y = x identity

Jo: Since the other parts of Th1 can be deduced in a similar manner, lets move on to other theorems.

Th2: 1. x = y Û x+z = y+z 1a. x = y Û z+x = z+y

2. x+z = y Û x = y-z 2a. x+z = y Û z = -x+y

3. x+z = x Û z = 0 3a. z+x = x Û z = 0

4. x+y = 0 Û x = -y 4a. x+y = 0 Û y = -x

Th3: 1. -0 = 0 2. -(-x) = x 3. -(x+y) = -y+-x

Th4: 1. -(x+y) = -x+-y 2. -(x-y) = y-x 3. (x+z)-(y+z) = x-y

Jan: To deduce the biconditional x = y Þ x+z = y+z just deduce a conditional and its converse. That x = y Þ x+z = y+z is just a rule for equality. To deduce x+z = y+z Þ x = y assume x+z = y+z and deduce x = y by adding -z and using the defing laws for groups..

Roy: Actually we could add -z and use Th1.

(1) x+z = y+z

(2) (x+z)+-z = (y+z)+-z

(3) x = y Th1

Bob: Th2.1a follows from part 1 using commutivity. It can also be deduced without using commutivity. That x = y Þ z+x = z+y is just another rule for equality. To deduce z+x = z+y Þ x = y assume z+x = z+y and deduce x = y by adding -z on the left..

Jo: How could you use part 3 of Th2 to deduce part 1 of Th3?

Jan: Substituting 0 for x and z in x+z = x Û z = 0, gives 0+-0 = 0 Û -0 = 0. Now use the inverse law.

Roy: We could use Th2.4 instead to get 0+0 = 0 Û 0 = -0.

Kay: Substituting -x for y in x+y = 0 Û x = -y gives x+-x = 0 Û x = -(-x). This can be used with the inverse law to deduce Th3.2.

Jo: Explain how to obtain (-y+-x)+(x+y) = 0 Û -y+-x = -(x+y) from Th2. Then deduce Th3.3.

Bob: Substitute -y+-x for x and x+y for y in Th2.4.

Roy: Using the basic group laws gives (x+y)+-y+-x = 0, so -y+-x = -(x+y).

Kay: And if you want to deduce -(x+y) = -y+-x from this just use the symmetric rule.

Jo: Now consider Th4

Roy: For Part 1 use Th3.3 and commutivity.

Jan: Using Th3.3 and Th3.2, -(x+-y) = -(-y)+-x = y+-x, which is what Th 4.2 says.

Bob: By Th4.1, (x+z)-(y+z) = (x+z)+(-z+-y). Using the basic group laws gives Th4.3

Kay: We used the commutative law to prove Th4.1. Since -(y+x) = -x+-y in all groups, to find an exception to -(x+y) = -x+-y, all we need is to find is values for x and y such that x+y ¹ y+x. This is always possible in any non-commutative group

Roy: Th4.2 and Th4.3 can be deduced without using the commutative law.

Jo: Multiplicative language is often used when discussing groups that may or may not be satisfy the commutative law. When using multiplicative language, we usually omit the multiplication sign, so ab is brief for a·b. Likewise, a/b is brief for a·/b. We also use exponents as in ordinary algebra.

Jan: For non-commutative groups the 2 statements of the identity and inverse laws are not redundant.

Kay: Th1, Th2, Th3 were deduced without using the commutative law. They are laws for all groups

Bob: I wrote these theorem in multiplicative instead of additive language.

Th1: 1. (xy)/y = x 2. /x(xy) = y 3. (x/y)y = x 4. x(/xy) = y

Th2: 1. x = y Û xz = yz 1a. x = y Û zx = zy

2. xz = y Û x = y/z 2a. zx = y Û x = /zy

3. xz = x Û z = 1 3a. zx = y Û z = 1

4. xy = 1 Û x = /y 4a. xy = 1 Û y = /x

Th3: 1. /1 = 1 2. //x = x 3. /(xy) = /y/x

Jan: In multiplicative language, Th4.3 says (xz)/(yz) = x/y. This is the law for reducing fractions.

Kay: Another law for reducing fractions does depend on commutivity, namely xy/(xz). I found an example where this law fails in non-commutative groups.

Notation: The standard notation for the multiplicative inverse of x is x^-1 rather than /x. We use /x for several pedagogical reasons. It focuses on the fact that / is an operation. The notation is similar in style to the notation for additive inverses. The concept of a multiplicative inverse is conceptually prior to the concept of negative exponents, as x^-1 is defined as the multiplicative inverse of x.

Jo: To add an extra perspective I want to mention some broader types of structures. A structure which satisfies the associative law is called a semigroup. Thus a group is a special kind of semigroup. Another special kind of semigroup is called a monoid. A structure which satisfies the associative and identity laws is called a monoid. Thus a group can be regarded as a monoid with a unary operation which satisfies the inverse law. Th1, Th2, Th3 all depend on the inverse law and thus do not apply to a monoid which is not a group. Monoids satisfy some of the laws of exponents. Exponents should be regarded as abbreviations for repeated products. For example thus aa, aaa, aaaa are abbreviated as a², a³, a⁴. The meaning of exponents can be defined recursively.

Definition: a⁰ = 1 a¹ = a aⁿ⁺¹ = aⁿ·a where n is a positive integer.

Exponent Theorem: Let m and n be any natural numbers.

(1) 1ⁿ = 1 (2) xⁿx^m = x^n+m (3) (xⁿ)^m = x^nm

Proof: Part 1 follows by definition for n = 0 and n = 1. Proof for more values are given below.

(1) 1² = 1¹·1 definition

(2) 1² = 1 th4.2 for n = 1 (1) identity

(3) 1³ = 1²·1 definition

(4) 1³ = 1 (2)(3) identity

(5) 1⁴ = 1³·1 definition

(6) 1⁴ = 1 (4)(5) identity

Each proof for such a value draws on the proof for the preceding one. This sequence of proofs could be extended to obtain a proof of 1ⁿ = 1 for any positive value of n. See problems for further discussion of this proof and for proofs of other parts of the theorem.

Exercises and Problems

Ex1: Give a detailed deduction for th1 part 2.

Ex2: Give informal deductions for parts 2 and 3 and 4 of Th2, which makes no use of earlier parts of the theorem. Do this in the usual way for proving biconditionals, proving each of the conditionals separately. Use conditional inference to prove these conditionals.

Ex3a: Explain how 0+-0 = -0 and 0+-0 = 0 follow from the basic laws for groups. Then explain how these can be used to deduce -0 = 0.

Ex3b: A group is a structure in which you can solve simple equations. This perspective can be used in deducing laws. For instance instead of using Th2.4 to deduce -(-x) = x write an equation involving -(-x) and solve for -(-x) as if it was your unknown. One way to obtain such an equation is to substitute -x for x in the identity law, obtaining -(-x)+-x = 0. Show in detail how to use this to deduce Th3.2 from the basic group laws.

Ex3c: The equation solving perspective can also be used to deduce Th3.3 without first deducing Th2.4. Explain how substitution give this equation -(x+y)+(x+y) = 0. Then use the basic group laws to solve for -(x+y).

Ex4: Give detailed deductions for various part of Th4.

Ex5: The informal deduction for Th1.2 was given as below. Write this in multiplicative language, showing that it also proves the multiplicative version of this theorem. Do the same for some of the other deduction for additive versions Th2.

(1) (x-y)+y = x+(-y+y) associative

(2) (x-y)+y = x+0 (1) inverse

(3) (x-y)+y = x (2) identity

Pr1: Give counterexamples to show that th3.4 and th3.6 are not satisfied by groups that are not commutative.

Pr2 Let A(n) be any formula with a variable n ranging over the natural numbers. Let A(t) be the result of substituting any numerical term t for n in A(n). Stated as an inference rule, the principle of mathematical induction says: A(0), A(k) Þ A(k+1) infer A(n). We use this to prove part 1 of the Exponent Theorem. Use mathematical induction to prove part 2 and 3 of this theorem.

(1) 1⁰ = 1 definition

(a) 1^k = 1

(b) 1^k+1 = 1^k·1 definition

(c) 1^k+1 = 1 (a) (b) identity

(2) 1^k = 1 Þ 1^k+1 = 1 deduct and generalization

(3) 1ⁿ = 1 (1) (2) mathematical induction

Pr3 For a Monoid that also satisfies the commutative law show (xy)ⁿ = xⁿyⁿ.

SECTION 2: A DEDUCTIVE PRopositional Theory for RINGS

Jo: We will now deduce general laws for rings. Does any one recall the basic laws that define a ring?

Jan: A ring is a structure with 2 binary operation, usually called addition and multiplication, since these operations satisfy many of the same laws of ordinary addition and multiplication. A ring has identity elements for each of these operations, a unary operation giving additive inverses.

Jo: Just to be clear, in all rings addition is commutative, but multiplication may or may not be. A commutative ring is one in which multiplication is commutative.

(x+y)+z = x+(y+z)	(x·y)·z = x·(y·z)	associative
0+x = x x+0 = x	1·x = x x·1 = x	identity
x+-x = 0 -x+x = 0		inverse
x+y = y+x		commutative
x·(y+z) = x·y+x·z	(y+z)·x = y·x+z·x	distributive

Bob: Only one distributive law would be needed for the definition of a commutative ring. The other could be deduced from the other distributive law using the commutative law for multiplication.

Jo: Below are some theorems that can be deduced from the basic ring laws. Th1 thru Th7 are satisfied by all rings. Th8 is satisfied only by commutative rings.

Th1: 1. (x+y)-y = x 2. (x-y)+y = x

Th2: 1. x = y Û x+z = y+z 2. x+z = y Û x = y-z 3. x+z = z Û x = 0 4. x+z = 0 Û x = -z

Th3: 1. -0 = 0 2. -(-x) = x 3. -(x+y) = -y+-x

Th4: 1. -(x+y) = -x+-y 2. -(x-y) = y-x 3. (x+z)-(y+z) = x-y

Th5: (x+y)(w+z) = xw+yw+xz+yz

Th6: 0x = 0 & x0 = 0

Th7: 1. -1·x = -x & x·-1 = -x 2. -x·y = -(xy) & x·-y = -(xy) 3. -x·-y = xy

Th8: 1. (x+y)(x+z) = x²+(y+z)x+yz 2. (x-y)(x-z) = x²-(y+z)x+yz

3. (x+y)(x-y) = x²-y² 4. (x+y)² = x²+2yx+y²

Kay: We are using the standard conventions abbreviations from ordinary algebra.

Roy: We already deduced Th1, Th2, Th3, Th4 in Section 1.

Bob: Of course, these are satisfied because a ring is an additive commutative group.

Jan: To deduce Th5 use both parts of the distributive law.

(x+y)(w+z) = (x+y)w+(x+y)z = (xw+yw)+(xz+yz)

Kay: Since xw+yw+xz+yz is brief for ((xw+yw)+xz)+yz we also need the associative law.

Jo: You all seem to be puzzled about deducing Th6. Find an equation that has 0x in it and think of 0x as an unknown to solve for.

Kay: I am stumped. The only laws we have for 0 involve addition.

Jo: Kay is correct about 0 being an additive concept. Which laws connect addition and multiplication?

Jan: The distributive laws. So I guess we need to substitute 0 into a distributive law.

Bob: We could get (0+0)x = 0x+0x, but I do not see how to solve this for 0x.

Roy: Instead we could start with (0+1)x = 0x+1x, which gives 0x+x = x. Solving gives 0x = 0.

Jan: To go from 0x+x = x to 0x = 0 we could use Th2.3. Or we could add -x to both sides.

Kay: We could also have started as Bob suggested to obtain 0x+0x = 0x, and then use Th2.3.

Roy: To deduce x0 = 0, start with x(0+1) = x0+x1.

Bob: I see. Since we do not have a commutative law for multiplication, we use the other distributive law.

Kay: To deduce Th7.1 start with (-1+1)x = -1x+1x, which gives -1x+x = 0x. The use 0x = 0.

Roy: To deduce Th7.2 use Th7.1 -x·y = -1xy = -(xy). Likewise x·-y = x·-1y = -x·y = -(xy)

Bob: Your deduction also uses the associative law.

Jan: Using Th7.2 and Th 3.2 gives -x·-y = -(x·-y) = -(-(xy)) = xy.

Kay: I can see why Th8.1 depends on the commutivity of multiplication. If we substitute x for w in Th5 we obtain (x+y)(x+z) = xx+yx+xz+yz. To get (y+z)x replace xz by zx and use the distributive law.

Roy: And as I am so often reminded you need the associative law. To deduce Th8.2 substitute -y for y and -z for z in Th8.1.

Jan: This gives (x-y)(x-z) = x²+(-y+-z)x+(-y)(-z). Then use Th3.3 and Th7.3.

Bob: Substitution in Th8.1 gives (x+y)(x+-y) = x²+(y+-y)x+y(-y). This can be used to deduce Th8.3

Jan: Substitution in Th8.1 gives (x+y)(x+y) = x²+(y+y)x+yy. This can be used to deduce Th8.4 is we replace y+y by 2y.

Kay: To do this we need to first deduce y+y by 2y. Using the basic laws give y+y = 1y+1y = (1+1)y. It would seem that we need to be working with numbers to use 1+1 = 2.

Jo: Good observation, but there is another alternative, namely to define 2 as an abbreviation for 1+1 in any ring regardless of whthr 1 is taken to be a number.

Kay: Since a ring has a unary operation -, we could define subtraction. However in ordinary algebra most of the operational structures we worked with also used multiplicative inverses and defined division.

Jo: Such operational structures are called fields. A field satisfies the laws defining a commutative ring along with the multiplicative inverse law below.

x·/x = 1 & /x·x = 1; where x is element of the field other than 0

In general, propositions involving the use of ‘/’ presuppose that what follow this symbol is not equal to 0. The following theorems show that a field is a ring that satisfies the basic laws that we use for ordinary algebra. In particular, Th10.3 shows that a linear equation has a unique root that can be found in the usual manner, while Th11.2 provides the basis for solving higher degree equations that will factor.

Th9: Let w ¹ 0 1. x = y Û xw = yw 2. xw = w Û x = 1

Th10: 1. xw = y Û x = y/w 2. xw = 1 Û x = /w 3. wx+y = z Û x = (z-y)/w

Th11: 1. xy = 0 Û x = 0 Ú y = 0 2.(x-a)(x-b) = 0 Û x = a Ú x = b

Th12: 1. /1 = 1 2. //x = x 3. /(xy) = /x/y 4. w ¹ 0 Þ x/y = (xw)/(yw)

Th13: 1. (x/y)·(z/w) = (xz)/(yw) 2. (x/y)/(z/w) = (xw)/(yz)

3. (x/y)+(z/y) = (x+z)/y 4. (x/y)-(z/y) = (x-z)/y

5. (x/y)+(z/w) = (xw+zy)/(yw) 6. (x/y)-(z/w) = (xw-zy)/(yw)

Jan: A field could be described as a structure for which both an additive and a multiplicative commutative groups. So except for Th11, we have already deduced most of the above laws.

Bob: We would also need to say that addition and multiplication are related by a distributive law. We would need this for the last 4 parts of Th13, which we have not already deduced.

Kay: A field is not quite a multiplicative group. It is only the set of elements other that 0 that are.

Roy: We had not already deduced Th11. To deduce xy = 0 Þ x = 0 Ú y = 0, I assumed xy = 0 and x ¹ 0. Multiplying by /x gives y = 0.

Kay: So xy = 0 & x ¹ 0 Þ y = 0, and we can use the rule X&ØY Þ Z inf X Þ YÚZ.

Jan: The converse x = 0 Ú y = 0 Þ xy = 0 can be deduced using cases. For the case x = 0 multiply by y to obtain xy = 0y, so xy = 0. The case x = z is similar.

Bob: We can use substitution in Th11.1 to deduce Th11.2.

Kay: The laws for given in Th9 and Th11 do not use inverses. They also apply to the ring of integers, but they cannot be deduced from the ring laws because they are not laws for the ring of integers mod 6.

Jo: A cancellation ring is a ring in which Th9.1 is satisfied. So Th9.1 shows that every field is a cancellation ring. As Kay just indicated, the ring of integers is an example of a cancellation ring that is not a field. This ring is a subring of the ring of rational numbers, which is a field. It can be shown that every cancellation ring is a subring of some field.

Bob: Kay also noticed that Th11 is satisfied by the integers. The deduction of xy = 0 Þ x = 0 Ú y = 0 that Roy used involved multiplicative inverses. We could not use this with the integers.

Jan: I can use cancellation to deduce xy = 0 & x ¹ 0 Þ y = 0. Assumed xy = 0 and x ¹ 0. Then xy = x0. Cancel to get y = 0. Now use the rule Kay gave to obtain xy = 0 Þ x = 0 Ú y = 0.

Roy: If I gave that deduction then someone would probably remind me that I needed a commutative version of cancellation.

Kay: Th11 could also be used to deduce Th9. That x = y Þ xw = yw follows by the operation rule. To show the converse, suppose w ¹ 0 and xw = yw. Then (x-y)w = 0. By Th9, x-y = 0 Ú w = 0. Since w ¹ 0 we have x-y = 0, and so x = y.

Exercises and Problems: When giving a detailed deduction, make sure that the use of the substitution and replacement rules is indicated.

Ex0: Our characters often appropriately leave the use of the associative or commutative laws implicit. However since this book focuses on logic, they sometimes remark on this fact. Find at least one implicit use of one these law that none of them commented on.

Ex1: Give a detailed deduction of Th5 showing how substitution and replacement might be used.

Ex2: Give a detailed deduction of Th6.

Ex3: Complete the deduction of Th7.1 that Kay suggested.

Ex4: Give a detailed deduction for Th7.2.

Ex5: Give a detailed deduction for Th7.3.

Ex6: Deduce all parts of Th8. Indicate at least a few instances of substitution and replacement.

Ex7: Deduce Th10.3

Ex8: Give a detailed deduction for Th11.

Ex9: Recalling that a/b is defined as a·/b, relate Th13.3 to the distributive law.

Ex10: Give a detailed deduction for Th13.4.

Ex11: Deduce Th13.5 and Th13.6

Pr1: For each integer n > 1, the structure (Z_n,{-,+,·}) can be defined in the same manner as (Z₆,{-,+,·}) was defined. It can be show that for each such n, (Z_n,{-,+,·}) is a commutative ring. If xy = 0 and y ¹0 then x is called an annihilator of y. Z₄, Z₆, Z₈, Z₉ all have annihilators other than 0. Show that Z₂, Z₃, Z₅, Z₇ have no non-zero annihilators. Make a general conjecture indicating necessary and sufficient conditions for Z_n to have annihilators other than 0.

Pr2: Let (R,{-,+,·}) be a finite cancellation ring with elements {r₁,...,r_n}. Let r be any element of R, except 0. Let S = {r·r₁,...,r·r_n}. Clearly S is a subset of R. Use the cancellation law to explain why S contains n elements, and hence is equal to R. Why does 1 belong to S? Why does this show that for any r in R, we have r·x = 1 for some x in R? How could we define an operation / on R, so (R,{-,+,·,/}) would be a field?

Pr3: The trivial ring is the ring whose only element is 0. Show in it is only in the trivial ring that 1 = 0.

SECTION 3: ORDERED CANCELLATION RINGS

Jo: An ordered cancellation ring is a non-trivial commutative cancellation ring along with an attribute ‘P’ which intuitively we interpret as ‘is positive’. This attribute satisfies the basic laws below.

xP & yP Þ (x+y)P	xP & yP Þ (x·y)P	positive closure
x = 0 Ú xP Ú -xP		trichotomy exhaustion
Ø(xP & -xP)	Ø0P	trichotomy exclusion

Jan: I thought an ordered ring would involve an ordering relation such as less than and greater than.

Jo: It does but instead of taking these relations as primitive we can define them in terms of ‘P’. For instance, since x is greater than y iff x-y is positive we can define both > and < as indicate below.

x > y means (x-y)P x < y means (y-x)P

This approach was chosen mainly because it involves an elementary theory in which a sufficient number of deductions employ logic significant enough to analyze. For most deductions I want you to give the mathematical essence of the proof, leaving most of the logic implicit. Later you can each make the logical analysis explicit and the compare notes if you like. For some deductions, you may want make some comments that would at least indicate how to make the logic explicit.

Roy: We can also define x ³ y and x £ y in the usual manner as x > y Ú x = y and x < y Ú x = y.

Jan: If -x is positive then x is negative. To remind us of this, I suggest we write -xP as xN.

Roy: I approve. Since Ø(xP & -xP) means that an element cannot be both positive an negative, writing this as Ø(xP & xN) makes this easier to see.

Bob: Trichotomy means to separate into three parts. The exhaustion part x = 0 Ú xP Ú xN says at least one of the 3 conditions of being zero or positive or negative holds for each element.

Kay: The exclusion part says no two of these conditions can hold for an element. The trichotomy laws taken together say that each element satisfies exactly one of these three conditions.

Jan: I can see that exhaustion part can be used to show that an element cannot be both zero and positive. Just assume x = 0 & xP and use replacement to infer 0P which contradicts Ø0P. Thus Ø(x = 0 & xP).

Roy: Showing Ø(x = 0 & xN) is similar. Assuming x = 0 & xN gives 0N, -0P, 0P.

Jo: Can you see why the following are some fairly immediate consequence of trichotomy?

xP Þ ØxN, xN Þ ØxP, x = 0 Þ ØxP, x = 0 Þ ØxN, xP Þ x ¹ 0 and xN Þ x ¹ 0.

Jan: Since ‘X Þ ØY’ and ‘Y Þ ØX’ and Ø(X&Y) and Øare logically equivalent, all of these follow from the exclusion law.

Jo: Can anyone show that 1 is positive?

Jan: Since 1 ¹0, by exhaustion 1P Ú 1N. We need to show Ø1N and use XÚY, ØY infer X.

Roy: Assume 1N, and use positive closure to get a contradiction.

Bob: I think I see what you mean. Assuming 1N means -1P. So by positive closure (-1·-1)P. Since -1·-1 = 1 this gives 1P. So 1P&-1P. This contradicts exclusion.

Jo: Deduce (xP & yP) Ú (xN & yN) Þ xyP.

Kay: We already have xP & yP Þ xyP. Assuming xN & yN means -xP & -yP. By positive closure (-x·-y)P, xyP. So xN & yN Þ xyP. Now us {X Þ Z, YÞ Z} infer XÚY Þ Z.

Jan: Here is a detailed deduction showing substitution and replacement..

(1) xP & yP Þ xyP	positive closure
(2) -xP & -yP Þ -x·-yP	positive closure: substitute -x®x, -y®y
(3) -xP & -yP Þ xyP	(2) replace -x·-y by xy
(4) xN & yN Þ xyP	(3) unabbreviated
(5) xP & yP Ú xN & yN Þ xyP	(1)(4) {X Þ Z, Y Þ Z} infer XÚY Þ Z

Bob: We could deduce (xP & yN) Ú (xN & yP) Þ xyN in a similar manner.

xP & yN Þ (x·-y)P, xP & yN Þ -(xy)P, xP & yN Þ xyN . Likewise (xN & yP) Þ xyN.

Jo: We should be able to deduce Th0 below.

Th0: 1. xyP Û (xP & yP) Ú (xN & yN) 2. xyN Û (xP & yN) Ú (xN & yP).

Roy: xyP Þ x ¹ 0 & y ¹ 0. So assuming xyP gives (xP Ú xN) & (yP ÚyN). This gives 4 case 2 of which we can easily eliminate. Assuming xyN works in a similar fashion.

Jan: A little more detail might help. Assume xyP, by exclusion xy ¹0, so by ring laws x ¹ 0 & y ¹ 0. The 4 cases Roy mentioned are using are (xP & yP) Ú (xP & yN) Ú (xN & yP) Ú (xN & yN). The second and third of these cases imply xyN, but ØxyN by exclusion. This leaves (xP & yP) Ú (xN & yN).

Kay: We can use a distributive rule {(XÚY)&(UÚV)} infer {X&UÚX&VÚY&UÚY&V} to infer
(xP & yP) Ú (xP & yN) Ú (xN & yP) Ú (xN & yN) from (xP Ú xN) & (yP ÚyN).

Jo: Using Th1, deduce Ø x²N and from this deduce x²P Û x ¹ 0.

Jan: Assuming xxN give (xP & xN) Ú (xN & xP), contradicting exclusion. So Øx²N.

Bob: By exclusion x²P Þ x² ¹ 0). Since Ø x²N, x²P Ú x² = 0. So by propositional logic x² ¹ 0 Þ x²P. By ring laws x² ¹ 0 Û x ¹ 0. So x²P Û x ¹ 0.

Kay: By ring laws x² ¹ 0 Þ x ¹ 0. To obtain x ¹ 0 Þ x² ¹ 0 we need to be in a cancellation ring. Th11 from the previous depends on having cancellation for multiplication.

Roy: For example, x ¹ 0 Þ x² ¹ 0 is not a law in Z₁₂ since 6² = 0.

Jo: We can deduce some order theorems which can be proved from the definition of ‘<’ and ‘£’ and Th0.

Th 1 (Reflexive and Irreflexive Laws): 1. x £ x 2. Ø(x < x)

Roy: x £ x follows from the reflexive law of equality.

Bob: In detail x = x so x = x Ú x < x, which by definition is x £ x. This uses our Ú-introduction rule.

Jan: This is the rule X infer XÚY, which wee noted earlier throws away information.

Kay: Assuming x < x gives by definition (x-x)P. But x-x = 0, contradiction exclusion. So Ø(x < x)

Bob: I used basically the same deduction, except that I that used Þ-elimination.

(1) (x-x)P Þ x-x ¹ 0	exclusion
(2) x-x = 0	ring
(3) Ø(x-x)P	X Þ ØY, Y infer ØX
(4) Ø(x < x)	definition of <

Jan: We could also deduce x ³ x and Ø(x > x) in a similar manner,

Kay: Since x > y and y < x both are defined as (x-y)P, we have x > y Û y < x. Likewise x ³ y Û y £ x. Substituting x for y gives the laws Jan just stated.

Jo: Good observation. We will focus on < and £, leaving it to you to think about > and ³.

Th2 (Transitive Laws): 1. x < y & y < z Þ x < z 2. x £ y & y £ z Þ x £ z

Roy: Suppose x < y & y < z. By definition (y-x)P & (z-y)P, so by positive closure (z-x)P.

Jan: For more detail positive closure gives (y-x)P & (z-y)P Þ (y-x+z-y)P, so (y-x+z-y)P. Now use ring laws and replace y-x+z-y by z-x so (z-x)P, which is x < z.

Kay: For part 2 assume x £ y & y £ z which means (x < y Ú x = y) &( y < z Ú y = z). Using propositional logic, (x < y & y < z ) Ú (x < y & y = z) Ú (x = y & y < z) Ú (x = y & y = z). Now consider 4 cases. In the case x < y & y < z, Th2 gives x < z and so x £ z using Ú introduction. In the case x < y & y = z. replace y by z to obtain x < z and so x £ z. The other cases are similar.

Th3 (Asymmetric & Antisymmetric Laws): 1. x < y Þ Ø(y < x) 2. x £ y & y £ x Þ x = y

Roy: Suppose x < y & y < x. By transitivity, x < x, contradicting Th1.

Jan: For part 2 assume x £ y & y £ x & x ¹ y. This gives x < y and y < x, contradicting Th3.1.

Th4 (Trichotomy exhaustion law): x < y Ú y < x Ú x = y

Roy: By the exhaustion law y-x = 0 Ú (y-x)P Ú (y-x)N, so change (y-x)N to (x-y)P.

Th5 (Trichotomy exclusion laws): 1. Ø(x = y & x < y) 2. Ø(x < y & y < x)

Roy: Assuming x = y & x < y gives x < x, contradicting Ø(x < x). Assuming x < y & y < x also contradicts the irreflexive law.

Th6: 1. x < y Û -y < -x 2. x < 0 Û 0 < -x 3. 0 < x Û -x < 0

Jan: x < y means (y-x)P, which is equivalent to (-x-(-y))P, which by definition is -y < -x. The other part follow from part 1 by substitution and replacing -0 by 0.

Th7: 1. x < y Û x+z < y+z 2. x < y & u < v Þ x+u < y+v

Kay: By ring laws, (y-x)P Û ((y+z)-(x+z))P. By the definition of < this is part 1.

Roy: For part 2 assume x < y & u < v, By part 1, x+u < y+u & u+y < v+y, so x+u < y+w.

Th8: 1. zP Þ (x < y Û xz < xy) 2. zN Þ (x < y Û yz < xz)

Kay: We can infer X Þ (Y Û Z) from {X&Y Þ Z), X&Z Þ Y}. So we could Dededuce Th8.1 by deducing two conditionals.

Jan: Assume zP & x < y. Then (y-x)P and by closure (yz-xz)P. This shows zP & x < y Þ xz < xy.

Roy: For the other conditional, assume zP & xz < yz. Then (y-x)zP. By Th0.1 (y-x)P, so x < y.

Bob: I think I see how you used Th0.1. (y-x)zP gives ((y-x)P & zP) Ú ((y-x)N & zN). The second alternative gives zN, so we must have the first alternative.

Kay: We could also deduce xP & yP & x < z & y < w Þ xy < zw.

Jo: As I hoped, for most deductions you gave the mathematical essence, leaving most of the logic implicit. I now recommend that you each go back and give some informal deduction using the style from earlier chapters. In order to make the logic explicit you may want to augment this with a detailed version of the deduction showing which propositional inference patterns were used and occasionally showing how the substitution and the equality replacement rules were used. Do enough of this so you will appreciate the role of inference rules in such mathematical deductions.