Relations and Functions Course Wiki

Institution: MIT

View original course

6 study materials · 8 sections

This course wiki provides a comprehensive guide to relations and functions, building upon foundational concepts from earlier studies. It systematically explores various types of relations, including empty, universal, reflexive, symmetric, and transitive, with a focus on equivalence relations and their classes. The wiki also delves into different classifications of functions such as one-one, onto, and bijective, alongside their composition and invertibility.

Course Sections

Relations and Functions: Chapter Summary

Key concepts: Relations and Functions (recap) · Definition of a Relation · Empty Relation · Universal Relation · Reflexive Relation · Symmetric Relation · Transitive Relation · Equivalence Relation · Equivalence Classes · One-one Function (Injective) · Onto Function (Surjective) · Bijective Function · Composition of Functions · Invertible Function

This chapter provides a comprehensive review of relations and functions, building upon Class XI concepts. It delves into various types of relations, including empty, universal, reflexive, symmetric, and transitive, culminating in the definition and application of equivalence relations and their corresponding equivalence classes. The chapter also introduces different types of functions, such as one-one, onto, and bijective functions, and explores the composition and invertibility of functions.

Relations and Functions: Chapter Summary

This chapter provides a comprehensive review and expansion of the fundamental mathematical concepts of relations and functions, building upon the groundwork laid in Class XI. It systematically defines various types of relations, explores their properties, and culminates in the crucial concept of equivalence relations. Subsequently, the focus shifts to functions, detailing their classifications as one-one, onto, and bijective, and examining their composition and invertibility. Understanding these structures is paramount for advanced topics in mathematics, computer science, and engineering, forming the bedrock for areas like discrete mathematics, abstract algebra, and calculus.

Recalling Foundational Concepts

Before delving into the intricacies of different relation types, it is essential to recall the basic definitions of relations and functions, along with their associated components: domain, codomain, and range. In essence, a relation describes a connection or association between elements of sets, while a function is a special kind of relation where each input from the domain maps to exactly one output in the codomain.

Definition of a Relation

The mathematical definition of a relation formalizes the intuitive idea of elements being "related." Given two non-empty sets, A and B, a relation R from A to B is formally defined as an arbitrary subset of their Cartesian product A × B. If A = B, then R is a relation on set A, meaning R ⊆ A × A.

Definition: Relation A relation R from a non-empty set A to a non-empty set B is a subset of the Cartesian product A × B. If (a, b) ∈ R, we say that a is related to b, often denoted as a R b.

Why it matters: This precise definition allows for the rigorous study of connections between mathematical objects, laying the groundwork for understanding functions, graphs, and various abstract structures. It provides a universal language to describe dependencies and mappings, crucial in areas from database design to social network analysis.

Concrete Example: Let A = {Alice, Bob, Carol} and B = {Math, Physics, Chemistry}. The Cartesian product A × B would list all possible pairings of students and subjects. A relation R from A to B could be "studies" defined as R = {(Alice, Math), (Bob, Physics), (Alice, Chemistry)}. Here, Alice R Math means Alice studies Math.

Types of Relations

Relations can exhibit various properties that classify them into distinct types. These classifications are crucial for understanding their behavior and applications, particularly in areas like database design, graph theory, and logic.

Empty Relation

The empty relation (or void relation) is the most trivial type of relation. It signifies a complete lack of any connection between elements within a set.

Definition 1: Empty Relation A relation R on a set A is called an empty relation if no element of A is related to any element of A, i.e., R = φ ⊂ A × A.

How it works: In an empty relation, the subset of A × A is the empty set φ. This means for any a, b ∈ A, the ordered pair (a, b) is not in R.

Concrete Example: Let A = {1, 2, 3}. Consider the relation R = {(a, b) : a, b ∈ A, a - b = 5}. The maximum difference between any two elements in A is 3 - 1 = 2 (or 1 - 3 = -2). There are no pairs (a, b) such that a - b = 5. Thus, R = φ, making it an empty relation.

Universal Relation

At the opposite end of the spectrum from the empty relation is the universal relation, where every element is related to every other element.

Definition 2: Universal Relation A relation R on a set A is called a universal relation if each element of A is related to every element of A, i.e., R = A × A.

How it works: The universal relation includes all possible ordered pairs from the Cartesian product A × A.

Concrete Example: Let A = {1, 2, 3}. Consider the relation R = {(a, b) : a, b ∈ A, |a - b| ≥ 0}. Since the absolute difference between any two real numbers is always non-negative, this condition holds for all pairs in A × A. Therefore, R = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)} = A × A, which is a universal relation.

Why it matters: Both empty and universal relations, while seemingly trivial, serve as important boundary cases in the study of relations. They are always reflexive, symmetric, and transitive (vacuously for empty, trivially for universal), making them equivalence relations.

Reflexive Relation

A relation is reflexive if every element in the set is related to itself. This property signifies a self-referential connection or identity.

Definition 3: Reflexive Relation A relation R on a set A is called reflexive if (a, a) ∈ R for every a ∈ A.

How it works: To check for reflexivity, one must verify that for every element a in the set A, the pair (a, a) is present in the relation R. If even one such pair is missing, the relation is not reflexive.

Concrete Example: Let A = {1, 2, 3}.

  1. R₁ = {(1, 1), (2, 2), (3, 3), (1, 2)} is reflexive because (1, 1), (2, 2), and (3, 3) are all in R₁.
  2. R₂ = {(1, 1), (2, 2), (1, 3)} is not reflexive because (3, 3) ∉ R₂.

Symmetric Relation

A relation is symmetric if whenever an element a is related to an element b, then b is also related to a. This property implies a mutual or two-way connection.

Definition 4: Symmetric Relation A relation R on a set A is called symmetric if (a, b) ∈ R implies (b, a) ∈ R for all a, b ∈ A.

How it works: For every ordered pair (a, b) found in R, its "reverse" pair (b, a) must also be in R. If (a, b) is in R but (b, a) is not, then the relation is not symmetric. Pairs of the form (a, a) trivially satisfy the condition, as they are their own reverse.

Concrete Example: Let A = {1, 2, 3}.

  1. R₁ = {(1, 2), (2, 1), (1, 1)} is symmetric because (1, 2) ∈ R₁ and (2, 1) ∈ R₁. (1, 1) is its own reverse.
  2. R₂ = {(1, 2), (2, 3)} is not symmetric because (1, 2) ∈ R₂ but (2, 1) ∉ R₂.

Transitive Relation

A relation is transitive if, whenever a is related to b and b is related to c, then a is also related to c. This property describes a chain-like connection.

Definition 5: Transitive Relation A relation R on a set A is called transitive if (a, b) ∈ R and (b, c) ∈ R implies (a, c) ∈ R for all a, b, c ∈ A.

How it works: If there's a "path" from a to b and from b to c in the relation, there must also be a direct "path" from a to c. If (a, b) and (b, c) are in R but (a, c) is not, then the relation is not transitive. Note that if there are no such (a, b) and (b, c) pairs (where the second element of the first pair matches the first element of the second pair), the condition is vacuously true, and the relation is considered transitive.

Concrete Example: Let A = {1, 2, 3}.

  1. R₁ = {(1, 2), (2, 3), (1, 3), (1, 1)} is transitive.
    • (1, 2) ∈ R₁ and (2, 3) ∈ R₁ implies (1, 3) ∈ R₁ (which it is).
    • (1, 1) ∈ R₁ and (1, 2) ∈ R₁ implies (1, 2) ∈ R₁ (which it is).
  2. R₂ = {(1, 2), (2, 3)} is not transitive because (1, 2) ∈ R₂ and (2, 3) ∈ R₂ but (1, 3) ∉ R₂.

Common Pitfall: For transitivity, ensure you check all possible chains a R b and b R c. A single missing a R c breaks transitivity. It's also easy to overlook the "vacuously true" case where no such (a,b) and (b,c) pairs exist.

Equivalence Relation

The concept of an equivalence relation is one of the most significant in mathematics. It combines the three fundamental properties: reflexivity, symmetry, and transitivity. Equivalence relations are used to partition a set into disjoint subsets called equivalence classes.

Definition 6: Equivalence Relation A relation R on a set A is called an equivalence relation if R is reflexive, symmetric, and transitive.

Why it matters: Equivalence relations allow us to group "similar" elements together, treating them as equivalent for a particular purpose. For instance, in geometry, congruence is an equivalence relation. In modular arithmetic, a ≡ b (mod n) is an equivalence relation, partitioning integers into residue classes. This concept is foundational to constructing new mathematical objects (e.g., rational numbers from integers, vectors from directed line segments).

How it works: To prove a relation is an equivalence relation, one must demonstrate all three properties (reflexive, symmetric, transitive) hold true for the given relation on the specified set.

Concrete Example: Consider the relation R on the set Z of all integers defined as R = {(a, b) : a - b is an even integer}.

  1. Reflexive: For any a ∈ Z, a - a = 0, which is an even integer. So (a, a) ∈ R. Thus, R is reflexive.
  2. Symmetric: If (a, b) ∈ R, then a - b is an even integer. This means a - b = 2k for some integer k. Then b - a = -(a - b) = -2k = 2(-k). Since -k is also an integer, b - a is an even integer. So (b, a) ∈ R. Thus, R is symmetric.
  3. Transitive: If (a, b) ∈ R and (b, c) ∈ R, then a - b is even and b - c is even. So a - b = 2k₁ and b - c = 2k₂ for some integers k₁, k₂. Adding these equations: (a - b) + (b - c) = 2k₁ + 2k₂, which simplifies to a - c = 2(k₁ + k₂). Since k₁ + k₂ is an integer, a - c is an even integer. So (a, c) ∈ R. Thus, R is transitive. Since R is reflexive, symmetric, and transitive, it is an equivalence relation.

Equivalence Classes: An equivalence relation R on a set A partitions A into disjoint non-empty subsets called equivalence classes. For an element a ∈ A, its equivalence class, denoted [a], is the set of all elements x ∈ A such that x R a. For the example R = {(a, b) : a - b is an even integer} on Z:

  • [0] = {x ∈ Z : x - 0 is even} = {..., -4, -2, 0, 2, 4, ...} (the set of even integers).
  • [1] = {x ∈ Z : x - 1 is even} = {..., -3, -1, 1, 3, 5, ...} (the set of odd integers). These two classes [0] and [1] partition Z.
Relation Type Definition Example on A = {1, 2, 3}
Empty R = φ R = {(a, b) : a + b = 10}
Universal R = A × A R = {(a, b) : a + b > 0}
Reflexive (a, a) ∈ R for all a ∈ A R = {(1,1), (2,2), (3,3), (1,2)}
Symmetric (a, b) ∈ R ⇒ (b, a) ∈ R R = {(1,2), (2,1), (3,3)}
Transitive (a, b) ∈ R, (b, c) ∈ R ⇒ (a, c) ∈ R R = {(1,2), (2,3), (1,3)}
Equivalence Reflexive, Symmetric, Transitive R = {(1,1), (2,2), (3,3)} (identity relation)

Functions as Special Relations

A function is a highly specific type of relation where each element in the domain is associated with exactly one element in the codomain. This uniqueness of mapping is what distinguishes functions from general relations. The chapter reviews the classification of functions based on their mapping properties: one-one (injective), onto (surjective), and bijective.

One-one (Injective) Functions

A function is one-one if distinct elements in the domain always map to distinct elements in the codomain. No two different inputs share the same output.

Definition: One-one (Injective) Function A function f: A → B is said to be one-one (or injective) if for all x₁, x₂ ∈ A, f(x₁) = f(x₂) implies x₁ = x₂. Equivalently, if x₁ ≠ x₂ implies f(x₁) ≠ f(x₂).

Concrete Example: Let f: R → R be defined by f(x) = 2x + 1. If f(x₁) = f(x₂), then 2x₁ + 1 = 2x₂ + 1, which implies 2x₁ = 2x₂, and thus x₁ = x₂. So, f is one-one.

Onto (Surjective) Functions

A function is onto if every element in the codomain has at least one corresponding element in the domain. In other words, the range of the function is equal to its codomain.

Definition: Onto (Surjective) Function A function f: A → B is said to be onto (or surjective) if for every y ∈ B, there exists at least one x ∈ A such that f(x) = y.

Concrete Example: Let f: R → R be defined by f(x) = 2x + 1. For any y ∈ R (codomain), we need to find an x ∈ R (domain) such that f(x) = y. 2x + 1 = y 2x = y - 1 x = (y - 1) / 2. Since y is a real number, (y - 1) / 2 is also a real number. Thus, for every y in the codomain, there exists an x in the domain. So, f is onto.

Bijective Functions

