# Limit of sequence of sets

• Aug 24th 2012, 05:12 PM
sepmo
Limit of sequence of sets
I am trying to prove a proposition, but it's proving harder than I expected. I was wondering if someone could lead me in the right direction. Please don't give full answers. I'm just looking for a hint. The problem says:
If $\{E_n\}$ is a sequence of sets and $D_1=E_1, D_{n+1}=D_n\bigtriangleup E_{n+1}, n=1,2,...$, show that $lim D_n$ existis if and only if $lim E_n = \emptyset$.

Thank you.
• Sep 18th 2012, 02:36 PM
johnsomeone
Re: Limit of sequence of sets
I don't know exactly what "the limit of a sequence of sets" has been defined to mean in your problem. However, I can show you something that I think might prove this claim for your whatever your definition there is. I'll just state what I can prove, and then leave it to you to see if that, when considered in light of whatever definition you have of "convergence sequences of sets", proves this claim. I suspect this will do the job.
(And it appears my suspicion proved wrong. Typical. (Doh) )

Given a set $\mathbb{X}$ and $\mathcal{E} = \{E_n\}_1^{\infty} \subset \mathcal{P}(\mathbb{X})$, define $D_1=E_1$, and then inductively $D_{n+1}=D_n\bigtriangleup E_{n+1}, n=1,2,...$.

Let $E^* = \bigcap_{n = 1}^{\infty}E_n$.

Claim #1: If $E^* \ne \emptyset$ and $x \in E^*$, then $x \in D_n \Leftrightarrow n$ is odd.

Proof: Will be by induction.

Note that $x \in E^* \Rightarrow x \in E_n \ \forall n \in \mathbb{N}$.

Now let $S(m)$ be the proposition " $k \in \mathbb{N} \ni 1 \le k \le 2m \Rightarrow (x \in D_k \Leftrightarrow k$ is odd)".

Since $x \in E_1$, have that $x \in D_1 = E_1$. But also $x \in E_2$, so it follows that $x \notin D_2 = D_1 \bigtriangleup E_2$.

Thus have proven that $x \in D_1$, and $x \notin D_2$. That proves that $S(1)$ is true.

Assume $S(n)$ is true for some $n \in \mathbb{N}, n \ge 1$.

Let $k=2n$. Then $k$ is even, and $k \le 2n$. Thus $S(n)$ true implies that $x \notin D_{k} ( = D_{2n})$.

So $x \notin D_{2n}$, but also $x \in E_{2n+1}$. Thus $x \in D_{2n+1}=D_{2n} \bigtriangleup E_{n+1}$.

Now $x \in D_{2n+1}$, but also $x \in E_{2n+2}$. Thus $x \notin D_{2n+2}=D_{2n+1} \bigtriangleup E_{n+1}$.

Have shown that $S(n)$ true implies that $x \in D_{2n+1}$ and also that $x \notin D_{2n+2}$.

But those three statements ( $S(n)$ true, $x \in D_{2n+1}$, and $x \notin D_{2n+2}$) together exactly comprise the statement $S(n+1)$.

Thus $S(n) \Rightarrow S(n+1) \ \forall n \in \mathbb{N}$. Also have shown that $S(1)$ is true.

Thus by induction, have proven $S(n)$ is true $\forall n \in \mathbb{N}$. That proves Claim #1.

Claim #2: If $x \in \mathbb{X}$ and there exists $N \in \mathbb{N}$ such that $x \notin E_n \ \forall \ n > N$ (always here $n \in \mathbb{N}$),

then $x \in D_N \Rightarrow x \in D_n \ \forall \ n \ge N$,

and $x \notin D_N \Rightarrow x \notin D_n \ \forall \ n \ge N$.

Proof:

If $x \in D_N$, then since $x \notin E_{N+1}$, have that $x \in D_{N+1}=D_N\bigtriangleup E_{N+1}$.

Next, since $x \in D_{N+1}$ and $x \notin E_{N+2}$, can conclude that $x \in D_{N+2}=D_{N+1}\bigtriangleup E_{N+2}$.

By the obvious induction, $x \in D_n \ \forall n \ge N$.

Conversely, if $x \notin D_N$, then $x \notin E_{N+1} \Rightarrow x \notin D_{N+1}=D_N\bigtriangleup E_{N+1}$.

