Let's call the first set in the question $S_1$ and the second set $S_2$. I'm not necessarily in this example in particular, it's just the first one that came to mind. Obviously, when defining a set that only contains ordered pairs, the first definition is a lot more clear. But if the set contains other elements that aren't ordered pairs, then we have to use an expression similiar to that of $S_2$ to define our set. But what if we are expecting a set that contains both ordered pairs and "singular" elements, which just so happens to have only ordered pairs in it. Is there a way to simplify the set definition so that we end up with a more readable definition, similar to that of $S_1$? Maybe by using rules of predicate logic, or other rules from set theory (which I'm not too familiar with)?

Thank you in advance!

  • 3
    $\begingroup$ I think this is simply the definition of the set builder notation when the expression before the colon is not just a variable. So it's not to be proved, it's just defined. $\endgroup$
    – aschepler
    Jun 28 at 22:34
  • $\begingroup$ I believe in your set $S_2$ you just wrote down the definition of $S_1$. It is an easy consequence of how the set-builder notation works. $\endgroup$
    – sadman-ncc
    Jun 28 at 23:15
  • $\begingroup$ Echoing the above sentiment about $S_2$ merely being the definition of $S_1.$ P.S. This question is orthogonally related. $\endgroup$
    – ryang
    Jun 29 at 9:12

1 Answer 1


Yes, you can prove it, but it will be very short.

Definition (set-builder notation with a function symbol) \begin{equation} \{f(x_1, x_2, x_3, …, x_n) : P(x_1, x_2, x_3, …, x_n)\} = \{a : \exists x_1 \exists x_2 \exists x_3 \cdots \exists x_n (a = f(x_1, x_2, x_3, …, x_n) \land P(x_1, x_2, x_3, …, x_n))\} \end{equation} if $n$ is a natural number, $x_1, x_2, x_3, \cdots, x_n$ are variables, $f$ is a $n$-ary function symbol and $P$ is a $n$-ary predicate symbol, for all $n, x_1, x_2, x_3, \cdots, x_n, f, P$.

You can prove it by applying this to $n = 2, x_1 = x, x_2 = y, \forall p \forall q \ f(p, q) = (p, q)$ and $\forall p \forall q \ P(p, q) = p < q$.

Your interest is likely to be in whether $\{(x, y) : P(x, y)\} = \{a : \exists x \exists y (a = (x, y) \land P(x, y))\}$ in general. We do not have to use an expression similiar to that of $S_2$ even if the set contains other elements that aren't ordered pairs: $\forall b (b \in \{(x, y) : P(x, y)\} \Longleftrightarrow b \in \{a : \exists x \exists y (a = (x, y) \land P(x, y))\} \Longleftrightarrow \exists x \exists y (b = (x, y) \land P(x, y)))$ Therefore, $\forall b (\lnot \exists x \exists y (b = (x, y) \land P(x, y)) \Longrightarrow b \notin \{(x, y) : P(x, y)\})$ i.e. if we cannot represent something as a pair, it is not in.

NB: I gave the answer within the framework of the naive set theory. We do not lose the essence of this question even if within it. Answering within the framework of the axiomatic one makes the discussion more difficult, as $<, S_1$ or $S_2$ is not necessarily a set, so we need to make a meta-argument.


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.