Question about proof from a guy with a highschool education

[Fredrik]

To fix the LaTeX, use an align environment. Click the quote button next to my post to see how I'm doing it. You can edit your post for 11 hours and 40 minutes. I like to use $\mathcal P$ (\mathcal P) for powersets.
\begin{align}
a &= b = c\\
&=d = e\\
&=f =g
\end{align} If you want to try to find $\mathcal P(\mathcal P(S))$ explicitly for some set S, I recommend that you consider a very simple S like S={1,2}, or even S={1}.

 

[reenmachine]

I recommend that you consider a very simple S like S={1,2}

$S=\{1,2\}$ $\mathcal P(S)=\{∅,\{1\},\{2\},\{1,2\}\}$$\mathcal P(\mathcal P(S))= \begin{align}&\{ \ ∅,\{\{1\}\},\{\{2\}\},\{\{1,2\}\},\{\{1\},\{1,2\}\},\\ &\{\{2\}\},\{1,2\}\},\{\{1\},\{2\}\},\\ &\{\{1\},\{2\},\{1,2\}\} \ \}\end{align}$

 

[Fredrik]

You have the right idea, but you forgot a few sets that involve the empty set. For example, when you listed all the subsets of $\mathcal P(S)$ with exactly 1 member, you left out $\{\emptyset\}$. When you listed the ones with exactly 2 members, you left out sets like $\{\emptyset,\{1\}\}$.

You should type the \begin{align} to the left of the code for your left-hand side, like I did in my example.

 

[reenmachine]

You have the right idea, but you forgot a few sets that involve the empty set. For example, when you listed all the subsets of $\mathcal P(S)$ with exactly 1 member, you left out $\{\emptyset\}$. When you listed the ones with exactly 2 members, you left out sets like $\{\emptyset,\{1\}\}$.

You should type the \begin{align} to the left of the code for your left-hand side, like I did in my example.

I was going to ask you about the ∅.Should ∅ be between brackets like {∅} when he's an element of a powerset? I thought ∅ was a special case that was always left alone as an element of every powerset , looks like I was wrong.

If $\{∅\}\in \mathcal P(S)$ , then $\{\{∅\}\} \in \mathcal P(P(S))$ but since $\{∅\}$ is a subset of every set , are $\{∅\}$ and $\{\{∅\}\}$ two separate elements of $\mathcal P(P(S))$?

For example, when you listed all the subsets of $\mathcal P(S)$ with exactly 1 member, you left out $\{\emptyset\}$

Here's what I wrote : $\mathcal P(S)=\{∅,\{1\},\{2\},\{1,2\}\}$

The ∅ is there , but not between brackets of his own.This is what you meant? If the brackets were missing , does the ∅ without brackets still stays there? (I think not)

thanks!

 

[Fredrik]

Your answer for $\mathcal P(S)$ was correct. We know that $\varnothing\subseteq S$, and that this implies that $\varnothing\in\mathcal P(S)$.

I was talking about your answer for $\mathcal P(\mathcal P(S))$, where your strategy appeared to be to first list all the subsets of $\mathcal P(S)$ with exactly 0 elements, then all subsets of $\mathcal P(S)$ with exactly 1 element,... This is a good strategy, but you left out a few sets.

Btw, there are two LaTeX codes for the empty set, \emptyset and \varnothing. It doesn't matter which one you use. The former looks like a zero with a slash through it, and the latter looks like a circle with a slash through it. I've been using \emptyset mostly, but I think I'm going to switch to \varnothing.

 

[reenmachine]

Your answer for $\mathcal P(S)$ was correct. We know that $\varnothing\subseteq S$, and that this implies that $\varnothing\in\mathcal P(S)$.

I was talking about your answer for $\mathcal P(\mathcal P(S))$, where your strategy appeared to be to first list all the subsets of $\mathcal P(S)$ with exactly 0 elements, then all subsets of $\mathcal P(S)$ with exactly 1 element,... This is a good strategy, but you left out a few sets.

