For the set N of natural numbers and a binary operation f : N x N -> N, an element z in N is called an identity for f, if f(a, z) = a = f(z, a), for all a in N. Which of the following binary operations have an identity? I. f(x, y) = x + y - 3 II. f(x, y) = max(x, y) III. f(x, y) = x^y. A. I and II only B. II and III only C. I and III only D. None of these
GATE 2006 · Discrete Mathematics · Binary Operation · easy
Answer: A. I and II only
- Operation I: f(x, y) = x + y - 3: f(a, z) = a + z - 3 = a requires z = 3. Check the other side: f(3, a) = 3 + a - 3 = a. Since 3 is a natural number, z = 3 is a valid identity.
- Operation II: f(x, y) = max(x, y): We need z <= a for all a, i.e. z is the least natural number (z = 1 if N starts at 1, or 0 if N includes 0). Then max(a, z) = a = max(z, a). So an identity exists.
- Operation III: f(x, y) = x^y: a^z = a forces z = 1. But then z^a = 1^a = 1, which is not a for general a (e.g. a = 2 gives 1 != 2). No single z works on both sides, so there is no two-sided identity.
- Collect the results: I and II have identities; III does not. This is option A.