A function that is both one-one (injective) and onto (surjective) is called a bijective function or a one-to-one correspondence. Bijective functions establish a perfect pairing between the elements of the domain and the codomain.

Definition: Bijective Function A function f: A → B is said to be bijective if it is both one-one and onto.

Why it matters: Bijective functions are crucial because they are precisely the functions that possess an inverse function. This property is fundamental for solving equations, transforming data without loss, and defining inverse operations. In fields like cryptography, bijections ensure that messages can be uniquely encrypted and decrypted.

Concrete Example: The function f(x) = 2x + 1 from R to R shown above is both one-one and onto, hence it is a bijective function.

Function Type Property Graphical Test (for real-valued functions)
One-one (Injective) Distinct inputs map to distinct outputs. f(x₁) = f(x₂) ⇒ x₁ = x₂ Horizontal Line Test: Any horizontal line intersects the graph at most once.
Onto (Surjective) Every element in the codomain is an image of at least one element in the domain. Range = Codomain. For every y in the codomain, a horizontal line at y intersects the graph at least once.
Bijective Both one-one and onto. Horizontal Line Test: Any horizontal line intersects the graph exactly once.

Composition of Functions

The composition of functions allows us to combine two functions to form a new function. This is a powerful operation that models sequential processes, where the output of one function becomes the input of another.

Definition: Composition of Functions Given two functions f: A → B and g: B → C, the composition of f and g, denoted g o f (read as "g of f"), is a function g o f: A → C defined by (g o f)(x) = g(f(x)) for all x ∈ A. Note that the codomain of f must be the domain of g for g o f to be defined.

How it works: The input x is first processed by f, producing an intermediate output f(x). This f(x) then serves as the input for g, yielding the final output g(f(x)).

Concrete Example: Let f: R → R be f(x) = 2x + 1 and g: R → R be g(x) = x². Then (g o f)(x) = g(f(x)) = g(2x + 1) = (2x + 1)² = 4x² + 4x + 1. And (f o g)(x) = f(g(x)) = f(x²) = 2(x²) + 1 = 2x² + 1. This example also illustrates that function composition is generally not commutative (g o f ≠ f o g).

Invertible Functions

An invertible function is one for which an inverse function exists, effectively "undoing" the action of the original function. The existence of an inverse is directly tied to the function being bijective.

Definition: Invertible Function A function f: A → B is said to be invertible if there exists a function g: B → A such that g o f = I_A and f o g = I_B, where I_A and I_B are the identity functions on sets A and B respectively. The function g is called the inverse of f and is denoted by f⁻¹.

Why it matters: Invertible functions are critical for solving equations, cryptography, and various transformations where reversibility is required. They ensure that for every output, there is a unique input that produced it, allowing for unambiguous reversal.

How it works: A function f is invertible if and only if f is bijective (both one-one and onto). If f is bijective, its inverse f⁻¹ can be found by setting y = f(x) and solving for x in terms of y. The resulting expression in y then defines f⁻¹(y).

Concrete Example: Let f: R → R be f(x) = 2x + 1. We established this is bijective. To find f⁻¹(y): Let y = 2x + 1. Solve for x: y - 1 = 2x x = (y - 1) / 2. So, f⁻¹(y) = (y - 1) / 2. To verify: (f⁻¹ o f)(x) = f⁻¹(f(x)) = f⁻¹(2x + 1) = ((2x + 1) - 1) / 2 = 2x / 2 = x = I_R(x). (f o f⁻¹)(y) = f(f⁻¹(y)) = f((y - 1) / 2) = 2((y - 1) / 2) + 1 = (y - 1) + 1 = y = I_R(y). Thus, f⁻¹(x) = (x - 1) / 2 is indeed the inverse function.

Connection to Inverse Trigonometric Functions: As highlighted in the introduction to inverse trigonometric functions (Lemh102), the existence of an inverse function for trigonometric functions (like sine, cosine, tangent) necessitates restricting their domains and ranges. This is because, over their natural domains, these functions are not one-one and onto. By carefully selecting a principal value branch, they become bijective, allowing for the definition of their inverses (e.g., sin⁻¹, cos⁻¹). This directly demonstrates the practical importance of bijectivity as a prerequisite for invertibility.

Summary of Key Properties and Connections

The concepts of relations and functions, along with their various classifications, form the bedrock of higher mathematics. Understanding reflexivity, symmetry, and transitivity allows for the identification of equivalence relations, which are powerful tools for partitioning sets and simplifying complex structures. Similarly, the properties of injectivity, surjectivity, and bijectivity are essential for defining invertible functions, enabling inverse operations and transformations. These foundational ideas are not merely theoretical constructs but have direct applications in diverse fields, from computer science algorithms to advanced physics.

Relations and Functions: Chapter Summary - Relations and Functions Course Wiki - diagram 1
Relations and Functions: Chapter Summary - Relations and Functions Course Wiki - diagram 1
Relations and Functions: Chapter Summary - Relations and Functions Course Wiki - diagram 2
Relations and Functions: Chapter Summary - Relations and Functions Course Wiki - diagram 2
Relations and Functions: Chapter Summary - Relations and Functions Course Wiki - diagram 3
Relations and Functions: Chapter Summary - Relations and Functions Course Wiki - diagram 3

1.1 Introduction

Key concepts: Relations (recap) · Functions (recap) · Domain · Codomain · Range · Mathematical Definition of a Relation · Functions as Special Relations

This section reviews fundamental concepts of relations and functions from Class XI, including domain, codomain, and range. It formally defines a relation as a subset of a Cartesian product and sets the stage for the chapter's topics, such as different types of relations and functions, composition, and invertible functions.

1.1 Introduction

The study of relations and functions forms the bedrock of advanced mathematics, providing the language and structure to describe connections between mathematical objects. This section serves as a crucial re-introduction and formalization of concepts initially encountered in Class XI, laying the groundwork for more complex topics such as inverse functions, composition of functions, and binary operations. We will revisit the fundamental definitions of relations and functions, precisely define their associated components like domain, codomain, and range, and establish the formal mathematical definition of a relation.

Recapping Foundational Concepts from Class XI

In Class XI, the preliminary notions of relations and functions were introduced, along with their graphical representations and key attributes such as domain, codomain, and range. These concepts are not merely abstract constructs but are essential tools for modeling real-world phenomena, from physical laws to economic trends. A clear understanding of these foundational elements is paramount before delving into their more intricate manifestations.

Relations and Functions: A Précis

A relation intuitively describes a connection or association between elements of two or more sets. For instance, "is less than" is a relation between numbers, and "is the capital of" is a relation between cities and countries. Mathematically, this intuitive idea is formalized through ordered pairs. A function, on the other hand, is a special type of relation where each input from the first set is associated with exactly one output in the second set. This uniqueness constraint is what gives functions their predictive power and makes them central to virtually every branch of mathematics and science.

Domain, Codomain, and Range

To precisely define and understand relations and functions, three critical terms are used to describe the sets involved in their definition: domain, codomain, and range. These terms help delineate the scope of the inputs, the potential outputs, and the actual outputs of a relation or function.

Term Definition For a Relation R from A to B For a Function f from A to B
Domain The set of all possible input values for which the relation or function is defined. The set A. The set A.
Codomain The set of all possible output values that the relation or function could produce. It is the target set where outputs reside. The set B. The set B.
Range The set of all actual output values produced by the relation or function when applied to its domain. It is a subset of the codomain. R_range = {b ∈ B : (a, b) ∈ R for some a ∈ A} f_range = {f(a) : a ∈ A}

For real-valued functions, these concepts are often visualized through graphs on a Cartesian plane, where the domain corresponds to the x-axis values and the range to the y-axis values that the graph covers.

The Mathematical Definition of a Relation

The intuitive notion of a "connection" is rigorously defined using the concept of a Cartesian product of sets. This definition is fundamental as it provides a universal framework for describing any relationship between elements of sets.

What it is: Precise Definition

A relation R from a non-empty set A to a non-empty set B is formally defined as any arbitrary subset of the Cartesian product A × B.

The Cartesian product A × B is the set of all possible ordered pairs (a, b) where a ∈ A and b ∈ B. If A has m elements and B has n elements, then A × B will have m × n ordered pairs. A relation R then simply selects some (or all, or none) of these possible pairs to define the specific connection.

Notation

If an ordered pair (a, b) belongs to the relation R, we can express this in two equivalent ways:

  • (a, b) ∈ R
  • a R b (read as "a is related to b by R")

Why it Matters: Foundational Structure

This definition is crucial because it provides a precise, unambiguous way to describe relationships. Without it, mathematical discourse about connections between objects would lack rigor. It forms the basis for defining more specialized structures like functions, equivalence relations, order relations, and graphs, all of which are essential in various fields, from computer science to physics.

How it Works: Mechanics of Definition

To construct a relation R from set A to set B:

  1. Identify the elements of set A and set B.
  2. Form the Cartesian product A × B, which includes every possible ordered pair (a, b) where a is from A and b is from B.
  3. Define a specific rule or condition that elements a and b must satisfy to be "related."
  4. Select all ordered pairs (a, b) from A × B that satisfy this condition. This collection of selected pairs forms the relation R.

Concrete Example

Let A = {1, 2, 3} and B = {2, 4, 6}. The Cartesian product A × B is: {(1, 2), (1, 4), (1, 6), (2, 2), (2, 4), (2, 6), (3, 2), (3, 4), (3, 6)}

Now, let's define a relation R from A to B with the rule: a R b if a divides b. We check each pair in A × B against this rule:

  • (1, 2): 1 divides 2 (True)
  • (1, 4): 1 divides 4 (True)
  • (1, 6): 1 divides 6 (True)
  • (2, 2): 2 divides 2 (True)
  • (2, 4): 2 divides 4 (True)
  • (2, 6): 2 divides 6 (True)
  • (3, 2): 3 does not divide 2 (False)
  • (3, 4): 3 does not divide 4 (False)
  • (3, 6): 3 divides 6 (True)

Therefore, the relation R is the subset of A × B containing only the pairs that satisfy the condition: R = {(1, 2), (1, 4), (1, 6), (2, 2), (2, 4), (2, 6), (3, 6)}

In this example:

  • Domain of R: {1, 2, 3} (all elements of A are involved as first components)
  • Codomain of R: {2, 4, 6} (the target set B)
  • Range of R: {2, 4, 6} (all elements of B are involved as second components in R)

Functions as Special Relations

While every function is a relation, not every relation is a function. Functions are a particularly important class of relations due to their deterministic nature.

What makes a relation a function?

A relation f from set A to set B is a function if it satisfies two specific conditions:

  1. Every element in the domain A must be related to some element in the codomain B. (No element in A is left "unmapped").
  2. Each element in the domain A must be related to exactly one element in the codomain B. (An element in A cannot map to two different elements in B).

This "one and only one" output for each input is the defining characteristic of a function.

Comparison: Relations vs. Functions

Feature Relation R from A to B Function f from A to B
Definition Any subset of A × B. A special subset of A × B.
Input Mapping An element in A can be related to zero, one, or many elements in B. Every element in A must be related to exactly one element in B.
Domain The set A. The actual elements involved as first components form the domain of R, which is a subset of A. The set A (every element of A must be an input).
Output Mapping Elements in B can be outputs for multiple inputs, or no inputs. Elements in B can be outputs for multiple inputs, or no inputs.
Notation (a, b) ∈ R or a R b (a, f(a)) ∈ f or f(a) = b
Example R = {(1, 2), (1, 4), (2, 2)} (1 maps to 2 and 4) f = {(1, 2), (2, 4), (3, 6)} (each input maps to one output)

Chapter Topics Overview

Building upon these foundational concepts, this chapter will delve deeper into the various classifications and properties of relations and functions. The subsequent sections will cover:

  • Different Types of Relations: Exploring classifications such as empty, universal, reflexive, symmetric, transitive, and equivalence relations.
  • Different Types of Functions: Examining one-one (injective), onto (surjective), and bijective functions.
  • Composition of Functions: Understanding how functions can be combined to form new functions.
  • Invertible Functions: Investigating functions that have inverses and the conditions for their existence.
  • Binary Operations: Introducing operations that combine two elements from a set to produce another element of the same set.

This structured approach ensures a comprehensive understanding of relations and functions, equipping readers with the necessary tools for advanced mathematical analysis.

1.1 Introduction - Relations and Functions Course Wiki - diagram 1
1.1 Introduction - Relations and Functions Course Wiki - diagram 1

1.2 Types of Relations

Key concepts: Relation in a set A · Empty Relation · Universal Relation · Trivial Relations · Reflexive Relation · Symmetric Relation · Transitive Relation · Equivalence Relation · Equivalence Classes