Btw, there are two LaTeX codes for the empty set, \emptyset and \varnothing. It doesn't matter which one you use. The former looks like a zero with a slash through it, and the latter looks like a circle with a slash through it. I've been using \emptyset mostly, but I think I'm going to switch to \varnothing.

(EDIT: are you sure my answer is correct for $\mathcal P(S)$?)

Ok , I understand what you mean when you're saying that I forgot all the subsets of $\mathcal P(S)$ including $\varnothing$ in them.Basically I can reproduce all elements of $\mathcal P(\mathcal P(S))$ and add $\varnothing$ in it.Here's something I'm more confused about:

$\mathcal P(S)=\{\varnothing,\{1\},\{2\},\{1,2\}\}$ (for clearness)Since $\{\varnothing\} \subset \mathcal P(S)$ , then $\{\varnothing\} \in \mathcal P(\mathcal P(S))$.If you create the powerset $\mathcal P(\mathcal P(\mathcal P(S)))$ , are $\{\{\varnothing\}\} \subset \mathcal P(\mathcal P(S))$ and $\{\varnothing\} \subset \mathcal P(\mathcal P(S))$ ? Will both of them become separate elements of $\mathcal P(\mathcal P(\mathcal P(S)))$ ?

Last question , if $\{\{\varnothing\}\} \subset \mathcal P(\mathcal P(S))$ and $\{\varnothing\} \subset \mathcal P(\mathcal P(S))$ , then $\{\{\{\varnothing\}\},\{\varnothing\}\} \in \mathcal P(\mathcal P(\mathcal P(S)))$ ?

What I really want to know is if $\{\varnothing\}$ is an element of a powerset A because he was a subset of A , do we have to add a pair of brackets to ''transform'' him into a subset of powerset A?

If we do , $\{\{\varnothing\}\}$ will be a subset of power set A , but since $\{\varnothing\}$ is a subset of every set , then both $\{\{\varnothing\}\}$ and $\{\varnothing\}$ will be different subsets of power set A?

I might be severely overthinking all of this.Sorry if that's the case.

thanks a lot

 

[Fredrik]

(EDIT: are you sure my answer is correct for $\mathcal P(S)$?)

Yes. Since S={1,2} has two elements, a subset of S will have 0,1 or 2 elements.

S has one subset with exactly 0 elements: ∅
S has two subsets with exactly 1 element each: {1} and {2}
S has one subset with exactly 2 elements: {1,2}

Therefore P(S)={∅,{1},{2},{1,2}}.

Since $\{\varnothing\} \subset \mathcal P(S)$ , then $\{\varnothing\} \in \mathcal P(\mathcal P(S))$.If you create the powerset $\mathcal P(\mathcal P(\mathcal P(S)))$ , are $\{\{\varnothing\}\} \subset \mathcal P(\mathcal P(S))$ and $\{\varnothing\} \subset \mathcal P(\mathcal P(S))$ ? Will both of them become separate elements of $\mathcal P(\mathcal P(\mathcal P(S)))$ ?

Yes to all of that.

Last question , if $\{\{\varnothing\}\} \subset \mathcal P(\mathcal P(S))$ and $\{\varnothing\} \subset \mathcal P(\mathcal P(S))$ , then $\{\{\{\varnothing\}\},\{\varnothing\}\} \in \mathcal P(\mathcal P(\mathcal P(S)))$ ?

No to the conclusion. $\{\{\varnothing\}\}$ and $\{\varnothing\}$ will be elements of $\mathcal P(\mathcal P(\mathcal P(S)))$, so you can write $\{\{\varnothing\}\},\{\varnothing\}\in\mathcal P(\mathcal P(\mathcal P(S)))$ or $\{\{\{\varnothing\}\},\{\varnothing\}\}\subset \mathcal P(\mathcal P(\mathcal P(S)))$.

