Relations

This chapter is covers notes on relations.

In the previous chapter on tuples, we saw that, given some sets

A_1, A_2, \ldots, A_n,

we can encapsulate all the possible tuples

(a_1 \in A_1, a_2 \in A_2, \ldots, a_n \in A_n)

into a single set ${A_1 \times A_2 \times \ldots \times A_n}$ called the Cartesian product. But what if we want to specify just a part of the Cartesian product? For that, we use another special set called a relation. We'll start with the simplest type, the binary relation.

Binary Relations

A binary relation is defined as follows:

binary relation. A set of ordered pairs ${(a,b)}$ is called a relation.

Notice what this definition implies: ${R}$ is a set, whose members are always 2-tuples (ordered pairs). For example, the set:

\set{(a,1), (b,2), (c,3)}

is a relation. In some cases, the relation is actually a subset of a Cartesian product. For example, suppose we had the following sets:

\eqs{ X &= \set{1,2,3} \\ Y &= \set{a,b,c}. }

The Cartesian product of these two sets is:

X \times Y = \lset{ \eqs{ & (1,a), & (2,a), && (3,a) & \\ & (1,b), & (2,b), && (3,b) & \\ & (1,c), & (2,c), && (3,c) & } }.

A binary relation is simply a subset of this Cartesian product. For example, this is a binary relation:

\lset{ (1,a), (2,b), (3,c) },

and so is this:

\lset{ (1,a), (2,a), (3,a) },

and this:

\lset{ \eqs{ & (1,a), & (2,a), && (3,a) & \\ & (1,b), & (2,b), && (3,b) & \\ & (1,c), & (2,c), && (3,c) & } }.

Notice that this is also the Cartesian product we specified earlier. The binary relation does not have to be a strict subset of the Cartesian product. It just has to be a subset. I.e., we can never have a tuple ${(a,b) \in R,}$ where ${R \subseteq A \times B}$ and ${a \notin A \lor b \notin B.}$

Now that we've seen what a relation is, let's introduce some new notation.

relation notation. Let ${R}$ be a relation from ${A}$ to ${B.}$ That is, ${R \subseteq A \times B.}$

If ${(a,b) \in R,}$ we say " ${a}$ is related to ${b}$ by ${R,}$ " and we write:

a \rel b.

Otherwise, if ${(a,b) \notin R,}$ we say " ${a}$ is not related to ${b}$ by ${R,}$ " and write:

a \nrel b

Relations Generally

Much like how the Cartesian product can be generalized to handle an ${n}$ number of sets, relations can be generalized for an ${n}$ number of sets.

general definition of a relation. Let ${A_1, A_2, \ldots, A_n}$ be sets. An ${n}$ -ary relation on the sets ${A_1, A_2, \ldots, A_n}$ is a subset of

A_1 \times A_2 \times \ldots \times A_n,

and ${n}$ is the relation's degree, and ${A_i, i = 1,2,\ldots,n}$ are called the relation's projections.

Certain ${n}$ -ary relations have unique names. For example, when ${n=3,}$ we have a ternary relation. When ${n = 4,}$ we have a quaternary relation. ${n}$ -ary relations are examined in closer detail at a later juncture. Until then, we'll use binary relations to explore the various properties of relations. Accordingly, we'll use the word "relation" to mean a binary relation, unless otherwise stated.

Relation Language

It's important to get used to some of the language associated with relations. Below are some common phrases often used in the study of relations.

Phrase	Symbolic Representation
${R}$ is a relation on ${A}$	${R \subseteq A \times A}$
${R}$ is a relation in ${A}$	${R \subseteq A \times A}$
${R}$ is a relation from ${A}$ to ${B}$	${R \subseteq A \times B}$
${a}$ is related to ${b}$ by ${R}$	${a \rel b}$ , ${(a,b) \in R}$

Homogenous Relations

Earlier, we saw the relation ${\reals \times \reals.}$ Notice that this is a relation from a set to itself. We call such relations homogenous relations.

homogenous relations. A relation ${R}$ on a set ${A}$ is a relation from ${A}$ to ${A.}$ That is,

R = \set{(a,b) : a \in A, b \in A}

We call the set ${A}$ the domain of discourse of ${R.}$

For example, say we had the set:

A = \set{1,2,3,4}

The relation:

R = \set{(a,b) \in A \times A : a \dv b}

