Exercise Set 2.3: Relations and Functions Study Notes
Relations and Functions: Core Concepts and Representations
This section covers fundamental concepts related to relations and functions, including their definitions, various methods of representation, and how to distinguish between them. The exercises emphasize practical application in determining properties of given relations.
1. Defining and Understanding Relations
Definition: A relation R from a set A to a set B is a subset of the Cartesian product A \times B. This means that R is a collection of ordered pairs (x, y) where x \in A and y \in B.
Notation: If (x, y) \in R, we can also write xRy (read as "x is related to y").
Domain and Codomain: For a relation R from A to B:
The domain of the relation is the set A. This is the set of all first components of the ordered pairs in A \times B.
The codomain of the relation is the set B. This is the set of all second components of the ordered pairs in A \times B.
Checking Membership: To determine if an ordered pair (x, y) (or if xRy) belongs to a relation R, one must check if the pair satisfies the specific condition or rule defining R. For example:
If A = {2,3,4} and B = {6,8,10}, and R means \frac{y}{x} is an integer:
To check if 4R6 (i.e., (4,6) \in R), calculate \frac{6}{4} = 1.5. Since 1.5 is not an integer, (4,6) \notin R. Thus, 4R6 is false.
To check if 4R8 (i.e., (4,8) \in R), calculate \frac{8}{4} = 2. Since 2 is an integer, (4,8) \in R. Thus, 4R8 is true.
To check if (3,8) \in R, calculate \frac{8}{3} \approx 2.67. Not an integer, so (3,8) \notin R.
To check if (2,10) \in R, calculate \frac{10}{2} = 5. Is an integer, so (2,10) \in R.
2. Representing Relations
Relations can be represented in several ways:
a. Set of Ordered Pairs
A relation can be explicitly listed as a set of all ordered pairs that satisfy its defining condition.
Example from Exercise 1: If A = {2,3,4} and B = {6,8,10} with R defined as \frac{y}{x} being an integer:
Possible pairs from A \times B are: (2,6), (2,8), (2,10), (3,6), (3,8), (3,10), (4,6), (4,8), (4,10).
Checking each:
(2,6) as \frac{6}{2} = 3 (integer).
(2,8) as \frac{8}{2} = 4 (integer).
(2,10) as \frac{10}{2} = 5 (integer).
(3,6) as \frac{6}{3} = 2 (integer).
(3,8) as \frac{8}{3} (not integer).
(3,10) as \frac{10}{3} (not integer).
(4,6) as \frac{6}{4} (not integer).
(4,8) as \frac{8}{4} = 2 (integer).
(4,10) as \frac{10}{4} (not integer).
Therefore, R = {(2,6), (2,8), (2,10), (3,6), (4,8)}.
Example from Exercise 2: If C=D={-3, -2, -1, 1, 2, 3} and S means \frac{1}{x} - \frac{1}{y} is an integer. To find ordered pairs in S, one must calculate the difference of reciprocals for all (x,y) \in C \times D (excluding x=0 or y=0 if they were in the set, which they are not here) and check if the result is an integer.
For example, (2,2) \in S because \frac{1}{2} - \frac{1}{2} = 0, which is an integer.
(2,-2) \notin S because \frac{1}{2} - \frac{1}{-2} = \frac{1}{2} - (-\frac{1}{2}) = 1, which is an integer. Thus, (2,-2) \in S.
And so on for all pairs.
Example from Exercise 3: If E={1, 2, 3} and F = {-2, -1, 0} and T means \frac{x-y}{3} is an integer. To list pairs, test each (x,y) \in E \times F.
(3,0) \in T as \frac{3-0}{3} = 1 (integer).
(1,-1) \in T as \frac{1-(-1)}{3} = \frac{2}{3} (not integer).
(2,-1) \in T as \frac{2-(-1)}{3} = \frac{3}{3} = 1 (integer).
(3,-2) \in T as \frac{3-(-2)}{3} = \frac{5}{3} (not integer).
b. Arrow Diagrams
An arrow diagram visually represents a relation between two finite sets A and B. Elements of A are listed in one column (or region), and elements of B in another. An arrow is drawn from x \in A to y \in B if (x, y) \in R.
Example: For R = {(2,6), (2,8), (2,10), (3,6), (4,8)} from Exercise 1:
Draw ovals for set A={2,3,4} and set B={6,8,10}.
Draw arrows from 2 to 6, from 2 to 8, from 2 to 10, from 3 to 6, and from 4 to 8.
This method is particularly useful for small, finite sets.
c. Cartesian Graphs (for R \to R)
When a relation is defined from the set of real numbers (\mathbb{R}) to the set of real numbers (\mathbb{R}), its graph can be plotted on a Cartesian plane.
Example from Exercise 5: Relation S from \mathbb{R} to \mathbb{R} means x \ge y. This represents all points (x,y) such that the x-coordinate is greater than or equal to the y-coordinate. This region is a half-plane, including the line y=x and everything below it.
(2,1) \in S because 2 \ge 1.
(2,2) \in S because 2 \ge 2.
2S3 means (2,3) \in S. This is false because 2 \not\ge 3.
(-1)S(-2) means (-1,-2) \in S. This is true because -1 \ge -2.
Example from Exercise 6: Relation R from \mathbb{R} to \mathbb{R} means y = x^2. This is the standard parabola opening upwards with its vertex at the origin.
(2,4) \in R because 4 = 2^2.
(4,2) \notin R because 2 \ne 4^2.
(-3)R9 means (-3,9) \in R because 9 = (-3)^2.
9R(-3) means (9,-3) \in R. This is false because -3 \ne 9^2.
3. Comparing Relations and Functions
a. Definition of a Function
A function is a special type of relation from a set A (the domain) to a set B (the codomain) where every element in A is related to exactly one element in B.
Key properties of a function f: A \to B:
Every element in the domain A must be mapped to some element in the codomain B (no element in A is left unmapped).
Every element in the domain A must be mapped to exactly one element in the codomain B (no element in A has more than one arrow originating from it in an arrow diagram, or no x-value leads to more than one y-value in a Cartesian graph).
b. Identifying Functions from Relations (using arrow diagrams)
Consider relations R, S, and T from A={4,5,6} to B={5,6,7}. The original problem gives specific conditions or set of ordered pairs for each related to A to B. Let's analyze potential outputs based on typical interpretations:
Relation R: x \ge y
Possible pairs: (5,5), (6,5), (6,6).
Arrow Diagram: From 5 to 5, from 6 to 5, from 6 to 6.
Is it a function? No. Element 4 \in A is not related to any element in B (i.e., no arrow originates from 4). Also, element 6 \in A is related to both 5 and 6 in B. Both violate the function definition.
Relation S: \frac{x-y}{2} is an integer
Possible pairs: (4,6) (since \frac{4-6}{2}=-1), (5,5) (since \frac{5-5}{2}=0), (6,6) (since \frac{6-6}{2}=0).
Arrow Diagram: From 4 to 6, from 5 to 5, from 6 to 6.
Is it a function? Yes. Every element in A has exactly one arrow originating from it.
Relation T = {(4,7),(6,5), (6, 7)}
Arrow Diagram: From 4 to 7, from 6 to 5, from 6 to 7.
Is it a function? No. Element 5 \in A is not related to any element in B. Also, element 6 \in A is related to both 5 and 7 in B. Both violate the function definition.
Example from Exercise 8: Let A = {2,4} and B = {1, 3, 5}.
Relation U: y-x>2
Pairs: (2,5) (5-2=3>2).
Is it a function? No. Element 4 \in A is not mapped to any element in B.
Relation V: \frac{x}{y-1} = \frac{1}{2}
This implies 2x = y-1, or y = 2x+1.
For x=2, y=2(2)+1=5. Pair: (2,5).
For x=4, y=2(4)+1=9. Not in B.
Is it a function? No. Element 4 \in A is not mapped to any element in B.
Relation W = {(2,5), (4, 1), (2, 3)}
Is it a function? No. Element 2 \in A is related to both 5 and 3 in B. This violates the exactly one mapping condition.
c. Counting Relations and Functions
Number of Relations: If set A has m elements and set B has n elements, then the number of possible ordered pairs in A \times B is \mathbf{mn}.
Each of these mn ordered pairs can either be in the relation or not be in the relation.
Therefore, the total number of distinct relations from A to B is 2^{mn}.
Number of Functions: If set A has m elements and set B has n elements, for each of the m elements in A, there are n possible choices in B to which it can be mapped.
Since each choice is independent, the total number of functions from A to B is n^m.
Example from Exercise 9: Let A={0,1} and B={1}.
Here, m=2 and n=1.
a. All relations from A to B: There are 2^{2 \times 1} = 2^2 = 4 relations.
The possible ordered pairs in A \times B are (0,1) and (1,1).
The relations are:
\emptyset (the empty relation)
{(0,1)}
{(1,1)}
{(0,1), (1,1)} (the full Cartesian product)
b. All functions from A to B: There are n^m = 1^2 = 1 function.
The only function is f = {(0,1), (1,1)}. (0 must map to 1 and 1 must map to 1).
c. Fraction of relations that are functions: \frac{\text{Number of functions}}{\text{Number of relations}} = \frac{1}{4}.
Exercise 10: To find four relations from A={a, b} to B={x, y} that are not functions, we need to violate the function definition.
Here m=2 and n=2. Total relations: 2^{2 \times 2} = 2^4 = 16. Total functions: 2^2 = 4. This leaves 16-4=12 relations that are not functions.
To be NOT a function, either:
An element in the domain is not mapped.
An element in the domain is mapped to more than one element.
Examples of non-function relations:
{} (empty relation - 'a' and 'b' are not mapped)
{(a,x)} ('b' is not mapped)
{(b,y)} ('a' is not mapped)
{(a,x), (a,y)} ('a' is mapped to two elements)
{(a,x), (a,y), (b,x)} ('a' is mapped to two elements)
{(a,x), (a,y), (b,x), (b,y)} (every element is related to everything, 'a' and 'b' are each mapped to two elements)
This comprehensive set of exercises provides a strong foundation for understanding, representing, and differentiating between relations and functions in discrete mathematics, covering both theoretical definitions and practical application with finite and infinite sets.