Relações e suas propriedades (parte 1)

Relações são estruturas fundamentais na matemática que nos auxiliam na construção de modelos.

Na teoria de conjuntos, as relações são implementadas como conjuntos de pares ordenados (ou seja, conjuntos cujos elementos são todos pares ordenados) e portanto, toda relação em teoria de conjuntos é fundamentalmente uma relação binária. (É possível emular relações n-árias quaisquer como veremos mais adiante).

$$ \forall R (R \space \text{é uma relação} \leftrightarrow \forall p (p \in R \rightarrow \exists x,y (p = \langle x , y \rangle ))) $$
Como as relações são conjuntos de pares ordenados, elas são comumente separadas de conjuntos formados através do produto cartesiano, por exemplo:

$$ R = \{\langle x , y \rangle \in A \times A \space | \space \phi[x,y]\} $$
Onde \( \phi[x,y] \) é uma sentença bem formada na linguagem de ZFC com \( x,y \) parametrizadas, assumindo a posição de termos, sem serem variáveis ligadas.

Note que \( A \times A \) é uma relação.

Como toda relação na teoria de conjuntos é essencialmente binária, representamos \( \langle x, y \rangle \in R \) por \( x R y \).

As relações possuem domínio e imagem, sendo definidas da seguinte forma:

Dada uma relação \( R\), seu domínio \( Dom(R) \) é o conjunto de todos os elementos que estão do lado esquerdo da relação:

$$\forall R (R \text{ é relação} \rightarrow Dom(R) = \{ x \in \bigcup \bigcup R \space |\space \exists y (x R y)\}) $$
Dada uma relação \( R \), sua imagem \( Im(R) \) (às vezes também escrita como \( Rng(R) \) em contextos de língua inglesa) é o conjunto de todos os elementos que estão do lado direito da relação:

$$ \forall R (R \text{ é relação} \rightarrow Im(R) = \{ x \in \bigcup \bigcup R \space | \space \exists y (yRx) \}) $$
Dizemos que \( R \) é uma relação sobre \( A \) quando \( R \subseteq A \times A \).

Curiosamente, dada uma relação \( R \) qualquer, podemos sempre achar um conjunto \( A \), tal que \( A \) é o "menor" conjunto tal que \( R \) é uma relação sobre \( A \).

Cabe aqui primeiro estabelecermos o que significa "menor" neste contexto.

Sempre quando dizemos que algo é o menor ou o maior estamos pressupondo que existe uma relação de ordem que é o critério para nos dizer o que significa ser maior ou menor.

Neste contexto específico estamos usando a relação de contingência ( \( \subseteq \) ) como relação de ordem.

Teorema: \( \forall R ( R \text{ é uma relação} \wedge (Dom(R) \cup Im(R)) = A \rightarrow \\ R \subseteq A\times A \wedge \forall S( R \subseteq S\times S \rightarrow A \times A \subseteq S \times S))  \).
Demonstração:

i. Provar que \( R \subseteq A \times A \):

Suponha \( x R y \) para \( x,y \) arbitrários.

\( x \in Dom(R) \wedge y \in Im(R)  \implies x,y \in Dom(R) \cup Im(R) \).

Por definição: \( \forall x,y (\langle x , y \rangle \in A \times A \leftrightarrow x,y \in Dom(R) \cup Im(R)) \).

Logo, \( \langle x, y \rangle \in A \times A \).

Como \( x, y \) são arbitrários, então \( R \subseteq S \times S \).

ii. Provar que \( R \subseteq S \times S \rightarrow A \subseteq S \) para qualquer \( S \):

Suponha \( R \subseteq S \times S\) para \( S \) arbitrário.

Portanto, \( \forall x,y (\langle x,y \rangle \in R \rightarrow \langle x,y \in \rangle S \times S) \).

E assim, como \( S \times S \subseteq R \) por hipótese, \( \forall x,y (\langle x,y \rangle \in R \rightarrow x \in S \wedge y \in S)\).

Acontece que, \( \forall x,y (\langle x,y \rangle \in R \leftrightarrow x \in Dom (R) \wedge y \in Im(R)) \).

Logo, \(Dom(R) \subseteq S \wedge Im(R) \subseteq S \).

Portanto, \(Dom(R) \cup Im(R) \subseteq S\).

Por fim, \( A \subseteq S\).