Número de elementos de una relación $R$ de $\{1, \cdots, n\}$ .

Question

Sea $A = \{1,2,...,n\}$ y $R$ sea una relación sobre $A$ (así $R \subset A \times A$ )

i) ¿Cuál es el mínimo número posible de elementos en $R$ ?

Traté de calcular esto como un producto cartesiano normal que tendría $n^2$ dentro del conjunto. Así que $R$ también necesitaría $n^2$ número de elementos para ser un subconjunto adecuado de $A\times A$ .

ii) ¿Cuál es el número máximo posible de elementos en $R$ ?

Este me confunde un poco más, pero creo que tendría algo que ver con calcularlo como $2^{n^2}$ es decir, si $n$ fue $3$ entonces sería $2^9$ o $512$ como el número máximo de elementos.

Answer 1

Está usted confundiendo las cosas. Una relación no es más que un subconjunto de un producto cartesiano (al menos en teoría de conjuntos). Así que una relación $R$ en $A$ significa que $R$ es un subconjunto de $A\times A$ . Has señalado correctamente que el tamaño de un producto cartesiano es igual al producto de los tamaños (al menos en el caso finito). Como escribiste, $A\times A$ tiene $n^2$ elementos.

Ahora, para cualquier $2$ conjuntos finitos $X$ y $Y$ tal que $X\subset Y$ siempre es cierto que $|X|\leq|Y|$ . Y como $\emptyset\subset R$ y $R\subset A\times A$ ¿qué puede concluir sobre el tamaño de $R$ ?