# Must a Set's size be a natural number, and would the contrary invalidate a solution?

I came up with a way of solving this counting problem that's not in my textbook and I am wondering if it is still valid because in one of the intermediate steps I calculate the number of elements in a subset and I often get a non-integer answer like $9.5849\dots$

The questions is

How many subsets of $S = \{1,2,....n\}$ contain at least one of the elements $\{1,2\}$ and at least $2$ of the elements $\{3,4,5\}?$

First I got the number of subsets which have at least one of the elements $\{1,2\}$ by using the subtraction principle and by using powers of two. For each element in the set I ask 'is this in the set?' and there are two options, yes or no. So the total number of subsets is $2^{n}.$ And finally I use subtraction because the number of subsets with at least one element from $\{1,2\}$ is the same as the total minus the number of subsets with nothing from $\{1,2\}:$

$$m = 2^{n} - 2^{n-2}$$

Next, I tried something different. I tried to imagine that I was starting the problem all over again but this time the original set is smaller. Now

$S = \{1,2....k\}$ where $k = log_{2}(m)$

I figured this was sound because if I had 10 element I would have $2^{10} = 1024$ possible subsets and $log_{2}(1024)$ gives me the number of elements in the set which is $10.$

Now I just have answer the simpler question:

How many subsets of $S = \{1,2,....k\},$ where $k = log_{2}(m),$ contain at least $2$ of the elements $\{3,4,5\}?$

And the answer to this is

$4 * 2^{k-3}$

I multiply by 4 because there are $3$ ways of of appending $2$ or more elements from $\{3,4,5\}$ back into to $S$ which has had $\{3,4,5\}$ taken away from it. They are $\{3,4\},\{3,5\},\{4,5\},\{3,4,5\}.$

What I find unusual about this approach is that the $log_{2}(m)$ is not always an integer. And I can't imagine going through each item in a set asking the question 'are you in the subset? if one of the elements is only a fraction of an element like $0.5849\dots$

For example, if $n = 10,$ then

$m = 2^{10} - 2^{8} = 768.$ Then

$k = log_{2}(m) = 9.584962\dots$

It feels wrong to ask how many subsets are in a set with $9.58\dots$ elements.

And yet I get the correct answer:

$4 * 2^{9.5849... - 3} = 384$ exactly!

• could be some use of average cardinality in the s=geometric mean sense. – user451844 Jul 29 '17 at 14:54

What you have discovered is that the formula $2^n - 2^{n-2}$ has a continuous extension from the natural numbers $n \in \{1,2,3,...\}$ to all real numbers $x \in \mathbb{R}$; in other words, the formula $2^x - 2^{x-2}$ makes sense no matter what the value of $x$.

This is a significant discovery. It is not at all obvious, from an elementary (precalculus) point of view, that an exponential function like $2^n$ can be extended in a continuous fashion to a function $2^x$ so that the laws of exponents remain valid, laws such as $2^x \cdot 2^y = 2^{x+y}$ and so on. It requires a semester or two of calculus to prove this rigorously, by a method which rigorously constructs the function $2^x$ and proves its properties.

However, you should not over-interpret this discovery. You are right that it makes no sense to ask how many subsets there are in the set with $9.58$ elements, so that is not what your formula says.

• Perhaps it makes more sense to think about it like this. If I have 9.58 bits and I remove three bits {3,4,5} and then add two bits {4 = 2^2}. Then I have 8.58 bits. And 2^8.58... is 384 meaning that i can store 384 pieces of information with 8.58.. bits! Got that idea from @ChristianBlatter below who mentioned Shannon below. – COOLBEANS Jul 29 '17 at 16:57
• Why do you think this shows that $2^n - 2^{n-2}$ has a continuous extension from the natural numbers $n$ to all real numbers? It is not $n$ that has a non-integer number, but the number of elements, $k$, in the imagined set $S=\{1,2,...,k\}$. – HelloGoodbye Jul 29 '17 at 18:26
• The original question switches from $S=\{1,2,...,n\}$ earlier to $S=\{1,2,...,k\}$ later, I was just using the earlier notation. – Lee Mosher Jul 29 '17 at 18:30

The reason this works is that the two conditions (i): at least one from $\{1,2\}$, and (ii): at least two from $\{3,4,5\}$, are independent when $n\geq5$. The probability that (i) is satisfied is $3/2^2$, and the probability that (ii) is satisfied is $4/2^3$. It follows that ${3\over8}$ of all $2^n$ subsets satisfy both conditions. Taking logarithms at the second step was a detour of yours that Shannon might have liked $\ldots$.

• A completely different perspective I didn't appreciate. Thanks. Was Shannon fond of detours or taking logs of things, or both? I'm curious. – COOLBEANS Jul 29 '17 at 15:20
• Shannon was the father of information theory. Here $N$ equiprobable outcomes incorporate $\log_2 N$ bits of information. – Christian Blatter Jul 29 '17 at 15:26
• This is interesting to me as a programmer. 5 equally likely outcomes are equal to log base 2 (5) = 2.3219.. bits of information. So even though information must be physically stored on an integer number of registers, they can hold a non-integer value of information. That interesting to me for some reason. – COOLBEANS Jul 29 '17 at 15:33