On P(X) > X

  • Thread starter Organic
  • Start date
1,208
0
An edited version:

General:

We say that B > A if A not= B but there is an injection between A and subset of B .


Theorem: P(X) > X

Proof:


Step 1 (injection between set A and subset of set B ):

Let us define injection between each member of X to each member of P(X), which includes a singleton as its content.

We define f(x) where f(x)={x}, for example: 1 <--> {1} , 2 <--> {2} , 3 <--> {3},… and so on.

At this stage we can say that P(X) >= X .


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

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

Let us look at this proof from another 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 the 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 .

Member t is simpler than member S .

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:

HallsofIvy

Science Advisor
Homework Helper
41,709
876
General:

We say that A > B if A not= B but there is a bijection between A and subset of B .
No, that's exactly backwards but I imagine it was a typo. A is larger than B is there is a bijection between B and a subset of A. And it is the same as saying "the cardinality of A is greater than or equal to the cardinality of B".

Actually, your proof uses a different statement which may be what you intended to say: A> B is A not= B AND there is NOT a bijection between A and a subset of B.

Let us say that there exist subset S in P(X) which includes every member of X that has no image Included in the subset which it is mapped to, for example:

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

By this example S ={1,3,5,…}.
Why should we say that? Do you have any reason to believe that such a subset does exist? If there doesn't exist such a set your proof fails. You need to prove that set's existence, not just "say" it.
 
1,570
1
tricks of the trade

P(X)>X is equivalent to saying there is no function that maps X onto P(X).

we will show that every function which maps X to P(X) is not onto. let f be any function mapping X to P(X). consider the set
D:={x in X such that x is not an element of f(x)}.

(D is for diagonal as in the diagonal argument. note that D is a subset of X and is therefore an element of P(X).)

D is not in the image of f because if it was, then we could say that
f(y)=D for some y in X which would imply that y is an element of
f(y) if and only if y is not an element of f(y).

since D is not in the image of f, f is not onto. since f was arbitrary, this shows that no function from X to P(X) is onto.
 
1,208
0
Hi phoenixthoth,

Thank you for your correction.

I wrote:
General:

We say that A > B if A not= B but there is a bijection between A and subset of B .
It is my mistake, and it has to be:
General:

We say that B > A if A not= B but there is a bijection between A and a subset of B .

I have a simple question:


The power of aleph0 is 2^aleph0, so if we construct a list of X subsets, then
by Cantor's diagonal second argument we can find maps between only aleph0 X
members and aleph0 X subsets, and always there is some subset (the diagonal subset) which is out of the map range.

Is this the idea that stands behind the proof that P(X) > X ?




Organic
 
Last edited:
1,570
1
yes. D is always out of the range of any function from X to P(X).

if you look at random examples of X's and P(X)'s and D's and maps f from X to P(X), you can see what D is in particular to see what the example f misses.

example. of course, the proposition is clear for finite sets, but let's say X={1,2}. then P(X)={Ø,{1},{2},X}. let f be defined so that f(1)=Ø and f(2)={1}. as you can see, f is not onto P(X) since {2} and X are out of the range but let's see what D would be in this case.
D:={x in X such that x is not an element of f(x)}. one by one, lets go through elements in X and see if x is not an element of f(x). if so, then x is an element of D. let's start with 1. is 1 not an element of f(1)? yes, since 1 is not an element of Ø=f(1). then 1 is an element of D. is 2 not an element of f(2)? yes, since 2 is not an element of {1}=f(2); so 2 is an element of D. in this case, D=X. and, as we know, X is not in the range of f. but this was automatic from the beginning.

perhaps this is like fitting a carpet into a room where if we just fix the problem, fit the carpet in one corner, then it will fit the room. alas, no, if we pull the carpet to this corner by making sure X is in the range of f, the carpet will pull out of another corner.

let's say f(1)=Ø and now that f(2)=X. maybe this will fix things since now that X is in the range of f. lets see what D is. i can guarantee you that it will either be {1} or {2} because neither of those are in the range of our new f even though X is. is 1 not an element of f(1)? yes, because 1 is not an element of Ø=f(1); so 1 is in D. is 2 not an element of f(2)? no, because 2 is an element of X=f(2); so 2 is not an element of D. therefore, D={1}. D is not in the range of f.

the carpet will not fit the room no matter which corner we force it to fit in. whenever we fit it into one corner, it will always come up in another corner.

