Sets, Relations, and Functions in Discrete Mathematics

Sets, relations, and functions are foundational concepts in discrete mathematics and computer science. They form the building blocks for various advanced topics such as logic, combinatorics, graph theory, and algorithms. Understanding these concepts is essential for modeling and solving problems in computer science.

In this lecture, we will explore these concepts in detail, progressing from basic definitions to more advanced properties and applications:

1. Sets
2. Cartesian Products
3. Relations
4. Functions

We will also frequently refer to the following hierarchy:

• Sets help model collections of things.
• Pairs of sets form Cartesian Products.
• Subsets of Cartesian Products form Relations.
• Relations with exactly one output for each input are Functions.
• Functions can have properties like injectivity, surjectivity, and bijectivity.

A set is a collection of distinct objects, called elements or members of the set. Sets are a fundamental way to represent and organize objects in mathematics and computer science.

• Notation: Sets are usually denoted by uppercase letters, e.g., $A$, $B$, $S$.
• Elements: Elements of sets are denoted by lowercase letters, e.g., $a$, $b$, $x$.

An element $x$ is a member of a set $A$ if $x$ belongs to $A$, written as $x \in A$.

Two important points about sets:

1. Order does not matter: The set ${1, 2, 3}$ is the same as ${3, 2, 1}$.
2. No repetition of elements: The set ${1, 2, 2, 3}$ is the same as ${1, 2, 3}$.

Common Confusion:

• Remember that sets are different from lists or sequences. In sets, the order and repetition of elements are not considered.

• Natural Numbers Less Than 5: ${0, 1, 2, 3, 4}$
• Vowels in the English Alphabet: ${\text{a}, \text{e}, \text{i}, \text{o}, \text{u}}$
• Programming Languages: ${\text{Python}, \text{Java}, \text{C++}}$
• Nested Set: ${1, {2, 3}}$ (This set has two elements: the number 1 and the set ${2, 3}$.)

Note: The set ${1, {2, 3}}$ has two elements, one of which is itself a set.

The empty set is the set containing no elements. It is denoted by $\emptyset$ or ${}$.

Common Confusion:

• The empty set $\emptyset$ is different from the set containing the number zero ${0}$.
  • $\emptyset$ has no elements.
  • ${0}$ has one element, the number zero.
• Also, $\emptyset \ne 0$ and $\emptyset \ne {\emptyset}$.

Certain sets are used so frequently that they have special symbols:

• Natural Numbers ($\mathbb{N}$): The set of non-negative integers.
  • $\mathbb{N} = {0, 1, 2, 3, \dots}$
  • Note: In this class, $\mathbb{N}$ includes zero. In other contexts, it might exclude zero.
• Integers ($\mathbb{Z}$): The set of whole numbers, both positive and negative, including zero.
  • $\mathbb{Z} = {\dots, -2, -1, 0, 1, 2, \dots}$
• Rational Numbers ($\mathbb{Q}$): Numbers that can be expressed as fractions of integers.
  • $\mathbb{Q} = \left{\frac{p}{q} \mid p, q \in \mathbb{Z}, q \neq 0\right}$
• Real Numbers ($\mathbb{R}$): All numbers on the number line, including irrational numbers like $\sqrt{2}$, $\pi$, $e$.

Superscripts for Positivity/Negativity:

• $\mathbb{N}^+$ or $\mathbb{N}_{>0}$: Positive natural numbers (excluding zero).
• $\mathbb{Z}^+$ or $\mathbb{Z}_{\geq 0}$: Non-negative integers (including zero).

Common Confusion:

• Be aware that the inclusion of zero in $\mathbb{N}$ varies by context.
• In this class, we include zero in $\mathbb{N}$: $\mathbb{N} = {0, 1, 2, 3, \dots}$.

• Definition: Lists all elements explicitly within curly braces.
• Example: $A = {1, 2, 3}$.

• Definition: Specifies a set by stating a property that its members must satisfy.
• General Form: $S = {x \in D \mid \text{condition involving } x}$, where $D$ is a domain.
• Examples:
  1. $A = {x \in \mathbb{N} \mid x \text{ is even and } x \leq 10} = {0, 2, 4, 6, 8, 10}$.
  2. ${x \in \mathbb{Z} \mid -2 < x < 5} = {-1, 0, 1, 2, 3, 4}$.

