# Set Properties: Formal Semantics of Programming Languages

What is the difference between the two notations below?

{x | x (is an element of) X & P(x)}


vs.

X = {x | P(x)}


These both seems to say to me x is in X as long as it abides by property P. The top one is defined as a comprehension and the bottom one is used as a lead into Russle's paradox.

-
The first specifies the collection of all elements of $X$ (which must already be defined) which satisfy $P$. If $X$ is a set, then this is a set by the Axiom of Separation. The second specifies the collection (possibly a proper class) of all objects that satisfy $P(x)$, and calls it $X$. –  Arturo Magidin Sep 8 '11 at 4:51
Note that the first one does not say "x is in X if it satisfies P". It says "This is the collection of all things that are both in $X$ and satisfy P". By contrast, the second says "The collection of all things that satisfy P is called X". –  Arturo Magidin Sep 8 '11 at 4:51
The first describes a certain subset of $X$, quite possibly not all of $X$. The second says that $X$ is the set of all objects in the universe with property $P$ (unrestricted comprehension, not allowed in ZFC). –  André Nicolas Sep 8 '11 at 4:52

The difference is that $X$ is required to be a set in the first, and in the second it may not be. It's kind of amazing, but this avoids the classical set-theoretic paradoxes. The classic Russell paradox $X=\{x|x\not \in x\}$ is a good example. Now in the first we know we have a set by the power set and separation axioms. In the second we don't.
In Zermelo set theory, the assertion that for any (already constructed) set $X$, the collection of all $x$ satisfying $P$ is a set is called the Axiom of Separation. Later, the notion of property was made more precise by replacing it with formula. Also later, Separation was strengthened to Replacement. To prove that Replacement implies Separation we do need Power Set, but then we need Power Set to do much of anything, if we use standard definitions. Some axiomatizations still have both Separation and Replacement. –  André Nicolas Sep 8 '11 at 5:18
@Ross Millikan: The answer to larger cardinality without Power Set is roughly speaking no you cannot. (Depending on details of presentation, you can get larger finite sets without Power Set, and Axiom of Infinity directly produces an infinite set, but that's all.) In the first construction mentioned by the OP, we do already have a set $X$, so constructing the subset of $X$ consisting of the elements that satisfy the formula $P(x)$ is a direct use of Separation, and does not require Power Set. –  André Nicolas Sep 8 '11 at 5:49