an example with infinite sets? ok. let X=R and P(X) is the power set of R. define f to be the following function:
for x in R, f(x)=(-infinity, x].
this f is an injection from X into P(X). as you can already see, f is hopelessly not onto. but let's see if we can get a handle on what is automatically out of the range of f, ie, what D is. let's follow our noses. x is an element of D if and only if x is not an element of f(x); therefore, x is an element of D if and only if x is not an element of (-infinity, x]. but wait, x is an element of (-infinity,x]; therefore, D is the empty set. and as you can see from the definition of f, Ø=D is not in the range of f.

here's an amusing exercise: let A and B be sets. prove there is no function from A onto B if and only if there is a bijection between A and a proper subset of B. (B is the only nonproper subset of B.) thus, either definition will suffice to mean A<B. i hope that's right...
 
Last edited:
1,208
0
Hi phoenixthoth,

You wrote:
an example with infinite sets? ok. let X=R and P(X) is the power set of R. define f to be the following function:
for x in R, f(x)=(-infinity, x].
this f is an injection from X into P(X). as you can already see, f is hopelessly not onto. but let's see if we can get a handle on what is automatically out of the range of f, ie, what D is. let's follow our noses. x is an element of D if and only if x is not an element of f(x); therefore, x is an element of D if and only if x is not an element of (-infinity, x]. but wait, x is an element of (-infinity,x]; therefore, D is the empty set. and as you can see from the definition of f, Ø=D is not in the range of f.
I will try to write it in a short way, please tell me if I do it right, thank you:

x in X such as f(x)=(-[oo],x]

x in D iff x not in (-[oo],x] --> D={}

D not in (-[oo],x] therefore D is out of the range of f.


Organic
 
1,570
1
D not in (-oo,x] therefore D is out of the range of f.
since D = Ø != (-oo,x] = f(x) for any x, D is not in the range of f.
 
1,208
0
Sorry I can't follow it.

Can you please write it again in simple english?

Thank you.
 
1,570
1
for x in R, f(x):={z in R : z <= x}.

in other words, f(x)=(-oo,x].

D={x in R such that x is not an element of f(x)}.

f(x)={z in R : z <= x}, so this means that

D={x in R such that x is not an element of {z in R : z <= x}}.

note that for all x in R, x *is* an element of {z in R : z <= x}.

therefore, the set of x in R such that x is *not* an element of
{z in R : z <= x} is empty.

since D is the set of x in R such that x is not an element of
{z in R : z <= x}, D=Ø.

in the argument i wrote about in "tricks of the trade," D is an element of P(X) automatically not in the range of any function from X to P(X). this last bit was an investigation into what various versions of D are for particular cases. in the last example, D=Ø and so Ø is not in the range of f. another way to say that is that for no x in R is the set {z in R : z <= x} empty. {z in R : z <= x}=f(x), so this is saying that f(x) != Ø for any x in R which means that Ø is not in the range of f. the central argument gives us a set, D, which is automatically not in the range of f and we can see what D looks like in this case; D=Ø.

triva question: true or false? if m and n are positive integers and A is any infinite set, then the set of funtions from A to a set of m elements is in 1-1 correspondance with the set of functions from A to a set of n elements; i.e., m^A = n^A.
 
1,208
0
phoenixthoth,phoenixthoth,

Please hold your horses.

I'll give a number to each line that is written below.
Please just answer by yes(if ok) or no(if not ok) to each line.
And if your answer is no, then please explain it in a simple and not formal way. Thank you.

1) x in X such as f(x)=(-[oo],x]

2) x in D iff x not in (-[oo],x] --> D={}

3) D not in (-[oo],x] therefore D is not in the range of f.


Organic
 
1,570
1
1) x in X such as f(x)=(-oo,x]
i'm not sure what "such as" means. for x in R, f(x) is defined to equal (-oo,x].

2) x in D iff x not in (-oo,x] --> D={}
yes since x *is* in (-oo,x] for all x in R.

3) D not in (-oo,x] therefore D is not in the range of f.
no. D != (-oo,x] (for all x in R) therefore D is not in the range of f. in other words, D != f(x) (for all x in R) therefore D is not in the range of f.
 
1,208
0
An edited version:


General:

We say that B > A if A not= B but there is an injection between A and subset of B .


Theorem: P(X) > X

Proof:


Step 1 (injection between set A and subset of set B ):

Let us define injection between each member of X to each member of P(X), which includes a singleton as its content.

We define f(x) where f(x)={x}, for example: 1 <--> {1} , 2 <--> {2} , 3 <--> {3},… and so on.

