Definition:Preimage/Relation/Element

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\RR \subseteq S \times T$ be a relation.

Let $\RR^{-1} \subseteq T \times S$ be the inverse relation to $\RR$, defined as:

$\RR^{-1} = \set {\tuple {t, s}: \tuple {s, t} \in \RR}$


Every $s \in S$ such that $\tuple {s, t} \in \RR$ is called a preimage of $t$.


In some contexts, it is not individual elements that are important, but all elements of $S$ which are of interest.

Thus the preimage of $t \in T$ is defined as:

$\map {\RR^{-1} } t := \set {s \in S: \tuple {s, t} \in \RR}$


This can also be written:

$\map {\RR^{-1} } t := \set {s \in \Img {\RR^{-1} }: \tuple {t, s} \in \RR^{-1} }$


That is, the preimage of $t$ under $\RR$ is the image of $t$ under $\RR^{-1}$.


Warning

Note that:

$t \in T$ may have more than one preimage.
It is possible for $t \in T$ to have no preimages at all, in which case $\map {\RR^{-1} } t = \O$.


Also known as

The preimage of $t \in T$ is also known as:

the fiber of $t$
the preimage set of $t$
the inverse image of $t$.


As well as using the notation $\Preimg \RR$ to denote the preimage of an entire relation, the symbol $\operatorname {Img}^{-1}$ can also be used as follows:

For $t \in \Preimg \RR$:

$\map {\operatorname {Img}^{-1}_\RR} t = \map {\RR^{-1} } t$

but this notation is rarely seen.