is a homogenous relation, since it consists of pairs where both elements are of the same set, ${A.}$ Explicitly listing its members:

\lset{ \eqs{ & (1,1) & (1,2) & \\ & (1,3) & (1,4) & \\ & (2,2) & (2,4) & \\ & (3,3) & (4,4) & \\ } }

Other examples of homogenous relations include ${\reals^2}$ and ${\reals^3.}$ Homogenous relations are particularly important because (1) they're the simplest relations to work with (the domain and the range are the same), and (2) they provide a medium for examining the properties of relations. Before we examine these properties, we introduce some special homogenous relations.

Heterogenous Relations

In contrast to homogenous relations, heterogenous relations are relations over two different sets ${X}$ and ${Y.}$ For these relations, we call the set ${X}$ the relation's domain, and ${Y}$ the relation's codomain. Heterogenous relations introduce several new types of relations.

For the first few types of relations, we'll stick to homogenous relations. That is, a relation ${R}$ on a single set called the domain of discourse ${\DD.}$ Starting with left-unique relations, we'll start using heterogenous relations, but it's important to keep in mind that for such relations, we can have ${X = Y.}$

Types of Relations

We now examine the various types of relations. As it turns out, there are many different types.

The Empty Relation

Because relations are simply sets of tuples, it follows that relations are sets. As such, there's a special relation called the empty relation — the relation that contains no members.

empty relation. Let ${X}$ be a set. The empty relation on ${X}$ is defined as:

\nil_{X} = \set{(x,y) \in X : x~\nil_{X}~y}

Reflexive Relations

The is equal to relation on the set of real numbers is an example of a reflexive relation — every real number is equal to to itself. Let's see a visual example. In the diagram below, the colored cells are members of a relation ${R_r.}$

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

The relation ${R_r}$ is an example of a reflexive relation — a relation containing all the pairs resulting from pairing each domain element with itself.

reflexive relation. A relation ${R}$ on a domain of discourse ${\DD}$ is a reflexive relation if, and only if:

${\forall a \in \DD \ix{(a,a) \in R}.}$

Or, equivalently:

For all ${a \in \DD,}$ ${a \rel a.}$

Note that definition of reflexivity does not prevent a relation from having other pairs. For example, both of these relations are reflexive:

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

However, the moment we're missing one of self-pairs, the relation is no longer reflexive. For example, all of the relations below are not reflexive:

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

We can also visualize relations with graphs. For example, the graphs below are all visual representations of a reflexive relation:

Irreflexive Relations

In the diagram below, the red cells are elements that are not members of a relation called ${R_i.}$

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

As long as the relation has this property, we say that it's irreflexive. If someone tells us that a relation ${R}$ is irreflexive, then they're essentially saying, "No matter how hard you search through ${R,}$ you'll never find an identity pair."

irreflexive relation. A relation ${R}$ on a domain of discourse ${\DD}$ is an irreflexive relation if, and only if:

${\forall a \in \DD \ix{(a,a) \notin R}.}$

Or, equivalently,

For all ${a \in \DD,}$ ${a \nrel a.}$

Importantly, reflexivity and irreflexivity are not opposites of one another. For example, the following relation is neither reflexive nor irreflexive:

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

Why? Because (1) it's nonreflexive because it doesn't contain all the pairs whose elements relate to themselves, and (2) it's nonirreflexive because some of the relation's pairs are elements relating to themselves.

Below are two graphs of irreflexive relations. Notice for both graphs, there are no loops.

Quasi-reflexive Relations

Consider the following relation. To the left is its tabular representation, and to the right is its corresponding graph.

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

This is an example of a relation that's neither reflexive nor irreflexive. We call such relations quasi-reflexive relations — a relation where some of the elements relate to themselves, and others do not. There are two kinds of quasi-reflexive relations. Left-quasi-reflexive relations:

left-quasi-reflexive relation. A relation ${R}$ on a domain of discourse ${\DD}$ is left-quasi-reflexive if, and only if:

${\forall a,b \in \DD \ix{(a,b) \in R \nc (a,a) \in R}.}$

Or, equivalently,

For all ${a,b \in \DD,}$ if ${a \rel b,}$ then ${a \rel a.}$

and right-quasi-reflexive relations:

right-quasi-reflexive relation. A relation ${R}$ on a domain of discourse ${\DD}$ is right-quasi-reflexive if, and only if:

${\forall a,b \in \DD \ix{(a,b) \in R \nc (b,b) \in R}.}$

Or, equivalently,

For all ${a,b \in \DD,}$ if ${a \rel b,}$ then ${b \rel b.}$

Symmetric Relations

Below, the colored cells are members of a relation called ${R_s:}$

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

${R_s}$ is an example of a symmetric relation. The basic idea is, if we reach into the relation and find:

(a,b)

then we can expect to later get:

(b,a)

Here's one definition:

symmetric relation. A relation ${R}$ on a domain of discourse ${\DD}$ is symmetric if, and only if:

${\forall a,b \in \DD \ix{(a,b) \in R \nc (b,a) \in R}}$

Or, equivalently,

For all ${a,b \in \DD,}$ if ${a \rel b,}$ then ${b \rel a.}$

Antisymmetric Relations

Beloow, the teal-colored cells are members of a relation called ${R_a,}$ and the and the red-colored cells are members not in ${R_a.}$

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

This is an example of an antisymmetric relation. The idea is, if someone tells us that a relation is antisymmetric, then:

If we reach into the relation and find the pair:
$(a,b)$
and ${a \neq b,}$ then we won't find a pair
$(b,a).$

Here's an explicit definition:

antisymmetric relation. A relation ${R}$ on a domain of discourse ${\DD}$ is antisymmetric if, and only if:

${\forall a,b \in \DD \ix{((a,b) \in R \land a \neq b) \nc (b,a) \notin R}}$

Or, equivalently,

For all ${a,b \in \DD,}$ if ${a \rel b}$ and ${a \neq b,}$ then ${b \nrel a.}$

Alternatively:

${\forall a,b \in \DD \ix{((a,b) \in R \land (b,a) \in R) \nc a = b}.}$

For all ${a,b \in \DD,}$ if ${a \rel b}$ and ${b \rel a,}$ then ${a = b.}$

Asymmetric Relations

If a relation ${R}$ is both antisymmetric and irreflexive, we say that ${R}$ is an asymmetric relation.

asymmetric relation. A relation ${R}$ on a domain of discourse ${\DD}$ is asymmetric if, and only if:

${\forall a,b \in \DD \ix{(a,b) \notin R \lor (b,a) \notin R}}$

Or, equivalently,

For all ${a,b \in \DD,}$ then ${a \nrel b}$ or ${b \nrel a.}$

Note that this is a very different type of relation from the antisymmetric relation. With the antisymmetric relation, we allow ${(a,b) \in R}$ and ${(b,a) \in R,}$ provided that ${a = b.}$ The asymmetric relation says if we have an ${(a,b) \in R,}$ we'd better not have a ${(b,a) \in R,}$ whether or not ${a = b.}$

Transitive Relations

When we see an argument of the form:

(1) ${R \subseteq S \times S.}$

(2) ${a, b, c \in S.}$

(3) ${a \rel b}$ and ${b \rel c.}$

(4) Therefore, ${a \rel c}$

then we can deduce that ${R}$ is a transitive relation.

transitivite relation. A relation ${R}$ on a domain of discourse ${\DD}$ is transitive if, and only if:

${\forall a,b,c \in \DD \ix{((a,b) \in R \land (b,c) \in R) \nc (a,c) \in R}}$

Or, equivalently,

For all ${a,b,c \in \DD,}$ if ${a \rel b}$ and ${b \rel c,}$ then ${a \rel c.}$

Intransitive Relations

Relations that are not transitive are called intransitive relations.

intransitive relation. A relation ${R}$ on a domain of discourse ${\DD}$ is intransitive if, and only if:

${\forall a,b,c \in \DD \ix{(~(a,b) \in R \land (b,c) \in R~) \nc (a,c) \notin R}.}$

Or, equivalently,

For all ${a,b,c \in \DD,}$ if ${a \rel b}$ and ${b \rel c,}$ then ${a \nrel c.}$

Left-total Relations

A left-total relation is defined as follows:

left-total relation. Let ${X}$ and ${Y}$ be sets, and ${R}$ a relation from ${X}$ to ${Y.}$ Then ${R}$ is a left-total relation if, and only if,

${\forall x \in X \ix{\exists y \in Y : (x,y) \in R}.}$

That is,

for all ${x \in X,}$ there exists a ${y \in Y}$ such that ${x \rel y.}$

Right-total Relations

A right-total relation is defined as follows:

right-total relation. Let ${X}$ and ${Y}$ be sets, and ${R}$ a relation from ${X}$ to ${Y.}$ Then ${R}$ is a right-total relation if, and only if,

${\forall y \in Y \ix{\exists x \in X : (x,y) \in R}.}$

That is,

for all ${y \in Y,}$ there exists an ${x \in X}$ such that ${x \rel y.}$

Comparable Relations

If a relation ${R}$ has the property of comparability, we say that ${R}$ is a comparabe relation or a strongly-connected relation.

comparable relation. A relation ${R}$ on a domain of discourse ${\DD}$ is comparable if, and only if:

${\forall a,b \in \DD \ix{(a,b) \in R \lor (b,a) \in R}}$

Or, equivalently,

For all ${a,b \in \DD,}$ ${a \rel b}$ or ${b \rel a.}$

Connex Relations

If a relation ${R}$ has the connex property, we say that ${R}$ is a connected relation or a connex relation.

connex. A relation ${R}$ on a domain of discourse ${\DD}$ is a connex relation if, and only if:

${\forall a,b \in \DD \ix{(a \neq b) \nc (a,b) \in R \lor (b,a) \in R}.}$

Or, equivalently,

For all ${a,b \in \DD,}$ if ${a \neq b,}$ then ${a \rel b}$ or ${b \rel a.}$

Incomparable Relations

If a relation ${R}$ has the property of incomparability, we say that ${R}$ is incomparable.

incomparability relation. A relation ${R}$ on a domain of discourse ${\DD}$ is incomparable if, and only if:

${\forall a,b \in \DD \ix{(a,b) \notin R \land (b,a) \notin R}}$

Or, equivalently,

For all ${a,b \in \DD,}$ ${a \nrel b}$ and ${b \nrel a.}$

Right Euclidean Relation

A right Euclidean relation is defined as follows:

right euclidean relation. A relation ${R}$ on a domain of discourse ${\DD}$ is right Euclidean if, and only if,

${\forall a,b,c \in \DD \ix{ (a,b), (a,c) \in R \nc (b,c) \in R }}$

Or, equivalently,

For all ${a,b,c \in R,}$ if ${a \rel b}$ and ${a \rel c,}$ then ${b \rel c.}$

Left Euclidean Relation

A left Euclidean relation is defined as follows:

left euclidean relation. A relation ${R}$ on a domain of discourse ${\DD}$ is left Euclidean if, and only if,

${\forall a,b,c \in \DD \ix{ (b,a), (c,a) \in R \nc (b,c) \in R }}$

Or, equivalently,

For all ${a,b,c \in R,}$ if ${b \rel a}$ and ${c \rel a,}$ then ${b \rel c.}$

Equivalence Relations

Earlier, we saw the relations:

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

	${a}$	${b}$	${c}$
${a}$	${(a,a)}$	${(a,b)}$	${(a,c)}$
${b}$	${(b,a)}$	${(b,b)}$	${(b,c)}$
${c}$	${(c,a)}$	${(c,b)}$	${(c,c)}$

Both of these are examples of equivalence relations.

equivalence relation. A relation ${\equiv}$ on a domain of discourse ${A}$ is an equivalence relation if, and only if:

${a \equiv a}$ reflexivity,
${a \equiv b}$ implies ${b \equiv a}$ symmetry, and
${a \equiv b}$ and ${b \equiv c}$ implies ${a \equiv c}$ transitivity.

Equivalence relations are a formalization of "sameness." Former U.S. presidents are all different people, but they're all equivalent (i.e., "the same") in terms of being former U.S. presidents. The equivalence relation between all of them is former U.S. president. Apples and oranges are the same in terms of being fruits.

Equivalence Class

If a object ${x}$ is related to an object ${y}$ by an equivalence relation, we say that ${x}$ and ${y}$ are equivalent, and write ${x \equiv y.}$ We say this earlier in our discussion of equivalence relations. Often, it's helpful to gather all the objects equivalent to some object ${x}$ into a single set. We call this set the equivalence class of ${x.}$

equivalence class. Let ${\equiv}$ be an equivalence relation on the domain of discourse ${\DD,}$ and ${a \in \DD.}$ Then the equivalence class of ${a}$ is defined as the set:

\class{a}_{\equiv}~~:=~~\set{b \in \DD : b \equiv a}

