# Does There Exist an Explicit Formula Describing Every Possible Sequence of Numbers?

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!

• No, there are way more sets than formulas. There are only countably many finite-length formulas over a countable alphabet, right? But there are uncountably many sets. – user4894 Sep 21 '14 at 5:37
• I won't post an answer, not being very competent in these matters. But beware that you are getting in somewhat philosophical waters here. As long as you haven't been able to specify your sequence, there is simply no sequence that you are talking about. Also "I know by the power set axiom that a set containing it exists" is wrong; if it doesn't exist, then there is no set containing it either. The power set axiom just gives you a set that contains all subsets of a given set, but it contains only those sets you can show to be subsets (and in particular none that are ill defined). – Marc van Leeuwen Sep 21 '14 at 10:10
• Just FYI: There is no unique way to know which sequence is meant by listing the first numbers in it. Even if there is an "obvious pattern" to them. You can always use polynomial interpolation to find the "next" number. Then you can use a different method that would be equally as valid to say that a different number is the "next" one. – Tim Seguine Sep 21 '14 at 10:29
• For what it worth, what you "believe" has nothing to do with set theory. And as I pointed out in some models of set theory, each step in the universe is definable by a parameter-free formula, and in other models of set theory it might not be the case. Not to mention that different models of set theory may have different sequences of integers (or different sets of integers altogether!) so the answer is just "sometimes, probably more often no than yes". – Asaf Karagila Sep 21 '14 at 22:30

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

• – Asaf Karagila Sep 21 '14 at 10:14
• That's like me saying "the sets are well-founded" and you reply "false, there are non-well-founded models". You did read my answer, right, with all the stuff about axiomatising the satisfaction predicate? – GME Sep 21 '14 at 10:16
• Yes, but the difference is that in a pointwise definable model you don't need to look from the outside to see that every set is definable. You just can't match a set to its definition uniformly from within the model. The satisfaction relation is indeed not definable, but that doesn't mean that there are undefinable sets. – Asaf Karagila Sep 21 '14 at 10:25
• I'm suggesting that we ${\it add}$ a satisfaction predicate and its associated axioms. Joel's argument, as far as I can see, doesn't apply to this new theory. – GME Sep 21 '14 at 10:27
• Here's another way to put it: I've given you a definition of "definable" and I've specified the theory in which I claim "There are undefinable sets" can be proved. The argument is: if every set were definable, we could map the sets 1-1 into the formulas (we just let $F(x) =$ the least $\phi$ such that $\forall z(z\in x$ iff $Sat(\phi, z)$)). But that's impossible. Where do you think that argument breaks down? Or do you disagree that my question is a perfectly good way of formulating the OP's? – GME Sep 21 '14 at 10:40

Existence is a semantic property, they require us to talk about a model (internally to that model, or externally to that model). Something exists in the model, if it is in the model. There's no other way to say it.

We can sometimes prove that certain objects exist, even if we have no explicit means of producing them. This, for example, is how the axiom of choice works. It proves that there is some choice function without giving us an explicit formula defining it. The negation of the axiom of choice works equally non-constructively, it tells us that there is some family of sets which do not admit a choice function, but it doesn't tell us what family it is.

So, is every set definable? Every set $A$ satisfies the formula with $A$ as a parameter, $A=\{x\mid x\in A\}$, but I'm assuming that you mean something less "obvious". The answer is possibly negative, and possibly positive. It depends on the model we take.

• I would rephrase "prove that certain objects exist" as "prove that certain kinds of object exist". The point is you get the existence of an object with a certain property (being a choice function) without any precise indication of which object it is. In a sense it is "prove that uncertain objects exist". – Marc van Leeuwen Sep 21 '14 at 9:59

By the power set axiom, the power set of the set $\mathbb{Z}$ of integers (which exists essentially by the axiom of infinity) exists. So all sets of integers exist. Of course, if you can't write the set, it is meaningless to ask whether the set exists. The formal question "does the set $S$ exist", or more accurately "does the set described by $\varphi$ exist" has the formulation $\exists x \varphi(x)$ (i.e., is this statement derivable in ZF). If you can't describe it by a formula, you can't even ask whether it exists.

• Thanks for your answer! I'm wondering, however: given an arbitrary sequence of numbers, although I can't find a formula, I know by the power set axiom that a set containing it exists. So could it just be that I'm just not clever enough to formulate an explicit formula, 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 it can be proven there exists a sequence without a formula. Does this question have to do with the Axiom of Choice (which I know very little about)? – Mathemanic Sep 21 '14 at 5:34
• On the contrary, most sets of integers don't have formulas, since there are countably many formulas but uncountably many sets of integers. This has nothing to do with the axiom of choice. The point is that if you can't ask the question then it doesn't have an answer. – Yuval Filmus Sep 21 '14 at 5:36
• Yuval, that's wildly inaccurate. There are models of $\sf ZFC$ which are pointwise definable. – Asaf Karagila Sep 21 '14 at 7:05

The real problem is "suppose this set continues forever". If by continues you mean with random choices then the set you described doesnt exist in ZF. You can create subsets of a given set only with first-order formulas. If you could select any subset regardless of properties, there would be no need for the axiom of choice: Given a family of sets you could just create a subset with one element of each element of the family. So the sets are created using axioms and almost every axiom somehow creates a set. For example, if you have shown that two sets are different then axiom of extensionality "creates" a set that belongs to only one of them (even if we cant exhibit one). Some sets (like Omega and the empty set) have axioms just for them. The axiom of specification enable us to separate a part of the set that satisfies a given first-order-logic-formula, but belonging to a set doesnt necessaraly implies existence.