Relations, Partitions, Orderings

Question 1

Relation

Answer 1

A way of describing a specific kind of relationship among objects.

Question 2

Binary Relation

Answer 2

Subset of the Cartesian product X×X ={ (x,y) : x,y ∈ X }, a set of ordered pairs (x,y) of elements of X. We (sometimes) write aRb if (a,b) ∈ R

Question 3

Reflexive

Answer 3

(x,x) ∈ R for all x ∈ X

Question 4

Antireflexive

Answer 4

(x,x) ∉ R for all x ∈ X

Question 5

Symmetric

Answer 5

(y,x) ∈ R if and only if (x,y) ∈ R

Question 6

Anti-Symmetric

Answer 6

xRy and yRx then x = y

Question 7

Transitive

Answer 7

if xRy and yRz then xRz

Question 8

The Converse of a Relation

Answer 8

If R is a relation from a set A to a set B,given as a subset of A×B, then the subset {(b,a) ∈ B×A | (ab) ∈ R} is a relation from B to A, called the converse of R. The converse of every relation is defined, but might not be a function.

Question 9

||

Answer 9

Strictly defined

Question 10

Digraph (Directed Graph)

Answer 10

• If the relation is reflexive, then there is a loop at every vertex
• if the relation is symmetric, then each arrow will be accompanied by another arrow in the opposite direction, which means that the arrows can be dropped, and the resulting double edges replaced by single edges, to give an undirected graph.

The same sort of thing can be done for a relation R from a set X to a set Y. In this case the digraph or graph is bipartite, with every arrow or edge joining a vertex in X with a vertex in Y.

In both cases, he converse of the given relation R is obtained by reversing all the arrows.

Question 11

Equivalance Relation

Answer 11

A relation on a set X that is reflexive, symmetric and transitive.

Question 12

Equivalance Class

Answer 12

Let be an equivalence relation on a set X. For each x ∈ X, let us define [x] = {y ∈ X | x ∈ y} , the set of all y ∈ X that are equivalent to x under the relation ≈, with the class sometimes denoted X/≈.

If x≈y, [x]=[y], [x]∩[y], then [x], [y] are equivalent.

Any two distinct equivalence classes are disjoint (that is, they have no element in common).

Question 13

Well-defined functions

Answer 13

Let f be a function from a set X to a set Y and let be a subset of the power set P(X) consisting of non-empty subsets of X. Define a map f∶Ω→Y by f(A)=f(a) for some a∈A. Then the map f* is well-defined if f(x) = f(y) for any x,y in A.

Thus f* is well-defined if it is independent of the choice of the representative x of A, for all A∈Ω , that is, if choosing any y∈A in place of x gives the same value for f* (A).

Question 14

Partitions

Answer 14

A partition of a set X is a collection Ω of non-empty subsets of X such that (1) every two subsets Ω in are disjoint, that is, A∩B =∅ whenever A,B∈Ω with A≠B, and (2) the union of the subsets in Ω is X, so that every element of X lies in one of the sets in Ω.

If ≈ is an equivalence relation on a set X, then the equivalence classes under ≈ form a partition of X.

Conversely, any partition Ω of a set X induces an equivalence relation ≈ on X, given by x≈y if and only if x and y belong to the same member of Ω. This is easy to see/prove.

Question 15

Orderings

Answer 15

Some relations induce an ordering on the elements of a set. Obvious examples include < and ≤ (on N, Z, Q and R), plus others such as divides (on N) and⊆ (on P(X)).

Question 16

Total Orderings

Answer 16

A relation ≼ on a set X is called a total ordering (on X) if the following three conditions are satisfied for all x,y,z∈X:
(1) If x≼y and y≼z then x≼z;
(2) If x,y∈X then either x≼y or y≼x;
(3) If x≼y and y≼x then x=y. Note that conditions (1) and (3) say that is transitive and anti-symmetric, while condition (2) says that any two elements of X are comparable under (and also that is reflexive).

Question 17

Partial Orderings and Partially Ordered Sets

Answer 17

A relation ≼ on a set X is called a partial ordering (on X) if it is reflexive, anti-symmetric, and transitive. In this case we say that X is a partially ordered set under ≼, or that the pair (X,≼ ) is a partially ordered set, or poset.

Question 18

Diagrammatic Representation of Posets

Answer 18

If ≼ is a partial ordering on a set X, then we can draw (or visualise) ≼ by a digraph as before, or by a different kind of diagram, called a Hasse diagram (or sometimes a lattice diagram).

To construct this, we consider a refined version of ≼,which we denote by ≺,defined by x≺y if and only if x≼y but x≠y. Also, we say that z covers x if x≺z and there exists no y∈X such that x≺y≺z. (For example, on N we consider < in place of ≤, and we see that 3 covers 2, indeed n+1 covers n for all n∈N.)

Then we create the Hasse diagram for ≼ by taking as points the elements of X, and drawing a line upwards from a point p to a point q whenever q covers p.

Question 19

Special Types of Elements in Posets

Answer 19

Let P=(X,≼) be a partially ordered set.

(a) An element b∈X is called a maximal element of P if there exists no c∈X with b≺c, or a minimal element of P if there exists no a∈X with a≺b.

(b) An element m∈X is called a maximum (or greatest) element of P if x≼m for all x∈X, or a minimum (or least) element of P if m≼x for all x∈X.

(c) If A⊆X, then an element b∈X is called an upper bound for A in P if a b for all a∈A, or a lower bound for A in P if b≼a for all a∈A

Question 20

Lattice

Answer 20

A (combinatorial) lattice is a special kind of partially ordered set P = (X,≼), in which there exists a maximum element and a minimum element, and every two elements x and y in X have both a least upper bound (namely an element that is the least element of the (non-empty) set of all upper bounds for {x,y}) and a greatest lower bound (namely an element that is the greatest element of the (non-empty) set of all lower bounds for {x,y}).

Question 21

Boolean Algebras

Answer 21

A Boolean algebra is a particular kind of lattice (called a distributive
lattice) that is used for circuit design in electrical engineering.

Question 22

Hasse Diagram

Answer 22

A Hasse diagram is a graphical representation of the relation of elements of a partially ordered set (poset) with an implied upward orientation. A point is drawn for each element of the partially ordered set (poset) and joined with the line segment according to the following rules:

If p<q in a poset, then the point corresponding to p appears lower in the drawing than the point corresponding to q.

The two points p and q will be joined by line segment if p is related to q.