On P(X) > X

  • Thread starter Organic
  • Start date
  • #26
1,569
2
there's a problem with the first line:

organic:
General:

We say that B > A if A not= B but there is an injection between A and subset of B .
phoenix:i'm having second thoughts about this definition. if we let N be the set of natural numbers and E be the set of even natural numbers, then, by this definition, E<N with the injection f(x)=x.
furthermore, what i didn't mention in my last post was that since there is a bijection between E and N, it wouldn't make sense to say that E<N.

using the definition hurkyl quoted, A<=B if there is an injection from A to B. (technically, it's |A|<=|B|, where |A| is the cardinal number of A.) in this case, we can say that "A is dominated by B." furthermore, we can say that A and B are "equipollent" if there is a bijection from A to B and write without ambiguity that |A|=|B| and A=B with some ambiguity. the standard way of then exctracting the < from the <= is to say < means "<= but not =." in other words, A<B if there is an injection from A to B but there is no bijection from A to B. i think this is equivalent to saying that there is a function from B onto A but no onto function from A to B.

using the definition in bold which reflects hurkyl's quote, one can proceed to prove that for any set X, X<P(X):
1. f(x)={x} is an injection from X to P(X). this proves that X<=P(X).

2. to prove X!=P(X), note that any function g from X to P(X) fails to be a bijection because it is not surjective. g is not surjective (onto) because the element of P(X) defined as {x in X such that x is not an element of g(x)} is not in the image of g.
 
  • #27
1,208
0
Hi phoenixthoth,

Please, please this time try to answer to what I write in this post.

Thank you.

By step 1 of Cantor's prof (P(X)>X) we can say that P(X) >= X .

Let us continue from step 2 (and please give your detailed remarks to each part of it)

Step 2:

Suppose there exists a bijection between P(X) and X .

We will show that this assumption leads us to contradiction.

There exists member S in P(X) which includes ALL members of X that have no image Included in the P(X) 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,…}.

-----------------------------------------------------------------------------
A proof that a non empty member S exists:

2^0=P({})={ {} }=1
2^1=P({0})={ {},{0} }=2
2^2=P({0,1})={ {},{0},{1},{0,1} }=4
2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
...

Therefore {} not in N but {} in P(N)

N members are the natural numbers.

P(N) members are the empty set + subsets of N + N itself.

It is easy to show an injection between any n of N to any singleton member {n} of P(N).

When we define this injection than P(|N|)>=|N|.

If P(|N|)=|N| then D is the member in P(N) includes the members of
N, that have no image in the member of P(N), which they are mapped with.

n in D because {} not in N, therefore D is not empty.

Q.E.D

t=n
X=N
S=D

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


Now, let us say that there exist some member in X (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(X) and X and we can conclude that P(X) > S .

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,...}:
Code:
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 X can be mapped with some member of P(X), 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 .


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(X) which includes ALL members of X that have no image Included in the P(X) 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,…}.


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

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

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
 
  • #28
1,569
2
There exists member S in P(X) which includes ALL members of X that have no image Included in the P(X) 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,…}.
"includes" should be "consists of," i think.

"...that have no image Included in the P(X) members which they are mapped [to]." when talking about an element x of X, to say that x has no image with a certain property simply means that f(x) doesn't have that property. would the following formalization be a correct interpretation:

S={x in X such that f(x) is not an element of f(x)}? (here, f is the arbitrary map from X to P(X) we are trying to show is not a bijection.)

or do you mean, "...that are not themselves included in the P(X) members which they are mapped to?" if so, then
S={x in X such that x is not an element of f(x)}.

in your example, it looks like you're using the last definition i just gave but in the way you phrased it, it looks like the first formalized S is what you mean.
A proof that a non empty member S exists:

2^0=P({})={ {} }=1
2^1=P({0})={ {},{0} }=2
2^2=P({0,1})={ {},{0},{1},{0,1} }=4
2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
...

Therefore {} not in N but {} in P(N)
question: are we assuming X=N?

if yes, then what is written may be relevant. if not, then what is written is not relevant (directly).

some observations about what comes after the "therfore." one doesn't have to define 0 to be a natural number. furthermore, one doesn't have to adopt the definition that {}=0. but if 0 is a natural number and if the definition of 0 is {}, then {} is in N. it is true that {} is in P(X) for any set X but the argument provided isn't what proves that. furthermore, it's not clear how what comes after the "therefore" follows from the argument given.
N members are the natural numbers.

