|
Author
|
Topic: Combinations
|
Doron Shadmi
Member
Member # 965
|
posted 11. December 2003 02:01
I realized that my last thread (named by "permutations") can’t be understood by professional mathematicians.
Because I don’t know how to write my idea in the common formal way, I am going to do it in a non-formal way, but I will do my best to write it in the clearest way.
So here it is:
Let us check these lists.
P(2) = {{},{0},{1},{0,1}} = 2^2 = 4
and also can be represented as:
00
01
10
11
P(3) = {{},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}} = 2^3 = 8
and also can be represented as:
000
001
010
011
100
101
110
111
Let us call any full 01 list, combinations list.
Now, let us use Cantor's Diagonalization method on some finitely long combinations list, for example, the combinations list of number 3:
000
001
010
011
100
101
110
111
We can change the order of the rows, and then use Cantor's Diagonalization method, for example:
001
011
010
000
101
100
111
110
The input for Cantor's Diagonalization method in the first example is 000 and the output is 111.
The input for Cantor's Diagonalization method in the second example is 010 and the output is 101.
In both examples we find that the result is already in the combinations list, and this combination, which is already in the list, is one of the combinations that Cantor's Diagonal does not cover.
The number of the combinations, which are out of the range of Cantor's diagonal is:
2^n - n
Every column, which belongs to some combinations list is a sequence of 01 notations, based on some periodic frequency changes, for example:
the right column of number 3 combinations list, is based on 2^0(=1).
Therefore the periodic frequency changes are 1, and the result in this case is:
01010101.
The result of the middle column is based on 2^1(=2), therefore the sequence is:
00110011.
The result of the left column is based on 2^2(=4), therefore the sequence is:
00001111.
and we get the full combinations list of number 3:
000
001
010
011
100
101
110
111
We can get a combinations list of infinitely many places, by using the ZF Axiom of infinity induction, on the left side of our combinations list, by using the induction on the power_value of each column, for example:
2^0, 2^1, 2^2, 2^3, ...
In this stage we have proven, by induction, that Cantor's diagonal cannot cover any full 01 combinations list, finite or infinite.
Therefore its result is not a new combination (that has to be added to the list).
Because Cantor's diagonal cannot cover the full 01 combinations list, (of aleph0 places for each combination) we can conclude that 2^aleph0 > aleph0.
But each infinitely long sequence of 01 notations can be mapped with some natural number, for example:
...000 <--> 1
...001 <--> 2
...010 <--> 3
...011 <--> 4
...100 <--> 5
...101 <--> 6
...110 <--> 7
...111 <--> 8
...
Therefore we can conclude that 2^aleph0 = aleph0, and we come to contradiction.
(2^aleph0 >= aleph0) = {}, and we have a proof saying that Boolean Logic cannot deal with infinitely many objects.
Doron
IP: Logged
|
|
Evan
Member
Member # 164
|
posted 11. December 2003 07:41
Comments and questions:
1) The word combination refers to arrangements in which order does not count: i.e., 010, 100, and 001 are all equivalent. Permutations refer to arrangements in which order does count. Therefore, permutation is the correct word for the arrangements in your post.
2) You wrote:
quote:
In both examples we find that the result is already in the combinations list, and this combination, which is already in the list, is one of the combinations that Cantor's Diagonal does not cover.
I don't understand the the phrase " is one of the combinations that Cantor's Diagonal does not cover." Given that your diagonalization method just produced the permutation in question, what do you mean that the method doesn't cover it?
3) It is already well known that infinite sets produce results that are paradoxical if compared to what we know about finite sets: e.g., a subset (such as the even numbers) can be as large as its parent set (in this case, the integers). So I think the fact that Boolean logic doesn't apply to finite sets (or at least that the logic of infinite sets is different than the logic of finite sets) is not a new result.
4) What does this have to do with intelliegnt design and complexity?
[ 11. December 2003, 08:05: Message edited by: Evan ]
IP: Logged
|
|
|
Topic Closed
Printer-friendly view of this topic