Union of sets

Printable View

November 30th 2009, 12:25 AM
aman_cc

Union of sets

Consider a set $S$ . ( $S$ can be finite or infinite)

Let $I_1,I_2,....I_n,.....$ be subsets of $S$ , such that
1. $I_i \subseteq I_{i+1}$
2. $\bigcup I_i$ is finite

Prove that there exits $n_0 \in \aleph$ , such that for any $n_1,n_2 \geq n_0$ , $I_{n1}=I_{n2}$

I want to prove this in a rigorous way. Here is my attempt

1. Claim there exists an $n_0$ , such $\bigcup I_i$ = $I_{n_0}$ . If this claim is true proving above is trivial.
2. So to prove the claim. Consider any $x \in \bigcup I_i$ . Thus $x$ must belong to some $I_n$ . Let $n_1$ be minimum such $n$ . Iterate over all the elements of $\bigcup I_i$ (say ' $k$ ' elements, as $\bigcup I_i$ is finite). We will have a set $A=\{n_1,n_2,....n_k\}$ . Now claim that $n_0=max(A)$ . (This claim is easy to prove)

I have two questions here:
1. Is the above proof rigorous enough !
2. How do I prove that $max(A)$ exists? More generally if $A$ is a finite subset of $\aleph$ , prove that $max(A)$ exits and is unique?

Please help !
November 30th 2009, 01:42 AM
clic-clac

Hi

Quote:

More generally if http://www.mathhelpforum.com/math-he...2eacbe29-1.gif is a finite subset of http://www.mathhelpforum.com/math-he...15134b0c-1.gif, prove that http://www.mathhelpforum.com/math-he...027a4521-1.gif exits and is unique?

Just apply the "fundamental property" of $\mathbb{N}$ (i.e. the natural order over $\mathbb{N}$ is a well order, i.e. any non-empty subset of $\mathbb{N}$ has a minimum) to the subset $\{n\in\mathbb{N}\ ;\ n>_n1,...,n>n_k\}.$
It is non-empty (why?) so it has a minimum; let $m$ be that minimum, what is $max(A)$ ?
November 30th 2009, 06:04 AM
aman_cc

Quote:

Originally Posted by clic-clac

Hi
Just apply the "fundamental property" of $\mathbb{N}$ (i.e. the natural order over $\mathbb{N}$ is a well order, i.e. any non-empty subset of $\mathbb{N}$ has a minimum) to the subset $\{n\in\mathbb{N}\ ;\ n>_n1,...,n>n_k\}.$
It is non-empty (why?) so it has a minimum; let $m$ be that minimum, what is $max(A)$ ?

Thanks. Sorry I have not followed your argument exactly. Do you mind saying it again plz?
November 30th 2009, 06:39 AM
clic-clac

If you consider $\emptyset\neq A=\{n_1,...,n_k\}\subseteq\mathbb{N},$ then the subset $B$ of $\mathbb{N}$ of elements greater than all $n_i, 1\leq i\leq k$ is non-empty ( $\sum\limits_{i=1}^kn_i +1$ belongs to it)
Therefore it has a minimum, $m,$ and $m-1=\max(A).$
Indeed, if $m-1\notin A;$ by definition of $m,\ p\geq m\Rightarrow p\notin A,$ so $m-1>n_i,\ 1\leq i\leq n,$ i.e. $m-1\in B,$ contradiction.
Hence $m-1\in A$ and forall $a\in A, a\leq m-1$ by definition of $m,$ i.e. $m-1=\max(A).$

There are various ways I guess to show that, we can proceed by induction on $k$ :

If $k=1,$ nothing to show $(n_1=\max(A)).$ Assume any subset of $\mathbb{N}$ with $k$ elements has a max, consider $\{n_0,...,n_k\},$ then $\{n_1,...,n_k\}$ has a max, let's say $n_j,$ two cases (because the order is total):
either $n_j<n_0,$ then $n_0=\max(\{n_0,...,n_k\})$
or $n_0<n_j,$ and $n_j=\max(\{n_0,...,n_k\})$

Actually the second proof may be better than the first: it only uses the totality of the order, which is a sufficient (and necessary) condition to be able to say that any finite non-empty subset has a maximum.
November 30th 2009, 06:47 AM
aman_cc

Quote:

Originally Posted by clic-clac

If you consider $\emptyset\neq A=\{n_1,...,n_k\}\subseteq\mathbb{N},$ then the subset $B$ of $\mathbb{N}$ of elements greater than all $n_i, 1\leq i\leq k$ is non-empty ( $\sum\limits_{i=1}^kn_i +1$ belongs to it)
Therefore it has a minimum, $m,$ and $m-1=\max(A).$
Indeed, if $m-1\notin A;$ by definition of $m,\ p\geq m\Rightarrow p\notin A,$ so $m-1>n_i,\ 1\leq i\leq n,$ i.e. $m-1\in B,$ contradiction.
Hence $m-1\in A$ and forall $a\in A, a\leq m-1$ by definition of $m,$ i.e. $m-1=\max(A).$

There are various ways I guess to show that, we can proceed by induction on $k$ :

If $k=1,$ nothing to show $(n_1=\max(A)).$ Assume any subset of $\mathbb{N}$ with $k$ elements has a max, consider $\{n_0,...,n_k\},$ then $\{n_1,...,n_k\}$ has a max, let's say $n_j,$ two cases (because the order is total):
either $n_j<n_0,$ then $n_0=\max(\{n_0,...,n_k\})$
or $n_0<n_j,$ and $n_j=\max(\{n_0,...,n_k\})$

Actually the second proof may be better than the first: it only uses the totality of the order, which is a sufficient (and necessary) condition to be able to say that any finite non-empty subset has a maximum.

Thanks very much. I follow it now. I had similar idea but was not sure how to put it. I was trying to repeatedly construct a sub-set by removing the min element (existence of which is guaranteed by well order property) repeatedly till only one element is left and I would then claim that this is the max. But was not able to put it formally. Thanks very much.

So with this - does my proof to the original problem looks convincing enough?
November 30th 2009, 07:39 AM
clic-clac

Well I wouldn't have anything to say against your proof :)