# $\{x : P(x)\}$ vs. $\{P(x) : x\}$ -— When are these set-builder notations the same and different?

I should clarify that I'm asking for intuition or informal explanations. I'm starting math and never took set theory so far, thence I'm not asking about formal set theory or an abstract hard answer.

From Gary Chartrand page 216 Mathematical Proofs -

\begin{align} \text{ range of } f & = \{f(x) : x \in domf\} = \{b : (a, b) \in f \} \\ & = \{b ∈ B : b \text{ is an image underfof some element of } A\} \end{align}

Wikipedia - \begin{align}\quad \{\text{odd numbers}\} & = \{n \in \mathbb{N} \; : \; \exists k \in \mathbb{N} \; : \; n = 2k+1 \} \\ & = \{2n + 1 :n \in \mathbb{Z}\} \end{align}

EDIT @Hurkyl 10/5. Lots of detail please.

Question 1. Hurkyl wrote $\{\text{odd numbers}\}$ in two ways.
But can you always rewrite $\color{green}{\{ \, x \in S: P(x) \,\}}$ with $x \in S$ on the right of the colon? How?
$\{ \, x \in S: P(x) \,\} = \{ \, \color{red}{\text{ What has to go here}} : x \in S \, \}$? Is $\color{red}{\text{ What has to go here}}$ unique?

Qusetion 2. Axiom of replacement --- Why $\{ f(x) \mid x \in S \}$ ? NOT $\color{green}{\{ \; x \in S \mid f(x) \; \}}$ ?

@HTFB. Can you please simplify your answer? I don't know what are ZF, extensionality, Fraenkel's, many-one, class function, Cantor's arithmetic of infinities, and the like.

-
The second one is just shorthand notation for the correct $\{y:(\exists x\in S)(y=P(x))\}$, where $P$ is some 'function'. See Axiom schema of replacement. – Git Gud Jul 12 '13 at 8:46
@RahulNarain: I felt this way from math.stackexchange.com/questions/149966/…. Was there something wrong with thinking this? – dresserse Oct 5 '13 at 8:48
@egreg: Where are the answers to the added four questions? I'm not after separate answers. It'd just be nice if the current answers can be expanded to answer these four. – François Muer Dec 23 '13 at 12:00
@egreg I don't understand why not? And what about added question 1? – François Muer Dec 23 '13 at 12:21
@egreg How is the added question 1 nonsense? Sometimes the predicate is written on the left of the colon and sometimes right. Hence it's interesting to find out why and when you can do this? – François Muer Dec 23 '13 at 13:20

I've never seen notation such as $\{n\in\mathbb{N}:2n+1\}$ and the answer you refer to says that $\{g\in G:gG\}$ is incorrect.

Well, incorrectness is a relative concept. Before using a notation you should define its meaning; nothing prevents you from assigning a meaning to $\{x\in X: f(x)\}$, but this is usually not done.

What's the difference between $\{x\in S:P(x)\}$ and $\{f(x):x\in S\}$?

In the first case $P$ is a “predicate”; more technically, a formula with a free variable. The symbol $\{x\in S:P(x)\}$ denotes the subset of elements of $S$ for which the statement $P(x)$ is true. For instance, $\{n\in\mathbb{N}:2\mid n\}$ means the even natural numbers.

In the second case, $f$ should be a function $f\colon X\to Y$ such that $S\subseteq X$. The notation $\{f(x):x\in S\}$ is just a shorthand for

$$\{y\in Y: \text{there exists }x\in S\text{ such that }y=f(x)\}$$

so it's not really a different concept. For instance $$\{2n:n\in\mathbb{N}\}= \{n \in \mathbb{N} : \text{there exists } m \in \mathbb{N}\text{ such that } n = 2m \} =\{n\in\mathbb{N}:2\mid n\}$$ where we use the function $f\colon\mathbb{N}\to\mathbb{N}$, $f\colon n\mapsto 2n$, so its image is just the set of even natural numbers.

-
@dresserse I can't understand. – egreg Sep 18 '13 at 10:24
I edited my question overhead. Is it better? Let me know if you can't. – dresserse Sep 18 '13 at 13:27
I have given a separate answer, below, which addresses both why the alternative notation is "usually" not done, and why the two sets $\{x \in S: P(x)\}$ and $\{f(x): x \in S\}$ are essentially different concepts; they are the result of applying two different operations and you cannot always prove the existence of a set using only one of them. – HTFB Feb 17 '14 at 12:48

