Club Sets and Fodor's Lemma

Jun 2014
650
54
USA
I'm trying to obtain a better understanding of what a club set is to get started. I understand what it means for a set to be unbounded with respect to a limit ordinal $\kappa$, but I'm having trouble grasping what it means for a set to be closed in $\kappa$:

https://en.wikipedia.org/wiki/Club_set

"If $\kappa$ is a limit ordinal, then $C \subseteq \kappa$ is closed if and only if for every $\alpha < \kappa$, if $sup(C \cap \alpha) = \alpha \neq 0$, then $\alpha \in C$."

According to Noah Schweber here both $\{evens\}$ and $\{odds\}$ are club in $\omega$.

According to Wiki, the set of countable limit ordinals is club with respect to $\omega_1$.

Question:

How is it that $\{evens\}$ and $\{odds\}$ are closed in $\omega$ as Noah states? We have $sup(\alpha) = \alpha - 1$ for any $\alpha < \omega$, so I don't understand how $sup(C \cap \alpha) = \alpha \neq 0$ could hold true for any $\alpha < \omega$.
 
Oct 2009
942
367
I'm trying to obtain a better understanding of what a club set is to get started. I understand what it means for a set to be unbounded with respect to a limit ordinal $\kappa$, but I'm having trouble grasping what it means for a set to be closed in $\kappa$:

https://en.wikipedia.org/wiki/Club_set

"If $\kappa$ is a limit ordinal, then $C \subseteq \kappa$ is closed if and only if for every $\alpha < \kappa$, if $sup(C \cap \alpha) = \alpha \neq 0$, then $\alpha \in C$."

According to Noah Schweber here both $\{evens\}$ and $\{odds\}$ are club in $\omega$.

According to Wiki, the set of countable limit ordinals is club with respect to $\omega_1$.

Question:

How is it that $\{evens\}$ and $\{odds\}$ are closed in $\omega$ as Noah states? We have $sup(\alpha) = \alpha - 1$ for any $\alpha < \omega$, so I don't understand how $sup(C \cap \alpha) = \alpha \neq 0$ could hold true for any $\alpha < \omega$.
Yep, so it is a vacuous condition that always holds. Any subset of $\omega$ is closed.
 
  • Like
Reactions: 1 person
Jun 2014
650
54
USA
Got it. Thank you.

With respect to Fodor's lemma:

If $(C_{\alpha})_{\alpha < \omega_1}$ is a sequence of club sets, the diagonal intersection $C = \Delta_{\alpha < \omega_1}C_{\alpha}$ is itself a club set.

Fodor's lemma hinges on the diagonal intersection of the club sets being another (uncountable) club set (given the uncountable cofinality of $\omega_1$).

I believe I am then correct to state, equivalently, that the least element of $C$ is equal to the least common fixed point between some sequence of normal functions $(f_{\alpha})_{\alpha < \omega_1}$ where the range of each $f_{\alpha}$ is equal to $C_{\alpha}$. I say this because each club set is itself just the range of some normal function that will inevitably have a fixed point and the diagonal intersection is the intersection of all the common fixed points, correct?

The uncountable cofinality of $\omega_1$ is what keeps the theory from being trivial, but is it also what allows us to assert that the least common fixed point of the functions $(f_{\alpha})_{\alpha < \omega_1}$ must be countable? In other words, do we know the least common fixed point must always be countable or is it possible, absent our notion of cofinality, that the least common fixed point could actually be $\omega_1$ itself?
 
Aug 2012
2,496
781
Got it. Thank you.
I fail to understand that. In fact I came here tonight to post in support of your point that the $\sup$ of a finite ordinal (ie natural number) $\alpha$ is $\alpha - 1$. I came here to confess that I too am a little bit confused on that exact point.

Then @[email protected] posted a response that did not address this point and you responded by saying that @[email protected]'s response was satisfactory to you.

So I'm confused. Let me lay out my own confusion.

To make things concrete, what's the $\sup$ of 14? Well 14 is the set {0, 1, 2, 3, 4, 5, 6, 7, 8,9,10, 11, 12, 13}. Now what is the sup of that set? Clearly 13. 13 is a number that is greater than or equal to each element of the set; and it's the least of all numbers with that property. But we know that the "right" answer is supposed to be 14. This mystery eludes me at the moment.

I did find this: "Union of Ordinals is Least Upper Bound":

https://proofwiki.org/wiki/Union_of_Ordinals_is_Least_Upper_Bound

