Relations and Functions

• Importance: need basic familiarity with the terminology

• A relation on sets S and T is a set of ordered pairs (s, t), where
  • s S (s is a member of S),
  • t T,
  • S and T need not be different,
  • The set of all first elements (s) is the domain of the relation, and
  • The set of all second elements is the range of the relation.

• A relation is a function iff every element of S occurs once and only once as a first element of the relation.

• A relation is a partial function iff every element of S occurs at most once as an element of the relation.