P(N) members are the empty set + subsets of N + N itself.
"subsets of N" is equivalent to "the empty set + subsets of N + N itself."
It is easy to show an injection between any n of N to any singleton member {n} of P(N).
when you say "map between @ and *," it usually means that @ is the whole domain of the map and not one element in the domain. one way to rephrase this is to say, "an injection that maps any n of N to any singleton member {n} of P(N)." by the way, the word "any" that comes before "singleton" means that the notation {n} is misleading because the notation {n} implies that n is mapped to a specific singleton {n} and not just any singleton which one might denote {m}. a way to rephrase that is to say, "...any n of N to the singleton {n}..."
When we define this injection thEn P(|N|)>=|N|.
since |N| refers to the cardinal number of N, i think it would be better to just say either |P(N)|>=|N| or P(N)>=N. when you say P(|N|), you're talking about the set of all subsets of the cardinal number aleph_0 and not the set of all subsets of N. i'm not even sure a cardinal number is a set. if it is, it might be something like the set of all things with that cardinality in which case P(|N|) would include many things irrelevant to N or P(N), including subsets of rational numbers for example.
If P(|N|)=|N| then D is the member in P(N) includes the members of
N, that have no image in the member of P(N), which they are mapped [to].
just out of curiosity, why use a second letter, D, to denote something you've already named S? doing so doesn't hurt the logic of the proof, of course, but it makes it less streamlined. here, the questions i asked of S now apply to D.
n in D because {} not in N, therefore D is not empty.
it's not clear how what comes after the "therefore" follows from what preceeds the "therefore." either it's a non sequitor or i'm just not understanding the argument (or both).

the essential thing that needs to be addressed before i can continue is the clarity of the definition of S=D.

i'm wondering (a) if D is really empty all the time and (b) whether the emptiness of D affects whether or not X=P(X). if you go back to what i've written with my version of D, D was sometimes empty in the examples i gave but that just meant that the empty set was an element of P(X) not mapped to and, hence, that the example map from X to P(X) was not a bijection.
 
  • #29
1,208
0
Hi phoenixthoth,


Thank you very much for your last post.

It is hard for me to express my ideas in English, so I really want to thank you for your help.

Please continue to help me to write it right, thank you.

Here is a corrected version, based on your remarks:

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

By step 1 of Cantor's prof (P(X)>X) we can say that P(X) >= X .

Let us continue from step 2 (and please give your detailed remarks to each part of it)

Step 2:

Suppose there exists a bijection between P(X) and X .

We will show that this assumption leads us to contradiction.

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

-----------------------------------------------------------------------------
A proof that a non empty member S exists:

2^0=P({})={ {} }=1
2^1=P({0})={ {},{0} }=2
2^2=P({0,1})={ {},{0},{1},{0,1} }=4
2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
...

{} not in N but {} in P(N)

N members are the natural numbers.

P(N) members are the empty set + N itself + other subsets of N.

It is easy to show an injection between any n of N to any singleton member {n} of P(N).

When we define this injection than |P(N)|>=|N|.

If |P(N)|=|N| then S is a member 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.

n in S because {} not in N, therefore S is not empty.

Q.E.D

t=n
X=N

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


Now, let us say that there exist some member in X (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(X) and X and we can conclude that P(X) > S .

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,...}:
Code:
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 X can be mapped with some member of P(X), 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 .


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(X) which is consists of ALL members of X that are not themselves included in the P(X) 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 X members is bigger than the power of existence of P(X) members.

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

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
 
Last edited:
  • #30
1,569
2
There exists member S in P(X) which is consists of ALL members of X that are not themselves included in the P(X) 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,…}.
S is nonempty in this example but there are instances in which S would be empty.

example: X=N and f(n)={n}. note that for all n in N, n is a member of f(n) and so the set of n in N such that n is not a member of f(n) is empty.

but it doesn't matter if S=Ø. this just means that Ø is not mapped to; that's good because it still shows that f is not a bijection because it's not onto.
A proof that a non empty member S exists:

2^0=P({})={ {} }=1
2^1=P({0})={ {},{0} }=2
2^2=P({0,1})={ {},{0},{1},{0,1} }=4
2^3=P({0,1,2})={ {},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2} }=8
...

{} not in N but {} in P(N)

N members are the natural numbers.

P(N) members are the empty set + N itself + other subsets of N.

It is easy to show an injection between any n of N to any singleton member {n} of P(N).

When we define this injection than |P(N)|>=|N|.

If |P(N)|=|N| then S is a member 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.

n in S because {} not in N, therefore S is not empty.

Q.E.D
in the line when n is recently mentioned, is n an arbitrary element of N? if so, by saying "n in S," you're saying that N is a subset of S which entails that for all n in N, n is not an element of f(n). and this claim is made for all maps f from N to P(N). but this is not always the case. the counterexample f(n)={n} gives an example where not only is it not that case that, "for all n in N, n is not an element of f(n)," but it is that case that for no n in N is n not an element of f(n). in other words, saying n in S implies N in a subset of S when, in fact, S could be empty for the right f.

