# Math Help - Union of sets

1. ## 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?

2. Hi
More generally if is a finite subset of , prove that 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)$ ?

3. 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?

4. 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 then $n_0=\max(\{n_0,...,n_k\})$
or $n_0 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.

5. 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 then $n_0=\max(\{n_0,...,n_k\})$
or $n_0 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?

6. Well I wouldn't have anything to say against your proof