Fracción de las relaciones de un conjunto a otro

Question

Estoy haciendo algunos de los ejercicios en Discrete Mathematics with Applications, Fourth Edition de Susanna Epp y hay una respuesta a los ejercicios que no entiendo. En el Ejercicio 1.3, No. 9.c:

¿Qué fracción de las relaciones de { 0, 1 } a { 1 } son funciones?

Y la respuesta es 1/4 (uno sobre cuatro). ¿Alguien puede decirme cómo llegar a esa respuesta?

Para ser honesto, apenas entiendo la pregunta.

Answer 1

Una relación en dos conjuntos es simplemente un subconjunto del Producto Cartesiano. El Producto Cartesiano aquí tiene 4 subconjuntos, cada uno de los cuales es una relación: $\varnothing, \{(0,1)\}, \{(1,1)\}, \{(0,1),(1,1)\}$. De estos, solo el último es una función, ya que una función es una relación que asigna 'todos' los elementos del dominio a algún elemento en el rango (en este caso, $1$).

Answer 2

Sean $A$ y $B$ conjuntos. En nuestro caso, $A=\{0,1\}$ y $B=\{1\}$. Pero seamos generales por un momento.

Una relación de $A$ en $B$ es cualquier subconjunto del conjunto de todos los pares ordenados $(a,b)$, donde $a\in A$ y $b\in B$. En nuestro caso, solo hay $2$ pares ordenados, que son $(0,1)$ y $(1,1)$. Entonces, el conjunto de pares ordenados es $\{(0,1),(1,1)\}$.

Este es un conjunto de dos elementos. Entonces tiene $2^2$ subconjuntos. Podemos listarlos todos explícitamente: son $$\emptyset,\quad \{(1,0)\},\quad \{(1,1)\}, \quad \{(0,1),(1,1)\}.$$

¿Cuáles de estos $4$ conjuntos de pares ordenados son funciones de $A$ a $B$? Formalmente, una función de $A$ en $B$ es un conjunto $F$ de pares ordenados $(a,b)$ tal que para cada $a\in A$, hay un único $b\in B$ tal que $(a,b)\in F.

Aquí no hay problema de unicidad, ya que $B$ tiene solo un elemento. Pero para cada $a$ en $A$, debemos tener un $b$ tal que $(a,b)\in F. Entonces eso debe cumplirse para $a=0$ y también para $a=1$. El único conjunto de pares ordenados que califica es $\{(0,1),(1,1)\}$: un conjunto de pares ordenados, de los $4$ conjuntos de pares ordenados disponibles.

Answer 3

Una relación en $\{0,1\}$ a $\{1\}$ es un subconjunto de $\{0,1\} \times \{1\} = \{(0,1), (1,1)\}$.

Los cuatro subconjuntos son

1) $\emptyset$

2) $\{(0,1)\}$

3) $\{(1,1)\}$

4) $\{(0,1), (1,1)\}$

Todos estos son funciones.

Probablemente la pregunta está pidiendo cuántas funciones de $\{0,1\} \rightarrow \{1\}$. Solo 4) tiene la propiedad de que el dominio es todo $\{0,1\}$.

---

Alternativamente, en lugar de enumerar todas las posibles relaciones, también se pueden usar algunas combinatorias. Sea $|A|$ el número de elementos en el conjunto finito $A$. $|A \times B| = |A| \times |B|$. Por lo tanto, $\{0,1\} \times \{1\}$ tiene $2 \cdot 1 = 2$ elementos. Sea $\mathscr{P}(A)$ el conjunto de todos los subconjuntos de un conjunto finito $A$. Por algunas combinatorias, $|P(\mathscr{A})| = 2^{|A|}$. Entonces hay $2^2 = 4$ subconjuntos de $\{0,1\} \times \{1\}$, es decir, hay cuatro relaciones de $\{0,1\} \rightarrow \{1\}$. Ahora el número de funciones $A \rightarrow B$ es $|B|^{|A|}$. El número de funciones $\{0,1\} \rightarrow \{1\}$ es $1^{2} = 1$. Por lo tanto, la razón es $\frac{1}{4}.