Relations and Functions

Relations

• An ordered pair (a,b) consists of two elements.
• In Z, ordered pairs are represented using the maplet notation: a ⟼ b
• The cartesian product, A X B is the set of all ordered pairs of A and B.
• A binary relation between A and B is any subset of A X B.
• Thus a relation R is given by R: P(A X B). R is a member of the powerset of the cartesian product of A and B.
• A relation IS-A set, so all set operations can be applied on relations.

Functions

• A function is a relation where a single element cannot be mapped to more than one element. No two maplets with the same source. No diverging arrows.
• A partial function is where not all the source elements are mapped to a target.
• A total function is where all the source elements are mapped to a separate target. (Note, all the targets need not be used).
• An injective function is where the target elements of the maplet dont have multiple sources. No converging arrows.
  • Partial injective : No converging arrows for a target and not all sources are mapped to a target.
  • Total injective: No converging arrows for a target and all sources are mapped to a target.
• Surjective function is where all the target elements are mapped by the function.
  • Partial surjective is where all sources are not mapped but all targets are.
  • Total surjective is where all sources are mapped and all targets are. (There can be converging arrows).
• A bijective function is one a function which is an injection, a surjection and is total.