The first set is the collection of all the $x$ which are both elements in $S$ and satisfy the property $P$.

The second set is the collection of the objects "$P(x)$" for all $x\in S$, for example if $P(x)$ is the function $x^2$ and $S=\Bbb N$ then the result is the set of squares.

-
What does the downvote represent? – Asaf Karagila Oct 5 '13 at 9:20
I didn't downvote but can you add more detail to your question please? – François Muer Dec 23 '13 at 12:02
@Frank: To my answer, you mean. What sort of details should I add? – Asaf Karagila Dec 23 '13 at 12:13
Yes thanks. Can you please answer in detail the 4 added questions by dresserse? No answer covered them. – François Muer Dec 23 '13 at 12:16

There are two basic ways to "build" sets, aside from listing their elements.

The first is the axiom of subsets: if you already have a set $S$ and you want to create the subset of $S$ of things satisfying some property $P$, then the usual notation is

$$\{ x \in S \mid P(x) \}$$

For example, the set of even numbers is { x in Z | x is divisible by 2}. This is sometimes written in the form of "unrestricted comprehension":

$$\{ x \mid x \in S \wedge P(x) \}$$

e.g. { x | x is an integer divisible by 2}. You have to be a little careful with this variation: sometimes it doesn't actually define a set. (relevant keywords: "proper class" and "class builder notation")

The second is the axiom of replacement: if you have a set $S$, and you have a function $f$ that you can apply to elements of $S$, then you can create a new set by using $f$ to transform each element of $S$. This is usually written

$$\{ f(x) \mid x \in S \}$$

For example, we could again define the set of even integers as { 2x | x in Z }.

Some other variations exist, but these are the two principal ways to use set builder notation to define sets.

Edit: to elaborate on some other versions, could use an 'all-in-one' version. The computer algebra system magma does this, for instance. We use the notation

$$\{ f(x) : x \in S \mid P(x) \}$$

to represent the set (or class) of all of the values $f(x)$ where $x$ is an element of $S$ that satisfies the predicate $P$. (the choice of : and | in the notation is based on what magma uses)

In this form, the axiom-of-subsets version of class version becomes

$$\{ x : x \in S \mid P(x) \}$$

and one could view the usual notation as being a shortened form of this. In mathematical writing, $x \in S$ usually gets folded into the predicate $P$ (or is implicit from context that $x$ is a varaible of 'type' $S$). That is, people often write

$$\{ f(x) \mid P(x) \}$$

for the class of all values $f(x)$ such that $x$ satisfies the predicate $P$. This may be a set; sometimes it is obviously so: e.g. the set of integers divisible by 6 could be written as

{ 3x | (x in Z) and (x is divisible by 2) }

which is obviously a set, since class of elements satisfying the predicate is clearly a subclass of the set of integers.

-

Mauro makes part of this point, but it's worth stressing: the two different ways of notating a set are used for instances of application of two different axioms (strictly, axiom schemas) in ZF: $$B = \{x \in A : \phi(x)\}$$ is an application of the subset axiom (a.k.a. separation): $$\forall y_1, \ldots, y_n \forall A\, \exists B\, \forall x (x \in B \leftrightarrow x \in A \wedge \phi(x, y_1, \ldots, y_n, A)),$$ where $\phi(x, y_1, \ldots, y_n, z)$ is a formula in the language of set theory. The symbol within the curly braces is guaranteed by this axiom to refer to an element of the domain of a model of ZF (and to exactly one element by the axiom of extensionality). So thanks to this axiom it is always a legitimate shorthand notation for a set.

Conversely, $B = \{f(x): x \in A\}$ is an application of the Fraenkel's axiom (schema) of replacement. The axiom schema is

