Partition Relation

From GM-RKB
Jump to: navigation, search

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

2019a

2019b

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

      Let [math]\Bbb S[/math] be a partition of a set [math]S[/math].

      Let [math]\mathcal R \subseteq S \times S[/math] be the relation defined as:

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

      Then [math]\mathcal R[/math] is the (equivalence) relation induced by (the partition) [math]\Bbb S[/math].

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.

1986

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) [math]\quad a \to (b_o ,\cdots, \hat{b}_n)'\quad \left(\text{or: } a\to (b_v)^r_{r\lt n})\right)[/math]

      The relation (1) expresses the fact that whenever

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

      then there are a number [math]v\lt n[/math] and a set [math]X \subset S[/math] such that

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

      More simply, this means that (2) implies that

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

.