Set 5 Notes: Set Theory Functions and Cardinality

Functions and Cardinality

Functions as Binary Relations

• A function is defined as a binary relation of type $A \times B$, where A and B are sets. $A \times B$ represents the Cartesian product, consisting of ordered pairs where the first element is from A and the second from B.
• Key Condition: For every $x$ in A, there is at most one $y$ in B such that $(x, y)$ belongs to the function (relation).
• If $(x, y)$ is in the function $f$, we write $f(x) = y$.
• This notation is justified by the condition that each $x$ in A relates to at most one $y$ in B, ensuring when $x$ is known, $y$ is uniquely determined by $f$.

Visual Representation

• When plotting the graph of a function, a vertical line drawn at any $x$ value will intersect the graph at most once.
• The inverse relation, obtained by interchanging $x$ and $y$, is not necessarily a function.

Domain and Codomain

• For a function $f: A \rightarrow B$, A is the domain and B is the codomain.
• The function $f$ as a relation is a subset of the Cartesian product $A \times B$.
• The domain and codomain are determined when the function is defined.
• A function isn't necessarily defined for every $x$ in A.

Domain of Definition

• The domain of definition is the subset of A for which $f(x)$ is defined. It comprises all $x$ in A such that there exists a $y$ in B with $(x, y) \in f$.
• The domain of definition is always a subset of the domain A.

Range (or Image)

• The range (or image), denoted as $R_f$, is the subset of B consisting of all $y$ such that there exists an $x$ in A with $y = f(x)$.
• In relational terms, $y$ is in the range if there exists an $x$ such that $(x, y) \in f$.

Total and Surjective Functions

• A function is total if its domain of definition is equal to its domain A.
• A function is surjective if its range is equal to its codomain B.
• The totality can be achieved if the domain is chosen appropriately. Similarly, surjectivity holds if the codomain is chosen appropriately (not too large).

Examples

1. Square Root Function: $f(x) = \sqrt{x}$
   • Defined from $\mathbb{R}$ to $\mathbb{R}$.
   • Domain of definition: $x \geq 0$
   • Range: All non-negative real numbers.
2. Reciprocal Function: $g(x) = \frac{1}{x}$
   • Defined from $\mathbb{R}$ to $\mathbb{R}$.
   • Domain of definition: All real numbers except 0.
   • Range: All real numbers except 0.

Injectivity

• Injectivity: Also called one-to-one, meaning that every element in the codomain has at most one element in the domain that maps to it.
• If $x<em>1 \neq x</em>2$, then $f(x<em>1) \neq f(x</em>2)$. Equivalently, if $f(x<em>1) = f(x</em>2)$, then $x<em>1 = x</em>2$.
• Geometrically, an injective function has at most one arrow ending at each element.

Example Illustrating Injectivity and Surjectivity

• Consider $f(x) = |3x - 1|$.
  1. If $f: \mathbb{R} \rightarrow \mathbb{R}^{\geq 0}$
     • The function is not injective because a horizontal line intersects the graph at more than one point. For example, $f(6)$ has two values.
     • The function is surjective because every horizontal line intersects the graph at least once.
  2. If $f: \mathbb{Z} \rightarrow \mathbb{N}$
     • The function is injective because every $x$ has a different function value. No horizontal line intersects two blue points.
     • The function is not surjective. Not every natural number is in the range. Values remaining after evaluation always contain remainder 1 when diving the natural number by 3.

Review Exercises

1. $f(x) = e^x$, where $f: \mathbb{R} \rightarrow \mathbb{R}$
   • Injective: Yes, because the function is strictly increasing. If $x<em>1 > x</em>2$, then $f(x<em>1) > f(x</em>2)$.
   • Not Surjective: The codomain is the entire set of real numbers, but the range only includes positive numbers, so any non-positive number is not in the range.
2. $f(n, m) = n - m$, where $f: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{Z}$
   • Not Injective: Multiple pairs $(n, m)$ can yield the same difference. For example, if $n = m$, then the same value is generated.
   • Surjective: Yes. For every integer $k$ there exists $n, m \in \mathbb{N}$ such that $n - m = k$. IF $k$ is positive, let $n = k$ and when $k$ is negative, let $m = -k$.

Composition of Functions

• Definition: If $f: A \rightarrow B$ and $g: B \rightarrow C$, then the composition $g \circ f$ (g after f) maps an element $x$ to $f(x)$ and then to $g(f(x))$.
• Formally, if $f(x) = y$ and $g(y) = z$, then $(g \circ f)(x) = z$.
• The pair $(x, y) \in f$ and $(y, z) \in g$ exist such that $(x, z) \in (g \circ f)$ precisely when there exists such a $y$.

Domain of Definition and Range of Composed Functions

