Question

4) In this problem, we will explore how the cardinality of a subset S ⊆ X relates to the cardinality of a finite set X.

(i) Explain why |S| ≤ |X| for every subset S ⊆ X when |X| = 1.

(ii) Assume we know that if S ⊆ <n>, then |S| ≤ n. Explain why we can show that if T ⊆ <n+ 1>, then |T| ≤ n + 1.

(iii) Explain why parts (i) and (ii) imply that for every n ∈ N, every subset of <n> is finite and has cardinality less than n + 1.

Answer 1

4.

Let and .

So the set contains exactly one element so its subset will also contains atmost one element because if contains more than one elemnt then and every element of is also an element of will also contains more than one elememt , a contradiction . So contains atmost one element .

, as

It is given that if then .

Suppose

So if we delete the element one element say from the set then it will be a subset of .

, by the given condition .

Hence if then

Let us assume the statement as if then .

So by the statement is true for .

By if the statement is true for   then it is true true for then by induction on the statement is true for all