Question

(a) Let S be a set, and define the set W as follows:
Basis: ∅ ϵ W.Recursive Definition: If x ϵ S and A ϵ W, then {x} U A ϵ W. Provide an explicit description of W, and justify your answer.

Answer 1

Let us show that $W=\{A\subset S\ |\ A\text{ is finite }\}$.

Let us prove using mathematical induction on the order of the elements of $W$.

Base case:

n=0: $\emptyset$ is a unique subset of $S$ of order 0, and by defenition of $W$, $\emptyset\in W$.

n =1: for each $x\in S$ the singleton $\{x\}=\{x\}\cup\emptyset\in W$, and thus $W$ contains all singletons.

Inductive step:

Assume that $W$ contains all subsets $A\subset S$ of cardinality $|A|=k$, and prove that it is also contains all subsets od cardinality $k+1$. Indeed, let $B=\{x_1,...,x_k,x_{k+1}\}$ arbitrary subsets of cardinality $k+1$. Then by assumption, $A=\{x_2,....x_{k+1}\}\in W,$ and consequently, $B= \{x_{1}\}\cup A\in W$.

Conclusion:

Therefore, by Mathematical Induction  $W=\{A\subset S\ |\ A\text{ is finite }\}$.