arrows relation

Let [X]α={YX|Y|=α}, that is, the set of subsets of X of size α. Then given some cardinals κ, λ, α and β


states that for any set X of size κ and any function f:[X]αβ, there is some YX and some γβ such that |Y|=λ and for any y[Y]α, f(y)=γ.

In words, if f is a partitionMathworldPlanetmathPlanetmath of [X]α into β subsets then f is constant on a subset of size λ (a homogeneousPlanetmathPlanetmath subset).

As an example, the pigeonhole principleMathworldPlanetmath is the statement that if n is finite and k<n then:


That is, if you try to partition n into fewer than n pieces then one piece has more than one elementMathworldMathworld.

Observe that if


then the same statement holds if:

  • κ is made larger (since the restrictionPlanetmathPlanetmathPlanetmathPlanetmath of f to a set of size κ can be considered)

  • λ is made smaller (since a subset of the homogeneous set will suffice)

  • β is made smaller (since any partition into fewer than β pieces can be expanded by adding empty setsMathworldPlanetmath to the partition)

  • α is made smaller (since a partition f of [κ]γ where γ<α can be extended to a partition f of [κ]α by f(X)=f(Xγ) where Xγ is the γ smallest elements of X)


is used to state that the corresponding relationMathworldPlanetmath is false.


Title arrows relation
Canonical name ArrowsRelation
Date of creation 2013-03-22 17:48:54
Last modified on 2013-03-22 17:48:54
Owner Henry (455)
Last modified by Henry (455)
Numerical id 5
Author Henry (455)
Entry type Definition
Classification msc 05A18
Classification msc 03E05
Related topic PartitionsLessThanCofinality
Related topic ErdosRadoTheorem
Defines homogeneous
Defines arrows
Defines homogeneous set
Defines homogeneous subset