Can we define every subset of an infinite set?

Question

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?

Answer 1

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.