$$\forall y_1, \ldots, y_n, \forall A \left(\left(\forall x (x \in A \rightarrow(\forall z_1, z_2\, (\phi(x, y_1, \ldots, y_n, A, z_1) \wedge \phi(x, y_1, \ldots, y_n, A, z_2))\rightarrow z_1 = z_2\right)) \rightarrow \exists B \forall z (z \in B \leftrightarrow \exists x (x \in A \wedge \phi(x, y_1, \ldots, y_n, A,z)))\right)$$ What this says is that if $\phi(x,z)$ is many-one when restricted to the domain $A$, so that there is a function (in the most abstract sense, i.e, a "class function") satisfying $x = f(z) \leftrightarrow \phi(x, z)$, then the collection of all the images of elements of $A$ under $f$ is also a set.

Or, in shorthand, there is a set which is the elementwise-image of $A$ under $f$. Again, by extensionality there is exactly one such set.

So which of the two notations you use for a particular set would be defined by the last axiom you apply in proving the existence of that set: are you thinking of it as a subset of something, or as the image of something? It should be obvious that $\{x \in \mathbb{N} :x\text{ is even}\}$ is the same set as $\{2\cdot x: x \in \mathbb{N}\}$. So very often the notation you choose will be determined by what you are wanting to say about a set that could be constructed either way. And as others have noted you can roll the two notations into one, when a set is constructed by successive applications of both axioms, and save paper.

You cannot always eliminate Replacement in favour of Separation: ZF is strictly stronger than Z (the collection of axioms omitting replacement). In general Replacement is needed to conduct Cantor's arithmetic of infinities inside set theory: see the Wikipedia page on replacement. A specific set that cannot be proved to exist without replacement is $\aleph_\omega$. But if you know a set $A$ exists you can trivially write it in either form with a bit of shorthand: $A = \{x \in A : x = x\}$ and also
$A =${$\text{Id}(x): x \in A\}$ (where $\text{Id}$ is the identity map). I hope this answers Question 1 of the edit.

For Question 2, note that your proposed backwards replacement set notation is indistinguishable from the usual subset notation, unless you are absolutely rigorous in separating your capital $P$ shorthand for a formula from your lower-case $f$ for a function. There would be an ambiguity in the notation when $P(x,y)$ had an extra free variable: is it the formula defining a function so the set is constructed by replacement, or is it being used to define a subset (for any given value of the free variable)? It's a bad idea!

More intuitively, you can pronounce $\{P : Q\}$ in English as "the set of elements P such that Q", and if you start reversing some of the notation it becomes much harder to read.

It's also worth noting that taking subsets, and taking the image under a function, are entirely intuitive operations that you want to do naively with sets well before axiomatising them: given a classroom of children, the set of girls in the classroom and the set of all fathers of the class are collections that any teacher might need to think about. The notation makes sense without worrying about the axioms.

-
Only a question - in form of comment - in order to understand. I agree that when using Replacement I need to "denote" the function $f$. I agree that it is useful to use "abbreviations", in order to shorten big set-th formula. My understanding is that, in "formal" set theory, the set term must be in the form : $\{x : \phi(x) \}$. Is the same with the quantifiers: we can write : $\forall x \in A \phi(x)$ but the correct way is : $\forall x (x \in A \rightarrow \phi(x))$. My question is, are we able to "specify" (instances of ) Replacement in the form : $\{x : f(x) \land ... \}$ ? – Mauro ALLEGRANZA Feb 17 '14 at 13:03
The answer to your first question is either "yes" or "it does not matter". The restricted quantifier "$\forall x \in A$" is not a part of the standard formalism of first-order logic as it mentions the special relation symbol "$\in$". But the equivalent formulation in the standard language (your "correct way") means that it can be added unambiguously. Understanding $\forall x \in A$ needs a purely logical substitution and does not rely on any of the truths of set theory. – HTFB Feb 17 '14 at 15:09
For your second question, by contrast, using the $\{ \ldots : \ldots\}$ notation does need the axioms of set theory. Used correctly the notation (in either of the forms) is guaranteed to name a set (and exactly one set) in any model of the set-theoretic axioms. The notation "$\{x: f(x) \wedge \ldots\}$ looks wrong in two ways: on the LHS, the $x$ appears on its own so the class function for this replacement axiom must be the identity $x \mapsto x$. And on the right, if $f$ is a class function then $f(x)$ is an object in the domain; but $\wedge$ is an operation on truth values, not objects. – HTFB Feb 17 '14 at 15:18
You are right! I beg your pardon for my sloppiness. The correct form is $\forall a [... \rightarrow \exists b \forall z[z \in b \leftrightarrow \exists x (x \in a \land \phi(x,z))]]$. The function $f$ being a set, must be "proxied" by a formula $\phi(x,z)$ with the "correct" behaviour. – Mauro ALLEGRANZA Feb 17 '14 at 17:36
Thank you. Voted up. Can you please simplify your answer? It looks very magnificent and prime. I never took set theory. I don't know what are ZF, extensionality, Fraenkel's, many-one, class function, Cantor's arithmetic of infinities, and the like. – dresserse Feb 17 '14 at 17:40

About Question 1), basically, the formula :

