What is the difference between "for all" and "there exists" in set builder notation?

I'm having trouble with a specific example of set builder notation, and I'm hoping someone can help.
Here's an example of what I am having trouble with: $$A = \{n \in \mathbb{N} : \exists x \in \mathbb{N} \text{ and } n=2^x\}$$ $$B = \{n \in \mathbb{N} : \forall x \in \mathbb{N} \text{ and } n=2^x\}$$ Both of these sets are supposed to be equivalent to set $$S$$ where
$$S = \{...,\frac{1}{4},\frac{1}{2},1,2,4,...\}$$ My question is what is the difference between set $$A$$ and set $$B$$? Is one of the notations more accurate than the other?

• The second one isn't really mathematical-grammatically correct to me. Sep 8, 2023 at 14:42
• The second one is the empty set. You want the set of all $n$ natural numbers such that for all $x$ a natural number we have $n = 2^x.$ Obviously, no natural number satisfies this. Sep 8, 2023 at 14:44
• Both $A$ and $B$ are defined to be sets of natural numbers, so they can't be equal to $S$, which contains fractions. Sep 8, 2023 at 14:44
• Normally, one writes $\exists x\in \Bbb N, n=2^x$, there should not be an "and", or it should rather be a "such that". Same comment with $\forall$, where one usually put nothing. Sep 8, 2023 at 14:47
• To the downvoters: Do not downvote purely because the question contains factual errors. Do that to answers only. If people already got it right they wouldn't ask here anyway. Sep 8, 2023 at 15:06

Neither are particularly accurate, but that's because in part I think you want $$x \in \mathbb{Z}$$ instead.

I would also insist on the use of "such that" in lieu of "and" in $$A$$, and no such connective in $$B$$, since they just don't read right. "There exists some $$x \in \mathbb{N}$$ and $$n=2^x$$" is just a strange statement grammatically since, after all, there are indeed elements of $$\mathbb{N}$$. "Such that" is a lot more appropriate here, since you're using that $$x$$ to define $$n$$.

If $$n \in B$$, then we need $$n = 2^x$$ for all $$x \in \mathbb{Z}$$. However, this is nonsense, as if $$x,x' \in \mathbb{Z}$$ are distinct then $$n=2^x = 2^{x'}$$ but this requires $$x=x'$$, a contradiction.

I get what $$B$$ is trying to go for - the set of all powers of $$2$$ - but written as-is, it does not properly convey that.

• Thanks! You were right, it is $x \in \mathbb{Z}$, I just thought of it wrong while typing it out. Sep 8, 2023 at 15:07

Actually, $$A=\left\{2,4,8,16,\ldots\right\}$$, whereas $$B=\emptyset$$. This second assertion comes from the fact that there is no $$n\in\Bbb N$$ which is equal to every power of $$2$$ with natural exponent. On the other hand, the natural numbers which are a power of $$2$$ for some natural exponent are precisely the numbers $$2,4,8,16,\ldots$$ (unless you consider $$0$$ a natural number, in which case you should add $$1$$ to the list).

• Can you elaborate, what is wrong here: $n=2^x,~ x\in\mathbb N$ yields $n\in\mathbb N$, such that $n:=2,4,8\cdots$ . Not ? Sep 8, 2023 at 14:51
• @lonestudent No! As I wrote in my answer, the expression $n=2^x$, $\forall x\in\Bbb N$ means that $n$ is equal to every power of $2$ with natural exponent. Sep 8, 2023 at 14:53
• If we define $$B = \{n \in \mathbb{N_{>0}} : x \in \mathbb{N_{>0}} \text{ and } n=2^x\}$$ this produces $$B:=2,4,8\cdots$$ Right ? Sep 8, 2023 at 14:59
• @lonestudent Not really. That $B$ is meaningless. After the “:” sign, there should be a proposition depending on $n$ (and only on $n$), but that's not the case here. Sep 8, 2023 at 15:01
• Or if we define $$B = \{n : n=2^x, x \in \mathbb{N_{>0}}\}$$ is it also incorrect ? Sep 8, 2023 at 15:05

When you're having trouble understanding the basic meaning of some expression like $$A = \{n \in \mathbb{N} : \exists x \in \mathbb{N} \text{ and } n=2^x\}$$ it can be helpful to separate the basic meaning from the details of the mathematics. That way you can think about the logic without being distracted by stuff about powers of $$2$$. Instead of this example, let's look at an example with the same structure but no arithmetic:

$$C = \{\text{a person n in the world} : \exists \text { person x} \text{ and n is the mother of x} \}$$

Here I've replaced $$\Bbb N$$ with the set of people in the world, and the property “$$n=2^x$$” with “$$n$$ is the mother of $$x$$”. Powers are complicated and maybe unfamiliar, but everyone has lots of practice thinking about mothers.

Here $$C$$ is the set of all people who are someone's mother. Your mom is in this set, because there exists a person $$x$$ (namely you) that she is the mother of. But your dad is not in this set because he is not the mother of anyone. Queen Elizabeth I is also not in this set, because she was not anyone's mother.

$$D = \{\text{a person n in the world} : \forall \text { person x} \text{ and n is the mother of x} \}$$

