DG2, DG3 - Commutativity and associativity

DG2, DG3 - Commutativity and associativity

Does a familiar-looking operation obey familiar algebraic laws? You will distinguish changing the order of two inputs from changing the brackets around three inputs, prove laws for every allowed input, and use a single valid counterexample to disprove a claim.

Proving commutativity and associativity

If a∗b=a+b+1a*b=a+b+1 on the integers, can you swap the inputs and move the brackets? For instance, 2∗5=8=5∗22*5=8=5*2. That calculation suggests a pattern, but it does not establish it for every pair of integers.

Two different laws

An operation ∗* on SS is commutative if a∗b=b∗aa*b=b*a for every a,b∈Sa,b\in S. It is associative if (a∗b)∗c=a∗(b∗c)(a*b)*c=a*(b*c) for every a,b,c∈Sa,b,c\in S.

Commutativity swaps the order; associativity changes only the brackets. In an associativity test the inputs stay in the order a,b,ca,b,c on both sides.

For a rule given by algebra, use general elements and simplify the two expressions separately. You may use known laws of ordinary integer or real arithmetic in the proof. You may not assume those same laws for the new symbol before proving them.

Worked example 1: a shifted sum

Question. For a∗b=a+b+1a*b=a+b+1 on Z\mathbb Z, prove that ∗* is commutative and associative.

Plan. Write down the reversed pair and both bracketings for general integers.

The output is an integer, so the rule is closed. For commutativity,

a∗b=a+b+1=b+a+1=b∗a.a*b=a+b+1=b+a+1=b*a.

For associativity, substitute the whole inner output into the rule:

(a∗b)∗c=(a+b+1)+c+1=a+b+c+2a∗(b∗c)=a+(b+c+1)+1=a+b+c+2.\begin{aligned} (a*b)*c&=(a+b+1)+c+1=a+b+c+2\\ a*(b*c)&=a+(b+c+1)+1=a+b+c+2. \end{aligned}

The two results agree for arbitrary integers, not just chosen examples.

Answer. ∗* is both commutative and associative on Z\mathbb Z.

Check. With a=2,b=−1,c=4a=2,b=-1,c=4, both bracketings give 77: (2∗(−1))∗4=2∗4=7(2*(-1))*4=2*4=7 and 2∗((−1)∗4)=2∗4=72*((-1)*4)=2*4=7. This checks the substitution; the general argument supplies the proof.

Now replace the fixed extra term 11 by the product abab. The proof needs more expansion: the word “plus” in a definition does not establish the laws automatically.

Worked example 2: adding a product term

Question. On Z\mathbb Z, define a∘b=a+b+aba\circ b=a+b+ab. Prove commutativity and associativity.

Plan. Swap the general inputs, then expand both bracketings without changing their order.

Closure follows because sums and products of integers are integers. For commutativity,

a∘b=a+b+ab=b+a+ba=b∘a.a\circ b=a+b+ab=b+a+ba=b\circ a.

For associativity,

(a∘b)∘c=a+b+ab+c+(a+b+ab)c=a+b+c+ab+ac+bc+abca∘(b∘c)=a+b+c+bc+a(b+c+bc)=a+b+c+ab+ac+bc+abc.\begin{aligned} (a\circ b)\circ c &=a+b+ab+c+(a+b+ab)c\\ &=a+b+c+ab+ac+bc+abc\\ a\circ(b\circ c) &=a+b+c+bc+a(b+c+bc)\\ &=a+b+c+ab+ac+bc+abc. \end{aligned}

Answer. Both laws hold for every integer input.

Check. The identity 1+(a∘b)=(1+a)(1+b)1+(a\circ b)=(1+a)(1+b) gives another explanation: either bracketing has one plus its output equal to (1+a)(1+b)(1+c)(1+a)(1+b)(1+c). This agrees with the expansion and links the new rule to ordinary multiplication.

For a finite set with mm elements, an exhaustive proof can instead check all m2m^2 ordered pairs for commutativity, or all m3m^3 ordered triples for associativity. Organised reductions using established properties can shorten the work, but a few successful trials cannot prove a universal law. Modular addition and multiplication inherit these laws because reducing an intermediate integer by a multiple of nn does not change the final remainder: for multiplication, replacing abab by ab−knab-kn changes the product with cc by kncknc, still a multiple of nn.

Watch out

In (a∗b)∗c(a*b)*c, substitute a∗ba*b as one complete first input. Do not write (a+b+1)∗c=a+b+1+c(a+b+1)*c=a+b+1+c: the rule adds another 11.

Use the same proof method after a small change in the constant.

Disproving laws with counterexamples

A law claiming “for every input” fails as soon as one allowed choice gives unequal results. Such a choice is a counterexample. State the inputs, calculate both sides of the law being tested, and give the conclusion.

One equality cannot prove a universal law, and a chosen example with equal sides cannot disprove it. For subtraction, a test with final input zero can conceal the failure of associativity.

Worked example 3: disproving commutativity

Question. On Z\mathbb Z, let a∗b=a−ba*b=a-b. Show that ∗* is not commutative.

Plan. Choose two different integers and compare them in opposite orders.

Take a=5a=5 and b=2b=2, both in Z\mathbb Z:

5∗2=5−2=3,2∗5=2−5=−3.5*2=5-2=3,\qquad2*5=2-5=-3.

Answer. Since 5∗2≠2∗55*2\ne2*5, ∗* is not commutative.

Check. In general, a−b=b−aa-b=b-a would require a=ba=b. Our chosen inputs are different, so they cannot satisfy that equality.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account