If A be a finite set having n element,then there are 2n distinct subset of A?
Answers
Answer:
this is the correct answer
Step-by-step explanation:
Prove: For any finite set S, if |S|= n, then S has 2n subsets.
Proof by induction.
Let P(n) be the predicate “A set with cardinality n has 2n subsets.
Basis step:
P(0) is true, because the set with cardinality 0 (the empty set) has 1 subset (itself)
and 20 = 1.
Inductive step
Prove P(k) → P(k+1)
That is, prove that if a set with k elements has 2k subsets, then a set with k+1
elements has 2k+1 subsets.
Proof
Assume that for an arbitrary k, any set with cardinality k has 2k subsets.
Let T be a set such that |T| = k+1.
Enumerate the elements of T:
€
T = e1,e2,...ek,e { k+1}.
Let
€
S = e1,e2,...e { k}
Then |S|=k, so S has 2k subsets, according to the inductive hypothesis.
Note that
€
T = S ∪ e{ k+1}, so every subset of S is also a subset of T.
Any subset of T either contains the element
€ ek+1, or it doesn’t contain
€ ek+1.
If a subset of T doesn’t contain
€ ek+1, then it is also a subset of S, and there are 2k of
those subsets. On the other hand, if a subset of T does contain the element € ek+1, then that subset is formed by including € ek+1 in one of the 2k subsets of S, so T has 2k subsets containing€
ek+1.