A Ramseyan theorem and an infinite game (Q1185887)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A Ramseyan theorem and an infinite game |
scientific article |
Statements
A Ramseyan theorem and an infinite game (English)
0 references
28 June 1992
0 references
The Ramseyan theorem of the title asserts the following. Let \(k,n\in\omega\), and let \(I\) be an ideal over \(\omega\) such that there does not exist pairwise almost disjoint \(A_ \alpha\in I^ +\), \(\alpha<2^{\aleph_ 0}\). Then given \(f: [\omega]^{k+1}\to[\omega]^{\leq(n+1)}\), there is a strictly increasing sequence \(x_ i\in \omega\), \(i\in \omega\), with \(\bigcup\bigl\{f(x_ j,\dots,x_{j+k}): j\in \omega\bigr\}\in I\). The authors point out that the above condition on \(I\) is sufficient but not necessary. The theorem was motivated by the study of an infinite game. Given \(n\in \omega\) and \(f: \omega\to\omega+1\), define the two-person game \(G(\omega,f,n)\) as follows: I chooses \(B_ 0\in[\omega]^{<(2+f(0))}\); II answers by selecting \(W_ 0\in[\omega]^{\leq(n+1)}\); I chooses \(B_ 1\in[\omega]^{<(2+f(1))}\) with \(B_ 0\subset B_ 1\); II picks \(W_ 1\in[\omega]^{\leq(n+1)}\); etc. II wins if and only if \(\bigcup_{i\in\omega} B_ i\subseteq\bigcup_{i\in\omega} W_ i\). It is shown that if \(f\) is the constant function with value \(\omega\), then there are no \(k,n\in\omega\) for which II has a winning \((k+1)\)-tactic (i.e. a winning strategy that requires knowledge of only the most recent \(k+1\) choices of I) in \(G(\omega,f,n)\). However if \(f: \omega\to\omega\) is strictly increasing, then II has a winning \(1\)-tactic in \(G(\omega,f,0)\).
0 references
Ramsey theorem
0 references
free ideal
0 references
infinite game
0 references
winning strategy
0 references