Common Confusion:

• Be careful with inequalities:
  • $-2 < x < 5$ means $x$ is greater than $-2$ and less than $5$, so $-2$ and $5$ are not included.
• The notation ${2, 4, \dots, 10}$ is roster notation, not set-builder notation.

A set $A$ is a subset of a set $B$ if every element of $A$ is also an element of $B$, denoted as $A \subseteq B$.

• If $A \subseteq B$ and $A \neq B$, then $A$ is a proper subset of $B$, denoted as $A \subset B$.

Examples:

• ${1, 2} \subseteq {1, 2, 3}$.
• ${1, 2, 3} \subseteq {1, 2, 3}$ (Every set is a subset of itself).

Common Confusion:

• Element vs. Subset:
  • $1 \in {1, 2, 3}$: $1$ is an element of the set.
  • ${1} \subseteq {1, 2, 3}$: ${1}$ is a subset of the set.
• The empty set $\emptyset$ is a subset of every set: $\emptyset \subseteq A$.

Venn diagrams are visual representations of sets and their relationships.

• Universal Set ($U$): The set containing all possible elements under consideration.
• Complement of a Set ($A’$ or $\overline{A}$): The set of elements in $U$ that are not in $A$.

Examples:

• Union: $A \cup B$ is represented by the area covered by both circles $A$ and $B$.
• Intersection: $A \cap B$ is represented by the overlapping area of circles $A$ and $B$.
• Difference: $A - B$ is represented by the part of circle $A$ that does not overlap with $B$.

Common Confusion:

• The empty set is a subset of every set but is not necessarily an element of every set.
• In a Venn diagram, the empty set is represented by the absence of elements.

• Definition: The set of all elements that are in $A$, or in $B$, or in both.
• Notation: $A \cup B = {x \mid x \in A \text{ or } x \in B}$.

• Definition: The set of all elements that are in both $A$ and $B$.
• Notation: $A \cap B = {x \mid x \in A \text{ and } x \in B}$.

• Definition: The set of all elements that are in $A$ but not in $B$.
• Notation: $A - B = {x \mid x \in A \text{ and } x \notin B}$.

• Definition: The set of all elements in the universal set $U$ that are not in $A$.
• Notation: $\overline{A} = {x \in U \mid x \notin A}$.

Let $A = {1, 2, 3}$, $B = {3, 4, 5}$, and $U = {1, 2, 3, 4, 5, 6}$.

• Union: $A \cup B = {1, 2, 3, 4, 5}$.
• Intersection: $A \cap B = {3}$.
• Difference:
  • $A - B = {1, 2}$.
  • $B - A = {4, 5}$.
• Complement:
  • $\overline{A} = U - A = {4, 5, 6}$.
  • $\overline{B} = U - B = {1, 2, 6}$.

Common Confusion:

• Be careful with set difference; $A - B$ is not the same as $B - A$.

• Union: $A \cup B = B \cup A$.
• Intersection: $A \cap B = B \cap A$.

• Union: $A \cup (B \cup C) = (A \cup B) \cup C$.
• Intersection: $A \cap (B \cap C) = (A \cap B) \cap C$.

• Union over Intersection:
  • $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.
• Intersection over Union:
  • $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.

• Union with Empty Set: $A \cup \emptyset = A$.
• Intersection with Universal Set: $A \cap U = A$.

• Union with Universal Set: $A \cup U = U$.
• Intersection with Empty Set: $A \cap \emptyset = \emptyset$.

• Complement of Union:
  • $\overline{A \cup B} = \overline{A} \cap \overline{B}$.
• Complement of Intersection:
  • $\overline{A \cap B} = \overline{A} \cup \overline{B}$.

Given $A = {1, 2, 3}$, $B = {3, 4}$, and $U = {1, 2, 3, 4, 5}$.

• Find $\overline{A \cup B}$.
  • $A \cup B = {1, 2, 3, 4}$.
  • $\overline{A \cup B} = U - (A \cup B) = {5}$.
• Find $\overline{A} \cap \overline{B}$.
  • $\overline{A} = U - A = {4, 5}$.
  • $\overline{B} = U - B = {1, 2, 5}$.
  • $\overline{A} \cap \overline{B} = {5}$.