At this stage we can say that P(X) >= X .


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

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

Let us look at this proof from another 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 the 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 .

Member t is simpler than member S .

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:
1,570
1
We say that B > A if A not= B but there is a bijection between A and subset of B .
i think it should be B > A and A not= B but there is a bijection between A and proper subset of B, where S is a proper subset of B if S is a subset of B and S != B.

with this in mind, let's prove X<P(X):
at least when X!=Ø, your map f(x)={x} will do the trick, but we have to show that the image of f is a proper subset of P(X). the image of f is precisely the set of all elements of P(X) that are singletons. therefore, Ø is not in the image of f but is in P(X), so the image of f is a proper subset of P(X). this proof doesn't work for X=Ø, but X=Ø<{Ø}=P(X) via the empty function which is a bijection (by vacuous truth) between Ø and Ø, a proper subset of {Ø}.

in some sense, this proof is "better" because it doesn't use a trick like the set D. note that the above definition of B>A is equivalent to the following: there is a function from B onto A and there is no function from A onto B. in this definition of B>A, i think one needs the trick set D.

this is related to the thread
https://www.physicsforums.com/showthread.php?s=&threadid=7924
though it doesn't look like it because that thread is analysis related and not set theory related. here's what i'm trying to accomplish in that thread. we know that P(A)=2^A. i'm trying to find a function f such that f(f(x))=2^x that is as well-behaved as possible. then the next step is to determine if a set B exists such that f(A)=B for any infinite A. (let's let all subsequently mentioned sets be infinite.) then we would have
P(A)=2^A=f(f(A))=f(B). the hope is that f is strictly increasing on sets; i.e., there is a bijection between X and a proper subset of f(X) for all sets X. thus, we would have a set B such that A<B<P(A) for any set A. since, i believe, this would prove the continuum hypothesis, i think i will fail. the idea then would be to analyze what the failure implies. perhaps it implies that there is no such well-behaved f. or it may be that the existence of a set with cardinality f(A) is equivalent to the continuum hypothesis. in that case, if we assume the continuum hypothesis, we would then be closer to actually finding a set B such that A<B<P(A). we gots to find the f first, though.

if A=N, then aleph_0=A and aleph_1=P(A). we'd then have fractional cardinals. for example, aleph_(1/2)=f(A). if we let h(x)=2^x, then aleph_(m/n) would be equal to g(A) where g is some function such that
g^n(x)=h^m(x) and by g^n, i mean the nth iterate of g. (this will also potentially work for negative m.) having defined what aleph_x means for rational x, one wonders if it can be defined for real x.
 
Last edited:
1,208
0
Hi phoenixthoth,


Please look again at my previous post, and please tell what
do you think about what I wrote after
this
|
|
|
V
=================================================
=================================================
 
1,570
1
you define D to be "the subset in P(N) [that] includes the members of N that have no image in the subset of P(N)." what do you mean by "the subset of P(N)"? which subset are you talking about? did you mean, "...no image in P(N)?" if that's what you mean, then D is automatically empty because for any map f from N to P(N), all members of N have an image in the set P(N), namely f(n). if f(N) is the image (or range) of f, are you defining D to be P(N)\f(N), the set of elements in P(N) not in the image of f? when you define D that way, there doesn't seem to be a guarantee that D will or won't be empty.

it's kinda confusing to be reusing the letter D in this thread because D has been refered to as something different, namely D used to be the set of elements n of N such that n is not an element of f(n).
 
1,208
0
No, I mean please read this part, which is another point of view on Cantor's proof.

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

Let us look at this proof from another 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 the 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 subset, 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 subset S .


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

Member t is simpler than subset S .

Subset 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:
1,570
1
i'll just start with the first thing i don't understand.

Any member of X can be put in map with some subset of P(X), once and only once.
do you mean put in a map or mapped to?

do you really mean "some subset of P(X)" or really an element of P(X)? if you're talking about subsets of P(X), it sounds like we're dicussing the relationship between X and P(P(X)) since subsets of P(X) are elements of P(P(X)).
 
1,208
0
Hi phoenixthoth,

Well, I am a bad formalist.

What I mean is this: no object in X is a set, all objects in p(X) are sets.


An example of X objects is: 23,5,17,...

An example of P(X) objects is: {23},{5},{17},{12,67},{},{2,4,6,...),...


So, I'll correct it to:

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

I'll write this corrected part again.

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

Let us look at this proof from another 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 the 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 .

Member t is simpler than member S .

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:
1,570
1
What I mean is this: no object in X is a set, all objects in p(X) are sets.
actually, every element of a set is also a set. that's why if you look in a set theory book, most sets are denoted by lower case letters rather than lower case for "elements" and upper case for "sets." there is *no* distinction, fundamentally, between a group of things called "elements" (which are not sets) and a group of things called "sets." for example, natural numbers are even sets:
1={Ø}
2={Ø,1}
3={Ø,1,2}
...
23={Ø,1,2,...,21,22}. note that "23" is a set with 23 elements.

Any member of X can be mapped with some member of P(X), once and only once.
it's clear now that you mean "can be mapped to some member of P(X)" and not a subset of P(X).

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.
i'm assuming that t is an arbitrary element of X and S is "a set in P(X) which includes ALL members of X that have no image Included in the P(X) members which they are mapped with."

"includes" should be "consists of," i think. for example, if i say S is a set including the empty set, it's ambiguous because S could be {Ø} or it could be {Ø,1}. i'll assume you mean "consists of." let me try to symbolize the definition of S:

actually, do you mean "a set in P(X)," which would mean that S is a set that is an element of P(X) so that S would be a subset of X, or "a subset of P(X)" which would mean that S consists of subsets of X? i'll assume you mean the latter. f is our arbitrary function from X to P(X).

S={x in X such that f(x) is not an element of f(x)}.

"the image of x" is f(x) and "members which they are mapped [to]" is also f(x). to put the word "no" in front of "image" is what lead me to put "not" in front of "an." let me know if this is the definition of S and then i'll be able to read the rest. if this isn't what you mean by S, then please write it down using symbols like the italycized ones above because that tends to be less ambiguous.
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
For the record, some set theories permit there to be objects that are not sets, and that list of natural numbers as sets is merely a model; natural numbers don't have to be those sets. (and, in general, they don't have to be sets at all, though in ZFC they do)
 
