Question

Given three sets: \(\mathrm{X}, \mathrm{Y}\) and \(\mathrm{Z}\), such that \(\mathrm{Y} \cap \mathrm{Z}=\Phi\). Prove that the set of functions from \(\mathrm{Y} \cup \mathrm{Z}\) to \(\mathrm{X}\) is equipotent to the set of functions from \(\mathrm{Y}\) to \(\mathrm{X}\) crossed with the set of functions from \(Z\) to \(X\).

Short answer

Define a function \(F: f \mapsto (f|_Y, f|_Z)\), where \(f: \mathrm{Y} \cup \mathrm{Z} \to \mathrm{X}\), \(f|_Y: Y \to X\) and \(f|_Z: Z \to X\). Show that \(F\) is injective (one-to-one) by assuming \(F(f_1) = F(f_2)\) and proving that \(f_1 = f_2\). Show that \(F\) is surjective (onto) by constructing a function \(f\) from an arbitrary element \((g_1, g_2)\) in the Cartesian product of the set of all functions from \(\mathrm{Y}\) to \(\mathrm{X}\) and the set of all functions from \(\mathrm{Z}\) to \(\mathrm{X}\) such that \(F(f) = (g_1, g_2)\). Since \(F\) is bijective, the set of functions from \(\mathrm{Y} \cup \mathrm{Z}\) to \(\mathrm{X}\) is equipotent to the set of functions from \(\mathrm{Y}\) to \(\mathrm{X}\) crossed with the set of functions from \(Z\) to \(X\).

Step-by-step solution

Define a specific function

Define a function \(F\) as follows: For each function \(f: \mathrm{Y} \cup \mathrm{Z} \to \mathrm{X}\), there are unique restrictions \(f|_Y: Y \to X\) and \(f|_Z: Z \to X\). We define \(F\) as the function that maps each \(f\) onto the ordered pair of its restrictions on \(Y\) and \(Z\): $$F: f \mapsto (f|_Y, f|_Z)$$.

Show \(F\) is one-to-one

Now, let's show that \(F\) is an injective (one-to-one) function. Suppose that \(F(f_1) = F(f_2)\) for some functions \(f_1\) and \(f_2\) from \(\mathrm{Y} \cup \mathrm{Z}\) to \(\mathrm{X}\). This means that \((f_1|_Y, f_1|_Z) = (f_2|_Y, f_2|_Z)\). Thus, \(f_1|_Y = f_2|_Y\) and \(f_1|_Z = f_2|_Z\). Since \(\mathrm{Y} \cap \mathrm{Z} = \Phi\) and \(f_1\) and \(f_2\) are each equal to their restrictions on \(Y\) and \(Z\), we have that \(f_1 = f_2\) on \(\mathrm{Y} \cup \mathrm{Z}\), which means \(f_1 = f_2\). Hence, \(F\) is injective.

Show \(F\) is onto

Now, let's show that \(F\) is a surjective (onto) function. Let \((g_1, g_2)\) be an element in the Cartesian product of the set of all functions from \(\mathrm{Y}\) to \(\mathrm{X}\) and the set of all functions from \(\mathrm{Z}\) to \(\mathrm{X}\). We need to show that there exists a function \(f: \mathrm{Y} \cup \mathrm{Z} \to \mathrm{X}\) such that \(F(f) = (g_1, g_2)\). To construct such a function, define \(f\) as follows: $$ f(x) = \begin{cases} g_1(x) & \text{if } x \in Y \\ g_2(x) & \text{if } x \in Z \end{cases} $$ Then, \(f|_Y = g_1\) and \(f|_Z = g_2\), so \(F(f) = (g_1, g_2)\). Hence, \(F\) is surjective.

Concluding the proof

Since \(F\) is both an injective and surjective (bijective) function, we can conclude that the set of functions from \(\mathrm{Y} \cup \mathrm{Z}\) to \(\mathrm{X}\) is equipotent to the set of functions from \(\mathrm{Y}\) to \(\mathrm{X}\) crossed with the set of functions from \(Z\) to \(X\).

Key concepts

Function Mapping

A function mapping is a mathematical relationship where each element of a given set, called the domain, is associated with an element of another set, known as the codomain. In our problem, we work with functions from various sets to a common codomain, denoted by \( \mathrm{X} \). When we map a union of two sets \( \mathrm{Y} \) and \( \mathrm{Z} \) to \( \mathrm{X} \), each function can be seen as a rule specifying which element of \( \mathrm{X} \) is paired with each element of \( \mathrm{Y} \cup \mathrm{Z} \).

If \( f: \mathrm{Y} \cup \mathrm{Z} \to \mathrm{X} \) is a function mapping, we can represent \( f \) using pairs, so that each input from the domain has a unique output in the codomain. This is critical for defining the function \( F \) that maps functions to pairs of restricted functions \( (f|_Y, f|_Z) \). These restrictions specify how \( f \) behaves on subsets \( \mathrm{Y} \) and \( \mathrm{Z} \), respectively.

• Domain: The set where inputs of the function come from.
• Codomain: The set where outputs of the function go.
• Union: The combination of elements from two or more sets.

This concept is essential for understanding how we can represent functions equivalently using their restrictions to subsets.

Injective and Surjective Functions

To fully grasp injective and surjective functions, it's important to understand these concepts in mapping functions. An injective function, or one-to-one function, is a mapping where each element of the domain is mapped to a unique element in the codomain. If we take two different inputs, they will always have different outputs. In our problem, defining \( F \) as a function that maps functions to pairs of restrictions demonstrates injective properties.

On the other hand, a surjective function, or onto function, covers the entire codomain. This means every element of the codomain is an output for at least one input from the domain. "Onto" ensures that all possibilities in the codomain are fulfilled by the domain.

In our exercise, proving \( F \) is bijective (both injective and surjective) supports the argument that the sets are equipotent:

• Injective: Ensures that distinct functions have distinct image pairs.
• Surjective: Guarantees for every possible pair in the Cartesian product, there is a corresponding function.

This showcases the bijective nature of \( F \), affirming balance between domains.

Cartesian Product

The Cartesian Product is a mathematical operation that returns a set from multiple sets. The product of two sets \( \mathrm{A} \) and \( \mathrm{B} \) consists of all ordered pairs \( (a, b) \), where \( a \) is in \( \mathrm{A} \) and \( b \) is in \( \mathrm{B} \). In our exercise context, the Cartesian Product is used to demonstrate a equivalence between function sets.

When we say that the set of functions from \( \mathrm{Y} \cup \mathrm{Z} \) to \( \mathrm{X} \) is equipotent with the Cartesian product of functions from \( \mathrm{Y} \) to \( \mathrm{X} \) and functions from \( \mathrm{Z} \) to \( \mathrm{X} \), we are essentially saying there is a one-to-one correspondence between these sets, just like how ordered pairs in a Cartesian product behave.

The Cartesian product offers a structure wherein:

• Each element is an ordered pair of inputs from the first and second set.
• It emphasizes combining elements of two distinct but potentially related sets.

The idea built on this product helps in understanding complex relationships by breaking them into digestible pairs of relations, just like pairing the outcomes of functions restricted to \( \mathrm{Y} \) and \( \mathrm{Z} \).