On 16 Jul 2009, at 16:06, Bruno Marchal wrote:
>
> On 16 Jul 2009, at 15:29, m.a. wrote:
>
>> Bruno,
>> I have no idea how to even begin to answer these
>> questions. Have you given us the definitions we need to do so?
>>
>>
>> marty
>> a.
>>
>>
>> ----- Original Message -----
>> From: "Bruno Marchal" <marc...@ulb.ac.be>
>>
>> >
>> > I let those interested to meditate on two questions (N is {0, 1,
>> 2, 3,
>> > 4, ...}):
>> >
>> > 1) What is common between the set of all subsets of a set with n
>> > elements, and the set of all finite sequences of "0" and "1" of
>> length
>> > n.
>> > 2) What is common between the set of all subsets of N, and the
>> set of
>> > all infinite sequences of "0" and "1".
>> >
>
>
> Read my last general post. I have to go now, you can wait for the
> answer.
>
> It is good to search without finding the answer, so as to better
> appreciate the answer.
>
> When I will give the answer, ask yourself question like "how is it
> that I didn't think about that, how is it that I have not seen this
> or that, how is it that I was forgetting this or that ...
>
> My last post should help a little bit,
>
> Think about this is as far as you have some fun by asking yourself,
> and then stop.
Ok, so now you have perhaps solve the riddle! The answer is No. I did
not really provide all the definitions you could need!
I feel a bit sorry. Mathematicians are kind of summarizing the rest of
the book in the exercises.
What are the sequences of "0" and "1" of length n?
That is the question.
I give some examples of sequences of "0" and "1" of length 7:
1111111, 0000000, 1010101, and 0100111
Here are some sequence of length three: 000, 101, 111.
Here are ALL examples of the sequences with length two:
00
01
10
11
Convince yourself that there are no other binary sequence of length 2.
Here is an example of sequence of "0" and "1" of length 24:
0111101010001000000000001
Here are the only two examples of binary sequences of length 1
0
1
And here is the only empty sequence, the one which length is 0.
You can't see it, of course. Even under a microscope! But there is one!
The problem "1)" was "What is common between the set of all subsets of
a set with n elements, and the set of all sequence of "0" and 1"?
You can search by yourself if the question is more clear, or look at
the explanation below. You = anyone interested, except Kim and Marty,
which have the obligation to train themselves, because they are victim
of summer school (that happens in hot summers).
Take your time. The problem was certainly not clear if you did not
know what is a so-called binary sequences, or sequences of "0" and "1".
.
.
.
.
------------------------------------------------------------------------------------
The answer is that they have the same number of elements.
And that number is 2^n.
Why?
Let us see, and, to fix the idea, consider what happens with the set
{a, b, c}, which powerset has already just be computed in a preceding
post:
The powerset of {a, b, c} is {{ }, {a}, {b}, {c}, {a, b}, {a, c}, {b,
c}, {a, b, c}}.
What is common between being a subset of {a, b, c} and a binary
sequence of length 3?
You can see the link immediately by realizing that a subset of a set
with n elements is entirely determined by the answers to n yes/no
questions. With {a, b, c}, there are only three possible question? We
can put them in the following order:
1)Does a belong to the subset?
2) Does b belong to subset?
3) Does c belong to the subset?
The poor empty subset { } is the one which get the answers: no, no, no.
The less poor singleton {a} is the one which get the answers: yes, no,
no.
Let us abstract, and let us write 0 in place of "no", and 1 in place
"yes",
------------------------------ { } ------------------ 000
------------------------------ {a} ------------------ 100
------------------------------ {b} ------------------ 010
------------------------------ {c} ------------------ 001
------------------------------ {a, b} ---------------- 110
------------------------------ {a, c} ------------------101
------------------------------ {b, c} ------------------011
and the winner is:
------------------------------ {a, b,c} ------------------111
So, there are as many subsets included in a set with n elements than
there are binary sequences of length n.
And how many?
Suppose I have to invent a binary sequence of length 1.
Well, it is a binary sequence, so I have not much choice in the
beginning. It is either 0 or 1. I can hesitate a long time, but I have
only two possibilities. 0, and 1.
Suppose I have to invent a binary sequence of length 2.
I have two possibilities for the first digit, and for each such choice
it remains two choice for the next, and last.
If I choose to begin with 0, I can still end with 1 or with 0: 01,
00. The possibilities of having 0 and 1 at a place does not depend of
what happened before: so they multiply.
How many sequences of length 3? =
= (2 possibilities for the first digit) times (2 possibilities for the
second digit) times (2 possibilities for the third digit)
= 2 times 2 times 2 = 8.
OK?
How many subsets of a set with three elements {a, b, c}.
If I have to "invent" a subset S
= (2 possibilities for the question "is a in the subset S") times (2
possibilities for the question "is b in the subset S") times (2
possibilities for the question "is c in the subset S")
= 2 times 2 times 2 = 8.
Question?
What about problem 2).?
I recall that N is the set of natural numbers {0, 1, 2, 3, ……… }. I
let you think about the relation between subset of N, and infinite
binary sequences.
Hint: the poor empty subset { } is the one getting the answer no, no,
no, no, no, no, no, no, no, no, no, no, no, ....
Hot summer!
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com
To unsubscribe from this group, send email to
everything-list+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
