Sets and Relations

Sets

A set is a fundamental concept in mathematics, representing a collection of distinct objects. These objects are called elements or members of the set. Sets are usually denoted by capital letters, and their elements are enclosed within curly braces {}. The order of elements in a set does not matter, and each element can appear only once.

For example, the set of vowels in the English alphabet can be represented as V = {a, e, i, o, u}. The elements here are 'a', 'e', 'i', 'o', and 'u'.

Representation of Sets

Sets can be represented in two primary ways:

• Roster Form (or Tabular Form): In this form, all the elements of the set are listed within curly braces, separated by commas. The order of elements does not matter. Example: A = {1, 2, 3, 4, 5}
• Set-Builder Form: In this form, the elements of the set are described by a property that all elements must satisfy. The general form is {x | P(x)}, which reads as "the set of all elements x such that x has the property P". Example: B = {x | x is a positive integer and x < 10}. This set B contains all positive integers less than 10.

Types of Sets

• Empty Set (or Null Set): A set containing no elements. It is denoted by {} or $\emptyset$. Example: The set of all even numbers divisible by 3 and ending in 5.
• Singleton Set: A set containing exactly one element. Example: {5}, {a}
• Finite Set: A set whose elements can be counted or there is a one-to-one correspondence with the set of natural numbers up to some integer n. The number of elements is its cardinality. Example: The set of days in a week has a cardinality of 7.
• Infinite Set: A set that is not finite. Its elements cannot be counted in a finite number. Example: The set of natural numbers N = {1, 2, 3, ...}
• Universal Set (U): A set containing all possible elements under consideration in a particular context. All other sets are subsets of the universal set.

Set Operations

Several operations can be performed on sets to derive new sets. Let A and B be two sets.

