1
$\begingroup$

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.

  • 0
    Do induction on $|A|$. Your condition is "if the algorithm is run repeatedly on $A$, eventually the cardinality of the set stabilizes".2011-11-21

3 Answers 3

0

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.

1

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.

0

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.)