4
$\begingroup$

I have a set $E$ and a predicate $P$ such that for any subset $S\subseteq E$, $P(S)$ is either true or false. Moreover, I know that there exists an set $X\subseteq E$ such that $P(X)$ is true. My question is: is it always the case that $\{S\mid P(S)\}$ has a maximal element, with respect to the set inclusion relation?

My intuition is that it is the case indeed. I am not a mathematician, so I am only weakly confident about it, but I imagine a proof by contradiction that would rely on transfinite induction. We know that the cardinality of $\{S\mid P(S)\}$ cannot be greater than the cardinality of the powerset of $E$. Yet, if there is no maximal element in the set, it means I can always find a strictly bigger set $S\subseteq E$ that satisfies $P$. If I keep growing the $S$ with a sufficiently large transfinite number of steps, I will necessarily reach a set strictly bigger than the powerset of $E$, and thereby prove a contraction.

I am not sure whether my proof is valid, and there may be a simpler argument, possibly based on axioms of set theory. Also, it seems to me that my "proof" would require something like the axiom of choice to work. Is it the case? Is the conjecture even true? If not, do you have a counter example?

$\endgroup$
6
$\begingroup$

There are two things here:

  1. Given a predicate on sets, it will always be either true or false (in a given universe of set theory, anyway, otherwise the terms "true" and "false" are meaningless).

  2. No, just consider $P(S)$ meaning that $S$ is finite. if $E$ is infinite, then there is no maximal finite set. If you require that $E$ is a finite set, then it only has finitely many subsets, so the answer becomes positive because a finite partial order always has maximal elements.

$\endgroup$
  • $\begingroup$ Very good and very quick answer! Regarding your first point: of course, and I am not saying the opposite. I could have formulated it in a better way, though. Regarding your second point: it definitely proves my conjecture wrong. However, my actual problem is more specific than what I asked here, and your counterexample, as well as any counterexamples that rely on the cardinality of the set, do not work as counterexamples to my true use case. I need to go back to work and make my question more specific. $\endgroup$ – Antoine Zimmermann Mar 14 '18 at 10:57
  • 1
    $\begingroup$ Well. You asked, I answered. Sure, if you give more details, one can see if there is a nice counterexample. But you can be sure that cardinality is not the only thing. For example, consider $E=\Bbb N$ and $P$ is "recursively enumerable and co-infinite". Or $E=\Bbb R$ and $P$ is "meager" or "null" and so on. $\endgroup$ – Asaf Karagila Mar 14 '18 at 11:04
  • $\begingroup$ I'm not sure about best practices for refining questions: should I ask another question or should I rather update this one to provide more details about my actual use case? This question is quite generic and could be of interest to more people. $\endgroup$ – Antoine Zimmermann Mar 14 '18 at 11:13
  • $\begingroup$ You've received two answers, and even accepted one of them. Clearly this answer is resolved through and through. Editing it now will only invalidate and possibly confuse people. I would note the tag changes for your next question, though. $\endgroup$ – Asaf Karagila Mar 14 '18 at 11:16
6
$\begingroup$

I do not know enough about transfinite induction to tell what goes wrong in your argument, but what you say is in general not true. Think for instance of $E=\mathbb{R}$ and $P$ the property "not being equal to $\mathbb{R}$" Edit: "being finite".

But if you have some stronger assumptions, in particular that the union of sets $S$ satisfying $P$ is still a set satisfying $P$, then you can use Zorn's Lemma (equivalent to the axiom of choice) to get a maximal element (but in general you will not be able to construct it explicitly).

$\endgroup$
  • $\begingroup$ You are right, of course. I understand what goes wrong in my proof now. The "proof" does not ensure that the property would still work for any limit ordinals. Since my actual use case is more precise than that of my question, I still need to work on it. $\endgroup$ – Antoine Zimmermann Mar 14 '18 at 11:00
  • $\begingroup$ I do have stronger assumptions in my actual use case, but precisely not that the union of sets $S$ also satisfy $P$, unfortunately. However, in my concrete problem, if $S$ satisfies $P$, then any of its subsets also satisfy $P$. $\endgroup$ – Antoine Zimmermann Mar 14 '18 at 11:05
  • 2
    $\begingroup$ I'm not sure your example works: The set $S = \mathbb{R}\setminus\{0\}$ seems to be maximal, right? Or am I missing something? (On the other hand, if $P(S)$ is the statement ``$\mathbb{R}\setminus S$ is countably infinite'', then I agree there is no maximal $S$: Given any $S$ for which $P(S)$ holds, pick $p\in \mathbb{R}\setminus S$, then $S\cup\{p\}$ is larger and still satisfies $P(S)$.) $\endgroup$ – Jason DeVito Mar 14 '18 at 15:21
  • $\begingroup$ Something like "$S$ is finite" also works for any infinite $E$. $\endgroup$ – MartianInvader Mar 14 '18 at 18:00
  • 1
    $\begingroup$ @Mjiig: I use the terminology "maximal" to mean "bigger than everything it can be compared to, but it can't necessarily be compared to everything else" and I use the terminology "maximum" to mean "bigger than everything else it can be compared to, and it can be compared with everything". When talking about partial orders (like the order induced by inclusion of subsets), I believe my use is standard, but I don't study partial orders for a living, so I could be off. $\endgroup$ – Jason DeVito Mar 14 '18 at 19:39
2
$\begingroup$

This is where your argument fails: If the a set is not maximal, there is a strictly bigger one with the same property, and this can be repeated a finite number of times. So far, so good. But what happens if you use a transfinite number of steps? If you have a sequence $S_1\subset S_2\subset\dots$ of sets satisfying $P$, there is no guarantee that the limit set $S_\omega=\bigcup_{i<\omega}S_i$ satisfies $P$.

If you look at any counterexample to your question, you can see this limit property fail. The easiest examples are probably $P(S)=\text{"$S$ is finite"}$ and $P(S)=S\neq E$. To make the limit property work, you need some kind of continuity of $P$. For properties with a suitable limit behavior your idea does indeed work.

$\endgroup$
  • $\begingroup$ Yes, you're right thanks. I figured it out after seeing the examples: see my first comment to 57Jimmy's answer. $\endgroup$ – Antoine Zimmermann Mar 15 '18 at 15:54

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.