What I really want to know is if $\{\varnothing\}$ is an element of a powerset A because he was a subset of A , do we have to add a pair of brackets to ''transform'' him into a subset of powerset A?

For all sets x,y, $x\in y$ is equivalent to $\{x\}\subset y$.

For all sets A, the following statements are equivalent (either all true or all false).

1. ∅ is an element of A.
2. {∅} is a subset of A.
3. {∅} is an element of P(A).
4. {{∅}} is a subset of P(A).
5. {{∅}} is an element of P(P(A)).
...

If we do , $\{\{\varnothing\}\}$ will be a subset of power set A , but since $\{\varnothing\}$ is a subset of every set , then both $\{\{\varnothing\}\}$ and $\{\varnothing\}$ will be different subsets of power set A?

No, ∅ is a subset of every set, but {∅} is not. A set that has {∅} as a subset has ∅ as an element, and ∅ is certainly not an element of every set.

{{∅}} and {∅} are not the same. If they were, then since two sets are equal if and only if they have the same elements, we would have {∅}=∅. But the left-hand side is a set with 1 element, and the right-hand side is a set with 0 elements.

 

[reenmachine]

Yes. Since S={1,2} has two elements, a subset of S will have 0,1 or 2 elements.

S has one subset with exactly 0 elements: ∅
S has two subsets with exactly 1 element each: {1} and {2}
S has one subset with exactly 2 elements: {1,2}

Therefore P(S)={∅,{1},{2},{1,2}}.

Ok good

No to the conclusion. $\{\{\varnothing\}\}$ and $\{\varnothing\}$ will be elements of $\mathcal P(\mathcal P(\mathcal P(S)))$, so you can write $\{\{\varnothing\}\},\{\varnothing\}\in\mathcal P(\mathcal P(\mathcal P(S)))$ or $\{\{\{\varnothing\}\},\{\varnothing\}\}\subset \mathcal P(\mathcal P(\mathcal P(S)))$.

Ok , I'm pretty certain I either meant $\{\{\{\varnothing\}\},\{\varnothing\}\} \in \mathcal P(\mathcal P(\mathcal P(\mathcal P(S))))$ or $\{\{\{\varnothing\}\},\{\varnothing\}\} \subset \mathcal P(\mathcal P(\mathcal P(S)))$ so basically I was right in my head

For all sets x,y, $x\in y$ is equivalent to $\{x\}\subset y$.

Even though I knew it it's a nice statement to look at once in a while.

For all sets A, the following statements are equivalent (either all true or all false).

1. ∅ is an element of A.
2. {∅} is a subset of A.
3. {∅} is an element of P(A).
4. {{∅}} is a subset of P(A).
5. {{∅}} is an element of P(P(A)).
...

Ok , so in our case , since A isn't a powerset , then all the statements will be false since ∅ can only be an element of powersets.

The correct statements would be:
1. ∅ is a subset of A.
2. ∅ is an element of P(A).
3. {∅} is a subset of P(A).
4. {∅} is an element of P(P(A)).
5. {{∅}} is a subset of P(P(A)).
6. {{∅}} is an element of P(P(P(A))).

and to add to these statements:

7. ∅ is a subset of all sets.
8. ∅ is also an element of P(P(A)) and P(P(P(A))).
9. {∅} is also a subset of P(P(A)) and P(P(P(A))) because of that.

So basically , there's an accumulation of ∅ involved (even if they are between many brackets) the deeper you go into powersets? (and I know that they aren't the same thing but if we were to write many many powersets of powersets etc... the symbol ∅ would appear more and more the deeper you go , between brackets or not is that correct?)

No, ∅ is a subset of every set, but {∅} is not. A set that has {∅} as a subset has ∅ as an element, and ∅ is certainly not an element of every set.

