Skip to content

11.18 Partition

Equivalence

\(R\) is an equivalence relation on \(A\).

\(R\subset A\times A\), where \(R\) is:

  • reflexive,
  • symmetric,
  • transitive.

Equivalence class

Given \(x \in A\), we denote: \(x/R=\{y\in A:xRy\}\) which is the equivalence class of \(x\).

We denote: \(A/R=\{x/R:x\in A\}\) which is the set of equivalence classes.

Example

  1. image​

    In Example 1:

    \(1/R = \{1, 2, 3, 4\}=2/R = 3/R = 4/R.\)

    \(5/R = \{5\}.\)

    \(6/R=\{6,7,8\}=7/R=8/R.\)

    \(9/R=\{9,10\}=10/R\)

    \(A/R = \{\{1, 2, 3, 4\}, \{5\}, \{6, 7, 8\}, \{9, 10\}\} \subseteq \mathcal{P}(A).\)

  2. \(A = \mathbb{Z}, R =\equiv_3\)

    image​

    \(0/{\equiv}_3=\{n\in\mathbb{Z}:3\mid n-0\}=\left\lbrace3k:k\in\mathbb{Z}\right\rbrace=3/{\equiv}_3=6/{\equiv}_3=-3/{\equiv}_3=-6/{\equiv}_3.\)

    \(1/{\equiv}_3=\{n\in\mathbb{Z}:3\mid n-1\}=\left\lbrace3k+1:k\in\mathbb{Z}\right\rbrace=1/{\equiv}_3=4/{\equiv}_3=-2/{\equiv}_3.\)

    \(2/{\equiv}_3=\{n\in\mathbb{Z}:3\mid n-2\}=\left\lbrace3k+2:k\in\mathbb{Z}\right\rbrace=2/{\equiv}_3=5/{\equiv}_3=-1/{\equiv}_3.\)

    \(\mathbb{Z}/{\equiv}_3=\{0/{\equiv}_3,1/{\equiv}_3,2/{\equiv}_3\}.\)

Theorem

Let \(R\) be an equivalence relation on \(A\).

  1. \(x/R \neq \emptyset \quad \forall x \in A.\)

    Proof

    \(xRx \implies x \in x/R.\) So \(x/R \neq \emptyset.\)

  2. If \(xRy\), then \(x/R = y/R.\)

    Proof

    Suppose \(xRy.\) We first show that \(y/R \subseteq x/R.\)

    Given \(z \in y/R \implies yRz \implies xRz\) because \(R\) is transitive.

    So \(z \in x/R.\)

    Since \(R\) is symmetric, \(yRx.\) With the same proof, we can show that \(x/R \subseteq y/R.\)

    So \(x/R = y/R.\)

  3. If \(x \cancel R y\), then \(x/R \cap y/R = \emptyset.\)

    Proof

    Suppose that \(x \cancel R y.\) Assume that \(x/R \cap y/R \neq \emptyset.\)

    Take \(z \in x/R \cap y/R \implies xRz \wedge yRz.\)(\(yRz=zRy\)​)

    By transitivity, \(xRy.\) Contradiction!

  4. \(\bigcup_{x \in A} x/R = A.\)

    Proof

    Given \(x \in A\), we have \(x \in x/R\), and so \(x \in \bigcup_{y \in A} y/R.\)

Coming back to congruence

Given \(m \in \mathbb{N}\), we have defined \(\equiv_m.\)

Notation:
​\(x / {\equiv}_m\) is denoted \(\overline{x}\) (or \(\overline{x}_m\)).

\(\mathbb{Z} / {\equiv}_m\) is denoted \(\mathbb{Z}_m\) (or \(\mathbb{Z} / m\mathbb{Z}\)).

