How is a Relation a Subset of an Ordered Pair?

[evinda]

Hey! (Cool)

According to my notes, each relation is a subset of an ordered pair.
How can it be that each relation is a subset of an ordered pair, knowing that a relation is a set of ordered pairs? (Thinking)

 

[Evgeny.Makarov]

According to my notes, each relation is a subset of an ordered pair.

No, a relation between $A$ and $B$ is a subset of the Cartesian product $A\times B$. This product, in turn, is a set of all ordered pairs whose first element comes from $A$ and whose second element comes from $B$.

 

[evinda]

No, a relation between $A$ and $B$ is a subset of the Cartesian product $A\times B$. This product, in turn, is a set of all ordered pairs whose first element comes from $A$ and whose second element comes from $B$.

There is the following theorem, that proves that a relation between $A$ and $B$ is a subset of the Cartesian product $A\times B$:

Let $R$ be a relation.There are unique sets $A,B$, such that:
$$x \in A \leftrightarrow \exists y: xRy \text{ and } y \in B \leftrightarrow \exists x: xRy$$
so:
$$A=\{x: \exists y (xRy) \}, B=\{ y: \exists x (xRy) \}$$

The proof of the theorem starts like that:

Let $<x,y> \in R$. Then:

$$\{ \{ x \}, \{ x,y \} \} \in R \rightarrow \{ x \} \in \bigcup R$$

Could you explain me how we conclude, that $\{ x \} \in \bigcup R$ ? (Thinking)

 

[Evgeny.Makarov]

There is the following theorem, that proves that a relation between $A$ and $B$ is a subset of the Cartesian product $A\times B$:

Let $R$ be a relation.There are unique sets $A,B$, such that:
$$x \in A \leftrightarrow \exists y: xRy \text{ and } y \in B \leftrightarrow \exists x: xRy$$
so:
$$A=\{x: \exists y (xRy) \}, B=\{ y: \exists x (xRy) \}$$

This theorem says more than a relation between $A$ and $B$ is a subset of the Cartesian product $A\times B$. This latter fact holds by definition. The theorem you quoted says that a relation has unique (minimal) domain and range in the sense described in Wikipedia.

The proof of the theorem starts like that:

Let $<x,y> \in R$. Then:

$$\{ \{ x \}, \{ x,y \} \} \in R \rightarrow \{ x \} \in \bigcup R$$

Could you explain me how we conclude, that $\{ x \} \in \bigcup R$ ? (Thinking)

This again holds by definition of generalized union since $\{x\}\in\{ \{ x \}, \{ x,y \} \} \in R$

 

[evinda]

This theorem says more than a relation between $A$ and $B$ is a subset of the Cartesian product $A\times B$. This latter fact holds by definition. The theorem you quoted says that a relation has unique (minimal) domain and range in the sense described in Wikipedia.

This again holds by definition of generalized union since $\{x\}\in\{ \{ x \}, \{ x,y \} \} \in R$

A ok.. (Smile) So, could we prove like that, that a relation $R$ has a unique range $B=\{ y: \exists x (xRy)\}$ ? (Thinking)

Let $<x,y> \in R$. Then, we have that $\{ \{x\},\{x,y\} \} \in R \rightarrow \{x,y\} \in \bigcup R$

From $\{x,y\} \in \bigcup R$ and $y \in \{x,y\}$, we have that $y \in \bigcup \bigcup R$.

Therefore, $\forall y(\exists x: <x,y> \in R) \rightarrow y \in \bigcup \bigcup R$

From the theorem: "Let $\phi$ a type. If there is a set $Y$, such that $\forall x(\phi(x)) \rightarrow x \in Y$, then there is the set $\{x: \phi(x) \}$"

we conclude that the set $\{y: \exists x(xRy) \}$ exists.

 

[Evgeny.Makarov]

Yes, I think this is fine.

 

[evinda]

Yes, I think this is fine.

Nice, thank you! (Smirk)