• For $g \circ f$ to be defined, the codomain of f must equal the domain of g.
• The domain of definition of $g \circ f$ is a subset of the domain of $f$.
• The range of $g \circ f$ is a subset of the range of $g$.

Example

• Let $f(x) = 1 - x^2$ and $g(x) = \sqrt{x}$, both with domain and codomain as the set of real numbers.
• The composed function is $(g \circ f)(x) = \sqrt{1 - x^2}$.
• The domain of definition is the set of all $x$ for which $1 - x^2$ is non-negative, i.e., $-1 \le x \le 1$.
• The range consists of all $y$ between 0 and 1, inclusive.

Inverse Functions

• The inverse relation of a function is not necessarily a function.
• The inverse relation is a function if and only if $f$ is injective.
• Need at most one arrow ending on each element in the codomain to avoid a non-functional relation when arrows are swapped
• Theorem: The inverse of the relation f is a function if and only if f is injective.

Bijections

• If $f$ is injective and total, it has an inverse function.
• The terminology of "total injection" results in the domain agreeing with the domain of definition.
• A total injection has a total inverse if and only if f is surjective.
• Bijection: A function that is injective, total, and surjective. Also a one-to-one correspondence between sets.

Properties of Bijections

• Bijective functions have bijective inverses.
• If a function is bijective, the two sets should have the same number of elements.

Exercises

• Given:
  • $s(x) = x^2$
  • $d(x) = 2x$
  • $\sigma(x, y) = x + y$
  • $\delta(x) = x - 1$
  • $i(x) = \frac{1}{x}$

1. Find the expression, domain of definition, and range for $f = i \circ \delta^{-1} \circ s$
   • $\delta^{-1}(x)$ is such that applying the former to the latter returns $x$, So if \delta(x) = x-1 => \delta^{-1}(x) = x + 1
   • So $f = i \circ (x+1) \circ s = \frac{1}{x^2+1}$
   • The denominator may never be zero, so definition is all x, and the range is 0 < y <= 1
2. Decompose $g(x) = \frac{x^2}{2} - 1$ in terms of $s, d, \sigma, \delta, i$
   • $g(x) = \delta(\frac{1}{d}(s(x)))$

Comparing the Size of Sets

• To compare the size of two sets, A and B, map each element in A to a distinct element in B. If successful (injective function), A is no larger than B.
• Cardinality: An abstract notion of the size of a set based on the existence of functions with special properties.

Definition

• The cardinality of set A is less than or equal to set B if there exists a total injection from A to B.
• Two sets have the same cardinality if there exists a bijection between them.

Cardinality and Finite Sets

• For finite sets, the cardinality is the number of elements.
• There exists a bijection from a set with m elements (counting 1 to m) to A.

Cardinality and Infinite Sets

• For an infinite set, if an element is removed it still has the same size.
• There is a bijection can be generated that maps all elements in $N$ to $N-1$ where the first element will be zero.
• $N$ shares the same cardinality as the set of even numbers, because for every $n$ we take, $2n$ generates the set of even natural numbers.

Cantor-Schroeder-Bernstein Theorem

• If there exists a total injection from A to B and a total injection from B to A, then there exists a bijection between A and B.
• If |A| <= |B| and |B| <= |A|, then |A| = |B|.
• The usefulness of the theorem is illustrated by proving that $N \times N$ has the same cardinality as N.
• Proving that Cartesian product for $N$ is equal to $N$ can be achieved as follows:
  1. Map $n \rightarrow (n, n)$, where total injection goes from $N \rightarrow N \times N$
  2. Map $(n, k) \rightarrow 2^n*3^k$, where total injection goes from $N \times N \rightarrow N$. This total injection uses prime number decomposition.
  3. Since both total injections exist, we now have bijection between $N \times N \rightarrow N$, even though it is difficult to cook up

Countable and Uncountable Sets

• Countably Infinite: A set with the same cardinality as the set of natural numbers.
• Which there exists a bijection from N to A
• Countable: A set that is either countably infinite or finite.
• Uncountable: A set that is not countable.

Enumeration

• A countable set can be enumerated explicitly. Every element in A can be assigned to a natural number.
• The Cartesian product of N with itself is countably infinite.

Uncountable Sets

• The interval (0, 1) has a cardinality greater than the set of natural numbers.

Proof (by contradiction)

• Assume enumerate x1, x2, x3, … such that every real # between 0 and 1 is assigned a natural number that appears upon enumeration
• Construct a real number that has the properties that cannot appear upon enumeration
  • Take from x1 the first gigit after the dot, from x2 the second, …
  • if the number is less than 5 add +2. This +2 only makes sense since the number must be <6, since 7 would lead to 9.999 which equals 1.
  • if the number is >= 5 then subtract 2
  • The number cannot be equal to Xn for any n by looking precisely at the nth position to create real number for each X.