Relations and Functions

Cartesian Products

Before we relate objects, we need a way to pair them.

The Cartesian Product \(A \times B\) is the set of all ordered pairs \((a, b)\) where \(a \in A\) and \(b \in B\).

• Notation: \(A \times B = \{ (a, b) \mid a \in A \text{ and } b \in B \}\)
• Example: If \(A = \{1, 2\}\) and \(B = \{x, y\}\):
  • \(A \times B = \{(1, x), (1, y), (2, x), (2, y)\}\)

What is a Relation?

A relation \(R\) from set \(A\) to set \(B\) is simply a subset of the Cartesian Product \(A \times B\).

• If \((a, b) \in R\), we say \(a\) is related to \(b\) (often written \(a R b\)).
• Domain: The set of all first elements in the pairs.
• Codomain: The set \(B\) (the set of potential “targets”).

Defining a Function

A function \(f\) from \(A\) to \(B\) is a special type of relation that follows two strict rules:

1. Every element in \(A\) must be used.
2. Each element in \(A\) maps to exactly one element in \(B\).

Notation: \(f: A \to B\)

Crucial Distinction: In a relation, one \(x\) can have many \(y\)s. In a function, one \(x\) can only have one \(y\).

Function Terminology

Let \(f: A \to B\) be a function.

• Domain: The set \(A\).
• Codomain: The set \(B\).
• Range (or Image): The set of all actual values \(f(x)\) hits in \(B\).
  • \(f(A) = \{ f(x) \mid x \in A \}\)

Function vs. Not a Function

Scenario A: \(A = \{1, 2\}, B = \{x, y\}\). \(R = \{(1, x), (1, y), (2, x)\}\). * Result: Not a function (1 maps to two different things).

Scenario B: \(A = \{1, 2\}, B = \{x, y, z\}\). \(f = \{(1, x), (2, x)\}\). * Result: Is a function! (Every \(x\) has exactly one \(y\), even if it’s the same \(y\)).

Equality of Functions

Two functions \(f\) and \(g\) are equal if: 1. They have the same domain. 2. They have the same codomain. 3. \(f(x) = g(x)\) for every \(x\) in the domain.

Just having the same formula isn’t enough; the “playground” (domain) must be the same too!

Real-World Connection: Databases

In Computer Science, a Relational Database is built on these concepts. * A “Table” is a relation (a subset of the product of all possible column values). * A “Primary Key” search is a function: one ID maps to exactly one record.

LaTeX Quick-Ref for Section 1.3

• A \times B \(\to A \times B\)
• f: A \to B \(\to f: A \to B\)
• (a, b) \(\to (a, b)\)
• f(x) = y \(\to f(x) = y\)
• \text{dom}(f) \(\to \text{dom}(f)\)

Activity: Spot the Function

Which of these relations from \(\{1, 2, 3\}\) to \(\{a, b\}\) is a function?

1. \(R_1 = \{(1, a), (2, b)\}\)
2. \(R_2 = \{(1, a), (2, a), (3, a)\}\)
3. \(R_3 = \{(1, a), (2, b), (3, a), (3, b)\}\)