Maths-1-Sets-Relations-Functions

Maths 1: Sets, Relations, and Functions

This guide provides a comprehensive overview of Sets, Relations, and Functions, tailored to the IIT Madras Qualifier exam pattern.

1. Core Concepts

1.1. Sets

A set is a well-defined collection of distinct objects. The objects in a set are called its elements.

A subset (written as A ⊆ B) is a set where all the elements of set A are also elements of set B.

1. Natural Numbers (ℕ): {1, 2, 3, 4, …} - The counting numbers.
2. Whole Numbers (W): {0, 1, 2, 3, …} - Natural numbers plus zero.
3. Integers (ℤ): {…, -3, -2, -1, 0, 1, 2, 3, …} - Whole numbers and their opposites.
4. Rational Numbers (ℚ): Numbers that can be expressed as a fraction p/q of two integers, where q ≠ 0. (e.g., 1/2, -3/4, 7).
5. Irrational Numbers: Numbers that cannot be expressed as a simple fraction (e.g., π, √2).
6. Real Numbers (ℝ): All rational and irrational numbers

• Notation: Sets are usually denoted by capital letters, and their elements are enclosed in curly braces {}.
• Example: $$\begin{gathered} A= \\ 1,2,3,4 \end{gathered}$$ is a set of the first four natural numbers.
• Cardinality: The number of elements in a set is called its cardinality, denoted by $|A|$. For the set $A$ above, $|A|=4$.
• Subset: A set $A$ is a subset of a set $B$ (denoted $A\subseteq B$) if every element of $A$ is also in $B$.
• Power Set: The set of all subsets of a set $A$ is called the power set of $A$, denoted by $P(A)$. If $|A|=n$, then $|P(A)|=2^n$.
• Set Operations:
  • Union ($A\cup B$): The set of all elements that are in $A$, or in $B$, or in both.
  • Intersection ($A\cap B$): The set of all elements that are in both $A$ and $B$.
  • Difference ($A\setminus B$): The set of all elements that are in $A$ but not in $B$.
  • Complement ($A^{\prime }$ or $A^c$): The set of all elements in the universal set $U$ that are not in $A$.

1.2. Relations

A relation $R$ from a set $A$ to a set $B$ is a subset of the Cartesian product $A\times B$. If $A=B$, we say $R$ is a relation on $A$.

• Properties of Relations on a Set A:
  • Reflexive: A relation $R$ is reflexive if for every element $a\in A$, $(a,a)\in R$.
  • Symmetric: A relation $R$ is symmetric if for every $(a,b)\in R$, we also have $(b,a)\in R$.
  • Transitive: A relation $R$ is transitive if for every $(a,b)\in R$ and $(b,c)\in R$, we also have $(a,c)\in R$.
  • Equivalence Relation: A relation that is reflexive, symmetric, and transitive is called an equivalence relation.

1.3. Functions

A function $f$ from a set $A$ to a set $B$ (denoted $f:A\to B$) is a special type of relation where every element in $A$ is associated with exactly one element in $B$.

• Domain: The set $A$ is the domain of the function.

• Codomain: The set $B$ is the codomain of the function.

• Range: The set of all images of the elements of $A$ under $f$. The range is a subset of the codomain.

• Types of Functions:

  • Injective (One-to-One): A function is injective if no two elements in the domain map to the same element in the codomain.
  • Surjective (Onto): A function is surjective if every element in the codomain is an image of at least one element in the domain. (i.e., range = codomain).
  • Bijective: A function is bijective if it is both injective and surjective.

2. Problem Patterns and Solved Examples

Pattern 1: Identifying Properties of Relations

Analysis: These questions provide a relation defined on a set and ask you to identify if it’s reflexive, symmetric, transitive, or an equivalence relation.

Solved Example (from PYQ):

Consider the relation $$\begin{gathered} R_2= \\ (x,y):x,y\in \mathbb{Z}\text{ and }5\text{ divides }x-y \end{gathered}$$. Is this an equivalence relation?

Solution:

1. Reflexive: For any integer $x$, $x-x=0$. Since 5 divides 0, $(x,x)\in R_2$. So, $R_2$ is reflexive.
2. Symmetric: If $(x,y)\in R_2$, then $x-y$ is divisible by 5. This means $x-y=5k$ for some integer $k$. Then, $y-x=-5k=5(-k)$, which is also divisible by 5. So, $(y,x)\in R_2$. Thus, $R_2$ is symmetric.
3. Transitive: If $(x,y)\in R_2$ and $(y,z)\in R_2$, then $x-y=5k_1$ and $y-z=5k_2$ for some integers $k_1,k_2$. Adding these two equations, we get $(x-y)+(y-z)=5k_1+5k_2$, which simplifies to $x-z=5(k_1+k_2)$. This means $x-z$ is divisible by 5, so $(x,z)\in R_2$. Thus, $R_2$ is transitive.

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

