# Partition Relation

A Partition Relation is a Equivalence Relation that states that for any Partition of a Set X there is a subset of X containing exactly one element from each part of the partition.

## References

### 2019b

• (Proof Wiki, 2019) ⇒ https://proofwiki.org/wiki/Definition:Relation_Induced_by_Partition Retrieved:2019-05-17.
• QUOTE: Let $S$ be a set.

Let $\Bbb S$ be a partition of a set $S$.

Let $\mathcal R \subseteq S \times S$ be the relation defined as:

$\forall (x, y) \in S \times S: (x, y) \in \mathcal R \iff \exists T \in \Bbb S: \{x, y\} \subseteq T$

Then $\mathcal R$ is the (equivalence) relation induced by (the partition) $\Bbb S$.

### 2019c

• (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Partition_of_a_set#Partitions_and_equivalence_relations Retrieved:2019-5-17.
• For any equivalence relation on a set X, the set of its equivalence classes is a partition of X. Conversely, from any partition P of X, we can define an equivalence relation on X by setting precisely when x and y are in the same part in P. Thus the notions of equivalence relation and partition are essentially equivalent.The axiom of choice guarantees for any partition of a set X the existence of a subset of X containing exactly one element from each part of the partition. This implies that given an equivalence relation on a set one can select a canonical representative element from every equivalence class.

### 1965

• (Erdos et al., 1965) ⇒ P. Erdos, A. Hajnal, and R. Rado (1965). "Partition relations for cardinal numbers". Acta Mathematica Hungarica, 16(1-2), 93-196.
• QUOTE: We define the ordinary partition relation (I-relation) as follows

(1) $\quad a \to (b_o ,\cdots, \hat{b}_n)'\quad \left(\text{or: } a\to (b_v)^r_{r\lt n})\right)$

The relation (1) expresses the fact that whenever

(2) $|S|=a;\quad [S]'=I_0+\cdots+\hat{I}_n$

then there are a number $v\lt n$ and a set $X \subset S$ such that

$|X| =b_v\quad[X]^r \subset I_v$

More simply, this means that (2) implies that

$b_v\in [I_v]_r$for some $v \lt n$

.