# Can we define every subset of an infinite set?

Given a set $$S$$ I can define subsets $$P \subseteq S$$ by predicates $$P(x)$$ in the following way: $$P: \{x \in S|P(x)\}$$ Now, since what I wrote is a string of symbols, in every mathematical theory the number of such subsets is countable. So how can I hope to reach every subset, say, of the natural numbers while respecting Cantor's theorem?

• It is not the case that the number of such subsets is countable. Why should there be only countably many $x \in S$ such that $P(x)$? Take $S$ to be uncountable and $P(x)$ to be "$x$ is in $S$", and there will be uncountably many $x$ that satisfy $P(x)$.
– kccu
May 31 '19 at 13:30
• @kccu I think you misunderstood the question. J.Ask was asking about the number of subsets and not the size of these subsets. May 31 '19 at 13:34
• @Jonathan No, I understand that. OP is concerned about the size of the set of all subsets of $S$, which they say can be defined by a finite string of symbols. I am pointing out that defining a set by a finite string of symbols does not imply that set is finite.
– kccu
May 31 '19 at 13:49
• Because of Tarski's undefinability theorem you can't even precisely define what the symbols "$P(x)$" mean. So this isn't really a question you can ask. The word "definable" is not definable! Jun 1 '19 at 6:19

It is consistent, but not provable.

In fact, it is consistent that all sets can be defined by a formula with a single free variable (and no parameters, of course).

But at the same time, it is consistent that this is not true at all.

The proof that either one is consistent requires understanding fairly advance techniques in set theory such as forcing and the constructible universe.

Joel David Hamkins, David Linetsky, and Jonas Reitz proved the first fact in a very nice paper with a very readable exposition on this.

Hamkins, Joel David; Linetsky, David; Reitz, Jonas, Pointwise definable models of set theory, J. Symb. Log. 78, No. 1, 139-156 (2013). ZBL1270.03101.

• I'd like to add that this property of a model, that every set is definable, isn't described by any first-order sentence. So the situation here isn't like the one with the Axiom of Choice of the Continuum Hypothesis, in which there is a particular sentence which is neither provable nor refutable. Jun 1 '19 at 6:24