{{∅}} and {∅} are not the same. If they were, then since two sets are equal if and only if they have the same elements, we would have {∅}=∅. But the left-hand side is a set with 1 element, and the right-hand side is a set with 0 elements

Ok that's good that you refreshed my mind with that.

BTW , \varnothing is definitely the best choice in LaTeX.

Thank you very much man!

 

[Fredrik]

Ok , so in our case , since A isn't a powerset , then all the statements will be false since ∅ can only be an element of powersets.

For all sets x with two elements or more, ∅ is an element of {∅,x}, and {∅,x} isn't the powerset of anything.

So basically , there's an accumulation of ∅ involved (even if they are between many brackets) the deeper you go into powersets? (and I know that they aren't the same thing but if we were to write many many powersets of powersets etc... the symbol ∅ would appear more and more the deeper you go , between brackets or not is that correct?)

Yes, that's right.

 

[reenmachine]

For all sets x with two elements or more, ∅ is an element of {∅,x}, and {∅,x} isn't the powerset of anything.
.

I don't understand this.I thought the empty set was generally not an element of sets.

 

[Fredrik]

I don't understand this.I thought the empty set was generally not an element of sets.

It certainly can be, just like any other set.

The axiom of pairing says that for all sets x,y there's a set z such that $x,y\in z$.

I think that this is equivalent to saying that for all sets x,y, {x,y} is a set. (I think I've seen a proof of that, but I don't want to think about that today).

So for any set x, there's a set that has ∅ and x as elements.

 

[reenmachine]

It certainly can be, just like any other set.

The axiom of pairing says that for all sets x,y there's a set z such that $x,y\in z$.

I think that this is equivalent to saying that for all sets x,y, {x,y} is a set. (I think I've seen a proof of that, but I don't want to think about that today).

So for any set x, there's a set that has ∅ and x as elements.

oh ok I didn't see it that way.Very clear.

Thanks!

It's been a long day , I'll go get some rest.

 

[CompuChip]

BTW , in the book of proof they denote the set $R^2$ with $\{(x,y) : x,y \in R\}$ , which is a notation of the form $\{x : p(x)\}$.It still confuses me a little bit when it is correct or not to use it.

If you prefer more formalism you could write $\{ (x, y) \in R \times R : x, y \in R \}$ or just $R \times R$. Since you are basically restating the definition of $R \times R$ now, you could even insert a trivial condition like $\{ (x, y) \in R \times R : 1 = 1 \}$, or - if you allow p(x, y) to be omitted if it is true for all x and y, $\{ (x, y) \in R \times R \}$.

Formally it is probably never "correct", in practice it is correct when it is clear what you mean and unambiguous, like in this case.

 

[Fredrik]

It's fine to use the notation $\{x:p(x)\}$ in those cases where we have already proved that $\{x:p(x)\}$ is a set.

 

[reenmachine]

Here's an exercise from the book of proof.

$\forall n \in N \ A_n = \{0,1,2,3,...,n\}$

$$\bigcup_{i \in N}A_i = ?$$

$$\bigcap_{i \in N}A_i = ?$$

My answers were:

$$\bigcup_{i \in N}A_i = \{0,1,2,3,...,\infty\}$$

and

$$\bigcap_{i \in N}A_i = \{0\}$$

The book answers are:

$$\bigcup_{i \in N}A_i = \{0\} \cup N$$

and

$$\bigcap_{i \in N}A_i = \{0,1\}$$

I don't understand what they are doing here.It seems the misconception I have comes from the role of 0 in N.In the second one , if $A_0$ , then $1$ isn't going to be an element of that set.In the first one it seems they are saying that $0$ isn't part of $N$ or something like that.

thx!

 

[micromass]

A lot of books don't define 0 as a natural number. So for them

\mathbb{N}=\{1,2,3,4,...\}

The book of proof is following that convention.

Anyway, I want to say something about your first answer. You wrote

\bigcup A_n = \{0,1,2,3,...,\infty\}

