LING 501, Fall 2004: Relations and functions

Properties and relations (especially binary relations)

• A ordered pair <x, y> is a list of two elements x, y, where x is the first element and y is the second element.
• An ordered n-tuple <x₁, ..., x_n> (n > 1) is a list of n elements.
• A 1-tuple <x> = x.
• A binary relation is a set of ordered pairs.
• An n-place relation is a set of ordered n-tuples.
• A 1-place relation (or unary relation or property) is a set of 1-tuples.
• The domain of a binary relation R is the set of first elements of the members of R.
• The range of a binary relation R is the set of second elements of R.
• R is a relation from A to B if and only if the domain of R is a subset of A and the range of R is a subset of B.
• The Cartesian product of A and B (A × B) is the relation which pairs every member of A with every member of B; i.e., {<x, y> | x Î A and y Î B}.

Binary relations in A Click on PDF for more information in Adobe acrobat (pdf) version; click on RTF for more information in rich text format version.

• R is a (binary) relation in A if R is a subset of A × A.

Reflexivity

• R is reflexive in A if and only if for every x in A, xRx.
• R is irreflexive if and only if for every x, ~ xRx).
• R is nonreflexive if and only if R is neither reflexive nor irreflexive. That is, R is nonreflexive if and only if there is some x such that xRx and some y such that ~ (yRy).
• R is antireflexive if and only if for every x, y if xRy and yRx then x ¹ y.

Symmetry

• R is symmetric if and only if for every x, y, if xRy then yRx.
• R is asymmetric if and only if for every x, y, if xRy then ~ (yRx).
• R is nonsymmetric if and only if R is neither symmetric nor asymmetric.
• R is antisymmetric if and only if for every x, y, if xRy and yRx then x = y.

Transitivity

• R is transitive if and only if for every x, y, z, if xRy and yRz then xRz.
• R is intransitive if and only if for every x, y, z, if xRy and yRz then ~ (xRz).
• R is nontransitive if and only if R is neither transitive nor intransitive.
• R is antitransitive if and only if for every x, y, z, if xRz then ~ (xRy) and ~ (yRz).

Note that the logical use of the terms 'transitive' and 'intransitive' differs from the normal linguistic use, in which 'transitive' is roughly the same as 'binary relation', and 'intransitive' as 'property'.

Equivalence

• R is an equivalence relation if and only if R is reflexive, symmetric, and transitive.
• Let R be an equivalence relation and x be a member of A. Then the equivalence class [x]_R generated by x with respect to R is the subset of A to which x bears the relation R.
• A partition of a set A is a class of subsets A₁, ... A_n such that È A_i = A and for every distinct A_i, A_j, A_i Ç A_j = Æ.

An equivalence relation partitions A into equivalence classes.

Orderings

• R is a partial ordering of A if and only if R is reflexive, antisymmetric, and transitive. Partial orderings are the bases of entailment relations.
• R is a strict ordering if and only if R is irreflexive and transitive.
• R is an ordering if and only if R is either a partial or strict ordering.
• x is maximal with respect to an ordering R if for every y ¹ x, ~ (xRy).
• x is minimal with respect to an ordering R if for every y ¹ x, ~ (yRx).
• An ordering R is bounded from above if R has a maximal element.
• An ordering R is bounded from below if R has a minimal element.
• An ordering R is unbounded if it has no maximal or minimal elements.
• R is a linear ordering if and only if R is an ordering, and for every distinct x, y, either xRy or yRx, but not both.
• If R is a linear ordering, then R has at most one maximal and one minimal element.
• x is the top (or supremum, symbolized T) with respect to an ordering R if it is the only maximal element.
• x is the bottom (or infemum, symbolized ^ ) with respect to an ordering R if it is the only minimal element.

Functions

• A binary relation f is a (unary) function from A to B if and only if every element of A bears f to exactly one element of B.
• Let f be a function from A to B, and let b be the member of B to which f assigns a in A. Then b is the image of f(a); i.e. b = f(a).
• If the range of f is a subset of its domain, then f is a (unary) function in A.
• An (n+1)-ary relation f is an n-place function from A₁ ´ ... × A_n to B if and only if every element of A₁ ´ ... × A_n bears f to exactly one element of B.
• If the image of <a₁, ..., a_n> is b, we write b = f(a₁, ..., a_n). We say that f has n argument places, and that a₁ is its first argument, ..., and a_n is its nth argument.
• If the domain of the n-place function f is A × ... × A, and the range of f is a subset of A, then f is an n-place function in A.
• Let f and g be functions such that the range of f is a subset of the domain of g. The composition of g with f, g°f = g(f), is the function which maps each element of the domain of f to the image under g of its image under f. For example:
• if f(a) = b and g(b) = c, then g°f(a) = g(f(a)) = c.
• If g is a binary function, then it can be composed with functions on each of its arguments. For example:
• if g(a, b) = c and f(d) = a, then g(f(d), b) = c;
• if also g(a, b) = c and h(e) = b, then g(a, h(e) = c, and g(f(d), h(e)) = c.
• A unary function f is many-to-one if and only if it is not one-to-one.
• If f is one-to-one, then f^-1, the inverse of f, is the one-to-one function obtained by interchanging its domain and range.
• A one-to-one correspondence from A to B (or: between A and B) is a one-to-one function whose domain is A and whose range is the entirety of B.
• A function f is onto (or surjective) if the entirety of B is the range of f. Otherwise f is into (or injective).

If A and B are in one-to-one correspondence then they have the same size (cardinality). For example the set A of positive numbers and the set B of squares of positive numbers have the same size since the function square(n) is a one-to-one onto mapping from A to B.