MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\phi$ be an undecidable statement of ZFC set theory, for example let's take continuum hypothesis.

What is the ontological status of the "set" $X=\bigl\{x\in\{1,2\}:x=1\text{ or }(x=2\text{ and }\phi)\bigr\}$ in ZFC?

share|cite|improve this question

closed as not a real question by Qfwfq, Noah Schweber, Steven Landsburg, Andrés E. Caicedo, Goldstern Jun 5 '13 at 2:30

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

What is the ontological status of $\{1\}$? What does that even mean? – Mariano Suárez-Alvarez Jun 4 '13 at 18:42
It is obviously a set, because it is constructed according to the rules that ZFC makes available to construct sets. It is a finite subset of $\mathbb N$, again obviously, because the inclusion map into $\{1,2\}$ is injective. Also obviously, it is undecidable in ZFC whether $2$ is in $X$ or not. Presumably you know all this and are trying to make some point? Remember that this is not a discussion site. – Mariano Suárez-Alvarez Jun 4 '13 at 18:58
I'm not sure this is a real question, but: $ZFC$ does prove that there exists a set $X$ such that EITHER the continuum hypothesis (or any $\varphi$) holds and $X=\lbrace 0\rbrace$, OR the continuum hypothesis fails and $X=\lbrace 1\rbrace$. There's nothing mysterious about the set $X$: rather, the only thing behaving oddly here is the intentional nature of $X$. As to your comment, it is not always possible to list all the elements of a finite set of natural numbers and be sure that you have done so correctly; note, however, that it is possible to list the elements of the set $X$ above: – Noah Schweber Jun 4 '13 at 19:03
The relevant axioms of set theory say, in this case, that there exists a set with such-and-such properties. They don't say - nor is there any reason they should, unless we want to leave classical logic - that we can "determine" that set in any way. The axioms are extensional, not intensional. Note that we don't need any "philosophical view" to do math: all mathematicians, despite having wildly different philosophies, can agree that (classical) ZFC proves the existence of such a set. – Noah Schweber Jun 4 '13 at 19:35
I agree with Noah's parenthetical comment that the problem is not ontological but epistemological. The set $X$ in the question is a perfectly good, nonempty, finite set of natural numbers, and ZF proves that. The only "problem" with this set is that we don't know as much about it as we might want. Specifically, we don't know whether 2 is an element of it and we don't know how many elements it has. But these unpleasant circumstances are entirely epistemological. – Andreas Blass Jun 4 '13 at 22:18
up vote 11 down vote accepted

Although you've been given a hard time in the comments, I think that this is actually a serious question in the philosophy of mathematics, whose answer depends on one's philosophical position concerning the nature of mathematical truth.

What is the nature of existence for the mathematical objects that we define?

There are a variety of natural positions to stake out, so let me describe at least a few of them. There are of course many more; I mention several perspectives specifically on CH in my answer to Gil Kalai's question on solutions to the continuum hypothesis, which you may find relevant.

As you describe the example, the puzzling thing here is that you seem to have defined a fairly simple set, yet we also find ourselves unable to answer some fairly simple questions about it, such as whether it has one or two elements. To my way of thinking, the philosophical question about the ontological status of your set is very similar to the philosophical question about the ontological status of the truth of $\phi$ itself; the two simply go together. So we could ask the question like this:

When a statement $\phi$ is independent of ZFC, what is the ontological status of the truth of $\phi$?

For example, does it still make sense to say that $\phi$ is definitely true or false, but definitely only one of these? Ontology has to do with the nature of reality---in our case, mathematical reality---independently of, say, our knowledge about it. But provability and non-provability (and thus independence) seem to have to do with our ability to know certain things, and thus relate to epistemological rather than ontological concerns.

Let me describe a few of the philosophical positions that are commonly held about this kind of question.

Traditional set-theoretic Platonism. On the traditional Platonist view, sets exist in a unique real Platonic realm---the realm consisting of all sets---and every set-theoretic assertion has a definitive truth value in this realm. On this account, there is a fact of the matter about whether CH is true or false, or whether your assertion $\phi$ is true or false. On this account, the set you have described is either in fact identical to $\{1\}$ or is identical to $\{1,2\}$. The fact that $\phi$ is independent of the ZFC axioms merely illustrates our lack of knowledge about which one of these sets you have actually described. On this account, the set is definitely one of them or the other, depending on whether it is the case that $\phi$ is true or not, and exactly one of these is the case. The independence of $\phi$ is an irrelevant distraction from whether $\phi$ is true. On this view, the pervasive independence phenomenon is seen as a side-show about our epistemological weakness---the weakness of our theories---rather than indicating any issue about the singular nature of mathematical truth.

Formalism. On this view, there is no realm of real existence for mathematical objects like sets, and rather the mathematical process consists of the manipulation of sequences of symbols, such as the definition in your question. On this view, assertions of existence in mathematics are merely a way of speaking, and no actual existence of mathematical objects is being asserted. Formalism thus trivializes the ontology of the mathematical objects that mathematics is about.

Plural realism, or the multiverse view. On the plural realist or multiverse conception of set-theoretic truth, one holds that there are diverse concepts of set, each giving rise to its own set-theoretic universe, a plurality of set-theoretic worlds with their own set-theoretic truth, but which can be connected in various ways, such as by forcing or by large cardinal embeddings. On this account, your sentence $\phi$ may be true in some of these worlds and false in other worlds, and your set will accordingly change its nature depending on the current set-theoretic background concept of set under which it is being interpreted. You can read more about the multiverse perspective in set theory in some of my recent papers, especially "The set-theoretic multiverse", RSL 2012.

