[FOM] Algebra and Ramsey Type Theorems

A. Mani a_mani_sc_gs at yahoo.co.in
Tue Nov 13 11:52:46 EST 2007


On Tuesday 13 Nov 2007 5:47:15 am Dana Scott wrote:
> You wrote:
> > For example the theorem that "Every finite semigroup
> > has at least one idempotent" is essentially a Ramsey type
> > theorem (it can be proved as well by a simple contra-
> > diction argument).
>
> I didn't see the Ramsey argument.  Here is a pretty easy
> number-theoretic proof.  Is this what you had in mind?

>Let x be any element.  Since the total number of elements
>is finite, there are positive integers n and m where:

>        x^(2^(n + m)) = x^(2^m).

>Let y = x^(2^m).  We see y^(2^n) = y.  If n = 1, we are
>done.  If n > 1, than multiply both sides of the last
>equation by y^(2^n - 2).  We conclude:

>        y^(2^n) y^(2^n - 2) = y^(2^n -1),

> but the RHS = y^(2^n + 2^n - 2) = (y^(2^n -1))^2.
> So we have found an idempotent.  Q.E.D.
 
It is to be seen in a slightly round about way.

[n] = {1,2,...,n}; k-subset = subset with k elements 
A r-colouring of a set F is simply a map \eta :S \mapsto [r], so that it is a 
partition of F into r parts.

Let
#(S)=r
By the original Ramsey thm we have a N= n(2, r, 3) such that for any 
r-coloring of the 2-element subsets of [N], there is a 3-element subset all 
of whose 2-elements have the same color.

consider any sequence {x1, x2, ..., xN} of elems of S and the r-coloring \eta 
of the 2-elem subsets of [N] defined via
If 1=< i < j =< N, then \eta({xi, xj}) = xi xi+1 ...xj-1 \in S (product of 
elements in the semigroup)

Clearly we have a 3-elem subset {i, j, k} of [N] with i < j < k s.t.

\eta({xi,xj})=\eta({xj, xk})= \eta({xi, xk}) = a (say)

but the product of the first two is the third, so a^2 = a.

----------------------------------
Actually Furstenberg, H and Katznelson, Y. in particular proved some results 
in compact semigroups that make use of Ramsey Theory, but in algebra proper 
few results are seen as being Ramsey-type theorems.  


Best

A. Mani 


-- 
A. Mani
Member, Cal. Math. Soc



More information about the FOM mailing list