40 For the induction step suppose that the statement is true for a set with N-1 elements, and let S be a set with N elements.
{"Image DocumentName": "The size of a finite power set", "Image ImageDescription": "For the induction step suppose that the statement is true for a set with N-1 elements, and let S be a set with N elements. Remove on element x from S to obtain a set T with N-1 elements. There are two types of subsets of S: those that contain x and those that do not contain x. The latter are subsets of T, of which there are 2^ N-1. Every subset P of S that does contain x can be obtained from a subset Q of T by adding x. The set Q is simply the set P with x removed. Clearly there is a unique and distinct set Q for each set P and every subset Q of T gives rise to a unique and distinct subset P of S. There are thus also 2^ (N-1) subsets of S that contain x, for a total of 2^ (N-1) + 2^ (N-1) = 2^ N subsets of S.", "Image XResolution": "37", "Image YResolution": "37", "Image ResolutionUnit": "Pixels/Centimeter", "Image Software": "SlidePlayer", "Image YCbCrPositioning": "Centered"}