User - MathOverflow

Partitions of central sets via dynamical systems

2013-02-01T09:35:08Z

In the book "Recurrence in Ergodic Theory and Combinatorial Number Theory", 1981, Furstenberg introduced the notion of central sets.

He proved in Theorem 8.8 that in each finite partition of $\mathbb{N}$, $\mathbb{N}=B_1 \cup B_2 \cup \dots \cup B_q$ one of the sets $B_j$ contains a central set. Then he states without proof that the same is true for partitions of central sets and that one can prove this "along the same lines" as Theorem 8.8 (p. 163).

I know that this fact follows immediately from the characterization of central sets by minimal idempotent ultrafilters. However, this is obviously not the proof that Furstenberg had in mind 1981 as this characterization was not available then. Thus my question:

How can one prove in the fashion of Theorem 8.8, i.e. using only tools recurrence in dynamical systems, that for each finite partition of a central set $S$, $S=B_1 \cup B_2 \cup \dots \cup B_q$ one of the $B_j$ contains a set that is again central?

For the sake of reference I include the necessary definitions and the proof of Theorem 8.8 below.

Let $(X,T)$ be a dynamical system. $x_1,x_2\in X$ are proximal if for some sequence $n_k\to \infty$, $d(T^{n_k}x_1,T^{n_k}x_2) \to 0$. A point $x\in X$ is called uniformly recurrent if for each neighborhood $U$of $x$, the sequence of values $n_1 < n_2 < \dots$, for which $T^{n_k}x\in U$, satisfies that $\{ n_{k+1}-n_k \}$ is bounded.

As set $S$ is called central if there is a $x,y\in X$ and a neighborhood $U$ of $y$ such that $y$ is uniformly recurrent and proximal to $x$ and $S=\{ n : T^nx\in U \}$.

The only tools we need for the proof Theorem 8.8 is then the Auslander-Ellis Theorem (Theorem 8.7) which reads as follows. If $(X,T)$ is a dynamical system an $X$ is compact. Then every point $x$ in $X$ is proximal to a uniformly recurrent point.

Proof of Theorem 8.8:

Consider the dynamical system with $(\Omega,T)$ with $\Omega =\{ 1, \dots, q \}^\mathbb{Z}$ and $T$ the shift $T\omega(n)=\omega(n+1)$. Let $\xi\in\Omega$ be a point with $\xi(n)=i$ implies $n\in B_i$ for $n\in\mathbb{N}$.

Let now $\eta\in\Omega$ be a uniformly recurrent point proximal to $\xi$. This point exists by the Auslander-Ellis Theorem. Let $j=\eta(0)$ and set $U=\{ \omega : \omega(0)=j \}$ and let $S=\{n: T^n\xi\in U \}$. Clearly $S$ is central and if $n\in S$ then $\xi(n)=T^n\xi(0)=j$, so that $n\in B_j$ and thus $S\subseteq B_j$.

Answer by alexod for (Un)Decidability of the root existence problem for functions with bounded domain

2013-01-19T16:22:08Z

Suppose there is an algorithm that decides whether a function $f\colon \Omega \to \mathbb{R}$ has a root. Then one can also compute a root of $f$ if $f$ has one.

One can see this using a standard bi-partition argument: Cover $\Omega$ with finitely many balls of radius $1$. This is possible since the closure of $\Omega$ is compact. Then using the algorithm we can find a ball that contains a root of $f$. Then we cover this ball with balls of radius $2^{-1}$ and again find a smaller ball which contains a root...

Iterating this process yield a sequence converging to a root of $f$ with rate $2^{-n}$ or in other words a Cauchy-real representation for a root.

Now, finding a root for a function implies Brouwer's fixed point theorem.

To see that let $\Omega$ be bounded and closed and $g\colon \Omega \to \Omega$ continuous. $g$ has a fixed-point at any root of the function $f\colon \Omega \to \mathbb{R}$, $f(x):= \lvert g(x) - x\rvert$.

For Brouwers fixed point theorem it is known that there is no algorithm to find solutions, see for instance Computable counter-examples to the Brouwer fixed-point theorem, Petrus H. Potgieter.

Thus, we can conclude that there is no algorithm which decides whether a function has a root.

Answer by alexod for About the well ordering of finite sequences of numbers

2013-01-12T13:31:42Z

The statement that the indicated order on $\mathbb{N}^{<\mathbb{N}}$ is well-founded is incomparable with $B\Sigma_2$.

I will denote the order by $\prec$. The statement that $\prec$ is well-founded can written as the statement that each non-empty set $X$ contains a $\prec$-minimal element, i.e.

(1) $\forall X \left( \exists x \in X \rightarrow \exists y \left( y \in X \land \forall z \prec y\ z\notin X\right)\right)$.

It think it is clear that $B\Sigma_2$ does not imply (1). Therefore, I will just show that (1) does not imply $B\Sigma_2$. This will be done by constructing a first-order model and extend it to a model of $RCA_0 + (1)$ in which $B\Sigma_2$ fails.

Let $\phi_i$ be (1) where $X$ is replaced by the $i$-th $\Delta_1$-sentence. Each $\phi_i$ is $\Sigma_2$. By Theorem 1 of [1] there exists an instance of $B\Sigma_2$ which is not implied by $(\phi_i)$. (Note that the principle $FAC^\Pi_1$ there is equivalent to $B\Pi_1$ or $B\Sigma_2$.)

