Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: deprecated: logic

Topic: Tukey's Lemma

সায়ন্তন রায় (Dec 12 2020 at 14:53):

A family of sets $\mathcal {F}$ is of finite character provided it has the following property: a set $A$ belongs to $\mathcal{F}$ iff every finite subset of $A$ belongs to $\mathcal{A}$.

Tukey's lemma is the following statement,

Tukey's Lemma. Let $Z$ be a set and let $\mathcal {F}\subseteq {\mathcal {P}}(Z)$. If $\mathcal {F}$ is of finite character and $X\in \mathcal {F}$, then there is a maximal $Y\in \mathcal {F}$ (according to the inclusion relation) such that $X\subseteq Y$.

It is known that Tukey's Lemma is equivalent to Axiom of Choice.

Let us now call a family of sets $\mathcal {F}$ to be of pseudo-finite character provided it has the following property: for any set $A$, if $A\in \mathcal{F}$ then so does every finite subset of $A$. Consider the following statement,

Let $Z$ be a set and let $\mathcal {F}\subseteq {\mathcal {P}}(Z)$. If $\mathcal {F}$ is of pseudo-finite character and $X\in \mathcal {F}$, then there is a maximal $Y\in \mathcal {F}$ (according to the inclusion relation) such that $X\subseteq Y$.

Is the above statement equivalent to Tukey's Lemma? Clearly, this statement implies Tukey's Lemma. Does it strictly imply Tukey's Lemma?

Morgan Rogers (he/him) (Dec 12 2020 at 14:59):

Isn't the pseudo-finite version false? Let Z be the natural numbers, and let $\mathcal{F}$ be the collection of finite subsets of $Z$, which clearly is of pseudo-finite character. Then there is no maximal member of $\mathcal{F}$, whence there is in particular no maximal member containing $\emptyset$.

Morgan Rogers (he/him) (Dec 12 2020 at 15:02):

I suppose there might be some models of set theory where there are maximal finite sets, but in any case you don't need to bother with AC to verify whether this variation holds, so I'm confident it can't be equivalent to Tukey's Lemma :+1: .

সায়ন্তন রায় (Dec 12 2020 at 15:09):

[Mod] Morgan Rogers said:

Isn't the pseudo-finite version false? Let Z be the natural numbers, and let $\mathcal{F}$ be the collection of finite subsets of $Z$, which clearly is of pseudo-finite character. Then there is no maximal member of $\mathcal{F}$, whence there is in particular no maximal member containing $\emptyset$.

Whoops! I didn't check it with examples! I Should have done that before trying to prove it.

Morgan Rogers (he/him) (Dec 12 2020 at 15:11):

One of the perils of abstract maths :wink:

সায়ন্তন রায় (Dec 12 2020 at 15:12):

It would then be interesting to know some weakening of the condition "finite character" to obtain a statement which strictly implies Tukey's Lemma (preferably in a form similar to Tukey's Lemma).

Morgan Rogers (he/him) (Dec 12 2020 at 17:02):

You could remove "finite", so it's just closed under subsets?

সায়ন্তন রায় (Dec 19 2020 at 14:12):

Your suggestion worked. Thanks @[Mod] Morgan Rogers. The definition on which I finally settled is the following (I hope I have got it right this time):

Let $Z$ be a set. Call a family of sets $\mathcal {F}$ to be of pseudo-finite character provided $\mathcal{F}=\mathcal{P}(Z)$ or it has the following properties:

• If $W\in \mathcal{F}$ then $\mathcal{P}(W)\subseteq \mathcal{F}$.
• There exists $\alpha\in Z$ such that $\{\alpha\}\notin \mathcal{F}$.

Then the pseudo-finite version of Tukey's Lemma is the following:

Let $Z$ be a set and let $\mathcal {F}\subseteq {\mathcal {P}}(Z)$. If $\mathcal {F}$ is of pseudo-finite character and $X\in \mathcal {F}$, then there is a maximal $Y\in \mathcal {F}$ (wrt the inclusion relation) such that $X\subseteq Y$.

Reid Barton (Dec 19 2020 at 15:00):

I don't think this is getting any closer to being correct. You could still take $\mathcal{F}$ to be the collection of all finite subsets of $Z$ (an infinite set) which don't contain some fixed element $\alpha$.

Reid Barton (Dec 19 2020 at 15:02):

Think about how the proof has to work. If you start from an $X \in \mathcal{F}$ which is not maximal, it means you can add an element to $X$ to get $X'$ which is still in $\mathcal{F}$. If $X'$ is still in $\mathcal{F}$, you can add another element, and so on. Suppose this goes on forever. Then you need some way to deduce that the union of $X$, $X'$, ... is still in $\mathcal{F}$.

Reid Barton (Dec 19 2020 at 15:04):

The "finite character" hypothesis provides this because a finite subset of this union is a finite subset of some finite stage. But your "pseudo-finite character" hypothesis only gives you statements of the form: if a set belongs to $\mathcal{F}$, then a smaller set belongs to $\mathcal{F}$, which can never help.

সায়ন্তন রায় (Dec 20 2020 at 04:16):

Yes, I guess I will take a break from this topic. I am making pretty silly mistakes lately due to my difficulty to think in terms of concrete examples.

Valeria de Paiva (Dec 22 2020 at 01:56):

Sayantan Roy said:

Yes, I guess I will take a break from this topic. I am making pretty silly mistakes lately due to my difficulty to think in terms of concrete examples.

Ok, but I was going to suggest https://www.researchgate.net/publication/265561030_Generalized_Galois-Tukey-connections_between_explicit_relations_on_classical_objects_of_real_analysis as well as
Andreas Blass "Questions and answers—a category arising in linear logic, complexity theory, and set theory", https://arxiv.org/pdf/math/9309208.pdf. (the second is the reason I know about the first).

সায়ন্তন রায় (Dec 22 2020 at 03:17):

Thanks for the references. I will take a look at them after the break. My interest in this topic resulted from trying to obtain a theorem like that of Dzik's Theorem for all Tarski-type logics.