Binary operations and their properties
Studying this course? Keep your progress in one place.
Key facts
- A binary operation combines two elements; it is closed if the result is always in the set.
- To prove a property use general ; to disprove it one counter-example is enough.
- Commutative: for all .
- Associative: for all ; expand both sides.
- In a Cayley table the row element is first and the column element second; a table symmetric in the leading diagonal is commutative.
Binary operations and closure
A binary operation combines two elements of a set into one, and the set is closed if the result is always in the set.
A binary operation on a set combines any two elements and to give . It is closed on if is always in .
Examples: addition on the integers, on the reals, and multiplication of matrices. Order matters: means first, then .
Bracket negative numbers when substituting, for example with .
- 1
Take any a and b in the set S
- 2
Work out a ∗ b
- 3
Is the result always in S?
if yes, S is closed; one result outside S shows it is not
To show closed
- Take general
- Show
To show not closed
- Give one pair with result outside
- e.g. on the natural numbers
Worked example
For , find .
- 1
Replace with and with , bracketing the negative: .
- 2
Simplify: .
Is subtraction a closed operation on the natural numbers ?
Modular arithmetic and matrices
Add or multiply as usual, then take the remainder; matrices multiply as usual, and closure needs checking for smaller sets.
On , addition modulo () and multiplication modulo () are binary operations: add or multiply as usual, then take the remainder on division by .
For example, and .
Multiplication of matrices is a binary operation on the set of all matrices. For a smaller set, check closure by multiplying general members.
- remainder of on division by
- remainder of on division by
Worked example
Is the set of matrices closed under matrix multiplication?
- 1
Multiply two general members: .
- 2
The result has the same form.
What is modulo 6?
Commutativity
An operation is commutative if swapping the two elements never changes the result.
To prove is commutative, take general and and show the two expressions are equal, using known laws. Example: because addition and multiplication of reals are commutative.
To disprove it, one counter-example is enough. For : but .
Matrix multiplication is not commutative in general, though it may be on a special set, such as the matrices .
- Commutative for all
To prove
- Use general and
- Show both orders give the same expression
To disprove
- Use unequal values, such as 1 and 2
- Show
Is commutative?
Associativity
An operation is associative if the bracketing never matters, so is unambiguous.
To prove is associative, expand both and separately and show they simplify to the same expression. To disprove it, give one counter-example.
Addition and multiplication of integers, modular addition and multiplication, and matrix multiplication are all associative.
To disprove for : but .
- 1
Expand (a ∗ b) ∗ c
- 2
Expand a ∗ (b ∗ c)
- 3
Simplify both
if they are always equal, ∗ is associative
- Associative for all
Worked example
Show that is associative.
- 1
Expand the left side: .
- 2
This gives .
- 3
Expand the right side in the same way: , which is also .
For , which shows it is not associative?
Cayley tables
A Cayley table lists every product of a finite set; check closure and symmetry directly from it.
A Cayley table lists every product of a finite set: the element on the left (row) is first and the element along the top (column) is second.
The table shown is on .
- Closed: every entry is an element of the set.
- Commutative: the table is symmetric about the leading diagonal (top left to bottom right).
- Associativity is not easy to read from the table, so prove it separately.
- 1
Closed
every entry is an element of the set
- 2
Commutative
the table is symmetric about the leading diagonal
- 3
Identity
the row and column that repeat the headings
| Column 1 | Column 2 | Column 3 | Column 4 | |
|---|---|---|---|---|
| Row 1 | 1 | 2 | 3 | 4 |
| Row 2 | 2 | 4 | 1 | 3 |
| Row 3 | 3 | 1 | 4 | 2 |
| Row 4 | 4 | 3 | 2 | 1 |
Column 1
- Row 1:
- 1
- Row 2:
- 2
- Row 3:
- 3
- Row 4:
- 4
Column 2
- Row 1:
- 2
- Row 2:
- 4
- Row 3:
- 1
- Row 4:
- 3
Column 3
- Row 1:
- 3
- Row 2:
- 1
- Row 3:
- 4
- Row 4:
- 2
Column 4
- Row 1:
- 4
- Row 2:
- 3
- Row 3:
- 2
- Row 4:
- 1
In the table above, what is (row 3, column 4)?
Try an exam question
A binary operation is defined on the real numbers by . Find , and show that is not associative.
[4 marks]
- [1].
- [1].
- [1].
- [1], so is not associative.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Find .
1 mark, marked against the mark scheme
Find .
1 mark, marked against the mark scheme