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.

Sequences

• A sequence is a specialised sort of function.
• It is a partial function which maps numbers to elements.
• Sequence starts from 1 and are consecutive.
• s : seq PERSON
  • Is shorthand for s: N ⟶ PERSON
  • Together with the restriction, dom s = 1..#s
• By default a sequence includes null. To exclude null from a sequence use seq₁
• Sequences may have repeated elements.
• To specify that a sequence has distinct elements use iseq
• Also written as s == <g, x, p>. g is in 1st pos, x in 2nd, p in 3rd.