Worksheet: Relations and Functions

A relation on a set A is defined as a subset of the Cartesian product A × A. The major types of relations include: 1. **Empty Relation**: The relation with no elements, illustrated by R = φ. Example: No one in a class is sitting next to a friend. 2. **Universal Relation**: Every element is related to every other element, denoted as R = A × A. Example: Every student knows their own score. 3. **Reflexive**: A relation where (a, a) ∈ R for all a in A, such as 'is equal to'. 4. **Symmetric**: If (a, b) ∈ R, then (b, a) ∈ R, e.g., 'is a sibling of'. 5. **Transitive**: If (a, b) and (b, c) are in R, then (a, c) must also be in R, like 'is greater than'. 6. **Equivalence Relation**: A relation that is reflexive, symmetric and transitive. Example: 'is of the same height'. Each of these types is fundamental in categorizing connections within sets.

An equivalence relation on a set A is a relation that satisfies three properties: reflexive, symmetric, and transitive. To prove a relation R is an equivalence relation, one must show: 1. **Reflexive**: Show (a, a) ∈ R for all a in A. 2. **Symmetric**: Show if (a, b) ∈ R then (b, a) ∈ R. 3. **Transitive**: Show if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R. **Example**: Let R be defined on integers Z by R = {(a, b): a is congruent to b modulo n}. This relation is reflexive (a ≡ a), symmetric (if a ≡ b, then b ≡ a), and transitive (if a ≡ b and b ≡ c then a ≡ c). Thus, it is an equivalence relation.

In mathematics, a function f: X → Y assigns to each element x in X exactly one element y in Y. 1. A function is **one-one (injective)** if it maps distinct elements in X to distinct elements in Y, meaning if f(x1) = f(x2), then x1 must equal x2. Example: f(x) = 2x is one-one as different x values yield different f(x) values. 2. A function is **onto (surjective)** if every element in Y is the image of at least one element in X; in other words, the range of f is equal to Y. Example: The function f(x) = x² is NOT onto when Y = R because negative numbers are not outputs of the function. A function can be both one-one and onto, termed **bijective**, like f(x) = x + 1 on integers.

The composition of two functions f: A → B and g: B → C is defined as (g ∘ f)(x) = g(f(x)). To compose, you apply f first, then g. **Example**: Let f(x) = 2x and g(x) = x + 3. Then the composite function (g ∘ f)(x) = g(2x) = 2x + 3. To analyze if g ∘ f is one-one or onto: 1. **One-one**: f is one-one (since it doubles the input) and g is also one-one (as it just adds a constant). Hence, g ∘ f is one-one. 2. **Onto**: g is onto (covers all of R), and f is onto for R as input is any real number. Thus, g ∘ f is onto as well.

A binary operation on a set A is a calculation that combines two elements a and b from A to produce another element in A. Formally, it's a function from A × A to A, denoted as *: A × A → A. **Examples**: 1. **Addition**: +: Z × Z → Z, where a + b is an integer if a and b are integers. 2. **Multiplication**: ×: R × R → R, where ab is a real number. These operations are functions because they map pairs of inputs to a single output. Relations can arise from binary operations when defining equivalences like a + b = c, leading to the exploration of properties like commutativity.

Injective (one-one) functions ensure distinct inputs have distinct outputs, significant in uniqueness in solutions. Surjective (onto) functions ensure every possible output can be achieved from at least one input. **Examples**: Injective: f(x) = 3x + 1 is injective as it never produces the same output for different inputs, while Surjective: g(x) = x² is surjective from R to R+ (non-negative reals) as every positive number has a pre-image. In analysis, injectivity maintains uniqueness in inverses, and surjectivity ensures covering complete output spaces, vital for defining functions in integration and calculus.

