3
$\begingroup$

Is the following provable and how? I feel like I am missing some proof technique or strong theorems, I'd be grateful for any pointer.

Let $(I, \leq)$ be an upwards-directed poset. Define an $f: I \to \{a,b\}$ such that $f$ is not eventually constant.

Upwards-directed ("every path can be recombined"): $\forall i_1, i_2 \in I\ \exists j \in I.\quad j \geq i_1, j \geq i_2$.

Eventually constant ("a path on which $f$ is constant"): $\exists C \in \{a, b\}\ \exists i \in I\ \forall j \geq i.\quad f(j) = C$

If $I = (\mathbb{N}, \leq)$ with the usual ordering, then my solution would be:

Set $f(0) := a$ and inductively choose $f(n + 1) \neq f(n)$.
Or put differently, define $f$ recursively by $$f(n) = \begin{cases} a &, n = 0 \\ \mathrm{flip}(f(n-1)) &, n > 0. \end{cases}$$

In general, if $I$ is wellordered, then such a (non-constructive) definition by transfinite recursion works.

What if $I$ is not wellordered? While the set $I$ can always be wellordered, that assigned order is not necessarily compatible with the old order.


The question popped up while attempting an exercise in Dr. Pete L. Clark's notes on nets & filters in topology, p. 10f., exercise 3.1.11. It asks readers to prove the following statement:

Within a topology $X$ we have: $$x \text{ is an isolated point} \Leftrightarrow \text{every net converging to } x \text{ is eventually constant}$$

$\Rightarrow$ is clear to me, my attempted solution for the rest:

For the direction $\Leftarrow$ I'd like to show the contraposition $$x \text{ is not isolated} \Rightarrow \exists \text{ net } f \text{ converging to x, which is not eventually constant.}$$

$x$ is not isolated, hence every neighborhood of $x$ has at least two elements. Define $f: (\mathcal{V}(x), \supseteq) \to X$ mapping neighborhoods to one of their elements, so that $f$ is not eventually constant (how?).

$\endgroup$
2
$\begingroup$

Since you tagged this question under , I'd like to add some information about that as well.

Theorem. It is consistent that there is a linearly ordered set without a maximal element, where every net which takes finitely many values is eventually constant.

The proof, of course, relies on a technical construction. Mostowski proved it is consistent to have a linear order which is dense, without end points, and every subset is a finite union of intervals.

Let $(I,\leq)$ be such linear order. Take $f\colon I\to\{0,\dots,n\}$ be any function. Then $A_i=f^{-1}(i)$ is a finite union of intervals for each $i\leq n$. If $f$ is not eventually constant, then there is some $i\leq n$ such that $A_i$ contains infinitely many intervals (every time you switch from $i$ to a different value, and back), so this is impossible.

Therefore every net is eventually constant in this case. $\square$

(This proof extends to define the term as a Läuchli continuum.)

So we need some modicum of choice in order to prove the theorem you're talking about. But we do not need to well-order $I$ or anything. We just need to split $I$ into two cofinal sets, which is far weaker, of course. Choice makes it easier, of course: well-order the set, and by transfinite recursion construct the two sets: each step add the element with the least index which is not bounded by some member of your set, and zigzag between the two sets.

$\endgroup$
  • $\begingroup$ ME Rudin's approach to proofs: well-order everything in sight! $\endgroup$ – Henno Brandsma Dec 18 '18 at 22:40
1
$\begingroup$

In order for the statement to be true, you need $(I, \le)$ to have no maximal elements; however, you don't need it to be upwards-directed—except perhaps to make sense of 'eventually constant'. The only assumption you need is that $(I, \le)$ is a poset with no maximal elements.

What follows is a proof—admittedly not a particularly elegant one—that if $(I, \le)$ is an arbitrary poset with no maximal elements, then there is a function $f : I \to \{ a, b \}$ such that, for all $C \in \{ a, b \}$ and all $i \in I$, there is some $j \ge i$ such that $f(j) \ne C$.

Every partial order $\le$ extends to a total order $\le_{\text{t}}$—that is, if $(I, \le)$ is a partially ordered set, then there is a total order $\le_{\text{t}}$ on $I$ such that if $i \le j$, then $i \le_{\text{t}} j$. The proof of this fact isn't entirely trivial (see here for example) and it depends on the axiom of choice, which is fine by me if it's fine by you. Note furthermore that if $(I, \le)$ has no maximal elements, then neither does $(I, \le_{\text{t}})$.

But then if $(I, \le_{\text{t}})$ is a totally ordered set, you can take some cofinal sequence $(i_{\gamma} \mid \gamma < \alpha)$ in $(I, \le_{\text{t}})$, where $\alpha$ is (necessarily) some limit ordinal, and then define $f : I \to \{ a, b \}$ by letting $f(i) = a$ if $i \ne i_{\gamma}$ for any $\gamma < \alpha$ or if $i=i_{\gamma}$ for some limit ordinal $\gamma < \alpha$, and letting $f(i_{\gamma+1}) = \mathrm{flip}(f(i_{\gamma}))$ for all $\gamma < \alpha$. You can then verify that $f$ is non-eventually-constant on $(I, \le)$.

Addendum: A neater and (slightly) more elementary approach under the assumption that $(I, \le)$ is upwards-directed is to simply avoid extending $\le$ to a total order. In this case, the fact that $(I, \le)$ itself has a cofinal sequence follows from the fact that it is upwards-directed.

$\endgroup$
  • $\begingroup$ Do you have a reference or a short explanation of the notation $(i_\gamma | \gamma < \alpha)$? Having never worked with ordinals before, your definition of $f$ stills seems a bit informal to me. What is the underlying principle? E.g. via transfinite recursion, existence and uniqueness of a solution can be proven. $\endgroup$ – ComFreek Dec 18 '18 at 14:12
  • 1
    $\begingroup$ @ComFreek: There might be too much to explain if you've never used ordinals before. A cofinal sequence $(i_{\gamma} \mid \gamma < \alpha)$ in $(I, \le_{\text{t}})$ is just a well-ordered (with respect to $\le_{\text{t}}$) subset of $I$, such that for each $i \in I$, there is some element of the subset that is $\ge i$. The existence and uniqueness of the function $f : (I, \le_{\text{t}}) \to \{ a, b \}$ as defined follows from transfinite recursion (in much the same way that the existence of the $f : \mathbb{N} \to \{ a, b \}$ in your question follows from regular recursion on $\mathbb{N}$). $\endgroup$ – Clive Newstead Dec 18 '18 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.