Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say I have a finite set $A$ and know its cardinality. How can I prove that, by repeatedly applying some algorithm, which removes a known number of elements from $A$ each time, its cardinality will stop at some value? It should stop because the aforementioned algorithm requires a fixed number of elements present in the set.

I tried induction, but couldn't figure out a condition over $n \in \mathbb{N}$ that resembled this problem. I also thought about limits of sequences, but this would be a finite sequence.

Any hint is appreciated! Thanks in advance.

share|improve this question
    
Do induction on $|A|$. Your condition is "if the algorithm is run repeatedly on $A$, eventually the cardinality of the set stabilizes". –  Yuval Filmus Nov 21 '11 at 0:41

3 Answers 3

up vote 0 down vote accepted

Sets have finite cardinality if and only if there is a bijection between them and the set $\{0,\ldots,n-1\}$ for some $n\in\mathbb N$.

That is, the cardinality of a finite set is some natural number $n\in\mathbb N$.

If your algorithm removes finitely many elements at each stage, the cardinality cannot go up. It can stay the same or become smaller.

Now we can use a fact (or prove it, if you have not seen it before) that every non-increasing sequence of natural numbers stabilizes after finitely many steps. (If not, then at some finite point we have to go below $0$ which is impossible)

Also note that while "removing" seems to require existing, this is not true. Mathematically we can remove one apple from a bag of oranges. This may seem strange, but recall: $$A\setminus B=\{x\in A\mid x\notin B\}$$ Thus if your algorithm removes 10 elements each round, even if the set has 9 elements we can still remove 10. We are simply left with an empty set.

share|improve this answer

Certainly no set can have negative cardinality, so if you're removing a fixed number $n$ of things from a finite set repeatedly, then the sets will stop shrinking eventually: is that what you're trying to prove? If so, I'm not sure induction is necessary. Proof by reductio: Otherwise, after some large number $N$ of steps, you'd have $n+\cdots+n$ ($N$ times) elements fewer in your set, i.e. negative cardinality. (I mean, there's induction in converting $n+\cdots+n$ to "more than the original cardinality", but I think that's the kind of induction we generally don't spell out.)

share|improve this answer

Try something like this: given a finite set $A$ of cardinality $c$, find an expression $f(n)$ in terms of $n$ (and involving $c$) such that if the algorithm is iterated $n$ times successfully (i.e. without terminating) starting with $A$ as input, the resulting finite set has cardinality at most $f(n)$. This is something you could prove by induction on $n$. Now if the function $f(n)$ is chosen well, you can show that it will be be negative for sufficiently large $n$, which would imply that for such large $n$, the algorithm cannot be iterated $n$ times (since it couldn't possible produce a set of negative cardinality!) That is, it will terminate before then.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.