• Conclusion: $\overline{A \cup B} = \overline{A} \cap \overline{B}$.

• Definition: The number of elements in a set $A$, denoted $|A|$.
• Examples:
  • $|A| = 3$ if $A = {1, 2, 3}$.
  • $|\emptyset| = 0$.

• Definition: The set of all subsets of $A$, including $A$ and $\emptyset$, denoted $\mathcal{P}(A)$.
• Formula: If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$.

Let $A = {a, b}$.

• Subsets: $\emptyset$, ${a}$, ${b}$, ${a, b}$.
• Power Set: $\mathcal{P}(A) = {\emptyset, {a}, {b}, {a, b}}$.
• Cardinality: $|\mathcal{P}(A)| = 4$.

Common Confusion:

• The cardinality of a set of sets depends on the number of elements at the top level, not on the number of elements within the nested sets.
• For example, if $S = { {1}, {1, 2} }$, then $|S| = 2$, not 3.

A Cartesian product of two sets $A$ and $B$, denoted $A \times B$, is the set of all ordered pairs where the first element is from $A$ and the second is from $B$.

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

Let $A = {1, 2}$ and $B = {x, y}$.

• Cartesian Product:
  • $A \times B = { (1, x), (1, y), (2, x), (2, y) }$.
• Visualization: Each element of $A$ paired with each element of $B$.

Let $A = {\text{red}, \text{blue}}$ and $B = {\text{circle}, \text{square}}$.

• Cartesian Product:
  • $A \times B = { (\text{red}, \text{circle}), (\text{red}, \text{square}), (\text{blue}, \text{circle}), (\text{blue}, \text{square}) }$.
• Interpretation: Possible combinations of colors and shapes.

Common Confusion:

• The ordered pairs are significant; $(a, b)$ is different from $(b, a)$ unless $A = B$ and $a = b$.

A relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A \times B$.

• That is, $R \subseteq A \times B$.
• If $(a, b) \in R$, we say that $a$ is related to $b$ via $R$.

Let $A = {1, 2, 3}$, $B = {4, 5, 6}$, and define $R = {(a, b) \in A \times B \mid b = a + 3}$.

• Relation: $R = { (1, 4), (2, 5), (3, 6) }$.
• Interpretation: Each element in $A$ is paired with a corresponding element in $B$.

Let $A = {\text{Alice}, \text{Bob}}$, $B = {\text{CS101}, \text{Math202}}$, and define $R$:

• $R = { (\text{Alice}, \text{CS101}), (\text{Bob}, \text{Math202}), (\text{Bob}, \text{CS101}) }$.
• Interpretation: Represents the enrollment of students in courses.

Let $A = \mathbb{N}$, and define the relation $R = { (a, b) \in \mathbb{N} \times \mathbb{N} \mid a \text{ divides } b }$.

• Relation: Pairs where $a$ is a divisor of $b$.
• Example Pairs: $(1, n)$ for all $n \in \mathbb{N}$, $(2, 4)$, $(3, 9)$.

Let $A$ be the set of IP addresses, and $B$ be the set of domain names. Define $R$ such that $(\text{IP}, \text{Domain}) \in R$ if the domain name resolves to the IP address.

• Relation: Associates IP addresses with domain names.
• Example Pairs: $(\text{192.168.1.1}, \text{example.com})$.

Common Confusion:

• Remember that relations are subsets of the Cartesian product. Not all possible pairs need to be included.
• The total number of possible relations from $A$ to $B$ is $2^{|A| \times |B|}$, since each pair may or may not be included.

Relations can be represented in multiple ways:

1. Set of Ordered Pairs: Listing all pairs in the relation.
2. Table or Matrix: Rows represent elements of $A$, columns represent elements of $B$, and entries indicate whether $(a, b) \in R$.
3. Directed Graph: Nodes represent elements, and edges represent the relation.

When the relation is on a set $A$ (i.e., $R \subseteq A \times A$), we can discuss properties like reflexivity, symmetry, and transitivity.

• Definition: A relation $R$ on $A$ is reflexive if every element is related to itself.
• Formal: $\forall a \in A, (a, a) \in R$.

