I'm trying to understand set builder notation, I was wondering what the difference (if any) is between:

$$ A = \lbrace k \; \vert \; \exists n \colon ( n \in \mathbb{N} \; \wedge k = 2n ) \rbrace $$ and: $$ B = \lbrace n \; \vert \; ( n,p \in \mathbb{N} \; \wedge n = 2p ) \rbrace $$

Both these set should contain all the positive even numbers. I also assume that both notations are correct.

  • $\begingroup$ The first is correct. The second makes no sense to me (where are the quantors?). $\endgroup$ – Henno Brandsma Jan 13 '16 at 19:29
  • $\begingroup$ The second notation is not correct because $p$ is not quantified. The formula $n,p\in\mathbb{N} \wedge n=2p$ is neither true nor false for any $n \in \mathbb{N}$. $\endgroup$ – kccu Jan 13 '16 at 19:29

$A$ is indeed the set of even integers.

$B$ is a bit bizarre. It is not the set of all even integers. $p$ is not bound, so If it didn't say "$p\in \Bbb N$" then we could give the definition the benefit of the doubt, and regard $p$ as a parameter. Assuming that $p$ is an integer, $B = \{2p\}$. In fact, even as written, we might still regard $p$ as a parameter, and then: $$ B = \begin{cases} \{2p\}&\text{if $p\in \Bbb N$,}\\ \emptyset&\text{if $p\notin \Bbb N$.}\\ \end{cases} $$

But this is very contrived: too little benefit, too much doubt. If someone wanted to define such a set $B$, in practice they wouldn't write it this way.

  • $\begingroup$ I think I am beginning to understand it, in $A$ the part $\exists n \colon$ binds $n$ making the whole term a predicate. In $B$ the term is not a predicate and as such cannot be used to create a set. Is this interpretation correct? (I apologize if I am imprecise, I'm a computer guy trying to learn set theory) $\endgroup$ – Baudin999 Jan 13 '16 at 20:06
  • $\begingroup$ No, that's not quite right. In the definition of $A$, the predicate following $\mid$ has one free variable, $k$, so it "is" or specifies a 1-ary predicate $P(k)$. In turn, the set-builder binds this variable $k$, and $A$ consists of all $k$ such that $P(k)$. In the definition of $B$, the formula following $\mid$ has two free variables, $n$ and $p$, and specifies a binary predicate $R(n,p)$. The set builder binds only $n$, and $B$ consists of all $n$ such that $R(n,p)$, whatever $p$ is. $\endgroup$ – BrianO Jan 13 '16 at 20:15
  • $\begingroup$ The older name for "set-builder notation" is "set comprehension". Do you know Python? "comprehensions" in Python (list comprehensions, dict comprehensions, generator expressions, ...) are inspired by set comprehensions in set theory. $\endgroup$ – BrianO Jan 13 '16 at 20:20
  • $\begingroup$ Again, though, nobody would write that definition of $B$. Although it's syntactically legal, it's weird for reasons indicated, almost certainly a mistake. If the intention is to define the even ints, then obviously it is a mistake. $\endgroup$ – BrianO Jan 13 '16 at 20:25
  • $\begingroup$ Thank you very much for the explanation, indeed, I've stumbled upon set-builder because of sequence expressions in F#. The main difference is that in F# (and Python) "what goes in" and "what comes out" is in a more familiar notation. It was hard to understand that even though, $\exists n \; so \; that \; ...$ is just a predicate and there is no $n$ being "injected" to test this $\Phi(n)$ on, this statement describes a set. I will need a few more hours to really understand all of your words, just know I'm really grateful that you took the time to help out a beginner with patience! $\endgroup$ – Baudin999 Jan 14 '16 at 7:02

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.