Theorem

  1. Given \(a \in \mathbb{Z}\), we have \(\overline{a} = \overline{r}\), where \(r\) is the remainder of the division of \(a\) by \(m.\)

    Proof

    Given \(a \in \mathbb{Z}\), we can express:
    ​\(a = qm + r, \quad 0 \leq r \leq m-1.\)

    Then \(a - r = qm\), so \(m \mid (a - r)\), i.e., \(a \equiv r \pmod{m}.\)

    By the previous theorem, \(\overline{a} = \overline{r}.\)​

  2. \(\mathbb{Z}_m = \{\overline{0}, \overline{1}, \dots, \overline{m-1}\}.\)

    This follows from 1), because \(r \in \{0, \dots, m-1\}.\)​

  3. If \(0\leq r\neq r^{\prime}\leq m-1\) are different integers, then \(\overline{r} \neq \overline{r'}.\)

    Suppose \(0\leq r<r^{\prime}\leq m-1\) and \(\overline{r} = \overline{r'}.\)

    Then \(r \equiv r' \pmod{m} \implies m \mid (r' - r).\)

    But \(0 \leq r' - r \leq m-1\), so \(r' - r = 0\), which implies \(r = r'.\)

    Contradiction!

Partition

Definition: Let \(A\) be a set. A partition of \(A\) is a collection \(\mathcal{P}\) of subsets \(X \subseteq A\) such that:

  1. \(X \neq \emptyset \quad \forall X \in \mathcal{P}.\)

  2. If \(X, Y \in \mathcal{P}\) are different, then \(X \cap Y = \emptyset.\)

  3. \(A = \bigcup_{X \in \mathcal{P}} X.\)

Example

If \(R\) is an equivalence relation on \(A\), we can create a partition: \(\mathcal{P} = \{x/R : x \in A\}.\)

This is a partition by a previous theorem.

More particularly:

\(\mathcal{P} = \{\{1, 2, 3, 4\}, \{5\}, \{6, 7, 8\}, \{9, 10\}\}\) is a partition of \(\{1, 2, 3, \dots, 10\}.\)

\(\mathcal{P} = \{\overline{0}_3, \overline{1}_3, \overline{2}_3\}\) is a partition of \(\mathbb{Z}.\)

Theorem

Let \(\mathcal{P}\) be a partition on \(A.\) Define \(xRy\) iff \(x, y\) belong to the same set of the partition.

Then \(R\) is an equivalence relation, and \(\mathcal{P} = A/R.\)

Proof

  • \(R\) is reflexive: ✓ \(xRx\) and \(x\) belongs to the same set of the partition.
  • \(R\) is symmetric: ✓ obvious.
  • \(R\) is transitive: ✓ Suppose \(xRy\) and \(yRz.\)

\(\implies \exists X, Y \in \mathcal{P}\) such that \(x, y \in X\) and \(y, z \in Y.\)

Now \(y \in X \cap Y \implies X = Y\) (根据定义 \(X,Y\) 要么空集 要么相等), so \(x, z \in X.\)

Thus, \(xRz.\)

Finally, \(x/R = \{y \in A : x, y \text{ belong to the same set of the partition}\}.\)

This is the element of \(\mathcal{P}\) that contains \(x.\)

Ordering relations

Definition

A relation \(R\) on \(A\) is called an ordering relation if it is transitive.

Example

  1. \(<\) or \(\leq\) on \(\mathbb{R},\)

  2. \(\subseteq\) on \(\mathcal{P}(X),\)

  3. \(\mid\) on \(\mathbb{Z}.\)

Anti-symmetric

A relation \(R\) on \(A\) is called anti-symmetric if \(xRy \wedge yRx \implies x = y.\)

Example

  1. \(\leq\) on \(\mathbb{R}.\)

  2. \(<\) on \(\mathbb{R}.\) (the antecedent is always false, then the statement is always true)

  3. \(\mid\) on \(\mathbb{N}.\)

Remark: \(\mid\) on \(\mathbb{Z}\) is not anti-symmetric, because \(3 \mid -3 \wedge -3 \mid 3\) but \(3 \neq -3.\)

Partial order

A relation \(R\) on a set \(A\) is called a partial order if it is:

  • reflexive,
  • anti-symmetric,
  • transitive.

In this case, we say that \(A\) is a partially ordered set (POSET).

Example

  1. \(\leq\) on \(\mathbb{R},\)

  2. \(\mid\) on \(\mathbb{N},\)

  3. \(\subseteq\) on \(\mathcal{P}(X).\)

A finite POSET can be represented by Hasse diagrams.

Example: Let \(X = \{1, 2, 3\}, \quad (\mathcal{P}(X), \subseteq)\) is a POSET.

image​

Immediate predecessor

In general, let \(A\) be a POSET. Given \(a \neq b \in A\), we say that \(a\) is an immediate predecessor of \(b\)

if \(aRb\) and there is not \(c \in A\) different from \(a, b\) such that \(aRc \wedge cRb.\)

Example

In the previous example, \(\{1, 3\}\) is an immediate predecessor of \(\{1, 2, 3\},\)
but it is not an immediate predecessor of \(\{1, 2\}.\)

Construction

To construct a Hasse diagram for a finite POSET \((A, R)\):

  1. If \(xRy\), then \(y\) will be depicted above \(x.\)

  2. We join \(x\) and \(y\) if \(x\) is an immediate predecessor of \(y.\)

Example

\(A = \{1, 2, 3, \dots, 10\}\) and \(R = ~\mid\)

image​

Conclusion

In general, a partial order \(R\) is denoted \(\leq.\)

Bound

Let \((A, \leq)\) be a POSET. Let \(B \subseteq A.\)

  1. \(a \in A\) is an upper bound for \(B\) if: \(a \geq b \quad \forall b \in B.\)

  2. \(a \in A\) is a lower bound for \(B\) if: \(a \leq b \quad \forall b \in B.\)

  3. \(a \in A\) is called a supremum of \(B\) if:

    • \(a\) is an upper bound.
    • If \(a'\) is another upper bound, then \(a \leq a'.\)

  4. \(a \in A\) is called an infimum of \(B\) if:

    • \(a\) is a lower bound.
    • If \(a'\) is another lower bound, then \(a' \leq a.\)

  5. \(a\in A\) is called a maximum for \(B\) if

    • \(a\in B\)
    • \(b\leq a\ \forall b\in B\ \text{ (or first element)}\)​

  6. \(a\in A\) is called a minimum for \(B\) if

    • \(a\in B\)​
    • \(a\leq b\ \forall b\in B\)​

Example

  1. Example: \(A = \mathbb{N}, \leq 1, B = \{1, 4, 6\}\).

    \(24\) is an upper bound.

  2. Example: \(A = \mathbb{N}, \leq 1, B = \{1, 4, 6\}\)

    A supremum is \(12\).

  3. Example: \(A = \mathbb{R}, \leq\) usual order.

    \(0\) is an infimum for \((0, 1)\) and also for \([0, 1]\).

  4. Example: \(1\) is a maximum for \([0,1]\) and \(0\) is minimum.

‍