The induction is clear: for $n \ge N, x$ will be in neither $E_{n+1}$ (by the definition of $N$), nor $D_n$ (by induction), and therefore $x$ won't be in $D_{n+1}$.

That proves Claim #2.
• Sep 18th 2012, 02:45 PM
sepmo
Re: Limit of sequence of sets
Quote:

Originally Posted by johnsomeone
I don't know exactly what "the limit of a sequence of sets" has been defined to mean in your problem. However, I can show you something that I think might prove this claim for your whatever your definition there is. I'll just state what I can prove, and then leave it to you to see if that, when considered in light of whatever definition you have of "convergence sequences of sets", proves this claim. I suspect this will do the job.

Given a set $\mathbb{X}$ and $\mathcal{E} = \{E_n\}_1^{\infty} \subset \mathcal{P}(\mathbb{X})$, define $D_1=E_1$, and then inductively $D_{n+1}=D_n\bigtriangleup E_{n+1}, n=1,2,...$.

Let $E^* = \bigcap_{n = 1}^{\infty}E_n$.

Claim #1: If $E^* \ne \emptyset$ and $x \in E^*$, then $x \in D_n \Leftrightarrow n$ is odd.

Proof: Will be by induction.

Note that $x \in E^* \Rightarrow x \in E_n \ \forall n \in \mathbb{N}$.

Now let $S(m)$ be the proposition " $k \in \mathbb{N} \ni 1 \le k \le 2m \Rightarrow (x \in D_k \Leftrightarrow k$ is odd)".

Since $x \in E_1$, have that $x \in D_1 = E_1$. But also $x \in E_2$, so it follows that $x \notin D_2 = D_1 \bigtriangleup E_2$.

Thus have proven that $x \in D_1$, and $x \notin D_2$. That proves that $S(1)$ is true.

Assume $S(n)$ is true for some $n \in \mathbb{N}, n \ge 1$.

Let $k=2n$. Then $k$ is even, and $k \le 2n$. Thus $S(n)$ true implies that $x \notin D_{k} ( = D_{2n})$.

So $x \notin D_{2n}$, but also $x \in E_{2n+1}$. Thus $x \in D_{2n+1}=D_{2n} \bigtriangleup E_{n+1}$.

Now $x \in D_{2n+1}$, but also $x \in E_{2n+2}$. Thus $x \notin D_{2n+2}=D_{2n+1} \bigtriangleup E_{n+1}$.

Have shown that $S(n)$ true implies that $x \in D_{2n+1}$ and also that $x \notin D_{2n+2}$.

But theose three statements together exactly comprise the statement $S(n+1)$.

Thus $S(n) \Rightarrow S(n+1) \ \forall n \in \mathbb{N}$. Also have shown that $S(1)$ is true.

Thus by induction, have proven $S(n)$ is true $\forall n \in \mathbb{N}$. That proves the claim #1.

Claim #2: If $x \in \mathbb{X} \ni \exists N \in \mathbb{N} \ni \ \forall n \in \mathbb{N}, n > N, x \notin E_n$,

then $x \in D_N \Rightarrow x \in D_n \forall n \in \mathbb{N}, n > N$, and $x \notin D_N \Rightarrow x \notin D_n \forall n \in \mathbb{N}, n > N.$.

Proof:

If $x \in D_N$, then $x \notin E_{N+1} \Rightarrow x \in D_{N+1}=D_N\bigtriangleup E_{N+1}$.

Then $x \in D_{N+1}$ and $x \notin E_{N+1}$ again together imply that $x \in D_{N+2}=D_{N+1}\bigtriangleup E_{N+2}$.

By the obvious induction, $x \in D_n \ \forall n > N$.

Conversely, if $x \notin D_N$, then $x \notin E_{N+1} \Rightarrow x \notin D_{N+1}=D_N\bigtriangleup E_{N+1}$.

The induction is clear: for $n \ge N, x$ will be in neither $E_{n+1}$ (by the definition of $N$), nor $D_n$ (by induction), and therefore $x$ won't be in $D_{n+1}$.

That proves Claim #2.

Thanks for the response. I actually found a way of proving it using the characteristic function. It is quite a short proof.