0

Question: Let $S$ be the set of stars in our galaxy. There is exactly the same number of subsets of stars in our galaxy as there are functions $f:S \to \{a,b\}$ .

My solution is; True.However, I'm confused with how to prove it. I know it can be proven by using the formula of the number of elements in a subset and for the formula of the number of elements in a function and proving that both values are equal.

Can someone provide me with some feedback, please.

vidhan
  • 1,020
Legion
  • 11

2 Answers2

2

You don't really need to enumerate. Any subset can be identified using an {a,b} mapping by regarding "a" as denoting "in the subset" and "b" as "not in the subset". And similarly any {a,b} mapping will define a subset by the same interpretation, so the two operations are homomorphic.

Joffan
  • 39,627
0

First you should note that the answer is very general and the context is simply a red herring.The same statement is true even if $S$ is the set of people who take bath on alternate days.

You are talking about functions taking values in a two-element set $\{a,b\}$.

Any such function is completely specified once the full subset of those elements that are sent to $b$ is known.

To each such function $f$, we associate $f^{-1}(b)$, a subset of $S$. This association is a bijective correspondence providing the answer you want.

P Vanchinathan
  • 19,504