Why a "set" whose elements is contingent on the truth value of a proposition is a set?

Question

Let $P$ be a proposition (such as Goldbach's conjecture) that we can state precisely, but that we do not necessarily know to be true or false. Now define $$ S = \begin{cases} \{\varnothing,\{\varnothing\}\}, & \text{for $P$ is true} \\ \{\{\varnothing\}\}, & \text{for $P$ is false } \\ \end{cases}$$

This is a "set" constucted to prove that "The Axiom of Regularity implies the Law of the Excluded Middle, if interpreted in the language of constructivism" on page 138 of Handbook of Analysis and its Foundations, Eric Schechter.

I don't know how to show that $S$ is a set from $\bf{ZFC}$.

Since page 138 is "visible" on googlebooks(here), I assume it is OK to post a screenshot here.

Answer 1

Formally, $S$ exists due to the Axiom of Separation (sometimes called the Axiom of Subsets, or of Comprehension).

Hopefully you agree that $A=\{\varnothing,\{\varnothing\}\}$ is a set.

Now $S$ is simply the set $\{x\in A \mid x=\{\varnothing\} \lor P \}$.

Then it is easy to prove that $P$ implies $S=\{\varnothing,\{\varnothing\}\}$ and that $\neg P$ implies $S=\{\{\varnothing\}\}$.

It is important to note that $S$ does not itself know that we have defined it in such a strange manner. A set knows only what its elements are, and "$S$" is actually just an alternative name for either the set $\{\varnothing,\{\varnothing\}\}$ or the set $\{\{\varnothing\}\}$. We don't know which, but our ignorance is really about which set the letter $S$ stands for, not which members a particular known set has. (However, this distinction is seldom observed when speaking about sets casually -- or even semi-formally).

---

How this could possibly be used to argue that "the Axiom of Regularity implies the Law of the Excluded Middle, if interpreted in the language of constructivism" I cannot fathom.

First off, it is more or less implicit in saying "ZFC" that the axioms are to be interpreted in the framework of classical first-order logic -- and there the law of the excluded middle is automatically true, independently of which axiom system we use to reason about it.

Second (and at last as puzzling), the defintion of $S$ here has nothing at all to do with the Axiom of Regularity; it would work exactly the same in ZF$-$Reg or even in an explicitly ill-founded set theory such as ZF$-$Reg$+$AFA.

Answer 2

I agree with Arthur's objection that the definition of the set $S$ seems to presume the Law of Excluded Middle, rendering the argument tautological. However, I think this can be fixed by instead defining

$$S = \left\{x \in \{\emptyset,\{\emptyset\}\} : x = \{\emptyset\} \text{ or } (P \mathbin{\And} x = \emptyset)\right\}.$$

The existence of this set is guaranteed by the Separation axioms. Note that the set $S$ is not only non-empty but is inhabited, because we know $\{\emptyset\} \in S$. The form of the Axiom of Regularity assumed in the quoted text then allows us to specify $x \in S$ such that $x \cap S = \emptyset$. We know that $x = \emptyset$ or $x = \{\emptyset\}$. If we can decide which one is true (which the quoted text seems to suggest that we can do) then we can decide the statement $P$: if $x = \emptyset$ then $\emptyset \in S$ and so $P$ is true, and if $x = \{\emptyset\}$ then $\emptyset \notin S$ and so $P$ is false. This would prove LEM, because $P$ was an arbitrary statement.

According to the Wikipedia article, in Intuitionistic Zermelo–Fraenkel set theory the Axiom of Regularity is replaced by the axiom schema of set induction (perhaps to avoid this argument for LEM.)

EDIT: Thinking more about it, it seems like the set $S$ defined by cases in the quoted text can still be proved to exist intuitionistically, provided that we interpret the definition as $$S = \left\{x \in \{\emptyset,\{\emptyset\}\} : (P \mathbin{\And} x \in \{\emptyset,\{\emptyset\}\}) \text{ or } (\neg P \mathbin{\And} x \in \{\{\emptyset\}\})\right\}.$$ However, the problem with this definition is that although it makes $S$ non-empty, we cannot show that $S$ it is inhabited unless we already know that $P$ is decidable. Presumably the form of the Regularity Axiom used in the text only applies to inhabited sets, although the author seems to ignore the distinction between "inhabited" and "non-empty".