A couple induction set proofs

• Feb 17th 2009, 09:10 PM
noles2188
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.
• Feb 19th 2009, 01:09 AM
aliceinwonderland
Quote:

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 $\displaystyle C_1=\{0\}, C_2=\{0,1\},,,,$ (You might use an empty set notation for an inductive set).
2. Define C as $\displaystyle 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 $\displaystyle N= \bigcap\{\text{A : A is inductive subset of U}\}$.

To show $\displaystyle 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 $\displaystyle c \in C$.
Conversely, N contains B and is closed under S. Thus $\displaystyle C \subseteq N$.

Quote:

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 $\displaystyle C \subseteq N$ (N is the smallest inductive set) and C' is an inductive set, $\displaystyle C \subseteq C'$. We also know that C' is a subset of C. Thus, C' = C.