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.
- AKA: Equivalence Relation Induced by Partition.
- Example(s):
- Counter-Example(s):
- See: Relation Theory, Partition Calculus, Partition of a Set, Partitional Clustering Algorithm.
References
2019a
- (Beers, 2019) ⇒ Jonathon Eric Beers (2019). "A Comparison of Pair and Triple Partition Relations". arXiv:1904.07790.
- QUOTE: Definition 9 (Partition Relations for Ordinals). Let [math]\displaystyle{ \alpha }[/math] be an ordinal, [math]\displaystyle{ r }[/math] a nonzero finite ordinal, [math]\displaystyle{ I }[/math] any indexing set, and for all [math]\displaystyle{ i \in I }[/math] let [math]\displaystyle{ \beta_i }[/math] be an ordinal. Then the partition relation
[math]\displaystyle{ \alpha \to (\beta_i)^r_{i\in I} }[/math]
pertains if and only if for all sets [math]\displaystyle{ A }[/math] such that [math]\displaystyle{ ot(A) = \alpha }[/math] and for all r-partitions [math]\displaystyle{ \mathcal{X} }[/math] of [math]\displaystyle{ A }[/math] in [math]\displaystyle{ I }[/math] colors there exists some [math]\displaystyle{ i \in I }[/math] and some [math]\displaystyle{ B \subseteq A }[/math] such that [math]\displaystyle{ ot(B) = \beta_i }[/math] and [math]\displaystyle{ \mathcal{x}([B]^r ) \subseteq {i} }[/math].
- QUOTE: Definition 9 (Partition Relations for Ordinals). Let [math]\displaystyle{ \alpha }[/math] be an ordinal, [math]\displaystyle{ r }[/math] a nonzero finite ordinal, [math]\displaystyle{ I }[/math] any indexing set, and for all [math]\displaystyle{ i \in I }[/math] let [math]\displaystyle{ \beta_i }[/math] be an ordinal. Then the partition relation
2019b
- (Proof Wiki, 2019) ⇒ https://proofwiki.org/wiki/Definition:Relation_Induced_by_Partition Retrieved:2019-05-17.
- QUOTE: Let [math]\displaystyle{ S }[/math] be a set.
Let [math]\displaystyle{ \Bbb S }[/math] be a partition of a set [math]\displaystyle{ S }[/math].
Let [math]\displaystyle{ \mathcal R \subseteq S \times S }[/math] be the relation defined as:
[math]\displaystyle{ \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]\displaystyle{ \mathcal R }[/math] is the (equivalence) relation induced by (the partition) [math]\displaystyle{ \Bbb S }[/math].
- QUOTE: Let [math]\displaystyle{ S }[/math] be a set.
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
- (Kanamori, 1986) ⇒ Akihiro Kanamori (1986). "Partition relations for successor cardinals". Advances in Mathematics, 59(2), 152-169. DOI:10.1016/0001-8708(86)90049-6
- QUOTE: Let us reaffirm some notation. For [math]\displaystyle{ X }[/math] a set of ordinals and [math]\displaystyle{ \alpha }[/math] an ordinal, [math]\displaystyle{ [X]^{\alpha} }[/math] denotes the set of subsets of [math]\displaystyle{ X }[/math] with order type [math]\displaystyle{ \alpha }[/math].
(i) The ordinary partition relation of Erdos and Rado for ordinals [math]\displaystyle{ \alpha \to \left(\beta\right)^n_{\delta} }[/math] asserts that whenever [math]\displaystyle{ f: [\alpha]^n \to \delta }[/math], there are an [math]\displaystyle{ X\in [\alpha]^\beta }[/math] and a [math]\displaystyle{ \rho\lt \delta }[/math] such that[math]\displaystyle{ f”[X]^n= \{\rho\} }[/math].
- QUOTE: Let us reaffirm some notation. For [math]\displaystyle{ X }[/math] a set of ordinals and [math]\displaystyle{ \alpha }[/math] an ordinal, [math]\displaystyle{ [X]^{\alpha} }[/math] denotes the set of subsets of [math]\displaystyle{ X }[/math] with order type [math]\displaystyle{ \alpha }[/math].
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]\displaystyle{ \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]\displaystyle{ |S|=a;\quad [S]'=I_0+\cdots+\hat{I}_n }[/math]then there are a number [math]\displaystyle{ v\lt n }[/math] and a set [math]\displaystyle{ X \subset S }[/math] such that
[math]\displaystyle{ |X| =b_v\quad[X]^r \subset I_v }[/math]More simply, this means that (2) implies that
- QUOTE: We define the ordinary partition relation (I-relation) as follows
.