This section systematically defines and illustrates various types of relations, starting with empty and universal relations. It then introduces the core properties of reflexive, symmetric, and transitive relations, which are essential for understanding equivalence relations. The concept of equivalence classes, which partition a set, is also explained with examples, followed by problems to classify relations.

1.2 Types of Relations

The study of relations forms a cornerstone of discrete mathematics, providing a formal framework to describe connections and associations between elements within sets. Building upon the foundational concepts of relations and functions introduced in Class XI, this section deeply explores the various classifications of relations defined within a single set. Understanding these types is crucial for advanced topics in algebra, logic, and computer science, particularly in areas like database design, graph theory, and the construction of abstract mathematical structures.

Relation in a Set A

What it is

A relation R in a set A is formally defined as any subset of the Cartesian product A × A. This means that R is a collection of ordered pairs (a, b) where both a and b are elements of A. When an ordered pair (a, b) belongs to R, we say that a is related to b by R, often denoted as a R b. This is a specific case of the more general definition of a relation from a set A to a set B, where R ⊆ A × B. Here, the domain and codomain are the same set A.

Why it matters

Defining relations within a single set A allows us to analyze intrinsic properties and structures within that set. It's the basis for classifying elements based on shared characteristics or connections, leading to powerful concepts like equivalence relations that partition a set, or order relations that structure it. This self-referential nature is fundamental to many mathematical and computational models.

How it works

To define a relation R in a set A, one specifies a rule or condition that elements a, b ∈ A must satisfy for the pair (a, b) to be included in R. For instance, if A is the set of integers, a relation could be "is less than or equal to" (≤), where R = {(a, b) ∈ A × A : a ≤ b}.

Concrete example

Let A = {1, 2, 3}. Consider the relation R defined as "is less than" on A. R = {(a, b) ∈ A × A : a < b}. The elements of R would be: {(1, 2), (1, 3), (2, 3)}. Here, 1 R 2 and 1 R 3, but 3 R 1 is false.

Common pitfalls

A common misconception is to confuse a relation in a set A with a function. While every function is a relation, not every relation is a function. In a relation, an element a can be related to multiple elements b, or to no elements at all, which is not permitted for functions. Also, ensure both elements of the ordered pair (a,b) truly belong to the specified set A.

Empty Relation

What it is

The Empty Relation (or Void Relation) on a set A is the relation R where no element of A is related to any element of A. Mathematically, it is defined as R = φ ⊂ A × A, where φ represents the empty set.

Why it matters

The empty relation serves as a boundary case in the spectrum of possible relations. While seemingly trivial, it is a valid relation by definition and is important for the completeness of mathematical theory. It represents a scenario where no connections exist between elements.

How it works

To construct an empty relation, one simply defines a condition that can never be met by any pair of elements from the set.

Concrete example

Let A = {1, 2, 3}. Consider the relation R = {(a, b) ∈ A × A : a + b = 7}. Since the maximum sum of any two elements from A is 3 + 3 = 6, there are no pairs (a, b) in A × A such that a + b = 7. Therefore, R = φ, which is the empty relation.

Universal Relation

What it is

The Universal Relation on a set A is the relation R where every element of A is related to every element of A. Mathematically, it is defined as R = A × A.

Why it matters

Like the empty relation, the universal relation is another boundary case, representing the maximum possible connectivity within a set. It signifies a scenario where all possible connections exist, which can be useful in certain theoretical contexts or as a baseline for comparison.

How it works

To construct a universal relation, one defines a condition that is always true for any pair of elements from the set.

Concrete example

Let A = {1, 2, 3}. Consider the relation R = {(a, b) ∈ A × A : a + b > 0}. Since all elements in A are positive, the sum of any two elements will always be greater than 0. Thus, R = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}, which is A × A, the universal relation.

Trivial Relations

The Empty Relation and the Universal Relation are collectively known as Trivial Relations because they represent the extreme, and often least interesting, cases of relatedness within a set. They serve as fundamental examples but typically lack the intricate structure found in other types of relations.

Reflexive Relation

What it is

A relation R in a set A is called reflexive if every element of A is related to itself. Formally, for every a ∈ A, the ordered pair (a, a) must belong to R. That is, (a, a) ∈ R for all a ∈ A.

Why it matters

Reflexivity signifies self-identity or self-connection. Many common relations, such as "is equal to" (=), "is a subset of" (⊆), or "is less than or equal to" (≤), are reflexive. This property is essential for defining equivalence relations and partial orderings, which are ubiquitous in mathematics and computer science.

How it works

To check if a relation R is reflexive, one must verify that for every element a in the set A, the pair (a, a) is present in R. If even one such pair is missing, the relation is not reflexive.

Concrete example

Let A = {1, 2, 3}.

  1. R₁ = {(1,1), (2,2), (3,3), (1,2)} is reflexive because (1,1), (2,2), and (3,3) are all in R₁.
  2. R₂ = {(1,1), (2,2), (1,2)} is not reflexive because (3,3) is missing from R₂.

Common pitfalls

The most common mistake is forgetting the "for all a ∈ A" clause. A relation might contain some (a,a) pairs but still not be reflexive if it doesn't contain all of them for every element in the set A.

Symmetric Relation

What it is

A relation R in a set A is called symmetric if whenever a is related to b, then b is also related to a. Formally, if (a, b) ∈ R, then (b, a) must also belong to R, for all a, b ∈ A.

Why it matters

Symmetry implies a bidirectional relationship or mutual connection. Relations like "is a sibling of," "is equal to," or "is connected to" (in an undirected graph) are symmetric. This property is crucial for understanding undirected graphs and defining equivalence relations.

How it works

To check for symmetry, for every pair (a, b) found in R where a ≠ b, you must ensure that its reverse pair (b, a) is also in R. If (a, b) ∈ R but (b, a) ∉ R, the relation is not symmetric. Note that (a, a) pairs do not affect symmetry, as (a, a) is its own reverse.

Concrete example

Let A = {1, 2, 3}.

  1. R₁ = {(1,2), (2,1), (3,3)} is symmetric because (1,2) has (2,1) and (3,3) is self-symmetric.
  2. R₂ = {(1,2), (2,3)} is not symmetric because (1,2) is in R₂ but (2,1) is not, and (2,3) is in R₂ but (3,2) is not.

Common pitfalls

Confusing symmetry with reflexivity. A relation can be symmetric without being reflexive (e.g., "is a sibling of" where no one is their own sibling), and vice-versa. Also, remember that if a pair (a,b) is not in R, then there's no requirement for (b,a) to be in R for symmetry to hold.

Transitive Relation

What it is

A relation R in a set A is called transitive if whenever a is related to b and b is related to c, then a is also related to c. Formally, if (a, b) ∈ R and (b, c) ∈ R, then (a, c) must also belong to R, for all a, b, c ∈ A.

Why it matters

Transitivity represents a chain-like property or a "transfer" of the relation across elements. Relations like "is less than" (<), "is a subset of" (⊆), or "is an ancestor of" are transitive. This property is fundamental to order relations and equivalence relations, allowing us to infer indirect connections.

How it works

To check for transitivity, identify all pairs (a, b) and (b, c) in R where the second element of the first pair matches the first element of the second pair. For each such "chain," verify that the pair (a, c) is also in R. If even one such (a, c) is missing, the relation is not transitive.

Concrete example

Let A = {1, 2, 3}.

  1. R₁ = {(1,2), (2,3), (1,3), (1,1)} is transitive.
    • (1,2) ∈ R₁ and (2,3) ∈ R₁ implies (1,3) ∈ R₁ (which it is).
    • (1,1) doesn't form a chain that would violate transitivity.
  2. R₂ = {(1,2), (2,3)} is not transitive because (1,2) ∈ R₂ and (2,3) ∈ R₂, but (1,3) is missing from R₂.

Common pitfalls

The "if" condition for transitivity (and symmetry) is crucial. If there are no pairs (a, b) and (b, c) in R that form a chain, then the relation is vacuously transitive for those specific a, b, c. This means a relation with very few elements can often be transitive by default. Also, remember that a, b, c do not have to be distinct.

Table: Properties of Relations