Given an element ${c \in \class{a}_{\equiv},}$ ${c}$ is called a representative of the equivalence class. Note that some authors denote the equivalence class with the notation ${\ix{a}.}$ Because we use this notation in another area of mathematics — combinatorics — we instead use the notation ${\class{a}_{\equiv}.}$

Partial Orders

Below is the definition of a partial order. Note that there's some new notation being used here. The symbol ${\preceq}$ is a generic symbol for a relation that can be replaced with ${\lt,}$ ${\le,}$ ${\prec,}$ ${=,}$ etc. The symbol ${\prec}$ means "immediately precedes" and the notation ${\succ}$ means "immdiately succeeds." These are useful notations when we're discussing comparisons between objects that aren't necessarily numbers. For example, if we define the tuple

(\text{George I}, \text{George II}, \text{George III})

as the partial order of British kings by reign, then we may denote the relation as:

\text{George I} \prec \text{George II} \prec \text{George III}.

Such a relation would be read as, "George I immediately precedes George II, and George II immediately precess George III." We could, of course, write:

\text{George I} \lt \text{George II} \lt \text{George III}

but it looks a bit awkward, given that the ${\lt}$ is commonly associated with numbers, the Georges aren't numbers (unless we define them as purely regnal numbers), and we risk offending some historian saying, "George I is less than George II ..." As such, we use the weaker symbol ${\preceq}$ to denote some hint of order.

partial order. A relation ${\preceq}$ on a domain of discourse ${\DD}$ is called a partial order if, and only if, for all ${a,b,c \in \DD,}$

If ${a \preceq b}$ and ${b \preceq c,}$ then ${a \preceq c}$ (transitivity), and
If ${a \preceq b}$ and ${b \preceq a,}$ then ${a = b.}$ (antisymmetry).

Partial orders come in three subtypes: weak partial orders, strong partial orders, and full orders.

Weak Partial Orders

A weak partial order is defined as follows:

weak partial order. A relation ${\preceq}$ on a domain of discourse ${X}$ is called a weak partial order if, and only if, for all ${a,b,c \in \DD}$

${a \preceq a,}$
If ${a \preceq b}$ and ${b \preceq c,}$ then ${a \preceq c}$ (transitivity), and
If ${a \preceq b}$ and ${b \preceq a,}$ then ${a = b.}$ (antisymmetry).

As we can see from the definition, weak partial orders are what allow us to define the notion of "less than or equal to."

Strong Partial Orders

Strong partial orders are what give us the notion of less than and greater than:

strong partial order. A relation ${\prec}$ on a domain of discourse ${\DD}$ is called a strong partial order if, and only if, for all ${a,b,c \in \DD}$

${a \not\prec a}$ (irreflexivity),
If ${a \prec b,}$ then ${b \not\prec a}$ (asymmetry), and
If ${a \prec b}$ and ${b \prec c,}$ then ${a \prec c}$ (transitivity).

A classic example of the strong partial order is the ${\lt}$ relation.

Total Order

A total order is defined as follows:

total order. A relation ${\leq}$ on a domain of discourse ${\DD}$ is called a total order if, and only if, for all ${a,b,c \in \DD}$

${a \leq a,}$ (transitivity),
${a \leq b}$ or ${b \leq a,}$ (comparability),
If ${a \leq b}$ and ${b \leq c,}$ then ${a \leq c}$ (transitivity), and
If ${a \leq b}$ and ${b \leq a,}$ then ${a = b.}$ (antisymmetry).

Preorders

Preorders are a particularly useful kind of relation that we'll use extensively later.

preorder. Let ${\lesssim}$ be relation on the domain of discourse ${\DD.}$ Then ${R}$ is called a preorder if, and only if, for all ${a,b,c \in \DD,}$

${a \lesssim a}$ (reflexivity), and
If ${a \lesssim b}$ and ${b \lesssim c,}$ then ${a \lesssim c}$ (transitivity).

The name preorder comes from the fact that preorders are "almost" partial orders. They have the property of transitivity, but not antisymmetry.

Posets

Partial orders lead to another kind of mathematical object called the poset. Posets are defined as a tuple ${(S,R),}$ where ${S}$ is domain of discourse, and ${R}$ is a relation. This is likely our first encounter with a definition of this form. As we'll see later (and throughout all of the volumes on this site), it is extremely common in mathematics to define objects as tuples:

(\text{set}, \text{relation})

(\text{set}, \text{function})