however, the last line feels like you're talking about a special n and not an arbitrary n, in which case saying "n in S" would be equivalent to asserting S is nonempty. however, if f(n)={n}, then
S={n in N such that n is not a member of f(n)}=Ø.

that S is empty (1) doesn't seem to matter and (2) isn't always true. it doesn't seem to matter because, in that case, it just means that Ø is not in the range of f and that's a good thing.

another thing is that N is continually refered to. if this is a prove that is supposed to work for all sets X, then N should not be referred to ever. your work amounts to proving N<P(N), not X<P(X) in general.

maybe it would be better to try to prove the following:
1. let X be any set
2. let f be any function from X to P(X)
3. let S={x in X such that x is not an element of f(x)}
4. prove that S is an element of P(X) not mapped to by f.

in 3-4, it doesn't matter if S=Ø. also, there is no need to prove S exists. the way S is defined, it exists by the subsets axiom. in fact, anytime you say "let S={x in X such that A(x)}," then S is a set as long as X is a set and A(x) is some well formed logical formula dependant on x such as "x is not a member of f(x)." the crux of that axiom is the part of the definition that says, "the set of elements of X such that..." as soon as a context is defined, and that context is a set like X is, then you can basically say any condition you want and the result exists and is a set. it might be empty, of course, like if you say {x in X such that x>0 and x<0}. empty or not, it exists and is a set. no need to prove S exists. no need to prove S!=Ø. step 4 doesn't require S to be nonempty.

the conclusions from 1-4, when those are done, are these:
5. there is always an element of P(X) not mapped to by any function f from X to P(X). (that element is S but at this point it no longer matters which element it is that isn't mapped to or even how many elements of P(X) are not mapped to.)
6. every function from X to P(X) is not onto
7. every function from X to P(X) is not a bijection
8. for every set X, X!=P(X)
9. since you already proved X<=P(X), this combined with 8 proves that X<P(X).

try to prove #4 and you'll be done.

regarding the notion of how many elements of P(X) are not mapped to, i think it's the following might be true:
let f be any function from X to P(X), let A\B be the set of elements in A that are not in B, and let f(X) be the set of all outputs of f.
1. for finite X, |P(X)\f(X)| >= 2^|X| - |X|. for example, if X has 10 elements, then the size of the set of targets in P(X) not mapped to by f is at least 2^10 - 10 = 1014. it could be even more than that if f is not injective. for example, if f(x)=Ø for all x, then
|P(X)\f(X)|=1023. if this number is greater than 0, f is not onto. 2^|X|-|X| is greater than 0 for all sets X, even if X=Ø.

2. for infinite X, |P(X)\f(X)|=|P(X)|. all it takes for f to not be onto is if |P(X)\f(X)|>0; for infinite X, not only is it >0, it's infinite! and not just that, but an infinity greater than X.
 
  • #31
1,569
2
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.
 
Last edited:
  • #32
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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| = aleph0


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.
 
  • #33
1,569
2
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. lets 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.
 
  • #34
1,569
2
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.
 
Last edited:
  • #35
1,208
0
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,...}:
Code:
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
 
Last edited:
  • #36
1,569
2
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.
 
  • #37
1,208
0
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...HI=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,...}:
Code:
[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
 
Last edited:
  • #38
1,569
2
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.
 
  • #39
1,208
0
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,...}:
Code:
[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
 
Last edited:
  • #40
1,569
2
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.
 
Last edited:
  • #41
1,208
0
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,...}:
Code:
[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
 
Last edited:
  • #42
1,569
2
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.
 
  • #43
1,208
0
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,...}:
Code:
[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.
 
Last edited:
  • #44
1,569
2
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.
 
  • #45
1,208
0
Does the axiom of subsets has anything to say on the changes of the complexity of its products?
 
  • #46
1,208
0
Is there another ZFC axiom or some combination of these axioms that deal with levels of complexity based on hierarchic recursion?
 
  • #47
1,569
2
you can use the axioms to build things that you could translate into complexity, i imagine.
 
  • #48
1,208
0
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,...}:
Code:
[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.
 
  • #49
1,569
2
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.
 
Last edited:
  • #50
1,208
0
{} and 0 are different things because |{}| = 0 not= {}
 
Last edited:

Related Threads on On P(X) > X

Replies
5
Views
2K
Replies
6
Views
1K
Replies
4
Views
663
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
8
Views
21K
Replies
3
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
633
Top