1,570
1
there are proper classes and such. i guess what i mean is that for what we're talking about, there need not be a second entity that is not a set.
 
Last edited:
1,208
0
An edited version:

General:

We say that B > A if A not= B but there is an injection between A and subset of B .


Theorem: P(X) > X

Proof:


Step 1 (injection between set A and subset of set B ):

Let us define injection between each member of X to each member of P(X), which includes a singleton as its content.

We define f(x) where f(x)={x}, for example: 1 <--> {1} , 2 <--> {2} , 3 <--> {3},… and so on.

At this stage we can say that P(X) >= X .


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
 
Last edited:
1,570
1
General:

We say that B > A if A not= B but there is an injection between A and subset of B .
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.

the previously used definition was that A < B if A not= B but there is a bijection between A and a proper subset of B. even with this, f(x)=x is a bijection from E to E which is a proper subset of N.

in fact, i think one defining attribute of an infinite set could be that there exists a bijection between it and a proper subset of it. (triva question true or false: let X be a set. there is an injection from N to X if and only if there is a bijection between X and a proper subset of X. the first part is the equivalent to saying X is an infinite set. recall that B is a proper subset of X if B is a subset of X and B!=X.)

therefore, i would contend that the definition of A<B has to be this: there is a function from B onto A but there is no function from A onto B. (if f maps X to Y and f(X) is the range of X, ie {y in Y such that f(x)=y for some x in X}, then f is defined to be onto if f(X)=Y).) in other words, there is a function f from B to A such that f(B)=A and for all functions g from A to B, g(A)!=B.

another approach is to define A <= B to mean that there is an injection from A to B and then say that A<B if
1. A <= B AND
2. there is no bijection from A to B.
(this is like saying A<B if A<=B but A!=B.)

(if this is the definition of < and = means that there is a bijection, is it always the case that for any sets A and B that either A<B, A=B, or B<A? about a zillion years ago i remember hearing something about the trichotomy of ordinals which vaguely makes me think that the answer might be yes.)

with this definition of < in mind, it seems to me that the best way to prove that X<P(X) for all sets X is to note that the set
D_f:={x in X such that x is not an element of f(x)} is an element of P(X) not in the image of f for all functions f mapping X to P(X).
 
1,208
0
Dear phoenixthoth, dear Hurkyl,


Please reply detailed remarks to my previous post.


Thank you.

Organic
 

Related Threads for: On P(X) > X

Replies
5
Views
2K
Replies
6
Views
1K
Replies
4
Views
598
Replies
2
Views
1K
Replies
8
Views
21K
Replies
3
Views
1K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top