The **domain** of a function is the set of all possible inputs, while the **range** is the set of all possible outputs (resulting from the domain). In the context of relations, they define sets involved in relationships. **Example**: For the function f(x) = 1/x, the domain is R - {0} because x cannot be zero (as it would be undefined), and the range is also R - {0} as it can take any real value except for zero. In relations, if A = {1, 2, 3} and B = {x | x is x ≤ 3}, a relation R defined as R = {(1, 1), (2, 2), (3, 3)} indicates a connection based on matching items within A and B.

Reflexive, symmetric, and transitive properties are essential to establish equivalence relations. A relation R is reflexive if every element is related to itself, symmetric if a relation between two different elements exists in both directions, and transitive if a relation between three elements forms a consistent chain. This helps in partitioning sets into equivalence classes, which is fundamental in areas like modular arithmetic and classification in algebra. **Example**: Consider R defined on the set of all people relating a person A to person B if 'A is the parent of B'. This relation is reflexive (root), symmetric (parent/child relationship), and transitive (generational linking). Thus, it can categorize people under similar lineage.

A binary operation combines two elements to create a third element from a given set. In set theory, these operations can influence structure and shape properties essential for deeper analysis. For instance, let A = {0, 1}. **Example**: - Addition mod 2: 0 + 0 = 0, 1 + 1 = 0, establishing a closure property within a finite group. - Multiplication has a distinct result where it generates 0 and 1 distinctly while defining actions within the group (0 acts as the identity). These dictate how elements relate within sets and establish closure and identity, stimulating exploration of fields, groups, and rings in algebra.

Reflexive relation: (a, a) ∈ R for all a. Example: R = {(1, 1), (2, 2)} on set {1, 2}. Symmetric relation: If (a, b) ∈ R, then (b, a) ∈ R. Example: R = {(1, 2), (2, 1)}. Transitive relation: If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R. Example: R = {(1, 2), (2, 3), (1, 3)}. Diagrams show how relationships overlap and intersect.

R is a function since every element in set A maps to exactly one element in set B. Each input has a unique output. Therefore, R is a function. Diagram shows arrows from A to corresponding B elements.

Proven. Let f: A → B and g: B → C be injective. If f(a1) = f(a2), then a1 = a2 (by injectivity of f). Thus, g(f(a1)) = g(f(a2)) implies a1 = a2, proving the composition g ∘ f is injective.

R is not reflexive (no (x,x) exists), not symmetric (if (x,y), then (y,x) does not hold), and transitive (if (x,y) and (y,z), then (x,z) holds). Thereby, R exhibits transitive property only.

R is reflexive (a - a = 0 is even), symmetric (if a - b is even, then b - a is even), and transitive (if a - b and b - c are even, then a - c is even). Thus, R is an equivalence relation.

f is not injective (since f(-1) = f(1)), not surjective (as values below 0 are not achieved). Therefore, f is neither injective nor surjective.

(g∘f)(x) = g(f(x)) = g(2x) = 2x + 3, which is indeed a function as every input results in a unique output.

The equivalence class of 1, denoted [1], includes elements related to 1 under R. Here, it is {1, 2}. Visualizing helps comprehend the relationships between elements.

R is not reflexive (if A ⊂ A, then not all A = A), not symmetric (A ⊆ B does not imply B ⊆ A), not transitive (A ⊆ B and B ⊆ C does not imply A ⊆ C). Hence, not an equivalence relation.

Justify your answer by providing examples of different equivalence classes within a network and analyze how these classes affect user behavior and connections.

Provide evidence about its injectivity and surjectivity, referring to its derivative and range.

Discuss the domain and range of each composition and whether they yield the same outputs for all inputs.

Discuss real-life scenarios where these properties help in understanding membership relationships within the community.

Demonstrate how the pigeonhole principle applies to prove the failure of injectivity in the chosen function.

Provide thorough reasoning for each property, discussing edge cases.

Evaluate various sets and operations showing fulfillment or failure of closure.

Create a corresponding graph to show the behavior of the function clearly illustrating the points made.

Identify each property: reflexivity, symmetry, transitivity and categorize R accordingly.

Discuss conditions under which functions may or may not have inverses along with example functions that illustrate these conditions.