$\{$ odd numbers $\} = \{ n \in \mathbb{N} : \exists \, k \in \mathbb{N} \; (n = 2k+1 ) \; \}$

is a shorthand for the formal :

$\{ n : n \in \mathbb{N} \quad \land \quad \exists \, k \; ( k \in \mathbb{N} \land n = 2k+1 ) \;\}$.

The syntax of first-order set-theory, requires $\{ x : \phi(x) \}$

where $\phi(x)$ is a well-formed formula with one free variable (a well-formed formula is an expression built up according to "language specifications").

Due to the fact that $\in$ is part of set-theoretic language, you can use it in $\phi$, so that you can have :

$\{ x : x \in S \land P(x) \}$.

Accordingly, I'll rewrite : $\{ f(x) : x \in S \}$ as :

$\{ \; y : \exists \, x \, \exists \, z \quad (Funct(z) \quad \land \quad x \in S \quad \land \quad <x,y> \in z) \; \}$;

where $Funct(z)$ is a "complex" expression saying that the set $z$ is a function; again, the formula at the right of the colon has form : $\phi(y)$, with $y$ free.

Of course, in addition to the syntactical aspects, that dictates how to build well-formed formulas, we have the aspects related to "existence" of sets, that depends on the axioms.

In Axiomatic set theory (the form due to Zermelo and Fraenkel, called $\mathsf {ZF}$) you must use Axiom Schema of Separation in order to prove that the previous set exists.

This answer also the question about $\{ x \in S: P(x) \} = \{ ? : x \in S \}$. It must be :

$\{ x \in S: P(x) \} = \{ x : x \in S \land P(x) \}$.

Left of the colon we must have a set variable; right of the column, a "condition" specifying that the resulting set will be the subset of $S$ made by the elements $x$ of $S$ such that $P(x)$ holds.

It must be also a formula with constant symbol (a "name", like : $\emptyset$): for example, we may have :

$\{ x : x \in S \land x \in \emptyset \}$.

In this case we "choose" the $x \in S$ that in addition belongs to $\emptyset$; but there are none, so the result will be simply the empty set.

NOTE about language. In order to understand the formulas above, we need some preliminary notions about first-order language.

We start with symbols : variables: $x$, $y$, ..., predicates : $P$, $Q$, ..., connectives : $\lnot$, $\land$, $\lor$, $\rightarrow$ and the quantifiers $\forall$ and $\exists$. We may add also constants, like $0$ and $1$ in arithmetic and $\emptyset$ in set theory.

A "special" (binary) predicate is $=$ (both in arithmetic and set theory), while the (binary) predicate $\in$ is used in set theory.

They are written usually - mainly due to tradition - in the infix form, i.e. $x \in y$ and $x = y$, instead of the "official" prefix form, i.e. $\in (x,y)$ and $=(x,y)$.
Infix form is more readible for humans; computers "prefer" the prefix one.

Variables and constants are terms : they behave like "nouns".

With predicates and connectives and quantifiers you can build formulas, like $x \in \emptyset$, $0 = 1$.

Roughly speaking, terms have denotation and formula have meaning: but, in order to achieve "meaningfulness", we must follow the rules of formation (the syntax of the language, like the formal specifications for a programming language).

The matter is like in natural language : the phrases "the flower is red" and "the man run slowly" are "well formed", while the phrase "the man runs redly" is meaningless.

In set theory we have that formulas like : $x \in A$ and $A \subseteq B \cap \emptyset$ are well-formed, i.e. they have meaning.

The expression $x \in \lor A$ is ill-formed, i.e. meaningless.

With quantifiers and connectives you can "build up" complex formulas (starting from "atomic" or elementary ones).

Examples from set theory.

Set theory add to the "basic" symbols (variables, connectives, quantifiers and equality ($=$)) only one predicate (bynary : $\in$) as primitive : all other symbols "specific" of set theory will be defined.