This says something very different: person $$n$$ is in this set if they are the mother of $$x$$ for every person $$x$$. That is, this is the set of people who are everyone's mother. Is your mom in this set? No, because she is not my mother and $$D$$ is the set of people who are the mother of every person $$x$$, including me.

Of course there is no person at all who is everyone's mother, so $$D$$ is empty. Your set $$B$$ is empty for the same reason: there is no number $$n$$ that is equal to $$2^x$$ for every $$x$$.

• Can you explain why this notation is incorrect, I just need to understand what is wrong and what is correct : $$B = \{n : n=2^x, x \in \mathbb{N_{>0}}\}$$ Why this notation is meaningless, exactly ? Sep 8, 2023 at 16:52
• It's because $x$ is what is called a “free variable”. Consider this example: We want the set of people $n$ such that $n$ is the mother of $x$. Who is in the set? It's impossible to say, because I didn't tell you who $x$ is! Here's a post I wrote that discusses this in more detail.
– MJD
Sep 8, 2023 at 17:31
• What is the fundamental difference between these notations : The set of even numbers $$B:=\{2n\mid n\in\mathbb Z\}$$ and $$B:=\{2^n\mid n\in\mathbb N_{>0}\}$$ Do you think that, both notations are incorrect/meaningless ? Thank you. Sep 8, 2023 at 18:21
• No, neither is.
– MJD
Sep 8, 2023 at 18:49
• @lonestudent I've replied to your queries in my answer below. Sep 9, 2023 at 14:21

The abbreviation $$∃x{∈}\mathbb N$$ is short for $$\text{there exists some natural x such that\ldots}\\\text{for some natural x,\ldots.}$$ Since it isn't a sentence (and doesn't mean “some natural number exists”), the line

$$A = \{n \in \mathbb{N} : \exists x \in \mathbb{N} \color{red}{\text{ and }} n=2^x\}$$

is not meaningful until we delete the “and”: \begin{align}A_\text{new} &= \{n \in \mathbb{N} : \exists x {\in} \mathbb{N}\;n=2^x\}\\&=\text{the set of naturals such that }\textbf{each}\text{, for some natural x, equals 2^x}\\&= \left\{n: \;n \in \mathbb{N} \quad\text{and}\quad\exists x\, (x\in\mathbb{N}\quad\text{and}\quad n=2^x)\,\right\}\\&= \left\{n:\; \exists x\, (n \in \mathbb{N} \quad\text{and}\quad x\in\mathbb{N}\quad\text{and}\quad n=2^x)\,\right\}\\&= \left\{n:\; \exists x\, (x\in\mathbb{N}\quad\text{and}\quad n=2^x)\,\right\}\\&=\color{brown}{\{n : \exists x {\in} \mathbb{N}\;n=2^x\}}\\&=\color{brown}{\{2^x:x\in\mathbb N\}}\\&=\text{the set of values of the form 2^x such that x is natural}\\&=\{2,4,8,16,\ldots\}.\end{align} In the above, the sets written in brown are notational alternatives to each other (Wikipedia says that the latter is an extension of the set-builder notation). In this case the domain specification is redundant, but if we insist: $$A_\text{new} =\{2^x\in\mathbb N:x\in\mathbb N\}.$$

$$S = \left\{...,\frac{1}{4},\frac{1}{2},1,2,4,...\right\}$$

\begin{align}S &= \{2^x:x\in\mathbb Z\}\\&=\{n : \exists x {\in} \mathbb{Z}\;n=2^x\}.\end{align}

$$B = \{n \in \mathbb{N} : \forall x \in \mathbb{N} \color\red{\text{ and }} n=2^x\}$$

Similarly as the above, because the abbreviation $$\text“\forall x{∈}\mathbb N\text”$$ is short for “for each natural $$x,\ldots\text”,$$ the above line is not meaningful until we delete the “and”: \begin{align}B_\text{new} &= \{n \in \mathbb{N} : \forall x {\in} \mathbb{N}\;n=2^x\}\\&=\text{the set of naturals such that }\textbf{each}\text{, for }\textbf{every}\text{ natural x, equals 2^x}\\&=\emptyset,\end{align} noting that no natural number simultaneously equals $$2, 4, 8,$$ etc.

Reply to @lone student's queries above

Why is this meaningless, exactly? $$B_1 = \{n : n=2^x, x \in \mathbb{N_{>0}}\}$$

This isn't meaningless per se: it says that each element of $$B_1$$ equals $$2^x$$ and that $$x$$ is natural. Here, we are given insufficient information (for example, we don't know whether every $$x$$ belongs to $$\{3,7,14\}$$) to fully specify $$B_1;$$ in contrast, the variable $$x$$ in each of these sentences is bound:

• for each $$x,$$ (each element of $$B_1$$ equals $$2^x$$ and $$x$$ is natural)
• for some $$x,$$ (each element of $$B_1$$ equals $$2^x$$ and $$x$$ is natural)
• each element of $$B_1,$$ for each natural $$x,$$ equals $$2^x$$
• each element of $$B_1,$$ for some natural $$x,$$ equals $$2^x.$$

Is this incorrect/meaningless? $$B_2 = \{2^n\mid n\in\mathbb N_{>0}\}$$

This sentence is meaningful; as a matter of fact, $$B_2=A_\text{new}.$$

• Thank you for the specific points, voted . Sep 9, 2023 at 18:00