230
Sets, Combinatorics, and Probability
For # to be a unary operation on a set S, it must be true that for any x [ S,
x# is well-defined and S is closed under #; in other words, for any x [ S, x# exists,
is unique, and is a member of S. We do not have a unary operation if any of these
conditions is not met.
example 12
Let x# be defined by x# = −x so that x# is the negative of x. Then # is a unary
operation on ℤ but not on ℕ because ℕ is not closed under #.
example 13
The logical connective of negation is a unary operation on the set of propositional
wffs. If P is a propositional wff, then P′ is a unique propositional wff.
From these examples it is clear that whether + (or # ) is a binary (or unary)
operation can depend not only on its definition but also on the set involved.
PraCtiCe 12 Which of the following candidates are neither binary nor unary operations on the given
sets? Why not?
a. x + y = x ÷ y; S = set of all positive integers
b. x + y = x ÷ y; S = set of all positive rational numbers
c. x + y = x
y
; S = ℝ
d. x + y = maximum of x and y; S = ℕ
e. x
#
= !x; S = set of all positive real numbers
f. x
#
= solution to equation (x
#
)
2
= x; S = ℂ
■
So far, all our binary operations have been defined by means of a description or an equation. Suppose S is a finite set, S = {x 1 , x 2 , … , x n }. Then a binary
operation + on S can be defined by an n × n table, where element i, j (ith row and
jth column) denotes x i + x j .
example 14
Let S = {2, 5, 9}, and let + be defined by the table
+
2
5
9
2
2
2
9
5
5
9
2
9
5
5
9
Thus, 2 + 5 = 2 and 9 + 2 = 5. Inspecting the table, we see that + is a binary
operation on S.
Operations on Sets
Most of the operations we have seen operate on numbers, but we can also operate on sets. Given an arbitrary set S, we can define some binary and unary
Sets, Combinatorics, and Probability
For # to be a unary operation on a set S, it must be true that for any x [ S,
x# is well-defined and S is closed under #; in other words, for any x [ S, x# exists,
is unique, and is a member of S. We do not have a unary operation if any of these
conditions is not met.
example 12
Let x# be defined by x# = −x so that x# is the negative of x. Then # is a unary
operation on ℤ but not on ℕ because ℕ is not closed under #.
example 13
The logical connective of negation is a unary operation on the set of propositional
wffs. If P is a propositional wff, then P′ is a unique propositional wff.
From these examples it is clear that whether + (or # ) is a binary (or unary)
operation can depend not only on its definition but also on the set involved.
PraCtiCe 12 Which of the following candidates are neither binary nor unary operations on the given
sets? Why not?
a. x + y = x ÷ y; S = set of all positive integers
b. x + y = x ÷ y; S = set of all positive rational numbers
c. x + y = x
y
; S = ℝ
d. x + y = maximum of x and y; S = ℕ
e. x
#
= !x; S = set of all positive real numbers
f. x
#
= solution to equation (x
#
)
2
= x; S = ℂ
■
So far, all our binary operations have been defined by means of a description or an equation. Suppose S is a finite set, S = {x 1 , x 2 , … , x n }. Then a binary
operation + on S can be defined by an n × n table, where element i, j (ith row and
jth column) denotes x i + x j .
example 14
Let S = {2, 5, 9}, and let + be defined by the table
+
2
5
9
2
2
2
9
5
5
9
2
9
5
5
9
Thus, 2 + 5 = 2 and 9 + 2 = 5. Inspecting the table, we see that + is a binary
operation on S.
Operations on Sets
Most of the operations we have seen operate on numbers, but we can also operate on sets. Given an arbitrary set S, we can define some binary and unary