Set Theory/Relations

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search

Contents

[edit] Ordered pairs

To define relations on sets we must have a concept of an ordered pair, as opposed to the unordered pairs the axiom of pair gives. To have a rigorous definition of ordered pair, we aim to satisfy one important property, namely, for sets a,b,c and d, (a,b)=(c,d) \iff a=c \wedge b=d.

As it stands, there are many ways to define an ordered pair to satisfy this property. A simple definition, then is (a,b) = {{a},{a,b}}. (This is true simply by definition. It is a convention that we can usefully build upon, and has no deeper significance.)

Theorem

(a,b)=(c,d) \iff a=c \wedge b=d

Proof

If a = c and b = d, then (a,b) = {{a},{a,b}} = {{c},{c,d}} = (c,d).
Now, if (a,b) = (c,d) then {{a},{a,b}} = {{c},{c,d}}. Then \cap \{\{a\},\{a,b\}\}=\cap \{\{c\},\{c,d\}\}, so {a} = {c} and a=c.
So we have (a,b) = (a,d). Thus \cup \{\{a\},\{a,b\}\}=\cup \{\{a\},\{a,d\}\} meaning {a,b} = {a,d}.

If a = b, we have {a} = {a,d} and thus d \in \{a\} so a = d.
If a \ne b, note b \in \{a,d\}, so b = d

[edit] Relations

Using the definiton of ordered pairs, we now introduce the notion of a binary relation.

The simplest definition of a binary relation is a set of ordered pairs. More formally, a set \ R\ is a relation if z \in R \rightarrow z=(x,y) for some x,y. We can simplify the notation and write (x,y) \in R or simply xRy.

We give a few useful definitions of sets used when speaking of relations.

  • The domain of a relation R is defined as \mbox{dom}\ R = \{x \mid \exists y, (x,y) \in R \}, or all sets that are the initial member of an ordered pair contained in R.
  • The range of a relation R is defined as \mbox{ran}\ R = \{y \mid \exists x, (x,y) \in R \}, or all sets that are the final member of an ordered pair contained in R.
  • The union of the domain and range, \mbox{field}\ R = \mbox{dom}\ R \cup \mbox{ran}\ R, is called the field of R.
  • A relation R is a relation on a set X if \mbox{field}\ R \subseteq X.
  • The inverse of R is the set R^{-1}=\{(y,x) \mid (x,y) \in R\}
  • The image of a set A under a relation R is defined as R[A] = \{y\in \mbox{ran}\ R \mid \exists x \in A, (x,y)\in R\}.
  • The preimage of a set B under a relation R is the image of B over R-1 or R^{-1}[B] = \{x\in \mbox{dom}\ R \mid \exists y \in B, (x,y)\in R\}

It is intuitive, when considering a relation to seek to construct more relations from it, or to combine it with others.

We can compose two relations, R and S to form one relation S \circ R =\{(x,z) \mid \exists y, (x,y) \in R \wedge (y,z) \in S\}. So x S \circ R z means that there is some y such that xRy \wedge ySz.

We can define a few useful binary relations as examples:

  1. The Cartesian Product of two sets is A \times B = \{(a,b) \in \mathcal{P}\mathcal{P}(A\cup B) \mid a \in A \wedge b \in B\}, or the set where all elements of A are related to all elements of B. As an excercise, show that all relations from A to B are subsets of A \times B. Notationally A \times A is written A2
  2. The membership relation on a set A, \in_A = \{(a,b) \mid a, b \in A, a \in b\}
  3. The identity relation on A, I_A = \{(a,b) \mid a,b \in A, a=b\}

The following properties may or may not hold for a relation R on a set X:

  • R is reflexive if xRx holds for all x in X.
  • R is symmetric if xRy implies yRx for all x and y in X.
  • R is antisymmetric if xRy and yRx together imply that x = y for all x and y in X.
  • R is transitive if xRy and yRz together imply that xRz holds for all x, y, and z in X.
  • R is total if xRy, yRx, or both hold for all x and y in X.

[edit] Functions

[edit] Definitions

A function may be defined as a particular type of relation. We define a partial function f: X \rightarrow Y as some mapping from a set X to another set Y that assigns to each x \in X no more than one y \in Y. Alternatively, f is a function if and only if f\circ f^{-1}\subseteq I_{Y}

If on each x \in X, f assigns exactly one y \in Y, then f is called total function or just function. The following definitions are commonly used when discussing functions.

  • If f \subseteq X \times Y and f is a function, then we can denote this by writing f : X \to Y. The set X is known as the domain and the set Y is known as the codomain.
  • For a function f : X \to Y, the image of an element x \in X is y \in Y such that f(x) = y. Alternatively, we can say that y is the value of f evaluated at x.
  • For a function f : X \to Y, the image of a subset A of X is the set \{ y \in Y : f(x) = y \mbox{ for some } x \in A\}. This set is denoted by f(A). Be careful not to confuse this with f(x) for x \in X, which is an element of Y.
  • The range of a function f : X \to Y is f(X), or all of the values y \in Y where we can find an x \in X such that f(x) = y.
  • For a function f : X \to Y, the preimage of a subset B of Y is the set \{x \in X : f(x) \in B\}. This is denoted by f - 1(B).

[edit] Properties of functions

A function f:X \rightarrow Y is onto, or surjective, if for each y \in Y exists x \in X such that f(x) = y. It is easy to show that a function is surjective if and only if its codomain is equal to its range. It is one-to-one, or injective, if different elements of X are mapped to different elements of Y, that is f(x)=f(y) \Rightarrow x=y. A function that is both injective and surjective is intuitively termed bijective.

[edit] Composition of functions

Given two functions f:X \rightarrow Y and g:Y \rightarrow Z, we may be interested in first evaluating f at some x \in X and then evaluating g at f(x). To this end, we define the composition' of these functions, written g \circ f, as

(g \circ f)(x) = g(f(x))

Note that the composition of these functions maps an element in X to an element in Z, so we would write g \circ f : X \rightarrow Z.

[edit] Inverses of functions

If there exists a function g:Y \rightarrow X such that for f:X \rightarrow Y, g \circ f = I_X, we call g a left inverse of f. If a left inverse for f exists, we say that f is left invertible. Similarly, if there exists a function h:Y \rightarrow X such that f \circ h = I_Y then we call h a right inverse of f. If such an h exists, we say that f is right invertible. If there exists an element which is both a left and right inverse of f, we say that such an element is the inverse of f and denote it by f - 1. Be careful not to confuse this with the preimage of f; the preimage of f always exists while the inverse may not. Proof of the following theorems is left as an exercise to the reader.

Theorem: If a function has both a left inverse g and a right inverse h, then g = h = f − 1.

Theorem: A function is invertible if and only if it is bijective.

← Relations · Orderings →

← Relations · Set Theory · Orderings →
Retrieved from "http://en.wikibooks.org/wiki/Set_Theory/Relations"