I encountered the following example whilst studying Equivalence Classes from How to prove it, Velleman. :

Let $ B= \{(p, q) ∈ P × P | \text{the person p has the same birthday as the person q } \} $

Let D be the set of all possible birthdays. In other words,$ D = \{Jan. 1, Jan. 2, Jan. 3, . . . ,Dec. 30, Dec. 31\}. $

Now for each $d ∈ D$, let $P_d = \{p ∈ P | \text{the person p was born on the day d } \} $ .

Then the family $ F = \{P_d | d ∈ D\} $ is an indexed family of subsets of P.

We can then redefine B as:

$B = \{(p, q) ∈ P × P | ∃d ∈ D(p ∈ P_d \land q ∈ P_d )\}$

$= \{(p, q) ∈ P × P | ∃d ∈ D((p, q) ∈ P_d × P_d )\}$

$ = ∪_{d∈D}(P_d × P_d ). $

My question: Could I write $ \{(p, q) ∈ P × P | ∃d ∈ D((p, q) ∈ P_d × P_d )\}$ as $ \{(p, q) ∈ P_d × P_d | d ∈ D\}$?

I think yes ( but I want to be sure ). My reasoning is since inside the set builder notation we have $ (p,q) ∈ P × P \land (p,q) ∈ P_d × P_d $ then $ (P × P) \land (P_d × P_d) = (P_d × P_d)$ Since $ P_d × P_d \subseteq P × P $.


This is not standard set builder notation and I would advise against using it. The general scheme is: $$ B:=\{x\in A\mid\varphi(x)\} $$ Here the collection $A$ serves as an upper bound on where the $x$'s come from, so that you immediately know that $B\subseteq A$. This notation is a direct implementation of the axiom of restricted comprehension, which tells us that if $A$ is a set, then $B$ as defined above is a set as well.

Crucially, the set $A$ is fixed before defining $B$! In your notation $$ \{(p, q) ∈ P_d × P_d | d ∈ D\} $$ however, the role of $A$ is taken by $P_d \times P_d$ which depends on the parameter $d$ which in turn varies over $D$. While it is clear what you want to define, your relaxed notation makes it very easy to write down set builder terms which denote proper classes, for example: $$ \{x\in A\mid A\text{ is a set with at most $2$ elements}\} $$

  • $\begingroup$ I think it is worth noting that you can write the set in a much more concise way without using the set builder notation at all. It is simply $\cup_{d\in D} P_d\times P_d$. $\endgroup$ – tomasz Feb 22 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.