share|cite|improve this answer
A quick side note about plural realism in this context: under that view, definitions of sets can now be thought of as "meta-functions" assigning to each universe a set in that universe. Then the distinction between "ambiguous" and "unambiguous" definitions is just the distinction between "non-constant" and "constant" functions. (The use of the word "function" here might, to be fair, be inappropriate!) – Noah Schweber Jun 5 '13 at 0:02
Noah, I find your description fine for particularly simple definitions, but I don't regard, say, "the reals, thought of as Dedekind cuts in the rationals" as a constant definition across set-theoretic universes, since different set-theoretic universes can have different collections of such cuts (not to mention different sets of rational numbers). – Joel David Hamkins Jun 5 '13 at 0:48
Nor do I - but then, I think of "the reals" as also ambiguous. – Noah Schweber Jun 5 '13 at 1:29
Joel, I decided to choose your answer since it is philosophy- oriented and informative. I like your idea of the multiverse, very interesting. – Godot Jun 5 '13 at 9:47
One thing I think is conspicuously lacking is the possibility of a many-valued but boolean truth; $\varphi \vee \neg \varphi$ is true, but that does not imply that true and false are the only possibilities for $\varphi$. I suppose, though, that this could be viewed as plural realism in disguise. – Hurkyl Jun 2 at 21:23

Consider the following descriptions of sets:

(1) $X=\lbrace i\in\omega: i=0\rbrace=\lbrace0\rbrace$,

(2) $Y=\lbrace i\in\omega: i=0\iff CH, i=1\iff \neg CH\rbrace=\lbrace 0\rbrace$ or $\lbrace 1\rbrace$, and

(3) $Z=\lbrace i\in\omega: \text{ the $i$th Diophantine equation (in some natural listing) has an integral solution}\rbrace$.

Now, the short version is: $ZFC$ (actually, much less than $ZFC$) proves that $X$, $Y$, and $Z$ exist.

A slightly longer version, which might help you understand what's going on here: really, what I have is not three sets $X$, $Y$, and $Z$, but rather three first-order formulas $\phi_1(x), \phi_2(x)$, and $\phi_3(x)$ with a single free variable. Now, for every such formula $\phi(x)$, $ZFC$ proves that $$ \lbrace i\in\omega: \phi(i)\rbrace$$ exists; this is just Separation + Infinity.

There are really three potential issues here, and none of them have to do with the "ontological status" of (2).

  • First, there's the issue of Infinity: whether we believe that infinite sets exist. It's perfectly reasonable to discard infinite sets, but (a) most mathematicians don't, and (b) if you do, then presumably you aren't very interested in $ZFC$.

  • Second, there's the issue of incompleteness: among the three formulas "$\phi_2(x)$" (defining the set $Y$), "$x=0$," and "$x=1$," $ZFC$ can prove that two of those formulas are actually equivalent; but $ZFC$ cannot prove any specific equivalence. This is an issue with the underlying logic, not the sets: classical logic can (and does: Excluded Middle) prove $\theta\vee\psi$ without proving $\theta$ or $\psi$. This is one reason some people prefer intuitionistic logic, but it's not really an issue with sets (in my opinion). Certainly it's not really a paradox, just something which newcomers to logic might find surprising at first. EDIT: To explain a bit more why this isn't a set issue, but a logic issue, note that for any sets $A$ and $B$ and any formula $\phi$, $ZFC$ proves $$\exists C[(C=A\iff \phi)\wedge(C=B\iff \neg\phi)]. $$ So this really has nothing to do with the sets themselves.

  • Finally, there's the real set-theoretic issue: the third set, $Z$, has no finite description! (This is the solution to Hilbert's Tenth Problem by Davis, Matiyasevitch, Putnam, and Robinson.) Note that this is not a property of the description of $Z$, but rather a property of the set $Z$ itself. To my mind, this begins to get into the real ontological weirdness of set theories: the extent to which they demand the existence of "undescribable" (which can range anywhere from "not efficiently computable" to "incomputable" to "undefinable") sets. Is the powerset of $\omega$ describable? Is a well-ordering of the reals describable? Set theory is full of instances where sets are describable only in a very indirect sort of way, and this is interesting; but it's very much not an issue with (2), which is just a logical curiosity, and it's also not a paradox, but a necessary feature of taking mathematics beyond the finitary, which I think is a good thing.

share|cite|improve this answer
What do you mean by a “finite description”?$Z$ is recursively enumerable, it has a finite, algorithmic description, there are very few notions that are even more constructive. – The User Jun 4 '13 at 21:50
I meant an algorithm; I'm just saying $Z$ is not recursive. My point is just that we can find sets with "somewhat nice" descriptions which provably have no "nice" descriptions, for almost any meanings of "somewhat nice" and "nice." :P – Noah Schweber Jun 4 '13 at 21:53
Also, that seems to be the meaning of "finite description" most consistent with the OP's question (which is, however, extremely vague). – Noah Schweber Jun 4 '13 at 21:54
Okay, then take the set of (codes for) Diophantine equations with infinitely many solutions, or the set of (codes for) recursive subtrees of $\omega^{<\omega}$ which are well-founded; or the real coding the true theory of arithmetic. It really doesn't matter. – Noah Schweber Jun 5 '13 at 0:00
I don't particularly mind, but I'm curious: why the downvote? – Noah Schweber Jun 5 '13 at 3:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.