Please note: also the "name" for the empty set ($\emptyset$) is defined; it is introduced after we have proved that, according to the axioms of our theory, there exists a set that has no members, and that this set is unique.

Atomic formulas : $x \in y$, $x = y$, etc.

From this "austere" groundfloor we can buil all we need, i.e. complex formulas like : $x \in y \land x = y$, $\lnot x \in y$ (abbreviated as : $x \notin y$), ...

When we write a formula like $\phi(x)$, we usually want to refer to an (atomic or) complex formula with one free variable, like $x \in \emptyset$. But we can also write : $x \in \emptyset \land x \notin x$. This last formula has the "form" $x \in S \land P(x)$ (where "incidentally" $P(x)$ is the predicate of the Russell's paradox).

Our first examples are of this "form": the set of even numbers is the set of all $x$ such that $x \in \mathbb{N} \land \exists y (x=2 \times y)$; here $\exists y (x=2 \times y)$ is a formula with the free variable $x$, like $P(x)$.

Note we have implicitly "added" to set language also symbols for arithmetic, like :$\mathbb{N}$, $+$, $0$, $\times$. Please, assume for the sake of discussion that it is admissible.

NOTE on functions in set theory.

Functions in set theory are a particular type of sets (in set theory - "obviously" - all is a set).

We nedd the concept of ordered couple $(a,b)$ that is different from $\{ a, b \}$ (because $\{ a, b \} = \{ b, a \}$, i.e. the order is immaterial, where the ordered couple is ... ordered); $a$ is the first element of the couple and $b$ is the second.

A function in set theory is a set of ordered couples,

provided that it satisfy the "basic rule" for functions, i.e. that if $f(x)=y_1$ and $f(x) = y_2$, then $y_1=y_2$.

This rule will be "rewrited" in set language as : a set $f$ of ordered couples is a function when :

$\forall x \forall y_1 \forall y_2 ( \quad <x,y_1> \in f \quad \land <x,y_2> \in f \quad \rightarrow y_1 = y_2 \quad )$.

We will write the function $f : \mathbb{N} \rightarrow \mathbb{N}$ defined as $f(x) = 2 \times x$ as :

$\{ \quad <x,y> \quad : \quad x,y \in \mathbb{N} \land y = 2 \times x \quad \}$.

This "object" in set theory (it is a set !) behaves like "usual" mathematical functions.

-
Voted up. Sorry for the confusing $\yen$. I changed it. Do you understand it now? I don't understand your answer sorry. Can you simplify or write more? I've never taken set theory so at this time, I don't know and won't need to know 'syntax of first-order set-theory', wff (this means well-formed formulas, yes ?), constant symbol, and the like? – dresserse Feb 17 '14 at 17:51
@dresserse - I expanded my answer; please, ask more, if needed. – Mauro ALLEGRANZA Feb 17 '14 at 18:04
Thanks. Chose yours for bounty for your magnificient effort. What's $S$? Why is $\phi(x) = x \in S \wedge P(x)$ ? And what do you mean 'set $z$ is a function'? Do you mean function as in calculus, a relation $A \to B$ such that each input is related to exactly one output? And how did you rewrite $\{ f(x) : x \in S \}$ as that complicated set underneath it? What does $<x, y> \in z$ mean? – dresserse Feb 18 '14 at 6:46
$\{x \in S : P(x) \}$ can be interpreted as the "elementhood test." This is more convenient for testing whether some $x \in S$ passes or fails $P(x)$. However, this may not help with listing all the elements in this set, because $P(x)$ may not be easily solvable for $x$.
$\{P(x) : x \in S \}$ is convenient for listing all the elements, but NOT for testing whether some $x \in S$ passes or fails $P(x)$.
For example, $P(x)$ could be a messy polynomial that cannot be solved handily.
Notwithstanding the positive votes and bonus this answer has received, it's a bit confused. In the second paragraph, $P$ on the RHS of the colon is a formula that says something either true or false about the element $x$. In the third paragraph, $P$ on the LHS of the colon should be a function, not a formula; you don't use a test of anything, but a rule for taking elements of $S$ and mapping them to something else. The idea of "solving" a polynomial (though a polynomial is correctly a function, not a formula) is a red herring. – HTFB Feb 17 '14 at 12:38