[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