(\text{set}, \text{operation})

(\text{set}, \text{functions})

(\text{set}, \text{set}, \text{functions})

(\text{set}, \text{operations})

In fact, there's an entire field of mathematics dedicated to studying the way we construct these definitions, called abstract algebra.

poset. Let ${\preceq}$ be a partial order on a set ${P.}$ Then the tuple ${P = (P,\preceq)}$ is called a poset (or partially ordered set) if, and only if, for all ${a,b,c \in P:}$

${a \preceq a}$ (reflexivity),
if ${a \preceq b}$ and ${b \preceq a,}$ then ${a = b}$ (antisymmetry), and
if ${a \preceq b}$ and ${b \preceq c,}$ then ${a \preceq c}$ (transitivity).

Posets are a much weaker notion of ordering (hence the name partial order). A poset can be ordered, but not necessarily. This is because posets impose no requirement for comparability.

Astute readers might have noticed something slightly off about posets. They're a bit, well, redundant. We could've just simply written:

\dom{\preceq}

When it comes to notation in mathematics, however, ${\text{tradition} \preceq \text{reason}.}$

Minimal and Maximal Elements

Below are the definitions of minimal and maximal elements. Minimals and maximals are much weaker notions of "minimum" and "maximum." A minimal ${m \in S}$ , informally, is an element that does not precede any other element of ${S.}$ That doesn't necessarily make it the smallest element. Why? Becuse posets, by definition, aren't necessarily comparable.

maximal element. Let ${(A, \preceq)}$ be a poset. Then an element ${b \in A}$ is a maximal element if, and only if,

there is no ${a \in A}$ such that ${b \preceq a.}$

If the above condition is satisfied, we write:

\text{maximal}{(A)} = b

The definition of a minimal element:

minimal element. Let ${(A,\preceq)}$ be a poset. Then an element ${b \in A}$ is a minimal element if, and only if:

there is no ${a \in A,}$ such that ${a \preceq b.}$

If the above condition is satisfied, we write:

\text{minimal}{(A)} = b

Chains

Chains are a stronger form of the poset.

chain. Let ${\le}$ be a partial order on a set ${L.}$ Then the tuple ${L = (L,\le)}$ is called a chain, if, and only if, for all ${a,b,c \in L,}$

${a,b \in L,}$ ${a \le b}$ or ${b \le a,}$ (comparability),
${a \le a}$ (reflexivity),
if ${a \le b}$ and ${b \le a,}$ then ${a = b}$ (antisymmetry), and
if ${a \le b}$ and ${b \le c,}$ then ${a \le c}$ (transitivity).

Like the poset, what we call a chain is simply the domain of a total order. Tradition, once again, calls upon us to use a specific term.

Lower Bound and Upper Bound

Here is the definition for lower bound:

lower bound. Let ${P}$ be a poset ${(P,\preceq),}$ and ${S \subseteq P.}$ If there exists an element ${\mathcal{a} \in P}$ such that:

for all ${s \in S,}$ ${\mathcal{a} \preceq s,}$

then ${\mathcal{a}}$ is called the lower bound of ${S,}$ which we denote as:

a \in S^{\ell}

where ${S^{\ell}}$ is the set of all lower bounds of ${S.}$

And the definition of an upper bound:

upper bound. Let ${P}$ be a poset ${(P, \preceq),}$ and ${S \subseteq P.}$ If there exists an element ${\mathcal{a} \in P}$ such that:

for all ${s \in S,}$ ${s \preceq \mathcal{a},}$

then ${\mathcal{a}}$ is called the upper bound of ${S,}$ which we denote as:

a \in S^{u}

where ${S^u}$ is the set of all upper bounds of ${S.}$

Infimum and Supremum

From the definition of a lower bound, we get another relation called the infimum:

infimum. Let ${(P,\preceq),}$ be a poset and ${S \subseteq P.}$ If:

there exists an element ${\texttt{i} \in S^{\ell},}$ and
for all ${s \in S^{\ell},}$ ${\texttt{i} \preceq s,}$

then we say the element ${\texttt{i} \in S}$ is the infimum of ${S.}$ To denote the infimum ${\texttt{i},}$ we may use any of the following notations:

\inf(S) = \bigwedge\limits_{\texttt{i} \in S} \texttt{i} = \texttt{i}

The symbol ${\bigwedge}$ is often called "big wedge" after its LaTeX command, \bigwedge. The benefit to using this notation is that it falls in line with the using the notation ${x \land y,}$ which returns the infimum of ${(x,y).}$ Those familiar with symbolic logic might recognize this as the and operator. Indeed, when ${x,y \in \set{0 := \string{false},1 := \string{true}},}$ it becomes apparent why ${\land}$ is an attractive notation. Given ${0 \land 1,}$ we get ${0,}$ or ${\string{false}.}$

Likewise, the definition of an upper bound gives us another relation called the supremum.

supremum. Let ${(P,\preceq)}$ be a poset and ${S \subseteq P.}$ If:

there exists an element ${\texttt{b} \in S^{u}}$ and
for all ${s \in S^{u},}$ ${s \preceq \texttt{b},}$

then we say the element ${\texttt{b} \in S}$ is the supremum of ${S.}$ To denote the supremum ${\texttt{b},}$ we may use any of the following notations:

\sup(S) = \bigvee\limits_{\texttt{b} \in S} \texttt{b} = \texttt{b}

Mimimum and Maximum

The maximum of a set ${P}$ is defined as follows:

minimum. Let ${(P,\preceq)}$ be a poset. If:

there exists an element ${\ell \in P,}$ such that
for all ${p \in P,}$ ${\ell \preceq p,}$

then ${\ell \in P}$ is the minimum of ${P,}$ denoted:

\min{(P)} = \ell

and the minimum of a set ${P:}$

maximum. Let ${(P,\preceq)}$ be a poset. If:

there exists an element ${u \in P,}$ such that
for all ${p \in P,}$ ${u \preceq b,}$

then ${u \in P}$ is the minimum of ${P,}$ denoted:

\max{(P)} = u

Well-ordered Relations

Now that we have the definition of minimal and maximal elements, we can define an extremely useful relation called a well ordering.

well ordering. Let ${R}$ be a on the domain of discourse ${\DD.}$ If, and only if,

${R}$ is a total order, and
every non-empty subset of ${\DD}$ has a minimum,

then ${R}$ is a well-ordered relation.

Left-unique Relations

A left-unique relation is defined as follows:

left-unique relation. Let ${X}$ and ${Y}$ be sets, and ${R}$ a relation from ${X}$ to ${Y.}$ Then ${R}$ is left-unique if, and only if,

${(\forall x,z \in X \land \forall y \in Y)\ix{ ((x,y) \in R \land (z,y) \in R) \nc x = z }.}$

That is,

For all ${x,z \in X}$ and for all ${y \in Y,}$ if ${x \rel y}$ and ${z \rel y,}$ then ${x = z.}$

Right-unique Relations

A right-unique relation (also called a univalent relation), is defined as follows:

right-unique relation. Let ${X}$ and ${Y}$ be sets, and ${R}$ a relation from ${X}$ to ${Y.}$ Then ${R}$ is right-unique if, and only if,

${(\forall x,z \in X \land \forall y \in Y)\ix{ ((x,y) \in R \land (z,y) \in R) \nc y = z }.}$

That is,

For all ${x,z \in X}$ and for all ${y \in Y,}$ if ${x \rel y}$ and ${z \rel y,}$ then ${y = z.}$

As we'll see later, the right-unique relation is a key component in the definition of functions.

Maps

Another type of relation is the map; also called mapping, assignment, function, operation, or transformation. While the latter terms are often used interchangeably, we take a bit more care in using the words and distinguish them by definition. In these materials, we will say that map, assignment, and mapping are synonymous, but function, operation, and transformation are special kinds of maps.

map. Let ${A,}$ ${B,}$ and ${\Gamma}$ be sets, such that ${\Gamma \subseteq A \times B.}$ Then the triple:

f = (A, B, \Gamma)

is a map if, and only if

For each ${a \in A,}$ there is exactly one ${b \in B}$ with ${(a,b) \in \Gamma.}$

We write ${f(a)}$ for this unique ${b,}$ and call it the value of ${f}$ at ${a}$ (or the image of ${a}$ under ${f}$ ). We say that ${A}$ is the domain of ${f,}$ ${B}$ the codomain of ${f,}$ and ${\Gamma}$ the graph of ${f.}$ We write:

f : A \to B

to indicate that ${f}$ is a map from ${A}$ to ${B.}$

Visualizing the map relation as a graph, all of the following are maps:

But the following are not: