Week_1_Sets_Relations_Functions

Week 1: Sets, Relations, and Functions

1. Sets

1.1 Definition & Representation

A set is a well-defined collection of distinct objects.

• Roster Form: Listing elements, e.g., $A=\{1,2,3\}$.
• Set-Builder Form: Describing properties, e.g., $A=\{x\in \mathbb{N}\mid x\le 3\}$.

1.2 Important Types of Sets

• Null/Empty Set ($\varnothing$ or $\{\}$): Contains no elements. $|\varnothing |=0$.
• Singleton Set: Contains exactly one element.
• Finite vs. Infinite Set: Based on the number of elements.
• Universal Set ($U$): The “parent” set containing all objects under discussion.
• Subset: $A\subseteq B$ if every element of $A$ is in $B$.
  • Pro-Tip: $\varnothing$ is a subset of every set. Every set is a subset of itself.
• Power Set ($\mathcal{P}(A)$): The set of all subsets of $A$. If $|A|=n$, then $|\mathcal{P}(A)|=2^n$.

1.3 Operations on Sets

• Union ($A\cup B$): Elements in $A$ OR $B$.
• Intersection ($A\cap B$): Elements in BOTH $A$ AND $B$.
• Difference ($A\setminus B$ or $A-B$): Elements different in $A$ but NOT in $B$.
• Symmetric Difference ($A\Delta B$): Elements in $A$ or $B$ but NOT both. $A\Delta B=(A\setminus B)\cup (B\setminus A)$.
• Complement ($A^{\prime }$ or $A^c$): Elements in $U$ but NOT in $A$.

1.4 Cardinality Rules (Inclusion-Exclusion)

• $|A\cup B|=|A|+|B|-|A\cap B|$
• $|A\cup B\cup C|=|A|+|B|+|C|-(|A\cap B|+|A\cap C|+|B\cap C|)+|A\cap B\cap C|$

---

2. Number Systems Classification

Understanding domains ($\mathbb{Z},\mathbb{R}$, etc.) is critical for functions.

• $\mathbb{N}$: Natural Numbers $\{1,2,3,\dots \}$
• $\mathbb{W}$: Whole Numbers $\{0,1,2,\dots \}$
• $\mathbb{Z}$: Integers $\{\dots ,-2,-1,0,1,2,\dots \}$
• $\mathbb{Q}$: Rational Numbers $\{\frac{p}{q}\mid p,q\in \mathbb{Z},q\ne 0\}$. (Terminating or Repeating decimals).
• ${\mathbb{Q}}^c$ or $\mathbb{I}$: Irrational Numbers (Non-terminating, Non-repeating). E.g., $\sqrt{2},\pi ,e$.
• $\mathbb{R}$: Real Numbers ($\mathbb{Q}\cup {\mathbb{Q}}^c$).

Tacit Knowledge:

Be very careful when a function domain is defined as $\mathbb{Z}$ or $\mathbb{N}$. A function like $f(x)=x/2$ might define a bijection on $\mathbb{R}\to \mathbb{R}$ but NOT on $\mathbb{Z}\to \mathbb{Z}$ (because $1/2\notin \mathbb{Z}$).

---

3. Relations

3.1 Cartesian Product

$A\times B=\{(a,b)\mid a\in A,b\in B\}$.

• Cardinality: $|A\times B|=|A|\cdot |B|$.

3.2 Definition of Relation

A relation $R$ from $A$ to $B$ is a subset of $A\times B$.

• Total number of relations from $A$ to $B$: $2^{|A|\cdot |B|}$.

3.3 Types of Relations (on a set $A$)

A relation $R\subseteq A\times A$:

1. Reflexive: $\forall a\in A,(a,a)\in R$. (Every element is related to itself).
2. Symmetric: If $(a,b)\in R$, then $(b,a)\in R$.
3. Transitive: If $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)\in R$.

Equivalence Relation: A relation that is Reflexive AND Symmetric AND Transitive.

Equivalence relations partition the set into disjoint Equivalence Classes.

---

4. Functions

4.1 Definition

A function $f:A\to B$ relates every element $x\in A$ to exactly one element $y\in B$.

• Domain: Set $A$.
• Codomain: Set $B$.
• Range: Set of actual outputs $\{f(x)\mid x\in A\}$. (Range $\subseteq$ Codomain).

4.2 Types of Functions

1. One-to-One (Injective): Unique inputs give unique outputs.
   • $f(x_1)=f(x_2)⟹x_1=x_2$.
   • Horizontal Line Test: No horizontal line cuts the graph more than once.
2. Onto (Surjective): Every element in Codomain is covered.
   • Range = Codomain.
   • $\forall y\in B,\exists x\in A$ such that $f(x)=y$.
3. Bijective: Both One-to-One AND Onto.
   • Only bijective functions are Invertible ($f^{-1}$ exists).

4.3 Composition

• $(f\circ g)(x)=f(g(x))$.
• Domain of $f\circ g$ is the set of all $x$ in domain of $g$ such that $g(x)$ is in domain of $f$.

---

5. Tacit Knowledge & Goated Examples

Example 1: Domain Traps

Question: Let $f:\mathbb{Z}\to \mathbb{Z}$ be $f(n)=2n$. Is it bijective? Analysis:

• One-to-One? Yes. $2n=2m⟹n=m$.
• Onto? No. The range is only even integers. Odd integers in the codomain $\mathbb{Z}$ have no pre-image. Verdict: Not Bijective. Contrast: If $f:\mathbb{R}\to \mathbb{R}$ defined by $f(x)=2x$, it is bijective.

Example 2: Counting Relations

Question: Set $A=\{1,2,3\}$. Total relations? Reflexive relations? Solution:

• $|A\times A|=3\times 3=9$.
• Total Relations = $2^9=512$.
• Reflexive: Must contain $(1,1),(2,2),(3,3)$. The other $9-3=6$ pairs can be present or absent.
  • Formula: $2^{n^2-n}$.
  • Calculation: $2^{9-3}=2^6=64$.