• Definition: $R$ is symmetric if whenever $(a, b) \in R$, then $(b, a) \in R$.
• Interpretation: If $a$ is related to $b$, then $b$ is related to $a$.

• Definition: $R$ is transitive if whenever $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$.

• Definition: $R$ is anti-symmetric if whenever $(a, b) \in R$ and $(b, a) \in R$, then $a = b$.
• Interpretation: No two different elements are related in both directions.

• Definition: A relation that is reflexive, symmetric, and transitive.
• Result: Partitions the set into equivalence classes.

Let $A = {1, 2, 3}$, and define $R = { (1, 1), (2, 2), (3, 3), (1, 2), (2, 1) }$.

• Is $R$ reflexive?
  • Yes, since $(a, a) \in R$ for all $a \in A$.
• Is $R$ symmetric?
  • Yes, since whenever $(a, b) \in R$, $(b, a) \in R$.
• Is $R$ transitive?
  • Let’s check: $(1, 2) \in R$ and $(2, 1) \in R$, and $(1, 1) \in R$.
  • All required pairs are present; thus, $R$ is transitive.
• Conclusion: $R$ is an equivalence relation.

Define $R$ on $\mathbb{N}$ by $(a, b) \in R$ if $a$ divides $b$.

• Is $R$ reflexive?
  • Yes, any number divides itself.
• Is $R$ symmetric?
  • No, e.g., $2$ divides $4$, but $4$ does not divide $2$.
• Is $R$ transitive?
  • Yes, if $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$.
• Is $R$ anti-symmetric?
  • Yes, if $a$ divides $b$ and $b$ divides $a$, then $a = b$.
• Conclusion: $R$ is reflexive, transitive, and anti-symmetric.

Let $A$ be the set of users in a social network.

Define relation $R$ on $A$ such that $(a, b) \in R$ if user $a$ follows user $b$.

• Is $R$ reflexive?
  • Typically no, unless users can follow themselves.
• Is $R$ symmetric?
  • Not necessarily; if $a$ follows $b$, $b$ may not follow $a$.
• Is $R$ transitive?
  • Generally no; if $a$ follows $b$ and $b$ follows $c$, $a$ doesn’t necessarily follow $c$.
• Interpretation: Represents the “following” relationship in social networks.

A function $f$ from set $X$ to set $Y$, denoted $f: X \rightarrow Y$, is a relation with the property that:

• Every element in $X$ is related to exactly one element in $Y$.

This means:

1. Totality: For every $x \in X$, there exists a $y \in Y$ such that $(x, y) \in f$.
2. Uniqueness: For every $x \in X$, there is exactly one $y \in Y$ such that $(x, y) \in f$.

Terminology:

• Domain: The set $X$.
• Co-domain: The set $Y$.
• Range: The set of actual outputs, ${ f(x) \mid x \in X }$.

Common Confusion:

• All functions are relations, but not all relations are functions.
• In a function, an element in the domain cannot be related to more than one element in the co-domain.

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be defined by $f(n) = n^2$.

• Function: For each natural number $n$, $f(n)$ is uniquely defined.
• Domain: $\mathbb{N}$.
• Co-domain: $\mathbb{N}$.
• Range: ${ n^2 \mid n \in \mathbb{N} }$.

Let $X = {1, 2, 3}$, $Y = {a, b}$, and define $f$ as:

• $f(1) = a$
• $f(2) = b$
• $f(3) = a$

This function maps elements of $X$ to elements of $Y$.

Consider relation $R = { (1, a), (1, b), (2, b) }$ from $X = {1, 2}$ to $Y = {a, b}$.

• Issue: $1$ is related to both $a$ and $b$.
• Conclusion: This is not a function because it violates the uniqueness requirement.

• Definition: A function $f: X \rightarrow Y$ is injective if different elements in $X$ map to different elements in $Y$.
• Formal: If $f(x_1) = f(x_2)$ implies $x_1 = x_2$.

• Definition: A function $f: X \rightarrow Y$ is surjective if every element in $Y$ is the image of at least one element in $X$.
• Formal: $\forall y \in Y, \exists x \in X \text{ such that } f(x) = y$.

• Definition: A function is bijective if it is both injective and surjective.
• Result: Bijective functions have inverses.

Common Confusion:

