Club sign-up sheet: relation, function, or neither?
At a government higher secondary school in Tiruchirappalli, four volunteers A={Arun, Bala, Chitra, Devi} run three mathematics-fair booths B={Algebra, Geometry, Puzzles}. The final sign-up sheet records: Arun to Algebra; Bala to Geometry; Chitra to Algebra and Puzzles; Devi to Puzzles. The teacher-coordinator must first decide whether this sheet represents a function from A to B. She then defines a relation T on B by 'booth X is related to booth Y if at least one volunteer has signed up for both X and Y'. She suspects T is an equivalence relation and wants it checked before grouping booths by shared volunteers. Finally, for the final presentation each volunteer must choose exactly one booth, and she wants the number of different assignment lists possible, including lists where two volunteers choose the same booth. She also wants to know how many of those lists use four different booths, because the head teacher has asked for a one-to-one display.
1. Is the sign-up sheet a relation from A to B? Is it a function from A to B? Justify using the definitions, and state the domain and range of the relation.
Read the worked answer
Yes, it is a relation: it is a set of ordered pairs with first component from A and second component from B, namely {(Arun, Algebra), (Bala, Geometry), (Chitra, Algebra), (Chitra, Puzzles), (Devi, Puzzles)}. It is not a function from A to B, because the element Chitra is paired with two different elements, Algebra and Puzzles. A function must assign exactly one image to each element of the domain. The domain is {Arun, Bala, Chitra, Devi}, since every volunteer appears at least once. The range is {Algebra, Geometry, Puzzles}, since all three booths appear as second components.
2. List all ordered pairs of T and determine whether T is reflexive, symmetric and transitive. Is T an equivalence relation?
Read the worked answer
From the sign-up sheet, the booths sharing a volunteer are Algebra with Geometry and Algebra with Puzzles (through Chitra). Every booth is related to itself because each booth has at least one volunteer. Hence T = {(Algebra, Algebra), (Geometry, Geometry), (Puzzles, Puzzles), (Algebra, Geometry), (Geometry, Algebra), (Algebra, Puzzles), (Puzzles, Algebra)}. Reflexive: yes, all three diagonal pairs are present. Symmetric: yes, whenever (X, Y) is present, (Y, X) is also present. Transitive: no. We have Geometry T Algebra and Algebra T Puzzles, but Geometry T Puzzles is false. Since transitivity fails, T is not an equivalence relation.
3. How many functions from A to B are possible for the final presentation? How many are one-to-one? Explain the difference.
Read the worked answer
Each of the four volunteers has 3 booth choices, independently, so the total number of functions is 3 x 3 x 3 x 3 = 3^4 = 81. A one-to-one function would need four distinct images in B, but B has only three booths. By the pigeonhole principle, two volunteers would have to choose the same booth, so no one-to-one function from a four-element set to a three-element set exists. The number is 0. The difference is that repetition is allowed in the 81 assignments, but a one-to-one display forbids repetition and is therefore impossible here.