Property Definition Example (on A={1,2,3}) Non-Example (on A={1,2,3})
Reflexive (a,a) ∈ R for all a ∈ A {(1,1), (2,2), (3,3), (1,2)} {(1,1), (1,2)} (missing (2,2), (3,3))
Symmetric If (a,b) ∈ R, then (b,a) ∈ R {(1,2), (2,1), (3,3)} {(1,2)} (missing (2,1))
Transitive If (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R {(1,2), (2,3), (1,3), (1,1)} {(1,2), (2,3)} (missing (1,3))

Equivalence Relation

What it is

A relation R in a set A is called an Equivalence Relation if it is simultaneously reflexive, symmetric, and transitive.

Why it matters

Equivalence relations are profoundly important because they formalize the concept of "sameness" or "being equivalent." They partition a set into disjoint, non-overlapping subsets called equivalence classes, where all elements within a class are considered equivalent to each other under the relation. This concept is foundational in abstract algebra (e.g., quotient groups, rings), topology, and computer science (e.g., state equivalence in automata, data clustering).

How it works

To verify if a relation is an equivalence relation, one must systematically check all three properties:

  1. Reflexivity: Is every element related to itself? ((a,a) ∈ R for all a ∈ A)
  2. Symmetry: If a is related to b, is b related to a? (If (a,b) ∈ R, then (b,a) ∈ R)
  3. Transitivity: If a is related to b and b is related to c, is a related to c? (If (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R) If all three conditions hold, the relation is an equivalence relation.

Concrete example

Let A be the set of all integers, Z. Consider the relation R = {(a, b) ∈ Z × Z : a - b is an even integer}. Let's check the properties:

  1. Reflexivity: For any a ∈ Z, a - a = 0, which is an even integer. So, (a, a) ∈ R. Thus, R is reflexive.
  2. Symmetry: If (a, b) ∈ R, then a - b is an even integer. This means a - b = 2k for some integer k. Then b - a = -(a - b) = -2k = 2(-k). Since -k is also an integer, b - a is an even integer. So, (b, a) ∈ R. Thus, R is symmetric.
  3. Transitivity: If (a, b) ∈ R and (b, c) ∈ R, then a - b is even and b - c is even. So, a - b = 2k and b - c = 2m for some integers k, m. Adding these equations: (a - b) + (b - c) = 2k + 2m. This simplifies to a - c = 2(k + m). Since k + m is an integer, a - c is an even integer. So, (a, c) ∈ R. Thus, R is transitive. Since R is reflexive, symmetric, and transitive, it is an equivalence relation.

Equivalence Classes

What it is

For an equivalence relation R on a set A and any element a ∈ A, the equivalence class of a, denoted [a], is the set of all elements x ∈ A that are related to a by R. Formally, [a] = {x ∈ A : (x, a) ∈ R}.

Why it matters

Equivalence classes provide a concrete way to visualize how an equivalence relation partitions a set. They demonstrate that the set A can be broken down into a collection of disjoint, non-empty subsets, where each element of A belongs to exactly one such subset. This partitioning is fundamental to constructing quotient sets and understanding modular arithmetic.

How it works

The properties of an equivalence relation guarantee that:

  1. Every element a ∈ A belongs to exactly one equivalence class (due to reflexivity and transitivity).
  2. Any two equivalence classes are either identical or completely disjoint (due to symmetry and transitivity).
  3. The union of all distinct equivalence classes equals the original set A.

Concrete example

Continuing with the equivalence relation R = {(a, b) ∈ Z × Z : a - b is an even integer} on the set of integers Z. Let's find the equivalence classes:

  • Equivalence class of 0: [0] = {x ∈ Z : x - 0 is an even integer} = {x ∈ Z : x is an even integer} = {..., -4, -2, 0, 2, 4, ...}. This is the set of all even integers.
  • Equivalence class of 1: [1] = {x ∈ Z : x - 1 is an even integer} = {x ∈ Z : x is an odd integer} = {..., -3, -1, 1, 3, 5, ...}. This is the set of all odd integers. Notice that [0] and [1] are disjoint, and their union is Z. Any other integer will fall into either [0] or [1]. For example, [2] would be {x ∈ Z : x - 2 is an even integer}, which is the same as [0]. Thus, the equivalence relation partitions Z into two distinct equivalence classes: the set of even integers and the set of odd integers.

Table: Real-world Applications of Relation Types

Relation Type Real-world Application Description
Reflexive "is equal to" (=) Any number is equal to itself.
"is a subset of" (⊆) Any set is a subset of itself.
Symmetric "is a sibling of" If Person A is a sibling of Person B, then Person B is a sibling of Person A.
"is connected to" (in a social network) If User A is connected to User B, then User B is connected to User A (e.g., Facebook friends).
Transitive "is less than" (<) If a < b and b < c, then a < c.
"is an ancestor of" If A is an ancestor of B, and B is an ancestor of C, then A is an ancestor of C.
Equivalence "has the same birthday as" Partitions people into 365 (or 366) equivalence classes based on their birth date.
"is congruent to" (modulo n) If a ≡ b (mod n), b ≡ c (mod n), then a ≡ c (mod n). Partitions integers into n remainder classes.

Common Pitfalls and Misconceptions

  1. Vacuously True Properties: Transitivity and symmetry can be "vacuously true" if the premise of their conditional statement is never met. For example, if a relation R has no pairs (a, b) and (b, c) such that b is shared, then R is transitive by default. Similarly, if R has no (a, b) pairs where a ≠ b, it's symmetric. This is a common source of confusion.
  2. "For all" vs. "For some": For reflexivity, it is critical that (a, a) ∈ R for every element a in the set A. If even one (a, a) is missing, the relation is not reflexive.
  3. Distinguishing Relation Types: A single relation can possess multiple properties or none at all. For example, the "less than or equal to" (≤) relation on integers is reflexive and transitive but not symmetric. The "is a sibling of" relation is symmetric but neither reflexive nor transitive. Exercise 1.1 from the source material (Lemh1An) provides excellent examples of relations exhibiting different combinations of these properties, reinforcing the need for careful verification of each.
1.2 Types of Relations - Relations and Functions Course Wiki - diagram 1
1.2 Types of Relations - Relations and Functions Course Wiki - diagram 1
1.2 Types of Relations - Relations and Functions Course Wiki - diagram 2
1.2 Types of Relations - Relations and Functions Course Wiki - diagram 2
1.2 Types of Relations - Relations and Functions Course Wiki - diagram 3
1.2 Types of Relations - Relations and Functions Course Wiki - diagram 3

1.3 Types of Functions

Key concepts: One-one Function (Injective) · Many-one Function · Onto Function (Surjective) · Bijective Function · Greatest Integer Function · Modulus Function · Signum Function

This section revisits various functions introduced in Class XI and then formally defines one-one (injective), many-one, onto (surjective), and bijective functions. It provides examples and counter-examples to clarify these concepts, discusses properties specific to finite sets, and includes problems to assess injectivity, surjectivity, and bijectivity.

1.3 Types of Functions

Understanding the fundamental classifications of functions is crucial for advanced mathematical concepts, particularly when delving into topics like inverse functions, calculus, and abstract algebra. Building upon the foundational knowledge of functions from Class XI, this section provides a rigorous treatment of key function types: One-one (Injective), Many-one, Onto (Surjective), and Bijective functions. We will explore their precise definitions, motivations, and implications, along with illustrative examples and a discussion of their properties on finite versus infinite sets. The concepts introduced here are directly applicable to problems found in Exercise 1.2, which often involve analyzing the injectivity, surjectivity, and bijectivity of various functions, including the Greatest Integer Function and the Modulus Function.

Review of Foundational Function Types

Before diving into the classifications based on mapping properties, it is beneficial to briefly recall some common real-valued functions studied previously. These functions serve as excellent examples and counter-examples when discussing injectivity and surjectivity.

Function Type Definition Domain (D) Range (R) Graph Characteristics
Identity Function f(x) = x R R Line y=x, passes through origin, slope 1.
Constant Function f(x) = c (where c is a constant) R {c} Horizontal line y=c.
Polynomial Function f(x) = a_n x^n + ... + a_0 R Varies Smooth, continuous curve; shape depends on degree.
Rational Function f(x) = P(x) / Q(x) (Q(x) ≠ 0) `R \ {x Q(x)=0}` Varies
Modulus Function `f(x) = x ` R
Signum Function f(x) = 1 if x > 0, 0 if x = 0, -1 if x < 0 R {-1, 0, 1} Step function with jumps at x=0.
Greatest Integer Function f(x) = ⌊x⌋ (floor function) R Z (integers) Step function, constant between integers, jumps at integers.

Injective Functions (One-one)

A function is injective or one-one if every distinct element in its domain maps to a distinct image in its codomain. In simpler terms, no two different inputs produce the same output.

Definition: One-one Function (Injective) A function f: X → Y is said to be one-one (or injective) if for all x₁, x₂ ∈ X, f(x₁) = f(x₂) implies x₁ = x₂. Equivalently, if x₁ ≠ x₂ implies f(x₁) ≠ f(x₂).

Why it Matters

The concept of injectivity is fundamental because it guarantees that each output corresponds to a unique input. This property is a prerequisite for a function to have an inverse, as an inverse function must be able to uniquely map an output back to its original input. Without injectivity, an inverse would not be well-defined, as a single output could correspond to multiple inputs. This is particularly critical for the existence of inverse trigonometric functions, where the domains of trigonometric functions must be restricted to ensure they become one-one (Lemh102).

How it Works

To prove a function f is one-one, one typically assumes f(x₁) = f(x₂) for arbitrary x₁, x₂ in the domain and then algebraically demonstrates that this assumption must lead to x₁ = x₂. If a counterexample can be found where f(x₁) = f(x₂) but x₁ ≠ x₂, then the function is not one-one.

Concrete Example

Consider the function f: R → R defined by f(x) = 2x + 3. To check if it's one-one: Assume f(x₁) = f(x₂). 2x₁ + 3 = 2x₂ + 3 Subtract 3 from both sides: 2x₁ = 2x₂ Divide by 2: x₁ = x₂ Since f(x₁) = f(x₂) implies x₁ = x₂, the function f(x) = 2x + 3 is one-one.

Many-one Functions

A function that is not one-one is called a many-one function. This means that there exist at least two distinct elements in the domain that map to the same image in the codomain.

Definition: Many-one Function A function f: X → Y is said to be many-one if there exist x₁, x₂ ∈ X such that x₁ ≠ x₂ but f(x₁) = f(x₂).

Why it Matters

Understanding many-one functions helps in identifying when a function cannot have a global inverse without domain restrictions. Trigonometric functions like sin(x) and cos(x) are classic examples of many-one functions over their natural domains (e.g., sin(0) = 0 and sin(π) = 0), necessitating domain restrictions to define their inverses (Lemh102).

Concrete Example

Consider the function f: R → R defined by f(x) = x². Let x₁ = 2 and x₂ = -2. Then x₁ ≠ x₂. However, f(x₁) = f(2) = 2² = 4 and f(x₂) = f(-2) = (-2)² = 4. Since f(2) = f(-2) but 2 ≠ -2, the function f(x) = x² is many-one.

Surjective Functions (Onto)

A function is surjective or onto if every element in its codomain is the image of at least one element in its domain. In other words, the range of the function is equal to its codomain.

Definition: Onto Function (Surjective) A function f: X → Y is said to be onto (or surjective) if for every y ∈ Y, there exists at least one x ∈ X such that f(x) = y. Equivalently, the range of f is equal to its codomain Y (i.e., Range(f) = Y).

Why it Matters

Surjectivity ensures that the function "covers" its entire intended output space. Like injectivity, it is a crucial condition for the existence of an inverse function. If a function is not onto, there would be elements in the codomain that are not mapped to by any element in the domain, making it impossible to define an inverse for those elements.

How it Works

To prove a function f: X → Y is onto, one typically takes an arbitrary element y from the codomain Y and then demonstrates that there exists an x in the domain X such that f(x) = y. This often involves solving the equation y = f(x) for x in terms of y and showing that the resulting x is always within the domain X.

Concrete Example

Consider the function f: R → R defined by f(x) = 2x + 3. Let y be an arbitrary element in the codomain R. We need to find an x ∈ R such that f(x) = y. y = 2x + 3 y - 3 = 2x x = (y - 3) / 2 Since y is a real number, (y - 3) / 2 will always be a real number. Thus, for every y in the codomain, there exists an x in the domain R such that f(x) = y. Therefore, f(x) = 2x + 3 is onto.

Not Onto Examples

A function is not onto if its range is a proper subset of its codomain. This means there are elements in the codomain that are never produced as outputs by the function.

Concrete Example

Consider the function f: R → R defined by f(x) = x². The codomain is R (all real numbers). The range of f(x) = x² is [0, ∞) (all non-negative real numbers), because x² can never be negative. Since Range(f) = [0, ∞) which is a proper subset of R, the function f(x) = x² is not onto when its codomain is R.

Bijective Functions (One-one and Onto)

A function that is both injective (one-one) and surjective (onto) is called a bijective function. These functions establish a perfect one-to-one correspondence between the elements of the domain and the elements of the codomain.

Definition: Bijective Function A function f: X → Y is said to be bijective if it is both one-one (injective) and onto (surjective).

Why it Matters

Bijective functions are of paramount importance because they are precisely the functions for which an inverse function f⁻¹ exists (Lemh102). An inverse function essentially "undoes" the original function, mapping elements from the codomain back to their unique original elements in the domain. This property is fundamental in many areas of mathematics, including solving equations, cryptography, and defining inverse trigonometric functions.

How it Works

To prove a function is bijective, one must prove both its injectivity and its surjectivity independently. If both conditions are met, the function is bijective.

Concrete Example

From our previous examples, the function f: R → R defined by f(x) = 2x + 3 was shown to be both one-one and onto. Therefore, f(x) = 2x + 3 is a bijective function.

Properties for Finite vs. Infinite Sets

A notable property emerges when considering functions defined on finite sets, which does not necessarily hold for infinite sets.

Key Property for Finite Sets For a finite set X, a function f: X → X is one-one if and only if it is onto.

This means if you have a function mapping a finite set to itself, proving it's one-one automatically implies it's onto, and vice-versa. This is because if every element maps to a distinct element, and the domain and codomain have the same finite size, then all elements of the codomain must be covered. Conversely, if all elements of the codomain are covered, and the domain and codomain have the same finite size, then no two elements can map to the same image.

Contrast with Infinite Sets

This property does not hold for infinite sets.

  • Example (One-one but not onto): Consider f: N → N (natural numbers) defined by f(x) = 2x.
    • One-one: If 2x₁ = 2x₂, then x₁ = x₂. So, it's one-one.
    • Not onto: The range of f is {2, 4, 6, ...}, which are the even natural numbers. This is a proper subset of the codomain N. Odd natural numbers (e.g., 1, 3, 5) are in the codomain but are not images of any x ∈ N.
  • Example (Onto but not one-one): Consider f: Z → N ∪ {0} (integers to non-negative integers) defined by f(x) = |x|.
    • Onto: For any y ∈ N ∪ {0}, we can choose x = y (if y ≥ 0) or x = -y (if y > 0). E.g., for y=5, f(5)=5 and f(-5)=5. So, it's onto.
    • Not one-one: f(2) = 2 and f(-2) = 2, but 2 ≠ -2. So, it's not one-one.
Property Finite Set X (f: X → X) Infinite Set (f: X → X or f: X → Y)
One-one ⇔ Onto Holds true Does NOT hold true
Implication Injectivity implies Surjectivity, and vice-versa. Injectivity does not imply Surjectivity, and vice-versa.
Reason Cardinality match ensures full mapping coverage. Infinite sets allow for subsets of the same cardinality, leading to "gaps" or "overlaps".

Case Study: Common Functions and their Properties

Let's analyze the injectivity and surjectivity of some common functions, often encountered in problems from Exercise 1.2.

1. Greatest Integer Function (f(x) = ⌊x⌋)

  • What it is: The function f: R → R (or f: R → Z) that assigns to each real number x the greatest integer less than or equal to x.
  • Injectivity: This function is many-one. For example, f(1.1) = 1 and f(1.5) = 1, but 1.1 ≠ 1.5.
  • Surjectivity: If the codomain is R, it is not onto, as its range is Z (the set of integers). Real numbers like 1.5 are in the codomain but are not images of any x. If the codomain is specified as Z, then it is onto, as every integer y is the image of x=y.

2. Modulus Function (f(x) = |x|)

  • What it is: The function f: R → R (or f: R → [0, ∞)) defined as f(x) = x if x ≥ 0 and f(x) = -x if x < 0.
  • Injectivity: This function is many-one. For example, f(2) = 2 and f(-2) = 2, but 2 ≠ -2.
  • Surjectivity: If the codomain is R, it is not onto, as its range is [0, ∞). Negative real numbers are in the codomain but are not images of any x. If the codomain is specified as [0, ∞), then it is onto.

3. Signum Function (f(x) = sgn(x))

  • What it is: The function f: R → R (or f: R → {-1, 0, 1}) defined as f(x) = 1 if x > 0, f(x) = 0 if x = 0, and f(x) = -1 if x < 0.
  • Injectivity: This function is many-one. For example, f(5) = 1 and f(100) = 1, but 5 ≠ 100.
  • Surjectivity: If the codomain is R, it is not onto, as its range is {-1, 0, 1}. Most real numbers are in the codomain but are not images of any x. If the codomain is specified as {-1, 0, 1}, then it is onto.
Function Type Domain (D) Codomain (Y) One-one? Onto? (for Y=R) Bijective? (for Y=R)
f(x) = 2x + 3 R R Yes Yes Yes
f(x) = x² R R No No No
f(x) = ⌊x⌋ R R No No No
`f(x) = x ` R R No
f(x) = sgn(x) R R No No No

Connecting to Inverse Functions

The classifications discussed here are not merely theoretical constructs; they have profound practical implications, especially for the existence of inverse functions. As stated in Lemh102, "the inverse of a function f, denoted by f⁻¹, exists if f is one-one and onto." This highlights why bijective functions are so significant: they are precisely the functions that are invertible. When a function is not bijective (i.e., it's many-one or not onto), its inverse cannot be defined over its natural domain and codomain. In such cases, as seen with trigonometric functions, specific restrictions on the domain and codomain are applied to create a new function that is bijective, thereby allowing the definition of an inverse (e.g., the principal value branches of inverse trigonometric functions).

Exercise 1.2: Injectivity, Surjectivity, Bijectivity

Exercise 1.2 typically presents a series of functions and asks the student to determine if they are injective, surjective, or bijective. This requires applying the formal definitions and proof techniques discussed. Common challenges include:

  • Algebraic manipulation: Correctly solving f(x₁) = f(x₂) for x₁ = x₂.
  • Domain and Codomain awareness: The properties of a function (one-one, onto) are highly dependent on its specified domain and codomain. A function that is not onto for f: R → R might become onto if its codomain is restricted to its range.
  • Counter-examples: Identifying specific values that violate injectivity or surjectivity (e.g., f(2)=f(-2) for f(x)=x²).
  • Understanding function behavior: Visualizing graphs or understanding the intrinsic nature of functions like ⌊x⌋ or |x| helps in quickly assessing their properties.
1.3 Types of Functions - Relations and Functions Course Wiki - diagram 1
1.3 Types of Functions - Relations and Functions Course Wiki - diagram 1
1.3 Types of Functions - Relations and Functions Course Wiki - diagram 2
1.3 Types of Functions - Relations and Functions Course Wiki - diagram 2
1.3 Types of Functions - Relations and Functions Course Wiki - diagram 3
1.3 Types of Functions - Relations and Functions Course Wiki - diagram 3

1.4 Composition of Functions and Invertible Function

Key concepts: Composition of Functions · Invertible Function · Bijective Function

This section introduces the concept of composing functions, defining `gof` and illustrating its application. It then explains invertible functions, establishing the condition that a function must be bijective for its inverse to exist, and provides examples of finding inverse functions.

1.4 Composition of Functions and Invertible Function

Overview

This section explores two advanced concepts in functions: composition and invertibility. It begins by defining the Composition of Functions, gof, for given functions f: A → B and g: B → C, where gof(x) = g(f(x)). Examples illustrate how to compute composite functions and emphasize that gof is generally not equal to fog. The section then moves to Invertible Functions, defining an inverse function g: Y → X for a function f: X → Y such that gof = IX (identity on X) and fog = IY (identity on Y). A crucial condition for a function to be invertible is established: it must be both one-one and onto (bijective). Examples demonstrate how to determine if a function is invertible and how to find its inverse.

Key Ideas

  • Composition of Functions: Given f: A → B and g: B → C, the composition gof: A → C is defined by gof(x) = g(f(x)). Note that gof is generally not commutative with fog.
  • Invertible Function: A function f: X → Y is invertible if there exists a function g: Y → X such that gof = IX and fog = IY. The function g is called the inverse of f, denoted f^-1.
  • Condition for Invertibility: A function is invertible if and only if it is one-one and onto (bijective).

Miscellaneous Examples and Exercises

Key concepts: Equivalence Relation · One-one Function · Onto Function · Composition of Functions · Number of Functions · Number of Relations

This section provides a collection of diverse examples that apply and extend the concepts of relations and functions, including properties of equivalence relations and counting functions. It also includes a comprehensive set of problems from the miscellaneous exercise to test overall understanding of Chapter 1.

Miscellaneous Examples and Exercises

This section serves as a crucial consolidation point for the foundational concepts of relations and functions, extending the theoretical understanding with advanced examples and practical exercises. It moves beyond basic definitions to explore intricate properties, such as the behavior of equivalence relations under set operations, the construction of relations on complex domains like ordered pairs, and the combinatorial aspects of counting specific types of functions. The exercises are designed to challenge and deepen comprehension, ensuring a robust grasp of the subject matter.

Equivalence Relations: Properties and Construction

An equivalence relation is a fundamental concept in mathematics that formalizes the idea of "sameness" or "equality" within a set. It partitions a set into disjoint subsets called equivalence classes, where all elements within a class are related to each other, and no element is related to an element outside its class. For a relation R on a set A to be an equivalence relation, it must satisfy three properties:

Definition: Equivalence Relation A relation R on a set A is an equivalence relation if it is:

  1. Reflexive: For all a ∈ A, (a, a) ∈ R (or a R a).
  2. Symmetric: For all a, b ∈ A, if (a, b) ∈ R, then (b, a) ∈ R (or a R b ⇒ b R a).
  3. Transitive: For all a, b, c ∈ A, if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R (or a R b and b R c ⇒ a R c).

Equivalence relations are paramount in various fields, from abstract algebra (quotient groups, rings) to computer science (data structures, type theory) and physics (symmetry groups). They allow us to simplify complex systems by grouping "equivalent" elements, effectively reducing the problem space.

Intersection of Equivalence Relations

A key property explored in the exercises is how equivalence relations behave under set operations. Specifically, the intersection of two equivalence relations on the same set A yields another equivalence relation.

What it is: If R1 and R2 are two equivalence relations on a set A, then their intersection, R1 ∩ R2, is also an equivalence relation on A. Why it matters: This demonstrates the closure property of equivalence relations under intersection, which is useful in constructing new equivalence relations or understanding the structure of relations. How it works: To prove this, we must show that R1 ∩ R2 satisfies reflexivity, symmetry, and transitivity.

Proof Sketch for R1 ∩ R2:

  1. Reflexivity: Since R1 and R2 are reflexive, for any a ∈ A, (a, a) ∈ R1 and (a, a) ∈ R2. Therefore, (a, a) ∈ R1 ∩ R2.
  2. Symmetry: Assume (a, b) ∈ R1 ∩ R2. This means (a, b) ∈ R1 and (a, b) ∈ R2. Since R1 and R2 are symmetric, (b, a) ∈ R1 and (b, a) ∈ R2. Thus, (b, a) ∈ R1 ∩ R2.
  3. Transitivity: Assume (a, b) ∈ R1 ∩ R2 and (b, c) ∈ R1 ∩ R2. This implies (a, b) ∈ R1, (b, c) ∈ R1, (a, b) ∈ R2, and (b, c) ∈ R2. Since R1 and R2 are transitive, (a, c) ∈ R1 and (a, c) ∈ R2. Hence, (a, c) ∈ R1 ∩ R2.

Common Pitfall: While the intersection of equivalence relations is an equivalence relation, the union of two equivalence relations is generally not an equivalence relation. It usually fails the transitivity property.

Equivalence Relations on Ordered Pairs

Equivalence relations can be defined on sets whose elements are themselves structured, such as ordered pairs. Consider a relation R on the set A × A (ordered pairs of integers (x, y) where y ≠ 0), defined as (x, y) R (u, v) if and only if xv = yu.

What it is: This relation essentially defines equivalence for rational numbers. The pair (x, y) can be thought of as the fraction x/y. The condition xv = yu is equivalent to x/y = u/v. Why it matters: This example demonstrates how abstract relations can model concrete mathematical concepts, like the equality of fractions. It also highlights the importance of domain constraints (e.g., y ≠ 0, v ≠ 0). How it works: We verify the three properties:

  1. Reflexivity: For any (x, y) ∈ A × A, xy = yx (by commutativity of multiplication). So, (x, y) R (x, y).
  2. Symmetry: If (x, y) R (u, v), then xv = yu. By commutativity, yu = xv, which can be rewritten as uy = vx. Thus, (u, v) R (x, y).
  3. Transitivity: If (x, y) R (u, v) and (u, v) R (a, b), then xv = yu and ub = va. From xv = yu, we have x/y = u/v (assuming y, v ≠ 0). From ub = va, we have u/v = a/b (assuming v, b ≠ 0). Therefore, x/y = a/b, which implies xb = ya. Hence, (x, y) R (a, b).

This relation is indeed an equivalence relation, and its equivalence classes correspond to rational numbers. For instance, [(1, 2)] = {(1, 2), (2, 4), (3, 6), ...} represents the rational number 1/2.

Equivalence Relations from Functions

Functions can also induce equivalence relations. Given a function f: X → Y, we can define a relation R on the domain X such that a R b if and only if f(a) = f(b).

What it is: This relation groups elements in the domain X that map to the same element in the codomain Y. Why it matters: This construction is crucial in understanding the structure of functions, particularly in defining quotient sets and canonical factorizations. How it works:

  1. Reflexivity: For any a ∈ X, f(a) = f(a). So, a R a.
  2. Symmetry: If a R b, then f(a) = f(b). By symmetry of equality, f(b) = f(a). So, b R a.
  3. Transitivity: If a R b and b R c, then f(a) = f(b) and f(b) = f(c). By transitivity of equality, f(a) = f(c). So, a R c.

This relation is an equivalence relation. Its equivalence classes are the preimages of the elements in the range of f.

Properties and Counting of Functions

Functions are special types of relations with specific constraints. Understanding their properties—one-one (injective) and onto (surjective)—is critical for analyzing their behavior and for constructing inverse functions.

Definition: One-one (Injective) Function A function f: A → B is one-one (or injective) if distinct elements of A have distinct images in B. Formally, for all x1, x2 ∈ A, if f(x1) = f(x2), then x1 = x2.

Definition: Onto (Surjective) Function A function f: A → B is onto (or surjective) if every element in the codomain B is the image of at least one element in the domain A. Formally, for every y ∈ B, there exists an x ∈ A such that f(x) = y.

A function that is both one-one and onto is called bijective. Bijective functions are precisely those for which an inverse function exists.

Counting One-one Functions

What it is: Determining the number of possible injective mappings between two finite sets. Why it matters: This is a fundamental problem in combinatorics and helps in understanding the "density" of injective functions within the space of all possible functions. How it works: If A and B are finite sets with |A| = m and |B| = n, the number of one-one functions from A to B depends on the relative sizes of m and n.

Number of One-one Functions from A to B:

  • If m > n: There are 0 one-one functions. (You cannot map more distinct elements to fewer distinct elements injectively).
  • If m ≤ n: The number of one-one functions is given by the permutation formula P(n, m) = n! / (n - m)!.
    • The first element of A can be mapped to any of n elements in B.
    • The second element of A can be mapped to any of the remaining n-1 elements in B.
    • ...
    • The m-th element of A can be mapped to any of the remaining n - (m-1) elements in B.

Concrete Example: Let A = {1, 2, 3} and B = {a, b, c, d}. Here, m = 3 and n = 4. The number of one-one functions from A to B is P(4, 3) = 4! / (4 - 3)! = 4! / 1! = 4 × 3 × 2 × 1 = 24.

Table: Counting Functions between Finite Sets

| Function Type | Condition on |A|=m, |B|=n | Formula | | :----------------- | :----------------------------- | :------------------------------------ | | All Functions | Any m, n | n^m | | One-one (Injective)| m ≤ n | n! / (n - m)! (or P(n, m)) | | One-one (Injective)| m > n | 0 | | Onto (Surjective) | m < n | 0 | | Onto (Surjective) | m ≥ n | n^m - Σ(n choose k) * (n-k)^m (complex, involves Stirling numbers of the second kind) | | Bijective | m = n | n! (or P(n, n)) | | Bijective | m ≠ n | 0 |

Common Pitfall: Confusing permutations (P(n, m)) with combinations (C(n, m)) when counting one-one functions. The order of mapping matters for functions.

Analyzing Properties of Sums of Functions

Another type of exercise involves analyzing the properties of functions formed by combining simpler functions, such as their sum. For example, if f: R → R and g: R → R are two functions, we can define (f + g)(x) = f(x) + g(x). The question often arises whether properties like injectivity or surjectivity are preserved.

What it is: Investigating if f + g is one-one or onto given properties of f and g. Why it matters: This helps develop intuition about how function properties interact under algebraic operations. It's crucial for understanding linear algebra and functional analysis. How it works: Typically, one constructs counterexamples to show that injectivity or surjectivity is not generally preserved.

Concrete Example: Let f(x) = x and g(x) = -x.

  • f is one-one and onto.
  • g is one-one and onto.
  • However, (f + g)(x) = f(x) + g(x) = x + (-x) = 0.
  • The function (f + g)(x) = 0 is neither one-one (e.g., (f+g)(1) = 0 and (f+g)(2) = 0 but 1 ≠ 2) nor onto (its range is {0}, not R).

This example illustrates that even if f and g are both bijective, their sum f + g is not necessarily one-one or onto.

Composition and Invertible Functions

The concepts of composition of functions and invertible functions are closely linked. The composition f o g combines two functions sequentially, while an invertible function f has an inverse f⁻¹ such that their composition yields the identity function.

Definition: Composition of Functions Given functions f: B → C and g: A → B, the composition of f and g, denoted f o g, is a function f o g: A → C defined by (f o g)(x) = f(g(x)) for all x ∈ A.

Definition: Invertible Function A function f: A → B is invertible if there exists a function g: B → A such that g o f = I_A (the identity function on A) and f o g = I_B (the identity function on B). The function g is called the inverse of f and is denoted by f⁻¹. A function is invertible if and only if it is bijective (both one-one and onto).

These concepts are fundamental, especially when dealing with inverse trigonometric functions, where restricting domains and ranges is necessary to ensure bijectivity and thus the existence of an inverse.

Miscellaneous Exercise on Chapter 1

The "Miscellaneous Exercise on Chapter 1" provides a comprehensive assessment of the entire chapter's content. It includes a variety of problem types designed to test both definitional understanding and the ability to apply concepts in diverse scenarios.

Typical Problem Categories:

| Category | Description | | :----------------------------------- | :----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------``` The provided content focuses on the exercises and examples related to relations and functions, including their types, properties, composition, and counting. I will expand upon these concepts, providing definitions, motivations, mechanics, concrete examples, variations, and common pitfalls, based on the outlines provided (Lemh101, Lemh102, Lemh1Ps, Lemh1An).


Miscellaneous Examples and Exercises

This section provides a deep dive into advanced applications and problem-solving techniques related to relations and functions, building upon the foundational concepts introduced in Chapter 1. It emphasizes rigorous proof methods, combinatorial analysis, and the nuanced understanding of function properties essential for higher mathematics and its applications. The examples and exercises are designed to solidify comprehension, preparing the reader for complex scenarios encountered in calculus, discrete mathematics, and various engineering disciplines.

Recapitulation of Relations and Functions

Before delving into advanced examples, it is crucial to recall the fundamental definitions and classifications of relations and functions. A relation R from a set A to a set B is any subset of the Cartesian product A × B. When R is a relation on a set A, it is a subset of A × A. A function f: A → B is a special type of relation where every element in the domain A is mapped to exactly one element in the codomain B.

Table: Fundamental Properties of Relations

Property Definition (for R on set A) Example (on {1,2,3}) Non-Example
Reflexive (a, a) ∈ R for all a ∈ A {(1,1), (2,2), (3,3), (1,2)} {(1,1), (1,2)} (missing (2,2), (3,3))
Symmetric (a, b) ∈ R ⇒ (b, a) ∈ R for all a, b ∈ A {(1,2), (2,1), (1,1)} {(1,2)} (missing (2,1))
Transitive (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R for all a, b, c ∈ A {(1,2), (2,3), (1,3)} {(1,2), (2,3)} (missing (1,3))

These properties are the building blocks for classifying relations, most notably the equivalence relation.

Equivalence Relations: Deep Dive

An equivalence relation is a cornerstone concept in mathematics, enabling the partitioning of a set into disjoint subsets, known as equivalence classes. Each class groups elements that are "equivalent" under the defined relation.

Definition: Equivalence Relation A relation R on a set A is an equivalence relation if and only if it is reflexive, symmetric, and transitive.

Why it matters: Equivalence relations are fundamental for constructing new mathematical objects (e.g., rational numbers from integers, quotient spaces), simplifying complex structures by focusing on properties shared by entire classes, and proving theorems by induction over equivalence classes. They provide a formal framework for "classification."

Proving the Intersection of Equivalence Relations

One common exercise involves demonstrating that certain operations on equivalence relations preserve their properties. The intersection of two equivalence relations is a prime example.

What it is: Given two equivalence relations R1 and R2 on the same set A, their intersection R1 ∩ R2 is also an equivalence relation on A. How it works: To prove R1 ∩ R2 is an equivalence relation, we must verify all three properties:

  1. Reflexivity: For any a ∈ A, since R1 is reflexive, (a, a) ∈ R1. Similarly, since R2 is reflexive, (a, a) ∈ R2. Therefore, (a, a) ∈ R1 ∩ R2.
  2. Symmetry: Assume (a, b) ∈ R1 ∩ R2. This implies (a, b) ∈ R1 and (a, b) ∈ R2. Since R1 is symmetric, (b, a) ∈ R1. Since R2 is symmetric, (b, a) ∈ R2. Consequently, (b, a) ∈ R1 ∩ R2.
  3. Transitivity: Assume (a, b) ∈ R1 ∩ R2 and (b, c) ∈ R1 ∩ R2. This means (a, b) ∈ R1, (b, c) ∈ R1, (a, b) ∈ R2, and (b, c) ∈ R2. Since R1 is transitive, (a, c) ∈ R1. Since R2 is transitive, (a, c) ∈ R2. Thus, (a, c) ∈ R1 ∩ R2.

Since R1 ∩ R2 satisfies all three properties, it is an equivalence relation. Common Pitfall: While intersection works, the union of two equivalence relations is generally not an equivalence relation, as it often fails transitivity. For example, if R1 = {(1,1), (2,2), (3,3), (1,2), (2,1)} and R2 = {(1,1), (2,2), (3,3), (2,3), (3,2)}, then R1 ∪ R2 contains (1,2) and (2,3) but not (1,3), failing transitivity.

Equivalence Relations on Ordered Pairs

Relations can be defined on sets of ordered pairs, which often represent more complex mathematical objects. Consider the set S = Z × (Z - {0}), which consists of ordered pairs of integers (x, y) where y is non-zero. Define a relation R on S as (x, y) R (u, v) if and only if xv = yu.

Motivation: This relation formalizes the concept of equality between rational numbers. The pair (x, y) intuitively represents the fraction x/y. The condition xv = yu is equivalent to x/y = u/v. How it works: We verify the equivalence properties for R:

  1. Reflexivity: For any (x, y) ∈ S, xy = yx by the commutative property of integer multiplication. Thus, (x, y) R (x, y).
  2. Symmetry: If (x, y) R (u, v), then xv = yu. By commutativity, yu = xv, which can be rewritten as uy = vx. Therefore, (u, v) R (x, y).
  3. Transitivity: If (x, y) R (u, v) and (u, v) R (a, b), then xv = yu and ub = va.
    • From xv = yu, we have x/y = u/v (dividing by yv, which is non-zero).
    • From ub = va, we have u/v = a/b (dividing by vb, which is non-zero).
    • By transitivity of equality for rational numbers, x/y = a/b.
    • Multiplying by yb (which is non-zero), we get xb = ya.
    • Therefore, (x, y) R (a, b).

Since all three properties hold, R is an equivalence relation. The equivalence classes under this relation are precisely the rational numbers. For instance, the equivalence class [(1, 2)] contains {(1, 2), (2, 4), (-1, -2), ...}, all representing the rational number 1/2.

Equivalence Relations Induced by Functions

Functions can naturally define equivalence relations on their domains. Given a function f: X → Y, we can define a relation R on the domain X such that a R b if and only if f(a) = f(b).

What it is: This relation groups elements in the domain X that map to the same element in the codomain Y under the function f. Why it matters: This construction is fundamental in category theory and abstract algebra, leading to the concept of quotient sets and the first isomorphism theorem. It provides a way to "collapse" the domain based on functional equivalence. How it works:

  1. Reflexivity: For any a ∈ X, f(a) = f(a) is trivially true. Hence, a R a.
  2. Symmetry: If a R b, then f(a) = f(b). By the symmetric property of equality, f(b) = f(a). Hence, b R a.
  3. Transitivity: If a R b and b R c, then f(a) = f(b) and f(b) = f(c). By the transitive property of equality, f(a) = f(c). Hence, a R c.

This relation R is an equivalence relation. The equivalence classes [a] consist of all elements in X that map to f(a). That is, [a] = {x ∈ X | f(x) = f(a)}.

Properties and Counting of Functions

The classification of functions based on their injectivity (one-one) and surjectivity (onto) is crucial for determining properties like invertibility and for combinatorial analysis.

Counting One-one Functions

What it is: Calculating the total number of possible injective functions from a finite set A to a finite set B. Why it matters: This is a core combinatorial problem with applications in discrete mathematics, probability, and algorithm design (e.g., hashing functions, unique identifiers). How it works: Let |A| = m and |B| = n.

  • If m > n: It's impossible to map m distinct elements to n distinct elements injectively. Therefore, the number of one-one functions is 0.
  • If m ≤ n: The process is sequential:
    1. The first element of A can be mapped to any of the n elements in B.
    2. The second element of A must be mapped to one of the remaining n-1 elements in B (to maintain distinct images).
    3. The third element of A must be mapped to one of the remaining n-2 elements in B.
    4. ...
    5. The m-th element of A must be mapped to one of the remaining n - (m-1) elements in B. The total number of ways is the product n × (n-1) × (n-2) × ... × (n-m+1). This is precisely the definition of the number of permutations of n items taken m at a time, denoted P(n, m) or n P m, which equals n! / (n - m)!.

Concrete Example: Consider A = {p, q} and B = {1, 2, 3}. Here, m = 2 and n = 3. The number of one-one functions from A to B is P(3, 2) = 3! / (3 - 2)! = 3! / 1! = 3 × 2 = 6. These functions are:

  1. f(p)=1, f(q)=2
  2. f(p)=1, f(q)=3
  3. f(p)=2, f(q)=1
  4. f(p)=2, f(q)=3
  5. f(p)=3, f(q)=1
  6. f(p)=3, f(q)=2

Table: Summary of Function Counting for Finite Sets

Function Type Domain Size m Codomain Size n Number of Functions
All Functions m n n^m
Injective (One-one) m ≤ n n n! / (n - m)! (P(n, m))
Injective (One-one) m > n n 0
Surjective (Onto) m < n n 0
Surjective (Onto) m ≥ n n n! * S(m, n) (where S(m, n) are Stirling numbers of the second kind)
Bijective m = n n n!
Bijective m ≠ n n 0

Analyzing Properties of Sums of Functions

When functions are combined through operations like addition, their individual properties (like injectivity or surjectivity) are not necessarily preserved. This is a common area for misconceptions.

What it is: Examining whether f + g (where (f + g)(x) = f(x) + g(x)) inherits injectivity or surjectivity from f and g. Why it matters: It highlights that function properties are not always "linear" and requires careful analysis rather than simple assumption. This understanding is crucial in areas like functional analysis, where properties of operators are studied. Common Pitfalls: Assuming that if f and g are one-one, then f+g must also be one-one. This is generally false.

Concrete Example: Let f: R → R be f(x) = x and g: R → R be g(x) = -x.

  • f(x) = x: This is a bijective function (one-one and onto).
    • One-one: If f(x1) = f(x2), then x1 = x2.
    • Onto: For any y ∈ R, f(y) = y, so y is an image.
  • g(x) = -x: This is also a bijective function.
    • One-one: If g(x1) = g(x2), then -x1 = -x2, so x1 = x2.
    • Onto: For any y ∈ R, g(-y) = -(-y) = y, so y is an image.
  • (f + g)(x) = f(x) + g(x) = x + (-x) = 0:
    • Not One-one: For example, (f+g)(1) = 0 and (f+g)(2) = 0, but 1 ≠ 2. Distinct inputs map to the same output.
    • Not Onto: The range of (f+g)(x) is {0}. It does not cover the entire codomain R.

This example clearly shows that the sum of two bijective functions is not necessarily one-one or onto.

Miscellaneous Exercise on Chapter 1

The "Miscellaneous Exercise on Chapter 1" serves as a comprehensive review, integrating all concepts related to relations and functions. These problems often require a deeper understanding and application of multiple definitions.

Key Areas Covered in Exercises:

  • Classifying Relations: Determining if given relations are reflexive, symmetric, transitive, or equivalence relations (e.g., relations on sets of triangles, lines, or integers).
  • Function Properties: Proving or disproving injectivity (one-one) and surjectivity (onto) for various functions, including those with restricted domains/codomains.
  • Equivalence Classes: Finding specific equivalence classes for a given equivalence relation.
  • Composition and Invertibility: Analyzing composite functions and determining if a function is invertible, often requiring proof of bijectivity.
  • Counting Problems: Calculating the number of specific types of functions or relations between finite sets.
  • Advanced Definitions: Working with relations defined on more complex structures, like ordered pairs or sets of polynomials.

These exercises are designed to test not just recall, but also the ability to synthesize information, construct logical arguments, and apply mathematical definitions rigorously.

Miscellaneous Examples and Exercises - Relations and Functions Course Wiki - diagram 1
Miscellaneous Examples and Exercises - Relations and Functions Course Wiki - diagram 1
Miscellaneous Examples and Exercises - Relations and Functions Course Wiki - diagram 2
Miscellaneous Examples and Exercises - Relations and Functions Course Wiki - diagram 2
Miscellaneous Examples and Exercises - Relations and Functions Course Wiki - diagram 3
Miscellaneous Examples and Exercises - Relations and Functions Course Wiki - diagram 3

Summary of Key Concepts

Key concepts: Empty Relation · Universal Relation · Reflexive Relation · Symmetric Relation · Transitive Relation · Equivalence Relation · Equivalence Class · One-one (injective) Function · Onto (surjective) Function · Bijective Function

This section provides a concise summary of the essential definitions and properties covered in Chapter 1, including various types of relations, equivalence classes, and the different classifications of functions.

Summary of Key Concepts

This section provides a comprehensive deep-dive into the foundational concepts of relations, building upon the introductory ideas from Class XI. Understanding these classifications—Empty, Universal, Reflexive, Symmetric, and Transitive relations—is crucial for advanced mathematical reasoning, particularly in abstract algebra, set theory, and computer science. The culmination of these properties leads to the definition of an Equivalence Relation, a powerful concept that enables the partitioning of sets into disjoint Equivalence Classes. This exploration will define each relation type precisely, illustrate its significance, and provide concrete examples to solidify understanding.

The Mathematical Definition of a Relation

Before delving into specific types, it's essential to recall the fundamental definition of a relation. In mathematics, a relation R from a set A to a set B is formally defined as any arbitrary subset of the Cartesian product A × B. This means R ⊆ A × B. If A and B are the same set, we speak of a relation on set A, where R ⊆ A × A. The notation (a, b) ∈ R or a R b signifies that element a is related to element b under the relation R.

A Relation R from a non-empty set A to a non-empty set B is a subset of the Cartesian product A × B. If A = B, then R is a relation on set A, meaning R ⊆ A × A.

Empty Relation

What it is

The Empty Relation, also known as the void relation, is the relation where no element of the set A is related to any element of A. It is the empty set φ (or {}) as a subset of A × A.

Definition 1 (Empty Relation): A relation R on a set A is called an empty relation if no element of A is related to any element of A, i.e., R = φ ⊂ A × A.

Why it matters

The empty relation serves as an edge case in set theory and logic. While seemingly trivial, its inclusion ensures that the definition of a relation is comprehensive, covering all possible subsets of A × A, including the one with no elements. It's a foundational concept for understanding the bounds of what a relation can be.

How it works

For a relation to be empty, the condition defining the relation must be impossible to satisfy for any pair of elements in the set.

Concrete Example

Let A = {1, 2, 3}. Consider the relation R = {(a, b) : a, b ∈ A, a - b = 5}. There are no two elements a, b in A such that their difference is 5. Thus, R = φ, which is an empty relation.

Universal Relation

What it is

The Universal Relation is the opposite extreme of the empty relation. In this relation, every element of set A is related to every element of A. It is the entire Cartesian product A × A.

Definition 2 (Universal Relation): A relation R on a set A is called a universal relation if each element of A is related to every element of A, i.e., R = A × A.

Why it matters

Like the empty relation, the universal relation defines another boundary case. It represents a scenario where all possible connections exist between elements within a set. It's important for theoretical completeness and as a baseline for comparison with more constrained relations.

How it works

For a relation to be universal, the condition defining the relation must be true for all possible ordered pairs (a, b) where a, b ∈ A.

Concrete Example

Let A = {1, 2, 3}. Consider the relation R = {(a, b) : a, b ∈ A, |a - b| ≥ 0}. Since the absolute difference between any two real numbers (and thus any two integers in A) is always greater than or equal to 0, this condition is true for all pairs. Thus, R = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)} = A × A, which is a universal relation.

Properties of Relations on a Set A

Beyond the empty and universal relations, specific properties define the structure and behavior of relations. These properties are particularly significant when a relation is defined on a single set A (i.e., R ⊆ A × A).

Reflexive Relation

What it is

A relation R on a set A is reflexive if every element of A is related to itself.

Definition 3 (Reflexive Relation): A relation R on a set A is called reflexive if (a, a) ∈ R for every a ∈ A.

Why it matters

Reflexivity implies a self-referential property. In many real-world scenarios, an object is considered "related" to itself (e.g., "is equal to", "is the same height as"). It's a fundamental property for relations that define equivalence or similarity.

How it works

To check for reflexivity, one must verify that for every single element a in the set A, the ordered pair (a, a) is present in the relation R. If even one (a, a) pair is missing, the relation is not reflexive.

Concrete Example

Let A = {1, 2, 3}. Consider the relation R₁ = {(1,1), (2,2), (3,3), (1,2)}. This relation is reflexive because (1,1), (2,2), and (3,3) are all present in R₁. Consider R₂ = {(1,1), (2,2), (1,2)}. This relation is not reflexive because (3,3) is missing.

Common Pitfall

A common mistake is to assume reflexivity if some (a,a) pairs exist, without checking that all elements a ∈ A have (a,a) ∈ R.

Symmetric Relation

What it is

A relation R on a set A is symmetric if whenever a is related to b, then b is also related to a.

Definition 4 (Symmetric Relation): A relation R on a set A is called symmetric if for all a, b ∈ A, (a, b) ∈ R implies (b, a) ∈ R.

Why it matters

Symmetry indicates a bidirectional relationship. If a connection exists in one direction, it must also exist in the reverse. Examples include "is a sibling of" (if A is a sibling of B, B is a sibling of A) or "is married to".

How it works

For every ordered pair (a, b) found in R where a ≠ b, you must check if the corresponding reversed pair (b, a) is also in R. If (a, b) ∈ R and (b, a) ∉ R for any such pair, the relation is not symmetric. Pairs of the form (a, a) do not affect symmetry, as (a, a) implies (a, a) itself.

Concrete Example

Let A = {1, 2, 3}. Consider R₁ = {(1,2), (2,1), (3,3)}. This relation is symmetric because for (1,2), (2,1) is present, and (3,3) is its own reverse. Consider R₂ = {(1,2), (2,3)}. This relation is not symmetric because (1,2) ∈ R₂ but (2,1) ∉ R₂.

Common Pitfall

Confusing symmetry with reflexivity or transitivity. Symmetry only cares about the existence of the reverse pair. Also, if a pair (a,b) is not in R, then its reverse (b,a) does not need to be in R for the relation to be symmetric. The implication (a, b) ∈ R ⇒ (b, a) ∈ R is key.

Transitive Relation

What it is

A relation R on a set A is transitive if whenever a is related to b, and b is related to c, then a is also related to c.

Definition 5 (Transitive Relation): A relation R on a set A is called transitive if for all a, b, c ∈ A, (a, b) ∈ R and (b, c) ∈ R implies (a, c) ∈ R.

Why it matters

Transitivity implies a chain-like property or a form of logical inference. If a leads to b and b leads to c, then a must lead to c. This property is fundamental to ordering relations (like "less than or equal to") and many logical systems.

How it works

To check for transitivity, identify all "chains" of related elements: (a, b) ∈ R and (b, c) ∈ R. For each such chain, verify if the direct connection (a, c) is also present in R. If such a chain exists and (a, c) is missing, the relation is not transitive. If no such chains exist, the relation is vacuously transitive.

Concrete Example

Let A = {1, 2, 3}. Consider R₁ = {(1,2), (2,3), (1,3), (1,1)}. This relation is transitive:

  • (1,2) ∈ R₁ and (2,3) ∈ R₁ implies (1,3) ∈ R₁ (which is true).
  • No other (a,b), (b,c) chains exist where a,b,c are distinct.
  • Pairs like (1,1) don't form chains that violate transitivity.

Consider R₂ = {(1,2), (2,3)}. This relation is not transitive because (1,2) ∈ R₂ and (2,3) ∈ R₂, but (1,3) ∉ R₂.

Common Pitfall

Forgetting to check all possible chains. Also, understanding that if there are no (a, b) and (b, c) pairs, the condition for transitivity is vacuously true, meaning the relation is transitive by default (e.g., the empty relation is transitive).

Equivalence Relation

What it is

An Equivalence Relation is a relation that simultaneously possesses all three key properties: reflexivity, symmetry, and transitivity.

Definition 6 (Equivalence Relation): A relation R on a set A is called an equivalence relation if R is reflexive, symmetric, and transitive.

Why it matters

Equivalence relations are profoundly important in mathematics. They generalize the concept of "equality" by grouping elements that are considered "equivalent" under some criterion. This grouping leads to the formation of equivalence classes, which partition the original set into disjoint subsets. This partitioning is a cornerstone of abstract algebra, allowing the construction of new sets (e.g., integers modulo n, rational numbers from integers).

How it works

To prove a relation R is an equivalence relation, one must demonstrate that it satisfies all three conditions:

  1. Reflexivity: Show that (a, a) ∈ R for all a ∈ A.
  2. Symmetry: Show that if (a, b) ∈ R, then (b, a) ∈ R for all a, b ∈ A.
  3. Transitivity: Show that if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R for all a, b, c ∈ A.

Concrete Example

Let A be the set of all integers, Z. Consider the relation R defined as (a, b) ∈ R if and only if a - b is an even integer. (This is equivalent to a ≡ b (mod 2)).

  1. Reflexivity: For any a ∈ Z, a - a = 0, which is an even integer. So, (a, a) ∈ R. R is reflexive.
  2. Symmetry: If (a, b) ∈ R, then a - b is an even integer. This means a - b = 2k for some integer k. Then b - a = -(a - b) = -2k = 2(-k). Since -k is also an integer, b - a is an even integer. So, (b, a) ∈ R. R is symmetric.
  3. Transitivity: If (a, b) ∈ R and (b, c) ∈ R, then a - b is even and b - c is even. So, a - b = 2k₁ and b - c = 2k₂ for some integers k₁, k₂. Adding these equations: (a - b) + (b - c) = 2k₁ + 2k₂ a - c = 2(k₁ + k₂). Since k₁ + k₂ is an integer, a - c is an even integer. So, (a, c) ∈ R. R is transitive.

Since R is reflexive, symmetric, and transitive, it is an equivalence relation.

Equivalence Classes

When an equivalence relation R is defined on a set A, it naturally partitions A into disjoint subsets called equivalence classes.

The equivalence class of an element a ∈ A, denoted by [a], is the set of all elements in A that are related to a under R. Formally, [a] = {b ∈ A | (a, b) ∈ R}.

Why it matters

Equivalence classes are the direct consequence and a key application of equivalence relations. They provide a way to "factor" a set by a relation, creating a new set whose elements are these classes. This concept is fundamental in constructing quotient sets, which are prevalent in advanced mathematics (e.g., quotient groups, quotient rings, topological spaces).

Example (continued from above)

For the relation (a, b) ∈ R if a - b is an even integer on Z:

  • The equivalence class of 0, [0], would contain all integers b such that 0 - b is even. This means b must be an even integer. So, [0] = {..., -4, -2, 0, 2, 4, ...} (the set of all even integers).
  • The equivalence class of 1, [1], would contain all integers b such that 1 - b is even. This means b must be an odd integer. So, [1] = {..., -3, -1, 1, 3, 5, ...} (the set of all odd integers).

These two equivalence classes, [0] and [1], partition the set of all integers Z into two disjoint subsets: even integers and odd integers. Every integer belongs to exactly one of these classes.

Summary of Relation Properties

The following table summarizes the key properties discussed, providing a quick reference for their definitions and implications.

Property Definition Example (on Integers) Non-Example (on Integers)
Reflexive (a, a) ∈ R for all a ∈ A a = b (equality) a < b (strict inequality)
Symmetric (a, b) ∈ R ⇒ (b, a) ∈ R for all a, b ∈ A a = b, a - b is even, a is a sibling of b a < b, a is a parent of b
Transitive (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R for all a, b, c ∈ A a = b, a ≤ b, a divides b a is a parent of b (grandparent is not parent)
Equivalence Reflexive, Symmetric, and Transitive a = b, a - b is even, a has the same birthday as b a ≤ b (not symmetric), a is a sibling of b (not reflexive)

Variations and Extensions

While the primary focus is on these core properties, relations can exhibit other characteristics, such as:

  • Irreflexive: No element is related to itself ((a, a) ∉ R for all a ∈ A). Example: a < b.
  • Asymmetric: If (a, b) ∈ R, then (b, a) ∉ R. Note that this is stronger than "not symmetric". Example: a < b.
  • Antisymmetric: If (a, b) ∈ R and (b, a) ∈ R, then a = b. Example: a ≤ b. This property is crucial for Partial Order Relations (reflexive, antisymmetric, transitive).

Understanding these variations provides a richer vocabulary for describing complex relationships between mathematical objects and is essential in fields like graph theory and database design.

Connecting Ideas: Relations and Functions

It's important to remember that functions are a special type of relation. A relation f: A → B is a function if every element in A is related to exactly one element in B. The properties discussed here (reflexive, symmetric, transitive) are typically applied to relations on a single set A, rather than general functions from A to B. However, the underlying set-theoretic definitions remain consistent.

Summary of Key Concepts - Relations and Functions Course Wiki - diagram 1
Summary of Key Concepts - Relations and Functions Course Wiki - diagram 1
Summary of Key Concepts - Relations and Functions Course Wiki - diagram 2
Summary of Key Concepts - Relations and Functions Course Wiki - diagram 2

Historical Note

Key concepts: History of Functions · Descartes · Leibnitz · Euler · Dirichlet · Cantor

This section offers a brief historical overview of the evolution of the concept of 'function,' tracing its development through the contributions of prominent mathematicians from Descartes to Cantor.

Historical Note

The concept of a function is fundamental to nearly every branch of modern mathematics, serving as a cornerstone for calculus, analysis, algebra, and computer science. Its evolution, however, was not linear but rather a fascinating journey spanning centuries, reflecting humanity's increasing need to describe relationships between varying quantities with greater precision and abstraction. This historical note traces the development of the function concept, highlighting the pivotal contributions of key mathematicians who shaped our understanding from implicit geometric notions to the rigorous set-theoretic definition we use today.

Overview of the Evolution of Functions

The journey of the function concept can be broadly categorized into several phases, each marked by a shift in perspective and an increase in generality:

  • Early Implicit Notions (17th Century): Functions were initially understood as relationships described by geometric curves or algebraic equations, without a formal, explicit definition.
  • Formalization and Analytical Expressions (Late 17th - Early 18th Century): Mathematicians began to define functions more explicitly as quantities derived from variables and constants, often tied to analytical formulas.
  • Generalization to Arbitrary Rules (Mid-18th - Early 19th Century): The scope expanded to include functions defined by any rule, even those without a single, continuous analytical expression.
  • Set-Theoretic Abstraction (Late 19th - Early 20th Century): The modern, rigorous definition emerged, viewing functions as special types of relations between sets, independent of formulas or graphs.

This evolution reflects a progressive move from concrete, visual representations to abstract, formal definitions, driven by the demands of new mathematical problems and the pursuit of logical rigor.

Early Implicit Notions: Descartes and Gregory

The seeds of the function concept were sown in the 17th century with the advent of analytical geometry. Before this, algebra and geometry were largely separate disciplines. René Descartes (1596–1650), in his seminal work La Géométrie (1637), revolutionized mathematics by demonstrating how geometric curves could be represented by algebraic equations. This established a profound connection: an equation like y = x² describes a parabola, where for every value of x, there is a corresponding value of y. While Descartes did not explicitly define "function," his work provided the crucial framework where variables were seen as dependent on others, paving the way for the idea of a functional relationship.

James Gregory (1638–1675), a Scottish mathematician, is sometimes credited with one of the earliest explicit (though informal) uses of the term "function" in the context of infinite series. He referred to a quantity "depending on another quantity" in his work on calculus. This early usage, though not a formal definition, underscored the growing recognition of dependent variables.

Why it matters: This period was crucial because it provided the visual and algebraic tools to think about how one quantity determines another. The ability to express curves as equations allowed for the study of their properties using algebraic methods, laying the groundwork for the development of calculus, where understanding rates of change and accumulation inherently relies on functional relationships.

Formalization and Analytical Expressions: Leibnitz and Bernoulli

The late 17th and early 18th centuries saw the first attempts to formally define "function." Gottfried Wilhelm Leibnitz (1646–1716), one of the co-inventors of calculus, introduced the term "function" in 1673. He initially used it to refer to geometric quantities associated with curves, such as tangents, normals, and chords. By 1694, he refined his usage to describe any quantity that "varies from point to point" along a curve.

Johann Bernoulli (1667–1748), a prominent Swiss mathematician, provided a more explicit and analytical definition in 1718. He defined a function as:

"a quantity composed in any manner whatever of a variable quantity and constants."

This definition marked a significant step forward, moving away from purely geometric interpretations towards an algebraic understanding. It emphasized that functions could be constructed using basic arithmetic operations and constants.

Comparison of Early Definitions:

Feature Descartes (Implicit) Leibnitz (Early Explicit) Bernoulli (Formal Analytical)
Primary Context Geometric curves/equations Geometric properties of curves Algebraic expressions
Core Idea Dependence of y on x Quantity varying along a curve Quantity formed from variable x and constants
Formal Definition None (implied by equations) Informal, evolving Explicit, analytical
Notation y = x² (equation) No specific function notation No specific function notation

Why it matters: These definitions were crucial for the development of calculus. By defining functions as analytical expressions, mathematicians could apply the new tools of differentiation and integration to a broad class of problems, leading to rapid advancements in physics and engineering.

Euler's Transformative Contributions

Leonhard Euler (1707–1783), arguably the most prolific mathematician in history, played a pivotal role in solidifying and generalizing the function concept. In his Introductio in analysin infinitorum (1748), Euler initially adopted a definition similar to Bernoulli's:

"A function of a variable quantity is an analytical expression composed in any way from that variable quantity and numbers or constant quantities."

This definition emphasized functions as expressions like x² + 3x + 5 or sin(x). Crucially, Euler introduced the now-standard notation f(x) to denote a function, making it easier to discuss and manipulate functions abstractly.

However, Euler later broadened his definition in response to problems involving vibrating strings (the D'Alembert-Euler controversy). He realized that a function didn't necessarily need to be described by a single, continuous analytical formula. He proposed a more general definition:

"If, however, some quantities depend on others in such a way that if the latter are changed the former undergo change, then the former quantities are called functions of the latter."

This was a radical departure, allowing for functions defined piecewise or even empirically, as long as there was a definite rule of correspondence.

How it works: Euler's shift allowed for functions like: f(x) = x² for x ≥ 0 f(x) = -x for x < 0 Such functions, while not described by a single analytical expression over their entire domain, still assign a unique output for every input.

Why it matters: Euler's work was transformative. His notation f(x) became universal, simplifying the language of mathematics. More importantly, his generalized definition liberated the concept of a function from the strict confines of analytical formulas, opening the door for functions that could be discontinuous, piecewise, or even defined by tables of values. This broader understanding was essential for the development of Fourier series and the study of more complex physical phenomena.

Generalization to Arbitrary Correspondences: Lagrange and Dirichlet

Following Euler, Joseph-Louis Lagrange (1736–1813) initially tried to base all analysis on power series, effectively returning to a more analytical expression-centric view of functions. However, the need for a more general definition persisted, particularly with the rise of Fourier analysis.

It was Peter Gustav Lejeune Dirichlet (1805–1859) who, in 1837, provided what is often considered the first truly modern and rigorous definition of a function, moving beyond the requirement of an analytical expression entirely. Dirichlet defined a function as:

"If a variable y is so related to a variable x that whenever a numerical value is assigned to x, there is a rule according to which a unique value of y is determined, then y is said to be a function of x."

This definition emphasizes the rule of correspondence and the uniqueness of the output for each input, regardless of whether that rule is an algebraic formula, a geometric construction, or a simple table. It explicitly allows for functions like the Dirichlet function: D(x) = 1 if x is a rational number D(x) = 0 if x is an irrational number

This function cannot be described by any simple analytical expression but perfectly fits Dirichlet's definition.

Why it matters: Dirichlet's definition was a landmark. It completely detached the concept of a function from its historical ties to "formulas" or "curves," paving the way for functions defined over abstract sets and for the rigorous study of continuity, differentiability, and integrability. It was crucial for understanding functions that arise in fields like signal processing and probability.

Set Theory and the Modern Definition: Cantor

The final major step in the evolution of the function concept came with the development of set theory in the late 19th century, primarily by Georg Cantor (1845–1918). Set theory provided the language and framework for defining mathematical objects with unprecedented rigor and abstraction. Within this framework, a function is understood as a special type of relation.

As reviewed in foundational mathematics (e.g., Lemh101), a relation R from a set A to a set B is any subset of the Cartesian product A × B. Each element of this subset is an ordered pair (a, b) where a ∈ A and b ∈ B.

The modern set-theoretic definition of a function formalizes Dirichlet's idea of a unique correspondence:

A function f from a set A (the domain) to a set B (the codomain), denoted f: A → B, is a relation f ⊆ A × B such that for every element a ∈ A, there exists exactly one element b ∈ B for which (a, b) ∈ f. The element b is called the image of a under f, written f(a) = b. The set of all images f(a) for a ∈ A is called the range of f.

This definition is entirely abstract, independent of any specific formula, graph, or rule. It simply requires a unique mapping for every element in the domain.

How it works: Consider sets A = {1, 2, 3} and B = {a, b, c, d}. A function f: A → B could be defined as the set of ordered pairs f = {(1, a), (2, c), (3, b)}. Here, each element in A (1, 2, 3) is paired with exactly one element in B. The domain is A, the codomain is B, and the range is {a, b, c}.

Why it matters: This set-theoretic definition provides the ultimate level of rigor and generality. It allows mathematicians to define functions between any types of sets (numbers, vectors, other functions, abstract objects), forming the bedrock for advanced topics like functional analysis, abstract algebra, and category theory. It is the definition universally accepted in contemporary mathematics, underpinning concepts like one-one (injective) and onto (surjective) functions, and the existence of inverse functions (as discussed in Lemh102).

Summary of the Evolution of the Function Concept

The journey from Descartes' geometric curves to Cantor's abstract set-theoretic mappings illustrates a profound intellectual progression. Each stage built upon the last, expanding the scope and rigor of what a "function" could represent.

Key Milestones in the Definition of a Function:

Era / Mathematician Primary Definition / Concept Key Contribution Limitations Overcome
Descartes (17th C.) Implicit in equations of geometric curves (y = f(x)) Linked algebra and geometry; y depends on x No explicit definition; tied to geometry
Leibnitz (Late 17th C.) Quantity varying from point to point on a curve Coined "function"; more analytical focus Still somewhat geometric; informal
Bernoulli (Early 18th C.) Quantity composed of variable and constants First analytical definition; algebraic expressions Restricted to single analytical formulas
Euler (Mid-18th C.) Initially analytical expression; later, any rule of correspondence Standardized f(x) notation; generalized to arbitrary rules Freed from single formula; allowed piecewise functions
Dirichlet (Early 19th C.) A rule determining a unique y for each x Fully abstract rule of correspondence; uniqueness Decoupled from analytical formulas/continuity
Cantor (Late 19th C.) A special type of relation between two sets Rigorous set-theoretic definition; universal Provided ultimate abstraction and logical foundation

This historical progression highlights how mathematical concepts evolve to meet new challenges and achieve greater clarity and universality, ultimately leading to the robust and versatile tool that the function is in modern mathematics.

Historical Note - Relations and Functions Course Wiki - image 1
Historical Note - Relations and Functions Course Wiki - image 1
Historical Note - Relations and Functions Course Wiki - diagram 1
Historical Note - Relations and Functions Course Wiki - diagram 1
Historical Note - Relations and Functions Course Wiki - diagram 2
Historical Note - Relations and Functions Course Wiki - diagram 2
Historical Note - Relations and Functions Course Wiki - diagram 3
Historical Note - Relations and Functions Course Wiki - diagram 3

Source Materials

Study Relations and Functions Course Wiki with AI — Free on Lykke

Sign up for free to generate personalized flashcards, quizzes, and study guides from this course. Chat with an AI tutor that knows the material.

Get Started Free

View this course wiki on Lykke · Browse all public course wikis