• Injective functions can have co-domain elements that are not mapped to (i.e., the function may not be surjective).
• Surjective functions can have domain elements mapping to the same co-domain element (i.e., the function may not be injective).

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ defined by $f(x) = 2x + 3$.

• Is $f$ injective?
  • Solution: Assume $f(x_1) = f(x_2)$.
    • $2x_1 + 3 = 2x_2 + 3$
    • Subtract $3$: $2x_1 = 2x_2$
    • Divide by $2$: $x_1 = x_2$
  • Conclusion: $f$ is injective.
• Is $f$ surjective?
  • Solution: For any $y \in \mathbb{R}$, solve for $x$:
    • $y = 2x + 3$
    • $x = \frac{y - 3}{2}$
    • Since $x \in \mathbb{R}$, $f$ is surjective.
  • Conclusion: $f$ is surjective.
• Is $f$ bijective?
  • Conclusion: Since $f$ is both injective and surjective, it is bijective.

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = n^2$.

• Is $f$ injective?
  • Solution: Assume $f(n_1) = f(n_2)$.
    • $n_1^2 = n_2^2$
    • Since $n_1, n_2 \geq 0$, $n_1 = n_2$
  • Conclusion: $f$ is injective.
• Is $f$ surjective?
  • Observation: Not every natural number is a perfect square.
  • Conclusion: $f$ is not surjective.
• Is $f$ bijective?
  • Conclusion: $f$ is injective but not surjective; thus, not bijective.

Let $f: {1, 2, 3} \rightarrow {a, b}$ defined by:

• $f(1) = a$

• $f(2) = a$

• $f(3) = b$

• Is $f$ injective?

  • Observation: $f(1) = f(2) = a$, but $1 \neq 2$.
  • Conclusion: $f$ is not injective.

• Is $f$ surjective?

  • Observation: Both $a$ and $b$ are outputs of $f$.
  • Conclusion: $f$ is surjective.

• Is $f$ bijective?

  • Conclusion: $f$ is surjective but not injective; thus, not bijective.

• Definition: If $f: X \rightarrow Y$ is bijective, then there exists an inverse function $f^{-1}: Y \rightarrow X$ such that $f^{-1}(f(x)) = x$ for all $x \in X$.

Given $f: \mathbb{R} \rightarrow \mathbb{R}$, $f(x) = 2x + 3$.

• Find the inverse function $f^{-1}(y)$.
  • Solve for $x$:
    • $y = 2x + 3$
    • $x = \frac{y - 3}{2}$
  • Conclusion: $f^{-1}(y) = \frac{y - 3}{2}$.

• Encoding/Decoding: Bijections are used in cryptography to encode and decode messages.
• Counting: Establishing a bijection helps in counting elements of complex sets.
• Algorithm Design: Functions model input-output relationships in programs.

• Sets: Fundamental collections of distinct elements, with operations like union, intersection, difference, and complement.
• Cartesian Products: Pairs of elements from two sets, forming ordered pairs.
• Relations: Subsets of Cartesian products, which can be characterized by properties like reflexivity, symmetry, and transitivity.
• Functions: Special types of relations where each input is related to exactly one output, with properties like injectivity, surjectivity, and bijectivity.

Understanding these concepts is crucial for modeling and solving problems in computer science, as they form the basis for data structures, algorithms, databases, and more.

1. Set Operations:
   • Given $A = {2, 4, 6, 8}$ and $B = {4, 8, 12}$, find:
     • $A \cup B$
     • $A \cap B$
     • $A - B$
     • $\overline{A}$, assuming universal set $U = {2, 4, 6, 8, 10, 12}$
2. Power Set and Cardinality:
   • Find the power set $\mathcal{P}(C)$ for $C = {x, y}$.
   • What is $|\mathcal{P}(C)|$?
3. Relation Properties:
   • For relation $R$ on $\mathbb{Z}$ defined by $a R b$ if $a - b$ is divisible by $5$:
     • Is $R$ reflexive?
     • Is $R$ symmetric?
     • Is $R$ transitive?
4. Function Classification:
   • Determine if the function $f: \mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = 2n$ is:
     • Injective
     • Surjective
5. Inverse Function:
   • Given $f: \mathbb{R} \rightarrow \mathbb{R}$, $f(x) = 3x - 7$, find the inverse function $f^{-1}(x)$.