Solution to (a) Let S be a set, and define the set W as follows: Basis: ∅ … - Sikademy
Author Image

Archangel Macsika

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

The Answer to the Question
is below this banner.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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.


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

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3496-qpid-2195