Thread: A couple induction set proofs

1. A couple induction set proofs

Prove the following statements

1) Prove: There is just one minimal induction set.
I know that there cannot be two minimal induction sets, but this says there does not exit zero minimal induction sets. I'm pretty sure that I have to use the definitions of propers subsets and subsets in there somewhere, I'm just not sure where it all fits in.
2) Prove: If C' is a subset of C, and C' is an induction set, then C' = C.
I haven't really gotten started on this one, but I know that an induction set is a set A such that 1 is an element of A and if x is in A, then x+1 is an element of A.

2. Originally Posted by noles2188
Prove the following statements
1) Prove: There is just one minimal induction set.
Let C be the set generated by a basis B={0} and a successor function S(n) = n+1. C can be constructed as follows:
1. Starting with B, recursively include an element using the successor function such that $C_1=\{0\}, C_2=\{0,1\},,,,$ (You might use an empty set notation for an inductive set).
2. Define C as $C=\bigcup_nC_n$.

We shall show that an intersection of all the inductive subsets of a universe U is C. That means, C is the minimal inductive set.

Let $N= \bigcap\{\text{A : A is inductive subset of U}\}$.

To show $N \subseteq C$, we only need to show C is an inductive set. C includes B and we see that a S(c) is in C for every $c \in C$.
Conversely, N contains B and is closed under S. Thus $C \subseteq N$.

2) Prove: If C' is a subset of C, and C' is an induction set, then C' = C.
Both C and C' are inductive sets. Since $C \subseteq N$ (N is the smallest inductive set) and C' is an inductive set, $C \subseteq C'$. We also know that C' is a subset of C. Thus, C' = C.