This thread was previously titled "Does a Set Require an Explicit Formula to Exist?".
I'm reading H. Enderton's Elements of Set Theory and working through understanding the Zermelo-Fraenkel axioms. While reading, the following question regarding the nature of sets occurred to me.
Suppose I give you an infinite set of integers, which seems to have no definable pattern. For instance, suppose I start listing elements of the set:
\begin{equation*}
S=\{3,4,11,199,205,6090,11238,…\}
\end{equation*}
I have simply chosen numbers at complete random and ordered them. As far as I know, there is no formula that describes those numbers. Suppose this set continues forever.
According to set theory, does this set exist? It seems hard to say it doesn't exist — after all, I've begun to write it already, so how could it not exist?
However, I believe set theory requires sets to have an explicit formula. Then the question becomes: given any arbitrary sequence of numbers like the one I've listed above (with no apparent "pattern"), does there exist a formula describing the sequence?
I realize this is a somewhat philosophical question, and it's coming from a new reader of set theory. However, this seems to be the kind of question that set theory was invented to answer. Thank you for your thoughts and explanations!
Edit: Thanks to Yuval for his answer! His answer raised some thoughts which I wanted to add to the question.
Given an arbitrary set of integers, although I can't find a formula describing it, since the set of ALL integers exists, then by the power set axiom any subset of it should exist as well.
So, could it just be that I'm just not clever enough to formulate an explicit formula for my arbitrary set of integers, but such a formula (as complicated as it may be!) actually exists? Maybe the existence of a formula describing any conceivable sequence of numbers is taken as an axiom, or maybe the opposite is true and it can be proven there exists a sequence without a formula.
I'm also wondering, although I know very little about it — does this question have anything to do with the Axiom of Choice?
Thanks again for your thoughts and explanations!
Best Answer
Say that a set $x$ is definable if there is a formula "$\phi$" in the language of set theory $\mathcal L_\in$ with only one free variable such that: for all $z$, $z\in x$ iff "$\phi$" holds of $z$. Then a simple way to read the question is:
Question: Is every set definable?
To ask this question, we need to say what it means for a formula in $\mathcal L_\in$ to "hold" of a set. But we can easily do that by adding a satisfaction predicate, $Sat$, to $\mathcal L_\in$, adding its associated axioms, and expanding the replacement and separation axioms of ZFC to the new language. In particular, in this new theory we can say that a set $x$ is definable if there is a formula "$\phi$" in $\mathcal L_\in$ with one free variable such that: for all $z$, $z\in x$ iff $Sat(``\phi", z)$.
Then we can show:
Theorem: There are undefinable sets.
Proof. As User4894 and Yuval pointed out, there are more sets than formulas in $\mathcal L_\in$.