Existence of a maximal set (with respect to set inclusion) having a certain property

Question

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?

Answer 1

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.

Answer 2

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).

Answer 3

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.