Is there a contradiction in P(X) > X?"

[phoenixthoth]

There exists member S in P(N)) which includes ALL members of N that have no image Included in the P(N) members which they are mapped with, for example:

1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}.

which of the following is what you're writing:
1. S={n in N such that f(n) is not a member of f(n)}
2. S={n in N such that n is not a member of f(n)}
3. something else?

Bucause {} does not exist in N, but {} exists in P(N), then S have at least one member of N, for example:

n <--> {}

In this example S ={n}.

in case 1, S=N but I'm not sure. are there any sets that are members of themselves? if not, which i think is the case, then S=N. in case 2, i think S could be made into any subset of N with the right f, including the empty set. if f(n)={n}, in case 2, then S=Ø. it is not the case that S has at least one member for every f. if f(n)=Ø for all n, then S=N.

t is some arbitrary member of N.

In this case we can ask: is t in S or t not in S ?

Options:

1) t in S , but by S definition t cannot be in S .
2) t not in S , in this case by S definition, t must be in S , but by (1) t can’t be in S .

and so on, and so on.

As we can see, both options lead us to logical contradiction.

Therefore, there cannot be a bijection between P(N) and N and we can conclude that P(N) > S .

Q.E.D

didn't you just say that S={n}? doesn't that mean n is in S?

"t in S , but by S definition t cannot be in S ." your example:
1 <--> {2,3} , 2 <--> {2,3,4} , 3 <-->{6,7} , 4 <--> {4,5,6} , 5 <--> {8,9}, …

In this example S ={1,3,5,…}

if t=1, then t is in S. it is not the case that t cannot be in S by definition, at least not the case for an arbitrary t.

but supposing that t is in S if and only if t is not in S, which is a contradiction, how is this contradiction logically dependent on the assumption that there was a bijection from N to P(N)? it doesn't seem to be used anywhere that the map is a bijection. since this contradiction is not the logical consequence of the assumption that there is a bijection from N to P(N), the contradiction does not prove that there is no bijection from N to P(N).

the statement that leads to a contradiction is that the map is onto. since S is a subset of N, it is an element of P(N). if the map is supposed to be onto P(N), that means n must be mapped onto S for some n in N. show that if this were true, there would be a contradiction. this contradiction is good because it followed from assuming the map from N to P(N) was a bijection which lead to saying it is onto.

By using the empty set (with the Von Neumann Hierarchy), we can construct the set of all *positive* [non-negative] integers {0,1,2,3,...}:

0 = { }

earlier, you said that {} is not in N. "Bucause {} does not exist in N..." but here, you're saying 0={} is in N. it doesn't matter. you said {} is not in N to try to prove S is nonempty. (a) S may be empty and (b) it doesn't matter if S is empty because (c) S, whatever it is, is not mapped to by any function from N to P(N) and, consequently, any function from N to P(N) is not onto.

 

[Organic]

Dear pheonixthoth,

Thank you for your detailed answer.

Instead of wrinting again Cantor's theorm I give you this address:

http://www.mathacademy.com/pr/prime/articles/cantor_theorem/index.asp?PRE=cantor&TBM=Y&TAL=Y&TAN=Y&TBI=Y&TCA=Y&TCS=Y&TDI=Y&TEC=Y&TFO=Y&TGE=Y&TGR=Y&THI=Y&TNT=Y&TPH=Y&TST=Y&TTO=Y&TTR=Y&TAD=&LEV=B

Now let us say that:

S=F
N=X
t is some member of N that matches with S

By using the empty set (with the Von Neumann Hierarchy), we can construct the set of all positive integers {0,1,2,3,4,...}:

[b][i]0[/i][/b] = |{ }| (notation = {}) 

[b][i]1[/i][/b] = |{[b]{[/b] [b]}[/b]}| (notation = {0})
               
[b][i]2[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b]}| (notation = {0,1})
  
[b][i]3[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b],[b]{[/b]{ },{{ }}[b]}[/b]}| (notation = {0,1,2})

[b][i]4[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b],[b]{[/b]{ },{{ }}[b]}[/b],[b]{[/b]{ },{{ }},{{ },{{ }}}[b]}[/b]}| (notation = {0,1,2,3})

and so on.

So, through this point of view the atom is {} and the natural numbers are structural|quantitative combinations of {}.

We have here an Hierarchy of infinitely many complexity levels, starting from {}.

If {} does not exist then we have no system to research, therefore we can learn that in the base of this number system, there is the idea of dependency, which can be translated to the idea of the power of existence.

Let us look at Cantor's proof from this point of view.

As we all know, any set includes only unique members or no members at all.

Now, let us examine options 1 and 2 again.

Option 1:

The all members which included in S , are different from each other.

Any member of N can be mapped with some member of P(N), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

Option 2:

If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


Therefore we cannot ask nor answer to anything that is connected to member S .


The general idea behind this point of view is the power of existence of member t and member S .


(S exists iff t is out of the scope of its definition. it means that the word ALL is omitted from S definition).


More you simple less you depended, therefore more exist.

Now, the power of existence of N members is bigger than the power of existence of
P(N) members.

Member t, which is some arbitrary member of N(and mapped with S), is simpler than S, which is a member of P(N) .

Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.


Organic

 

[phoenixthoth]

if i understand correctly,
S={x in X such that x is not in f(x)} and t is defined to be some element of X such that f(t)=S. i gather this from the statement S=F and since this is their definition of F on the site. i also gather that f(t)=S since you say "t is some member of N that matches with S." (again, N should not be referred to since this is a proof about all sets X.)

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

anything you say about t is true. in other words, the statement if f(t)=S, then !(*#&!@# is true no matter what !(*#&!@# is.

anything you say about t is true because {t in X such that f(t)=S} is empty.

there seems to be a question about when S can be defined, something about assumptions needing to be checked.

here's the order:
goal: show that no map from X to P(X) is a bijection.
method: show that if f maps X to P(X), then f is not surjective.

how to do that: f is given and arbitrary. define S so that x is in S iff x is not an element of f(x). perhaps a better notation is S_f because the "shape" of S depends on what f is. here, S must come after f and f can't come after S, at least not with this approach.

fact: for no x in X is f(x)=S. this means f is not surjective because S is an element of P(X) that is not mapped to by f.

 

[Organic]

Hi phoenixthoth,

Please let us talk only on P(N) and N where t is a member of N and S is a member of P(N).

What I clime is this:

S={n in N such that n is not in f(n)} CANT BE DEFINED because:

By using the empty set (with the Von Neumann Hierarchy), we can construct the set of all positive integers {0,1,2,3,4,...}:

[b][i]0[/i][/b] = |{ }| (notation = {}) 

[b][i]1[/i][/b] = |{[b]{[/b] [b]}[/b]}| (notation = {0})
               
[b][i]2[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b]}| (notation = {0,1})
  
[b][i]3[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b],[b]{[/b]{ },{{ }}[b]}[/b]}| (notation = {0,1,2})

[b][i]4[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b],[b]{[/b]{ },{{ }}[b]}[/b],[b]{[/b]{ },{{ }},{{ },{{ }}}[b]}[/b]}| (notation = {0,1,2,3})

and so on.

So, through this point of view the atom is {} and the natural numbers are structural|quantitative combinations of {}.

We have here an Hierarchy of infinitely many complexity levels, starting from {}.

If {} does not exist then we have no system to research, therefore we can learn that in the base of this number system, there is the idea of dependency, which can be translated to the idea of the power of existence.

Let us look at Cantor's proof from this point of view.

As we all know, any set includes only unique members or no members at all.

Now, let us examine options 1 and 2 again.

Option 1:

The all members which included in S , are different from each other.

Any member of N can be mapped with some member of P(N), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

Therefore S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.

Option 2:

If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

In this case we also find that S cannot be defined BEFORE we check our assumption in step 2 of Cantor's proof.


Therefore we cannot ask nor answer to anything that is connected to member S .


The general idea behind this point of view is the power of existence of member t and member S .


(S exists iff t is out of the scope of its definition. it means that the word ALL is omitted from S definition).


More you simple less you depended, therefore more exist.

Now, the power of existence of N members is bigger than the power of existence of
P(N) members.

Member t, which is some arbitrary member of N(and mapped with S), is simpler than S, which is a member of P(N) .

Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.

Conclusion: Cantor did not prove that P(N) > N because the definition S={n in N such that n is not in f(n)} CANNOT EXISTS.


Organic

 

[phoenixthoth]

it's not neccessarily objectively true that S can be defined by saying S={n in N such that n is not in f(n)}.

however, if you accept the subsets axiom
http://mathworld.wolfram.com/AxiomofSubsets.html ,
then this implies S exists if you take the following particulars:
x=S
a=N
y=n
A(y)=A(n) says ¬(n &isin; f(n)).

the possible question is whether or not A(n) is a well formed formula. the site http://www.ltn.lv/~podnieks/mlog/ml1.htm#firstorder has some relevant information on how to build formulas like A(y). look for the bold formula.

 

[Organic]

Dear phoenixthoth,

Please read this: http://mathworld.wolfram.com/CantorDiagonalMethod.html

N=S
P(N)=T
S=D
t=x

Now, please follow my idea until the end of it, and then please write your remarks.

thank you.

By using the empty set (with the Von Neumann Hierarchy), we can construct the set of all positive integers {0,1,2,3,4,...}:

[b][i]0[/i][/b] = |{ }| (notation = {}) 

[b][i]1[/i][/b] = |{[b]{[/b] [b]}[/b]}| (notation = {0})
               
[b][i]2[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b]}| (notation = {0,1})
  
[b][i]3[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b],[b]{[/b]{ },{{ }}[b]}[/b]}| (notation = {0,1,2})

[b][i]4[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b],[b]{[/b]{ },{{ }}[b]}[/b],[b]{[/b]{ },{{ }},{{ },{{ }}}[b]}[/b]}| (notation = {0,1,2,3})

and so on.

So, through this point of view the atom is {} and the natural numbers are structural|quantitative combinations of {}.

We have here an Hierarchy of infinitely many complexity levels, starting from {}.

If {} does not exist then we have no system to research, therefore we can learn that in the base of this number system, there is the idea of dependency, which can be translated to the idea of the power of existence.

Let us look at Cantor's proof from this point of view.

As we all know, any set includes only unique members or no members at all.

Now, let us examine options 1 and 2 again.

Option 1:

All members which included in S , are different from each other.

Any member of N can be mapped with some member of P(N), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

(S exists iff t is out of the scope of its definition. it means that the word ALL is omitted from S definition).

Therefore S cannot be defined, and we can't check our assumption in step 2 of Cantor's proof.

Option 2:

If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

(S exists iff t is out of the scope of its definition. it means that the word ALL is omitted from S definition).

In this case we also find that S cannot be defined, and we can't check our assumption in step 2 of Cantor's proof.


Therefore we cannot ask nor answer to anything that is connected to member S .


The general idea behind this point of view is the power of existence of member t and member S .

More you simple less you depended, therefore more exist.

Now, the power of existence of N members is bigger than the power of existence of P(N) members.

Member t, which is some arbitrary member of N(and mapped with S), is simpler than S, which is a member of P(N) .

Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.

Conclusion: Cantor did not prove that P(N) > N because S (as Cantor defined it) does not exist.


Organic

 

[phoenixthoth]

Any member of N can be mapped with some member of P(N), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

(S exists iff t is out of the scope of its definition. it means that the word ALL is omitted from S definition).

Therefore S cannot be defined, and we can't check our assumption in step 2 of Cantor's proof.

i'm not understanding the first or second therefore in the above quote. t is in S iff t is not in f(t), so I'm not seeing how t is different from each member of S or how that implies t must be included in S. if t is different from each element of S then that means t is not in S, not t is in S. if t is in S and t is an arbitary element of N, that means N&sub;S. and since S&sub;N, N=S.

S can be defined and exists by the subsets axiom.

S may be empty (depending on f).

your final conclusion below seems to be that since S doesn't exist, N<P(N) and I'm not following it.

 

[Organic]

Dear phoenixthoth,


I clime that because S (as Cantor defined it) does not exist, all we can say is:
P(N) >= N.

If you want to understand the idea that stands behind my clime, then you have to understand and accept the idea of hierarchy of power of existence.

Please let us talk about this idea, so I write it again:


By using the empty set (with the Von Neumann Hierarchy), we can construct the set of all positive integers {0,1,2,3,4,...}:

[b][i]0[/i][/b] = |{ }| (notation = {}) 

[b][i]1[/i][/b] = |{[b]{[/b] [b]}[/b]}| (notation = {0})
               
[b][i]2[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b]}| (notation = {0,1})
  
[b][i]3[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b],[b]{[/b]{ },{{ }}[b]}[/b]}| (notation = {0,1,2})

[b][i]4[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b],[b]{[/b]{ },{{ }}[b]}[/b],[b]{[/b]{ },{{ }},{{ },{{ }}}[b]}[/b]}| (notation = {0,1,2,3})

and so on.

So, through this point of view the atom is {} and the natural numbers are structural|quantitative combinations of {}.

We have here an Hierarchy of infinitely many complexity levels, starting from {}.

If {} does not exist then we have no system to research, therefore we can learn that in the base of this number system, there is the idea of dependency, which can be translated to the idea of the power of existence.

Thae main idea is: More you simple more you exist.

Let us look at Cantor's proof from this point of view.

 

[phoenixthoth]

I clime that because S (as Cantor defined it) does not exist, all we can say is.

if the subsets axioms is accepted, S exists. I'm not saying it does or does not exist. just that if the subsets axioms is accepted, then it does exist. but if the subsets axioms isn't accepted, i think it's also the case that N is not necessarily a set (ie it doesn't exist) either.

 

[Organic]

Does the axiom of subsets has anything to say on the changes of the complexity of its products?

 

[Organic]

Is there another ZFC axiom or some combination of these axioms that deal with levels of complexity based on hierarchic recursion?

 

[phoenixthoth]

you can use the axioms to build things that you could translate into complexity, i imagine.

 

[Organic]

Please give an example of how you use ZFC axioms to construct this:

By using the empty set (with the Von Neumann Hierarchy), we can construct the set of all positive integers {0,1,2,3,4,...}:

[b][i]0[/i][/b] = |{ }| (notation = {}) 

[b][i]1[/i][/b] = |{[b]{[/b] [b]}[/b]}| (notation = {0})
               
[b][i]2[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b]}| (notation = {0,1})
  
[b][i]3[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b],[b]{[/b]{ },{{ }}[b]}[/b]}| (notation = {0,1,2})

[b][i]4[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b],[b]{[/b]{ },{{ }}[b]}[/b],[b]{[/b]{ },{{ }},{{ },{{ }}}[b]}[/b]}| (notation = {0,1,2,3})

and so on.

 

[phoenixthoth]

weird. I'm actually writing a document about this topic just for kicks.

use empty set axiom to get Ø. define 0 to be Ø.

pair set axiom: for two sets x and y there is a set z such that
w is in z iff w=x or w=y.

z is denoted {x,y}.

use pair set axiom with x=a and y=a to get the set {a} from a given set a.

sum set axiom: for a set x there is a set z such that
w is in z iff there is a y in x such that w is in y.

this z is denoted Ux. (i think it was discussed earlier in this thread.)

define the union of two sets operator &cup; to mean this:
x&cup;y=U{x,y}.
(it is useful to notice that w is in x&cup;y iff w is in x or w is in y.)

now that we have &cup; and 0 and that {a} is a set whenever a is a set, we can define the rest of the natural numbers:
for n>=0, n+1:=n&cup;{n}. this is a recursive definition. for natural numbers, one doesn't need any symbols other than 1 and + but they are convienient. for example, 5 is defined to be
(((((0+1)+1)+1)+1)+1). examples:
1=0+1=0&cup;{0}=Ø&cup;{0}={0}
2=1+1=1&cup;{1}={0}&cup;{{0}}={0,{0}}={0,1}
3=2+1=2&cup;{2}={0,{0}}&cup;{{0,{0}}}={0,{0},{0,{0}}}={0,1,2}.

i think there are other ways to use ZFC to get the natural numbers. you may also want to check out the peano axioms. the peano axioms assume an induction principle when i think you can use ZFC to prove the induction principle is equivalent to the well ordering principle in N.

 

[Organic]

{} and 0 are different things because |{}| = 0 not= {}

 

[phoenixthoth]

the symbol 0 has many uses. 0 could be the identity element in a group.

0 could be a cardinal number or it could be a natural number. in the first case, |{}|=0 and in the second case, {}=0. it can be ambiguous that 0 is used so much. as far as i know, |{}|!={} yet people use the symbol 0 for both.

0 = |{ }| (notation = {})

1 = |{{ }}| (notation = {0})

of 1={0}, then shouldn't it be 1=||{}|| and not |{{}}|?

while this construction of N isn't necessarily "wrong," i like the ZFC better because it doesn't mention cardinality (under the general impression that less is more).

 

[Organic]

By writing the natural numbers as ...(((0+1)+1)+1)... you clearly say that N is an hierarchic recursion.

So P(N) members are totally dependent on N members for their existence, isn’t it?

 

[phoenixthoth]

i would say that for any set x, P(x) totally depends on x.

 

[Organic]

So, don't you think that the axiom of subsets ignore this hierarchic of dependency ?

 

[phoenixthoth]

in a way it does but it also makes a given set depend on a (bigger) set, a context.

 

[Organic]

Dear phoenixthoth,

So, we can't ignore the idea of dependency, which can be translated to the idea of the power of existence of any N memeber, which is bigger than the power of existence of any P(N) member (exclude {}, and S not= {} because {} not in N, therefore S includes the N member, which mapped with {}).

I'll write it down again, and please read it by the light of "the idea of dependency".


Please read this: http://mathworld.wolfram.com/CantorDiagonalMethod.html

N=S
P(N)=T
S=D
t=x

Now, please follow my idea until the end of what I write, and then please write your remarks.

thank you.

By using the empty set (with the Von Neumann Hierarchy), we can construct the set of all positive integers {0,1,2,3,4,...}:

[b][i]0[/i][/b] = |{ }| (notation = {}) 

[b][i]1[/i][/b] = |{[b]{[/b] [b]}[/b]}| (notation = {0})
               
[b][i]2[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b]}| (notation = {0,1})
  
[b][i]3[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b],[b]{[/b]{ },{{ }}[b]}[/b]}| (notation = {0,1,2})

[b][i]4[/i][/b] = |{[b]{[/b] [b]}[/b],[b]{[/b]{ }[b]}[/b],[b]{[/b]{ },{{ }}[b]}[/b],[b]{[/b]{ },{{ }},{{ },{{ }}}[b]}[/b]}| (notation = {0,1,2,3})

and so on.

So, through this point of view the atom is {} and the natural numbers are structural|quantitative combinations of {}.

We have here an Hierarchy of infinitely many complexity levels, starting from {}.

If {} does not exist then we have no system to research, therefore we can learn that in the base of this number system, there is the idea of dependency, which can be translated to the idea of the power of existence.

Let us look at Cantor's proof from this point of view.

As we all know, any set includes only unique members or no members at all.

Now, let us examine options 1 and 2 again.

Option 1:

All members which included in S , are different from each other.

Any member of N can be mapped with some member of P(N), once and only once.

Therefore t is different from each member in S , therefore t MUST BE INCLUDED in S .

(S exists iff t is out of the scope of its definition. it means that the word ALL is omitted from S definition).

Therefore S cannot be defined, and we can't check our assumption in step 2 of Cantor's proof.

Option 2:

If we want to keep S as an existing member, we MUST NOT INCLUDE t in S .

(S exists iff t is out of the scope of its definition. it means that the word ALL is omitted from S definition).

In this case we also find that S cannot be defined, and we can't check our assumption in step 2 of Cantor's proof.


Therefore we cannot ask nor answer to anything that is connected to member S .


The general idea behind this point of view is the power of existence of member t and member S .

More you simple less you depended, therefore more exist.

Now, the power of existence of N members is bigger than the power of existence of P(N) members.

Member t, which is some arbitrary member of N(and mapped with S), is simpler than S, which is a member of P(N) .

Member S existence depends on objects like t , therefore we have to check S by t as we did here, and not t by S as Cantor did.

Conclusion: Cantor did not prove that P(N) > N because S (as Cantor defined it) does not exist.


Organic

 

[phoenixthoth]

maybe you can use transfinite induction to prove P(N)>N. ;)

i think this boils down to a discussion of whether or not to accept the subsets axiom. there is no real right or wrong answer to that.

 

[Organic]

Proofs by transfinite induction typically need to distinguish three cases:

1) m is a minimal element, i.e. there is no element smaller than m.

2) m has a direct predecessor, i.e. the set of elements which are smaller than m has a largest element.

3) m has no direct predecessor, i.e. m is a so-called limit-ordinal.


In all cases "m does not exist" = "transfinite induction does not exist"

We have here an hierarchic of dependency that can't be ignored.

Therefore I still clime that we have to check S by t as I did, and not t by S as Cantor did.

The order of this difference (S by t XOR t by S) can't be ignored.