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

Question

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 under $f$ of 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}$

But Why $G/G = \{gG : g \in G \} \quad ? \quad$ And not $\{g \in G : gG\} ?$

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.

Answer 1

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.

Answer 2

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.

Answer 3

Consult the answer at https://math.stackexchange.com/a/149985/53259. It may help you. In brief, according to that answer:

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

Answer 4

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.

Answer 5

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.

Answer 6

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.