which proves that the sup of 14 is 14. I didn't go through the proof, my eyes are glazing.

@Micro can you please supply whatever it is that's missing from my understanding? This must be obvious, right?

With respect to Fodor's lemma:
I'm struck by the weird vertical path you explore. You're slinging buzzwords from a level of set theory that you'd get to in your second graduate level course in set theory. You'd already be through Kunen (first edition's regarded as superior to the second) and understand the basics of forcing and independence results.

You plunge into this thicket of difficult (even for grad students in set theory) material, linking things together by intution and logic ...

And yet ... I admit this. You have a very good instincts. It's kind of bizarre but you do have some sort of sense for things far beyond your grasp.

You can find a pdf of Kunen. It might amuse you. Even the introductory material touches on the philosophical aspects and puts everything into a very clear context.

tl;dr: You convinced me that sup(14) = 13 but the right answer is 14 and I haven't the wit at this moment to figure it out. I have some mental block on something obvious.

Also @Micro didn't address this point AND you didn't mind at all. So I must have gotten a completely different point from your post than everyone else.
 
Last edited:
Oct 2009
942
367
I did find this: "Union of Ordinals is Least Upper Bound":

https://proofwiki.org/wiki/Union_of_Ordinals_is_Least_Upper_Bound

which proves that the sup of 14 is 14. I didn't go through the proof, my eyes are glazing.
Does it prove that? Maybe, I'm missing something, but essentially:
$$\bigcup\{0,1,2,3\} = 0\cup 1 \cup 2\cup 3 = \emptyset \cup \{0\}\cup \{0,1\}\cup\{0,1,2\} = \{0,1,2\} = 3.$$

So the union of 4 is 3. Same way, the least upper bound of 14 is 13.

A good thing too since note that any supremum in $\omega$ is actually a maximum. Claiming that $\sup 14 = 14$ would imply $14\in 14$, which would mean natural numbers are not well founded. This is a problem.

Likewise, let's take a set with $\bigcup A = A$. I don't actually know a complete characterization of these sets. I know they are transitive. I know that 0, but also any limit ordinal satisfies this. Interesting to think about...
 
Oct 2009
942
367
I'm struck by the weird vertical path you explore. You're slinging buzzwords from a level of set theory that you'd get to in your second graduate level course in set theory.
He sure has good instincts, but he needs to learn the foundations. This is why I refuse to interact much with him. He expects to be fed answers without him doing any real effort to communicate.
 
Jun 2014
650
54
USA
I fail to understand that. In fact I came here tonight to post in support of your point that the $\sup$ of a finite ordinal (ie natural number) $\alpha$ is $\alpha - 1$. I came here to confess that I too am a little bit confused on that exact point.
We have a statement saying that if condition A is met with respect to a particular $\alpha$, the element $\alpha$ must be in the club set $C$ (condition A is $sup(C\cap\alpha)=\alpha\neq0$). There is no statement saying what the result is if condition A is not met with respect to a particular $\alpha$ (meaning $\alpha$ may or may not be in $C$ if condition A isn't met). It's only when condition A is met that $\alpha$ must be in $C$. Where condition A cannot be met for any $\alpha$ less than $\omega$, it's impossible to find an $\alpha$ where the condition was met but $\alpha$ wasn't in $C$, so we are assured $C$ must be club.

Does that help you?
 
Jun 2014
650
54
USA
He sure has good instincts, but he needs to learn the foundations. This is why I refuse to interact much with him. He expects to be fed answers without him doing any real effort to communicate.
I don't intend on going back to school for math, but I may get a phd in Accounting that would have me cranking out some statistics no doubt. Right now I have a Masters in Accounting and Taxation along with my CPA license, but since I don't ever intend to put in "the effort" in your perspective, perhaps you would consider that there is no effort to put in from mine. It's all for fun and all I'm doing is making a real effort to communicate. It may sound like crap, as though I'm learning the violin and will often hit bad notes, but it doesn't mean I'm not making an effort.

You on the other hand don't need to make any effort either. The only purpose for you being here is that maybe I say something interesting to you, or that teaching me helps solidify your own understanding and therefore helps you. Maybe you just feel good about helping others with Math. Either way is fine with me because your motives don't matter to me. If possible, I would like to keep you happy and amused the same way I want world peace, so let's just hope.
 
Jun 2014
650
54
USA
The enumeration of $\epsilon_0$ below can be used to demonstrate Fodor’s lemma if, for $\alpha > 0$, we say:
$$\phi(\alpha) = \begin{cases}
(\mu,\beta,\gamma) & \text{if Rule } \alpha \text{ : } (\mu,\beta,\gamma) \implies \{\alpha\} \text{ and } \mu,\beta,\gamma < \alpha \\
(0,0,0) & \text{if Rule } \alpha \text{ : } (\mu,\beta,\gamma) \implies \{\alpha\} \text{ and } \mu,\beta, \text{ or } \gamma \geq \alpha \\
\end{cases}$$

Let $Ord$ denote the class of all ordinals and let each $Ord_{\alpha}$ be a subclass of ordinals such that $(Ord_{\alpha})_{\alpha \in Ord}$ forms a partition of $Ord$. The transfinite sequence $(Ord_{\alpha})_{\alpha \in Ord}$ is defined as follows:

$Ord_0$ is the class of ordinals that are not limit ordinals.
$Ord_{\alpha} = (K, <)$, where $<$ is the standard ordering and $K = \{ x_j : (x_j, <)_{j \in Ord} \text{ well orders } Ord \setminus \bigcup_{\kappa < \alpha} Ord_{\kappa} \text{ and } j \text{ is not a limit ordinal} \}$.

Note that where $\alpha \geq \omega$ we need $u,v < \alpha$ for each $(\alpha)_{u,v}$ to be successful.

$$\begin{matrix}
Ord_0 \text{ : } & 0_{0,0} & 1_{0,1} & 2_{0,2} & \dots & (\omega + 1)_{0,\omega} & (\omega + 2)_{0,\omega+1} & (\omega + 3)_{0,\omega+2} & \dots & (\omega \cdot 2 + 1)_{0,\omega \cdot 2} & (\omega \cdot 2 + 2)_{0,\omega \cdot 2 + 1} & (\omega \cdot 2 + 3)_{0,\omega \cdot 2 + 2} & \dots\\

Ord_1 \text{ : } & (\omega)_{1,0} & (\omega \cdot 2)_{1,1} & (\omega \cdot 3)_{1,2} & \dots & (\omega^2 + \omega)_{1,\omega} & (\omega^2 + \omega \cdot 2)_{1,\omega+1} & (\omega^2 + \omega \cdot 3)_{1,\omega+2} & \dots & (\omega^2 \cdot 2 + \omega)_{1,\omega \cdot 2} & (\omega^2 \cdot 2 + \omega \cdot 2)_{1,\omega \cdot 2 + 1} & (\omega^2 \cdot 2 + \omega \cdot 3)_{1,\omega \cdot 2 + 2} & \dots \\

Ord_2 \text{ : } & (\omega^2)_{2,0} & (\omega^2 \cdot 2)_{2,1} & (\omega^2 \cdot 3)_{2,2} & \dots & (\omega^3 + \omega^2)_{2,\omega} & (\omega^3 + \omega^2 \cdot 2)_{2,\omega + 1} & (\omega^3 + \omega^2 \cdot 3)_{2,\omega + 2} & \dots & (\omega^3 \cdot 2 + \omega^2)_{2,\omega \cdot 2} & (\omega^3 \cdot 2 + \omega^2 \cdot 2)_{2,\omega \cdot 2 + 1} & (\omega^3 \cdot 2 + \omega^2 \cdot 3)_{2,\omega \cdot 2 + 2} & \dots\\
\vdots \\

Ord_{\omega} \text{ : } & (\omega^{\omega})_{\omega,0} & (\omega^{\omega} \cdot 2)_{\omega,1} & (\omega^{\omega} \cdot 3)_{\omega,2} & \dots & (\omega^{\omega} \cdot \omega + \omega^{\omega})_{\omega,\omega} & (\omega^{\omega} \cdot \omega + \omega^{\omega} \cdot 2)_{\omega,\omega + 1} & (\omega^{\omega} \cdot \omega + \omega^{\omega} \cdot 3)_{\omega,\omega + 2} & \dots & (\omega^{\omega} \cdot \omega \cdot 2 + \omega^{\omega})_{\omega,\omega \cdot 2} & (\omega^{\omega} \cdot \omega \cdot 2 + \omega^{\omega} \cdot 2)_{\omega,\omega \cdot 2 + 1} & (\omega^{\omega} \cdot \omega \cdot 2 + \omega^{\omega} \cdot 3)_{\omega,\omega \cdot 2 + 2} & \dots\\

\vdots \\

\exists Ord_{\alpha} \text{ : } & (\alpha)_{\alpha,0} \in Ord_{\alpha} & <------ \text{Oops!!!!}\\

\vdots

\end{matrix}$$


The following rules are for a $T$ sequence that enumerates $\epsilon_0$:

$$\text{Rule 1 : } \mu = 3, \beta = 2, \gamma = 1 \implies \{0\}$$
$$\text{Rule } \alpha \text{ : } \mu = 0, \beta = 1, \gamma = \alpha - 1 \implies \{\alpha\}, \text{ where } 2 \leq \alpha < \omega$$
$$\text{Rule } \alpha \text{ : } \mu = 0, \beta = u, \gamma = v \implies \{\alpha_{u,v}\}, \text{ where } \alpha \geq \omega$$
Each $Ord_{\alpha}$ can be associated with a normal function $f_{\alpha}$, the range of which is a club set $C_{\alpha} = Ord \setminus \bigcup_{\gamma \leq \alpha} Ord_{\alpha}$. For example, with respect to $Ord_0$, the set of countable limit ordinals $C_0 = \{ \omega \cdot \alpha : \alpha \in Ord \}$ and $f_0(\alpha) = \omega \cdot \alpha$ are the relative club set and normal function, respectively. For $Ord_1$, we have $C_1 = \{ \omega^2 \cdot \alpha : \alpha \in Ord \}$ and $f_1(\alpha) = \omega^2 \cdot \alpha$.

For any particular ordinal $\alpha$ where $0 < \alpha < \omega_1$, note that:
$$\alpha \not\in C_{\delta} \text{ for any particular } \delta < \alpha \implies (\alpha)_{\beta,\gamma} : \beta, \gamma < \alpha \implies (\text{Rule } \alpha \text{ is capable of extending the sequence by asserting } (0,\beta,\gamma) \implies \{\alpha\})$$
$$\alpha \in C_{\delta} \text{ for each } \delta < \alpha \implies (\alpha)_{\beta,\gamma} : \beta \geq \alpha \implies (\text{Rule } \alpha \text{ is not capable of extending the sequence by asserting }(0,\beta,\gamma) \implies \{\alpha\})$$

Note that $\epsilon_0$ is a fixed point of each $f_{\alpha}$ such that $\alpha < \epsilon_0$. In fact, it is the least fixed point that is a common fixed point across all the functions $(f_{\alpha})_{\alpha < \epsilon_0}$. Equivalently, $\epsilon_0$ is the least element of $C = \Delta_{\alpha < \omega_1}C_{\alpha}$ and the first element for which Fodor's lemma asserts a constant $\phi(\epsilon_0) = (0,0,0)$ must be assigned.



I just said you need to... study how things are done in math.
And just how are things done in math anyways? I have to ask... I assume we start with axioms and go on to prove theorems. The end, IMHO.

Maybe you believe in the old "we could train you to be a manager in 6 months or less but you should probably work as a teller for 15 years first just because the managers before you had to" philosophy. That is a really crappy philosophy for math though, as building on the work of others instead of having to relearn it all from scratch is the ideal that is accomplished via optimized means of communication (thank goodness for the internet!).

In any case, here is the effort I've put in. Via my silly $T$ sequences, I have now learned about:

1) Ordinal arithmetic & Cantor normal form
2) Normal functions
3) Fixed points
4) Cofinality
5) Ackerman Ordinal
6) Veblen Hierarchy, Large and Small Veblen Ordinals
7) Church-Kleene Ordinal and Kleene's $\mathcal{O}$
8) Stationary sets
9) Club sets (closed and unbounded sets)
10) Diagonal intersections
11) Fodor's lemma
12) Some expanded philosophy

After all this, I still just want someone to answer my basic question:

https://math.stackexchange.com/questions/3401372/question-regarding-ordinals#3401372

Where my $\phi : \omega_1 \rightarrow \omega_1^3$, there may be a way for my $\phi$ to exist even though Fodor shows no regressive $\phi : \omega_1 \rightarrow \omega_1$ can exist.

PS - I use triplets, but we could use doublets, quadruplets, quintuplets, etc., until we got to $\omega$-lets for lack of a better way to put it, in which case we would be building towards a set that must be equal in cardinality to $\mathcal{P}(\mathbb{N})$ is how far I may choose to pursue this...
 
Last edited: