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

[phoenixthoth]

cardinality question for hurkyl or whoever

in this thread, we've been talking about |P(X)|.

there's another set operation i'd like to discuss if the thread originator doesn't mind.

i hope it won't be too distracting to use lower case for all sets now. if x is a set, then let Ux be defined as follows:

z is in Ux if and only if there is an element y in x such that z is in y.

in other words Ux={z such that z is in y is in x for some y in x}.

Ux is the set of members of members of x.

(one can define x u y to be U{x,y}.)

for any set x, UP(x)=x.

(to see this we can prove that z is in UP(x) if and only if z is in x. suppose z is in x. then {z} is a subset of x; so {z} is in P(x). since z is in {z} is in P(x), z is in UP(x). now suppose z is in UP(x). then z is in y is in P(x) for some y in P(x). since y is in P(x), y is a subset of x; therefore, since z is in y, z is in x.)

however, it is not always the case that P(Ux)=x. the sets for which this is true are called transitive, i think. a quick counterexample is x=Ø.

hence, if P and U were functions on sets, which there not (what would their domain be?), then U would be a kind of left inverse for P.

since |UP(x)|=|x|, I'm wondering what |Ux| is. could we define a log on cardinals to be |LOG(x)|=|Ux|? generally speaking, what is |Ux| in terms of |x|?

i'm doubting a log would be appropriate. if x={P(N)}, then while |x|=1, |Ux|=2^|N|. however, UP(x)=U{Ø, x}=Ø u x=x, so |UP(x)|=|x|=1.

 

[Hurkyl]

generally speaking, what is |Ux| in terms of |x|?

There certainly can't be an exact relationship; e.g. consider

x = {{1}} and y = {N}

|x| = |y| = 1
but
|Ux| = 1 and |Uy| = aleph₀


However, there is something interesting you can say. Consider the finite case:

Theorem: Suppose x is a finite set of sets. Then, |Ux| >= lg |x|. (lg is the base two logarithm)

The proof is simple. It is clear that x must be a subset of P(Ux). If |Ux| is finite, |x| <= 2^|Ux|, and the conclusion follows. If |Ux| is infinite, then the conclusion ollows as well.

 

[phoenixthoth]

on an earlier notion of X<=Y

an earlier notion of X<=Y (technically |X|<=|Y|) was that there is a bijection between X and a subset of Y. this notion was rejected but i'd like to give concrete reasons for it to be rejected (just for fun).

i claim that there is an injection from N to X if and only if there is a bijection between X and a proper subset of X.

if the above were the definition of <=, then this entails that X is infinite if and only if X<=X. since we'd like to say X<=X for all sets X, this would imply that all sets are infinite. in other words, defining <= in the above way entails that either all sets are infinite or it is not the case that X<=X for all sets X.

proof:
suppose f is an injection from N to X. define h to be a map from X to X in the following way: if x is in X\f(N), h(x)=x and if x is in f(N), h(x)=f(finv(x)+1). finv is the inverse of f that is defined on f(N) which exists because f is injective. i claim that h is a bijection between X and X\{f(0)}, a proper subset of X. to show h is injective, suppose h(a)=h(b). there are two cases: a is in f(N) or a is in X\f(N). if a is in f(N), then h(a)=f(finv(a)+1). since h(a)=h(b), h(b) is in f(N) since f(finv(a)+1)=h(b). b must be in f(N) because if b is not in f(N), then h(b)=b which would imply h(b) is not in f(N) yet we just said that h(b) is in f(N). since b is in f(N), f(finv(a)+1)=h(b)=f(finv(b)+1). since f and finv are injections, a=b. the second case is if a is not in f(N). then h(b)=h(a)=a. since h(b)=a and a is not in f(N), b must not be in f(N) because if b is in f(N), h(b) would be f(finv(b)+1) which is in f(N) yet we just said that h(b)=a is not in f(N). since b is not in f(N), b=h(b)=h(a)=a. h is injective. to show that h is surjective, let x be any element of X\{f(0)}. (note that f(0) is not mapped to by h since if it were the case that h(x)=f(0), that would imply that f(finv(x)+1)=f(0) so that finv(x)=-1 which is impossible since the range of finv is N and -1 is not in N. no problem. x is an element of X\{f(0)} anyway.) there are two cases: x is in f(N)\{f(0)} or x is in X\f(N). if x is in f(N)\{f(0)} then h maps f(finv(x)-1) onto x. to see this, first note that since x!=f(0) and x is in f(N), finv(x)-1 is in N and so it is in the domain of f and, furthermore,
h(f(finv(x)-1)) = f(finv(f(finv(x)-1))+1) = x. the second case is if x is in X\f(N). then h maps x onto x. h is a bijection.

the driving idea behind that was to use the following two facts: (1) f inserts a copy of N into X and (2) N is in bijection with N\{0} and so the copy of N must be in bijection with the copy of N\{0} if the rest of X is left alone.

for the converse, suppose there is a bijection between X and a proper subset of X. let's call this map f and the proper subset X'. X cannot be a finite set. this is pretty clear, but to see this, let n be any natural number and to arrive at a contradiction, suppose g is a bijection from {1,...,n} onto X (the existence of such an n and bijection g is equivalent to saying X is finite--btw, if n=0, then {1,...,n}:=Ø which wouldn't happen here anyway since Ø has no proper subsets and so X!=Ø). this entails that f o g is a bijection from {1,...,n} to X'. the contradiction is that this means X and X' both have n elements yet X' is a proper subset of X. so X is infinite. the map h from N to X will be defined now:
let h(0) be any element of X
for n>0, let h(n) be any element of X\{h(0),...,h(n-1)}. such an element will always exist because X is infinite and {h(0),...,h(n-1)} is finite.
to show that h is an injection, suppose that h(a)=h(b). we will show that a<b and b<a both lead to contradictions and so a=b. if a<b, then h(b) is an element of X\{h(0),...,h(b-1)} which implies h(b)!=h(k) for all k<b. since a<b, this contradicts the assumption h(a)=h(b). that argument was symmetrical, so b!<a. there is an injection from N to X.

this also proves that there is an injection from N to any infinite set.

 

[phoenixthoth]

Theorem: Suppose x is a finite set of sets. Then, |Ux| >= lg |x|. (lg is the base two logarithm)

me likey.

it's also pretty clear that there is no upper bound on |Ux|.

i would suspect that since lg |x| <= |Ux|, |x| <= 2^|Ux| which would entail that there is an injection from x to P(Ux). this works even if x=Ø if we define lg 0 = -oo (or anything less than 0). it's definitely not the case that there is an injection from P(Ux) to x for every x and so not only is x!=P(Ux) for all x, |x|!=|P(Ux)| for all x, although we already said that.

by the way, organic, one can show that if there is an injection from A to B and an injection from B to A, then there is a bijection from A to B. thus, another way to show that X<P(X) is to show that there is no injection from P(X) into X.

 

[Organic]

Hi phoenixthoth,

Please limit your detailed answer only to the case of N and P(N).

Thank you.

---------------------------------------------------------------------------

|N|=aleph0

|P(N)|=2^aleph0

There exists member S in P(N) which is consists of ALL members of N that are not themselves included in the P(N) members which they are mapped to, 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,…}.



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}.


Now, let us say that there exist some member in N (let us call it t ) which is mapped with S (t <--> S ).




--------------------------------------------------------------------------

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) > N .

Q.E.D

=================================================
=================================================

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

0 = { } 

1 = {{ }} = {0}
               
2 = {{ },{{ }}} = {0,1}
  
3 = {{ },{{ }},{{ },{{ }}}} = {0,1,2}

4 = {{ },{{ }},{{ },{{ }}},{{ },{{ }},{{ },{{ }}}}} = {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 omited from S definition).


More you simple less you depended, therefore more exist.

I'll write S defenition again, in an informal way:

There exists member S in P(N) which is consists of ALL members of N that are not themselves included in the P(N) members which they are mapped to, 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,…}.

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]

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.