Share
Explore BrainMass

Denumerability and induction

1. Show that if A and > are denumerable disjoint sets then A u > is denumerable

2. Show that every set of cardinalty c contains a denumerable subset

3. Show by induction that 6 divides n^3 - n for all n in N

Solution Preview

1. Show that if A and > are denumerable disjoint sets then A u > is denumerable
Proof:
For better notation, I replace > with B. So the statement is: if A and B are denumerable disjoint sets, then A U B is denumerable.
We note, a set is denumerable if and only if it is finite or coutable infinite. So we have 4 cases.
Case 1: Both A and B are finite. Let |A|=n and |B|=m, since A and B are disjoint, then |A U B|=m+n is also finite. So A U B is denumerable.
Case 2: A is finite, B is countable infinite. Let |A|=n, ...

Solution Summary

There are three proofs here: one regarding denumerability, one regarding cardinality and denumerable subsets, and a proof of divisibility by induction.

$2.19