Thus, there is a first-order model of $I\Sigma_1+(\phi_i)_i+\neg B\Sigma_2$. Extending this model to a second-order model by taking all $\Delta_1$-sets as second-order part we arrive at the desired counter-example.

[1] Charles Parsons, On a Number Theoretic Choice Schema and its Relation to Induction, In: A. Kino, J. Myhill and R.E. Vesley, Editor(s), Studies in Logic and the Foundations of Mathematics, Elsevier, 1970, Volume 60, Pages 459-473, ISSN 0049-237X, ISBN 9780720422573, 10.1016/S0049-237X(08)70771-7. http://www.sciencedirect.com/science/article/pii/S0049237X08707717

Applications of infinite Ramsey's Theorem (on N)?

2010-01-18T17:52:32Z

Finite Ramsey's theorem is a very important combinatorial tool that is often used in mathematics. The infinite version of Ramsey's theorem (Ramsey's theorem for colorings of tuples of natural numbers) also seems to be a very basic and powerful tool but it is apparently not as widely used.

I searched in the literature for applications of infinite Ramsey's theorem and only found

straight forward generalization of statements that follow from finite Ramsey's theorem (example: Erdos-Szekeres ~> every infinite sequence of reals contains a monotonic subsequence) and some other basic combinatorial applications,
Ramsey factorization for \omega-words,
the original applications of Ramsey to Logic.

Where else is infinite Ramsey's theorem used? Especially are there applications to analysis?

Sequence that converge if they have an accumulation point

2010-05-13T14:03:09Z

I am looking for classes of sequence, that converge iff they contain a converging sub-sequence.

The basic example of such sequences are monotone sequences of real numbers.
A more interesting examples comes from metric fixed point theory:
Let $B$ be a Banach space and $f\colon B \to B$ be a continuous mapping that is non-expansive (i.e. $\lVert f(x) - f(y)\rVert \le \lVert x -y\rVert$ ).
Define $x_{n+1} := \frac{1}{2} x_n + \frac{1}{2} f(x_n)$ for any startingpoint $x_0\in B$ . This is the so called Krasnoselski iteration.
One can show that any accumulation point $\tilde{x}$ of $(x_n)$ is a fixed point of $f$. Since $f$ is non-expansive, it follows that
$\lVert x_{n+1}-\tilde{x}\rVert = \frac{1}{2}\lVert (x_{n}-\tilde{x}) + (f(x_{n}) - f(\tilde{x}))\rVert\le \lVert x_n -\tilde{x}\rVert$ .
Hence $(x_n)$ converges iff it contains a converging sub-sequence.

This is a special case of Ishikawa's fixed point theorem. (The Krasnoselski-Mann iteration - a generalization of the Krasnoselski iteration - also has this property.)

I am interested in this sequence because they provide very nice applications of the Bolzano-Weierstrass principle.

Do you know of any other examples of sequences with this property?
Do you know other proofs that uses this property together with the Bolzano-Weierstrass principle to prove the convergence of a sequence?

Comment by

2013-04-26T20:11:10Z

I do not know whether this is what you are looking for but Keita Yokoama used non-standard analysis to analyze the strength of the Riemann mapping theorem in terms of reverse mathematics, see math.tohoku.ac.jp/~y-keita/papers/…

Comment by

2013-02-01T15:09:51Z

Asaf: The sets $S,S′$ are clearly central. But I do not see why this implies that $\{ s_{n′} \mid n′\in S′ \}$ is central. However, this might be what Hillel was thinking about. Maybe there is just an argument missing

Comment by

2013-02-01T12:21:37Z

@Gabor: your right that should be 0, thank you. It is now corrected.

Comment by

2013-01-19T18:23:32Z

@François thank you, I missed that point.

Comment by

2011-11-26T22:17:26Z

In arxiv.org/abs/0709.4364 Heunen, Landsman and Splitters construct a sheaf over a C*-algebras for quantum logic. But I don't know whether their construction differs from your definition.

Comment by

2010-05-20T14:18:47Z

@Steven your right [0,1] is not a boolean algebra

Comment by

2010-05-15T18:45:28Z

Dear Neel, I am little bit confused: Is there a difference between "logical relations" and structural induction over the types of your term system?

Comment by

2010-05-14T06:23:28Z

@Henno: you are right - this even seems to hold for any ultra-limit and the sequence converging to it. I was hoping for a more constructive way to find such sequences, but this is definitely an answer to the first question.

Comment by

2010-05-08T08:50:56Z

@Tran The compactness argument only proves the finite version of Ramsey's theorem from the infinite one. The infinite Ramsey's theorem is proof-theoretically stronger than the finite version. For instance finite Ramsey is provable in PA, where infinite Ramsey implies the Paris-Harrington variant, which is not provable there.

Comment by

2010-05-08T08:44:25Z

For c) I suppose if you apply a proof normalization (or cut elimination) to a proof of say a $\Pi^0_2$-statement in $ACA_0$, second order quantification will vanish and the proof will become first order.

Comment by

2010-01-19T10:42:54Z

This is a nice application of Ramsey's theorem, but as far as I can see they are could have used finite Ramsey's theorem if they would have calculated the size of the sets $\sigma_i$.