Pattern 2: Cardinality of Sets from Word Problems

Analysis: These questions involve Venn diagrams and the principle of inclusion-exclusion. You are given information about overlapping sets and asked to find the cardinality of a specific region.

Solved Example (from PYQ):

In a survey of 500 people, 49% liked comedy, 53% liked thriller, and 62% liked romantic. 27% liked comedy and thriller, 29% liked thriller and romantic, and 28% liked comedy and romantic. 5% liked none. How many people like all three?

Solution:

Let C, T, and R be the sets of people who like comedy, thriller, and romantic movies, respectively.

• $|U|=500$
• $|C|=0.49\times 500=245$
• $|T|=0.53\times 500=265$
• $|R|=0.62\times 500=310$
• $|C\cap T|=0.27\times 500=135$
• $|T\cap R|=0.29\times 500=145$
• $|C\cap R|=0.28\times 500=140$
• People who liked at least one movie = $500-(0.05\times 500)=475$. So, $|C\cup T\cup R|=475$.

Using the Principle of Inclusion-Exclusion: $|C\cup T\cup R|=|C|+|T|+|R|-(|C\cap T|+|T\cap R|+|C\cap R|)+|C\cap T\cap R|$ $475=245+265+310-(135+145+140)+|C\cap T\cap R|$ $475=820-420+|C\cap T\cap R|$ $475=400+|C\cap T\cap R|$ $|C\cap T\cap R|=75$

Answer: 75 people like all three genres.

Pattern 3: Determining Function Properties

Analysis: You’ll be given a function and its domain/codomain, and you need to determine if it’s one-to-one, onto, or both.

Solved Example (from Assignments):

Define a function $f:\mathbb{Q}\to \mathbb{Z}$, such that $f(p/q)=p-q$, where $gcd(p,q)=1$. Is this function one-to-one, onto, or bijective?

Solution:

1. One-to-One (Injective)? Let’s take two different rational numbers and see if they map to the same integer. Consider $f(3/2)=3-2=1$. Consider $f(4/3)=4-3=1$. Since two different inputs (3/2 and 4/3) produce the same output (1), the function is not one-to-one.

2. Onto (Surjective)? Can we generate any integer $k\in \mathbb{Z}$? Let $k$ be any integer. We need to find a rational number $p/q$ (with $gcd(p,q)=1$) such that $p-q=k$. We can choose $p=k+1$ and $q=1$. Then $p/q=(k+1)/1$ is a rational number. $gcd(k+1,1)=1$ is always true. $f((k+1)/1)=(k+1)-1=k$. Since we can find a rational number that maps to any integer $k$, the function is onto.

Conclusion: The function is onto but not one-to-one.

3. Practice Problems

1. Relation Properties: Let $$\begin{gathered} S= \\ 1,2,3 \end{gathered}$$. A relation $R$ on $S$ is defined as $$\begin{gathered} R= \\ (1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2) \end{gathered}$$. Determine if $R$ is reflexive, symmetric, and/or transitive.

2. Set Cardinality: A class has 100 students. 60 students passed in Physics, 50 passed in Chemistry, and 30 passed in both. Find the number of students who passed in exactly one of the two subjects.

3. Function Properties: Let $f:\mathbb{R}\to \mathbb{R}$ be defined by $f(x)=x^2+1$. Is this function injective, surjective, or bijective?

4. Solutions to Practice Problems

1. Solution:

   • Reflexive: Yes, because $(1,1),(2,2),(3,3)$ are all in $R$.
   • Symmetric: Yes. For $(1,2)$, we have $(2,1)$. For $(2,3)$, we have $(3,2)$.
   • Transitive: No. We have $(1,2)\in R$ and $(2,3)\in R$, but $(1,3)\notin R$.

2. Solution: Let P be the set of students who passed in Physics and C be the set of students who passed in Chemistry.

   • $|P|=60$
   • $|C|=50$
   • $|P\cap C|=30$ Number of students who passed only in Physics = $|P|-|P\cap C|=60-30=30$. Number of students who passed only in Chemistry = $|C|-|P\cap C|=50-30=20$. Total students who passed in exactly one subject = $30+20=50$.

3. Solution:

   • Injective: No. For example, $f(1)=1^2+1=2$ and $f(-1)=(-1{)}^2+1=2$. Different inputs give the same output.
   • Surjective: No. The range of $f(x)=x^2+1$ is $[1,\infty )$, because $x^2$ is always non-negative. Therefore, there is no $x\in \mathbb{R}$ such that $f(x)=0$ (or any other number less than 1). The range is not equal to the codomain $\mathbb{R}$.
   • Bijective: No, because it is neither injective nor surjective.