The $\infty$ shouldn't be there. Infinity is not a natural number. And infinity is also not in any of the sets $A_n$. So it's not in the union.

Regardless, try to solve these exercises: (I use the convention here that $\mathbb{N}$ does not contain $0$, but I usually don't follow that convention)

\bigcup_{n\in \mathbb{N}} [0,1-(1/n)]
\bigcup_{n\in \mathbb{N}} [0,1-(1/n) )
\bigcap_{n\in \mathbb{N}} [0,1+(1/n)]
\bigcap_{n\in \mathbb{N}} [0,1+(1/n))

 

[reenmachine]

\bigcup_{n\in \mathbb{N}} [0,1-(1/n)]
\bigcup_{n\in \mathbb{N}} [0,1-(1/n) )
\bigcap_{n\in \mathbb{N}} [0,1+(1/n)]
\bigcap_{n\in \mathbb{N}} [0,1+(1/n))

I don't understand the difference between the first two and the last two.I see the brackets changes but it doesn't make sense in my mind.

$$\bigcup_{n\in \mathbb{N}} [0,1-(1/n)] = \{-0,9 , -0,4 , ... , 0,1\}$$

 

[micromass]

I don't understand the difference between the first two and the last two.I see the brackets changes but it doesn't make sense in my mind.

The first one asks you to calculate

[0,1-(1/1)]\cup [0,1-(1/2)] \cup [0,1-(1/3)]\cup ...

The second one is

[0,1-(1/1))\cup [0,1-(1/2)) \cup [0,1-(1/3))\cup ...

Do you know the difference between [a,b] and [a,b) (or sometimes written as [a,b[ in Europe)?

 

[micromass]

anyway , \bigcup_{n\in \mathbb{N}} [0,1-(1/n)] = $\{-0,9 , -0,4 , ... , 0,1\}$

Not sure what you mean with this.

 

[reenmachine]

Do you know the difference between [a,b] and [a,b) (or sometimes written as [a,b[ in Europe)?

I have no clue.

 

[micromass]

I have no clue.

[a,b] = \{x\in \mathbb{R}~\vert~a\leq x \leq b\}
[a,b) = \{x\in \mathbb{R}~\vert~a\leq x < b\}
(a,b] = \{x\in \mathbb{R}~\vert~a < x\leq b\}
(a,b) = \{x\in \mathbb{R}~\vert~a < x < b\}

The last one should not be confused with (a,b) as an ordered pair. It's usually clear from context which one is meant.

 

[reenmachine]

not sure what you mean with this.

$0.1 - 1/1 = -0.9$
$0.1 - 1/2 = -0.4$
...
$0.1 - 1/\bar{9} = 0.1?$

I was just trying to write the elements at both extreme.I can't calculate millions of fractions to find all elements.I'm not really sure what I should do here.

 

[Fredrik]

There's no 0.1 in the exercises suggested by micromass. Did you look at the definitions in post #413? For example, $[0,1-1/2]=[0,1/2]=\{x\in\mathbb R:0\leq x\leq 1/2\}$. This is the interval of all real numbers from 0 and 1/2 (including 0 and 1/2). So you're supposed to find the union of infinitely many intervals. Note that we're talking about a sequence of smaller and smaller intervals. Edit: And by "smaller", I meant "bigger".

 

[reenmachine]

There's no 0.1 in the exercises suggested by micromass. Did you look at the definitions in post #413? For example, $[0,1-1/2]=[0,1/2]=\{x\in\mathbb R:0\leq x\leq 1/2\}$. This is the interval of all real numbers from 0 and 1/2 (including 0 and 1/2). So you're supposed to find the union of infinitely many intervals. Note that we're talking about a sequence of smaller and smaller intervals.

that went over my head , I thought it was 0.1 minus something.Rough day at the office for me.

So it's $0 ,$ then $1- 1/n$.

I'm going to the restaurent I'll try them again when I come back.

 

[reenmachine]

\bigcup_{n\in \mathbb{N}} [0,1-(1/n)]
\bigcup_{n\in \mathbb{N}} [0,1-(1/n) )
\bigcap_{n\in \mathbb{N}} [0,1+(1/n)]
\bigcap_{n\in \mathbb{N}} [0,1+(1/n))

\bigcup_{n\in \mathbb{N}} [0,1-(1/n)] = $\{x \in R : 0 ≤ x ≤ 1\}$

\bigcup_{n\in \mathbb{N}} [0,1-(1/n) ) = $\{x \in R : x = 0\}$ ? If n=1 , then it is [0,1-(1/1)) so [0,0) , how do I operate with this? Is this the empty set?

\bigcap_{n\in \mathbb{N}} [0,1+(1/n)] I'm not sure I get it , how could any number intersect if n changes? I apologize for my lack of entrepreneurship on these exercises but I am confused as hell.

What I mean by numbers can't intersect is [0,1+(1/1)] = [0,2] and [0,1+(1/2)] = [0,1.5] and so on...which intersection can we find by changing n?

edit: maybe I get it , is the intersection $\{x \in R : 0 ≤ x ≤ 1\}$ ? So basically the same set as the first.

Hopefully you see my edit before replying if I'm right lol

 

[Fredrik]

First one: Close, but not quite right. There's one little thing you seem to be overlooking.

Second: Nope, that's pretty far off.

Yes the notation [0,0) is weird, because the "[" suggests that 0 is included, and the ")" suggests that 0 is not included. But the definition gives us a clear answer: $[0,0)=\{x\in\mathbb R:0\leq x<0\}$. At least it's clear to me. You may have to think about it. Can you see it? Is [0,0) equal to {0} or ∅ or perhaps neither? Does our attempt to define [0,0) even make sense?

Third: Look at the definition of "intersection" again. What does the definition say about $$\bigcap_{n\in\mathbb N}\left[0,1-\frac 1 n\right]?$$ Don't try to come up with the final answer, just tell me what the definition says that the expression above (not including the question mark) means.

OK, now I've seen your edit. Nope, that answer is wrong. My advice is still the same.

Edit: Apparently I read the sign wrong in the third exercise.

 

[reenmachine]

First one: Close, but not quite right. There's one little thing you seem to be overlooking.

At least re-assure me that what I am missing isn't 1 divided by n=0 before I start to overheat my brain

 

[micromass]

At least re-assure me that what I am missing isn't 1 divided by n=0 before I start to overheat my brain

That's not what you're missing

 

[reenmachine]

Second: Nope, that's pretty far off.

Yes the notation [0,0) is weird, because the "[" suggests that 0 is included, and the ")" suggests that 0 is not included. But the definition gives us a clear answer: $[0,0)=\{x\in\mathbb R:0\leq x<0\}$. At least it's clear to me. You may have to think about it. Can you see it? Is [0,0) equal to {0} or ∅ or perhaps neither? Does our attempt to define [0,0) even make sense?

$[0,0)=\{x\in\mathbb R:0\leq x<0\}$ This doesn't make sense in my head , in this notation x could be equal to 0 yet it explicitely says that 0 is bigger than x.

Suppose x=0
Then 0 < 0 doesn't make sense

Suppose x=0,00001
Then 0,00001 < 0 doesn't make sense

Suppose x=-1
Then 0 ≤ -1 doesn't make sense

what's left to make sense here?

 

[reenmachine]

That's not what you're missing

I haven't been thinking about it for long but what I see that could be a problem now would be the second ≤ in $\{x \in R : 0 ≤ x ≤ 1\}$

Maybe $\{x \in R : 0 ≤ x < 1\}$ but then again I thought 0,9999999999... = 1.

And that's not to mention your statement that [a,b] = \{x\in \mathbb{R}~\vert~a\leq x \leq b\}