• Union (A $\cup$ B): The union of two sets A and B is the set containing all elements that are in A, or in B, or in both. A $\cup$ B = {x | x $\in$ A or x $\in$ B} Example: If A = {1, 2, 3} and B = {3, 4, 5}, then A $\cup$ B = {1, 2, 3, 4, 5}.
• Intersection (A $\cap$ B): The intersection of two sets A and B is the set containing all elements that are common to both A and B. A $\cap$ B = {x | x $\in$ A and x $\in$ B} Example: If A = {1, 2, 3} and B = {3, 4, 5}, then A $\cap$ B = {3}.
• Difference (A - B or A \ B): The difference of two sets A and B is the set containing all elements that are in A but not in B. A - B = {x | x $\in$ A and x $\notin$ B} Example: If A = {1, 2, 3} and B = {3, 4, 5}, then A - B = {1, 2}. Note that B - A = {4, 5}.
• Complement (A'): The complement of a set A (with respect to a universal set U) is the set of all elements in U that are not in A. A' = U - A = {x | x $\in$ U and x $\notin$ A} Example: If U = {1, 2, 3, 4, 5, 6} and A = {1, 2, 3}, then A' = {4, 5, 6}.
• Symmetric Difference ($\Delta$ or A $\oplus$ B): The symmetric difference of two sets A and B is the set of elements which are in either of the sets, but not in their intersection. A $\Delta$ B = (A - B) $\cup$ (B - A) = (A $\cup$ B) - (A $\cap$ B) Example: If A = {1, 2, 3} and B = {3, 4, 5}, then A $\Delta$ B = {1, 2} $\cup$ {4, 5} = {1, 2, 4, 5}.

Properties of Set Operations

Let A, B, and C be subsets of a universal set U.

• Commutative Laws: A $\cup$ B = B $\cup$ A A $\cap$ B = B $\cap$ A
• Associative Laws: (A $\cup$ B) $\cup$ C = A $\cup$ (B $\cup$ C) (A $\cap$ B) $\cap$ C = A $\cap$ (B $\cap$ C)
• Distributive Laws: A $\cup$ (B $\cap$ C) = (A $\cup$ B) $\cap$ (A $\cup$ C) A $\cap$ (B $\cup$ C) = (A $\cap$ B) $\cup$ (A $\cap$ C)
• Identity Laws: A $\cup$ $\emptyset$ = A A $\cap$ U = A
• Idempotent Laws: A $\cup$ A = A A $\cap$ A = A
• Complement Laws: A $\cup$ A' = U A $\cap$ A' = $\emptyset$ (A')' = A
• De Morgan's Laws: (A $\cup$ B)' = A' $\cap$ B' (A $\cap$ B)' = A' $\cup$ B'
• Absorption Laws: A $\cup$ (A $\cap$ B) = A A $\cap$ (A $\cup$ B) = A

Cardinality of Sets

The cardinality of a finite set A, denoted by |A|, is the number of elements in the set.

For two finite sets A and B: |A $\cup$ B| = |A| + |B| - |A $\cap$ B|

For three finite sets A, B, and C: |A $\cup$ B $\cup$ C| = |A| + |B| + |C| - |A $\cap$ B| - |A $\cap$ C| - |B $\cap$ C| + |A $\cap$ B $\cap$ C|

These are known as the Principle of Inclusion-Exclusion.

Relations

A relation R from a set A to a set B is a subset of the Cartesian product A $\times$ B. The Cartesian product A $\times$ B is the set of all ordered pairs (a, b) where a $\in$ A and b $\in$ B.

If R is a relation from a set A to itself (i.e., R $\subseteq$ A $\times$ A), it is called a binary relation on A. We say that 'a' is related to 'b' (denoted as a R b) if the ordered pair (a, b) is in the relation R.

Example: Let A = {1, 2, 3} and B = {a, b}. A $\times$ B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}. A relation R from A to B could be R = {(1, a), (2, b), (3, a)}. Here, 1 is related to a, 2 is related to b, and 3 is related to a.

Example of a binary relation on A = {1, 2, 3}: Let R = {(1, 1), (1, 2), (2, 3), (3, 3)}. Here, 1 is related to 1, 1 is related to 2, etc.

Representation of Relations

Relations can be represented in several ways:

• Ordered Pairs: As a set of ordered pairs, like R = {(1, 1), (1, 2), (2, 3), (3, 3)}.
• Arrow Diagram: Visual representation showing elements of the domain and codomain, with arrows indicating the relationships.
• Matrix Representation: For a relation R from set A = {$a_1, a_2, ..., a_m$} to set B = {$b_1, b_2, ..., b_n$}, an m x n matrix M can be used. M_ij = 1 if ($a_i, b_j$) $\in$ R, and M_ij = 0 otherwise. For a relation on a set A, it's an n x n matrix. Example for R = {(1, 1), (1, 2), (2, 3), (3, 3)} on A = {1, 2, 3}: The matrix would be:

  	1	2	3
  1	1	1	0
  2	0	0	1
  3	0	0	1

• Graphical Representation: Similar to a directed graph where elements are nodes and relations are edges.

Properties of Relations

Let R be a binary relation on a set A. R is said to have certain properties:

• Reflexive: For every element a $\in$ A, (a, a) $\in$ R. (Every element is related to itself). Example: R = {(1, 1), (2, 2), (3, 3), (1, 2)} on A = {1, 2, 3}. This is reflexive. Counter-example: R = {(1, 1), (1, 2), (2, 3)} on A = {1, 2, 3}. Not reflexive because (2, 2) and (3, 3) are missing.
• Symmetric: If (a, b) $\in$ R, then (b, a) $\in$ R for all a, b $\in$ A. (If a is related to b, then b is related to a). Example: R = {(1, 2), (2, 1), (3, 3)} on A = {1, 2, 3}. This is symmetric. Counter-example: R = {(1, 2), (3, 3)} on A = {1, 2, 3}. Not symmetric because (1, 2) $\in$ R but (2, 1) $\notin$ R.
• Antisymmetric: If (a, b) $\in$ R and (b, a) $\in$ R, then a = b for all a, b $\in$ A. (If a is related to b and b is related to a, they must be the same element). This means a relation cannot have distinct ordered pairs (a, b) and (b, a) unless a=b. Example: R = {(1, 1), (2, 3), (3, 3)} on A = {1, 2, 3}. This is antisymmetric. Counter-example: R = {(1, 2), (2, 1), (3, 3)} on A = {1, 2, 3}. Not antisymmetric because (1, 2) $\in$ R and (2, 1) $\in$ R, but 1 $\neq$ 2.
• Transitive: If (a, b) $\in$ R and (b, c) $\in$ R, then (a, c) $\in$ R for all a, b, c $\in$ A. (If a is related to b, and b is related to c, then a must be related to c). Example: R = {(1, 2), (2, 3), (1, 3)} on A = {1, 2, 3}. This is transitive. Counter-example: R = {(1, 2), (2, 3)} on A = {1, 2, 3}. Not transitive because (1, 2) $\in$ R and (2, 3) $\in$ R, but (1, 3) $\notin$ R.

Equivalence Relations

A binary relation R on a set A is called an equivalence relation if it satisfies three properties:

1. Reflexive: (a, a) $\in$ R for all a $\in$ A.
2. Symmetric: If (a, b) $\in$ R, then (b, a) $\in$ R.
3. Transitive: If (a, b) $\in$ R and (b, c) $\in$ R, then (a, c) $\in$ R.

Equivalence relations partition a set into disjoint subsets called equivalence classes.

Equivalence Class: For an equivalence relation R on a set A, the equivalence class of an element a $\in$ A, denoted by [a], is the set of all elements x $\in$ A such that x is related to a by R. [a] = {x $\in$ A | (x, a) $\in$ R}

All equivalence classes for a given equivalence relation are either identical or disjoint. The collection of all distinct equivalence classes forms a partition of the set A.

Example: Let R be the relation "has the same remainder when divided by 3" on the set of integers Z. Let's check the properties for R:

• Reflexive: For any integer a, a has the same remainder as itself when divided by 3. So, (a, a) $\in$ R. (Reflexive).
• Symmetric: If a has the same remainder as b when divided by 3, then b has the same remainder as a when divided by 3. So, if (a, b) $\in$ R, then (b, a) $\in$ R. (Symmetric).
• Transitive: If a has the same remainder as b, and b has the same remainder as c when divided by 3, then a must have the same remainder as c. So, if (a, b) $\in$ R and (b, c) $\in$ R, then (a, c) $\in$ R. (Transitive).

Since R is reflexive, symmetric, and transitive, it is an equivalence relation.

The equivalence classes are: [0] = {..., -6, -3, 0, 3, 6, ...} (Numbers divisible by 3, remainder 0) [1] = {..., -5, -2, 1, 4, 7, ...} (Numbers with remainder 1 when divided by 3) [2] = {..., -4, -1, 2, 5, 8, ...} (Numbers with remainder 2 when divided by 3)

These three sets form a partition of the integers Z.

Partial Ordering Relations

A binary relation R on a set A is called a partial ordering (or partial order) if it satisfies three properties:

1. Reflexive: (a, a) $\in$ R for all a $\in$ A.
2. Antisymmetric: If (a, b) $\in$ R and (b, a) $\in$ R, then a = b.
3. Transitive: If (a, b) $\in$ R and (b, c) $\in$ R, then (a, c) $\in$ R.

If R is a partial order on A, then the pair (A, R) is called a partially ordered set (or poset).

In a poset, not all pairs of elements need to be comparable. If for two elements a and b, either (a, b) $\in$ R or (b, a) $\in$ R, then a and b are said to be comparable. If neither is true, they are incomparable.

If every pair of elements in a poset is comparable, it is called a total ordering (or linear ordering).

Example 1: The relation "less than or equal to" ($\leq$) on the set of real numbers R is a partial order.

• Reflexive: a $\leq$ a for all a $\in$ R.
• Antisymmetric: If a $\leq$ b and b $\leq$ a, then a = b.
• Transitive: If a $\leq$ b and b $\leq$ c, then a $\leq$ c.

This is also a total ordering because any two real numbers are comparable.

Example 2: The relation "divides" (denoted by |) on the set of positive integers Z$^+$ is a partial order. Let a | b mean "a divides b".

• Reflexive: a | a for all a $\in$ Z$^+$ (since a = a * 1).
• Antisymmetric: If a | b and b | a, then a = b. If a divides b, b = ka for some integer k. If b divides a, a = lb for some integer l. Substituting, a = l(ka) = (lk)a. Since a is a positive integer, lk = 1. Since k and l are positive integers, k=1 and l=1. Thus, b=a.
• Transitive: If a | b and b | c, then a | c. If b = ka and c = lb, then c = l(ka) = (lk)a. So a divides c.

This is a partial order. However, it's not a total order. For example, 2 and 3 are incomparable with respect to divisibility because 2 does not divide 3, and 3 does not divide 2.

Example 3: Consider the set A = {1, 2, 3, 4, 6, 12} and the relation "divides" on A. This is a poset. We can visualize this using a Hasse diagram.

Hasse Diagrams

A Hasse diagram is a graphical representation of a finite partially ordered set. It is a directed graph without loops and with edges drawn upwards, omitting transitive edges and the direction arrows (implied by the upward direction).

For the set A = {1, 2, 3, 4, 6, 12} with the "divides" relation:

• 1 divides every element. It is the minimum element.
• 12 is divisible by every element. It is the maximum element.
• Elements are placed at different vertical levels according to their "size" in the ordering.
• An edge is drawn from element 'a' to element 'b' if 'a' divides 'b' and there is no element 'c' such that 'a' divides 'c' and 'c' divides 'b'. (i.e., 'b' is the immediate successor of 'a').

The Hasse diagram would show: 1 at the bottom. Arrows upwards to 2 and 3. Arrows from 2 to 4 and 6. Arrows from 3 to 6 and 12. Arrows from 4 to 12. Arrows from 6 to 12. (Note: The actual drawing omits arrows and transitive relations like 1|6, 1|12, 2|12, 3|12).

Key elements in a poset that can be identified using Hasse diagrams include:

• Minimal element(s): Element(s) with no elements below them (except possibly themselves if reflexive).
• Maximal element(s): Element(s) with no elements above them.
• Least element: A minimal element that is smaller than or equal to all other elements.
• Greatest element: A maximal element that is larger than or equal to all other elements.
• Lattice: A poset where every pair of elements has a unique least upper bound (join) and a unique greatest lower bound (meet).