3
$\begingroup$

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?

$\endgroup$
6
  • 2
    $\begingroup$ The second one isn't really mathematical-grammatically correct to me. $\endgroup$
    – Randall
    Sep 8, 2023 at 14:42
  • 7
    $\begingroup$ 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. $\endgroup$
    – William M.
    Sep 8, 2023 at 14:44
  • 5
    $\begingroup$ Both $A$ and $B$ are defined to be sets of natural numbers, so they can't be equal to $S$, which contains fractions. $\endgroup$
    – Sambo
    Sep 8, 2023 at 14:44
  • 3
    $\begingroup$ 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. $\endgroup$
    – LL 3.14
    Sep 8, 2023 at 14:47
  • 3
    $\begingroup$ 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. $\endgroup$
    – Trebor
    Sep 8, 2023 at 15:06

4 Answers 4

7
$\begingroup$

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.

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

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).

$\endgroup$
6
  • $\begingroup$ 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 ? $\endgroup$ Sep 8, 2023 at 14:51
  • $\begingroup$ @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. $\endgroup$ Sep 8, 2023 at 14:53
  • $\begingroup$ 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 ? $\endgroup$ Sep 8, 2023 at 14:59
  • $\begingroup$ @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. $\endgroup$ Sep 8, 2023 at 15:01
  • $\begingroup$ Or if we define $$B = \{n : n=2^x, x \in \mathbb{N_{>0}}\}$$ is it also incorrect ? $\endgroup$ Sep 8, 2023 at 15:05
3
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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 ? $\endgroup$ Sep 8, 2023 at 16:52
  • $\begingroup$ 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. $\endgroup$
    – MJD
    Sep 8, 2023 at 17:31
  • $\begingroup$ 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. $\endgroup$ Sep 8, 2023 at 18:21
  • $\begingroup$ No, neither is. $\endgroup$
    – MJD
    Sep 8, 2023 at 18:49
  • $\begingroup$ @lonestudent I've replied to your queries in my answer below. $\endgroup$
    – ryang
    Sep 9, 2023 at 14:21
2
$\begingroup$

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}.$

$\endgroup$
1
  • $\begingroup$ Thank you for the specific points, voted . $\endgroup$ Sep 9, 2023 at 18:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .