Prev: Fitch's paradox and OWA
Next: Cardinality and Hereditary sets.
From: zuhair on 1 Jan 2010 04:37
Hi all,

In the last one month I've posted many topics on cardinality. This one
is also another trial to define cardinality in ZF, i.e. without
Choice.

First from T. Jeck's paper, it appears that his proof can be
generalized to every well orderable set x.

So for every well order-able set x, there exist the set of all
sets hereditarily subnumerous to x.

This is a theorem of ZF.

Now this time the main idea of the trial is to associate a unique
ordinal with each set in ZF such that all sets equinumerous to each
other have a corresponding unique ordinal.

So for example lets take any set x, then all sets equinumerous to x
would be associated with the same ordinal d(x), now every y that are
strictly subnumerous to x would be associated with an ordinal
d(y) that is also strictly subnumerous to d(x), same thing applies
every set z that is strictly supernumerous to x would be associated
with an ordinal d(z) that is strictly supernumerous to d(x).

Next step we define for every x, the set of all sets hereditarily
subnumerous to d(x) (i.e. the set of all sets that are subnumerous
(injective) to d(x) were every member of their transitive closures is
also subnumerous to d(x) )

Lets denote this set as H(d(x))

Then we define cardinality as:

Cardinality (x) is the class of d(x) and of all subsets of H(d(x))
that are equinumerous to x.

The point is how to define d(x).

This is a trial:

Define(d(x)):

A=d(x) <-> for all y ( y e A <->
Exist u,z( u strictly subnumerous to x & z=d(u) &
& y is ordinal & y equinumerous to d
(u))).

This is a trick really,

Now we start with x=0 i.e. x is the empty set.

we'll see that d(0) = 0, because there do not exist any set u that is
strictly subnumerous to 0

so d(0)=0.

Now d(x) were x is singleton would be 1 i.e. {0}

So for every finite set x, d(x) would be the ordinal that is
equinumerous to x, i.e. the Von Neumann cardinal of x.

Also for every Countably infinite set x, d(x) would be Omega.

However for Aleph_1 , d(x) = Aleph_1 itself.

Actually we can conclude that for every ordinal x, d(x) is the Von
Neumann Cardinal of x.

Now lets take Power(omega) and lets assume it is incomparable to any
of the uncountable ordinals.

Now d(power(omega))=Aleph_1
d(power(power(omega)))=Aleph_2
etc....

so we managed to define d(x) for every set x.

Of course it is easy to prove that d(x) is not empty for every set x
in ZF.

So now we come to our Cardinal here.

Lets take the Cardinality of Power(omega) and lets assume that power
omega is not comparable to any of the uncountable ordinals.

Now we have H(Aleph_1) as a set in ZF.

So the cardinality of power(omega) is the class having Aleph_1 as a
member and also having all subsets of H(Aleph_1) that are equinumerous
to Power(omega) as members.

Now The cardinality of Aleph_1 would be the class of all subsets of H
(Aleph_1) that are equinumerous to Aleph_1.

Clearly they are not the same cardinality, since all proper subsets of
aleph_1 that are equinumerous to Aleph_1 would be members of the
Cardinality of Aleph_1, but not of the Cardinality of
Power(omega)).

Now from the other hand, two sets that are equinumerous, it is obvious
that they will have the same cardinality, because the will have the
same d(x), and the rest of the sets in their cardinal are equinumerous
to each of them. so they will have the same cardinal.

two sets that are strictly non equinumerous will also have different
cardinals also since their members would not be equinumerous.

so:

(1)Card(x)=Card(y) iff x and y have the same members(Extensionality).

(2)Card(x) > Card (y) iff [(every member of Card(x) is strictly
supernumerous to every member of Card (y)) and (every
subset of d(x) that is equinumerous to d(x) is a member of Card(x) iff
every subset of d(y) that is equinumerous to d(y) is a member of Card
(y)) ].

(3)Card(x) < Card(y) <-> Card(y) > Card(x)

(4)Card(x) incomparable with Card(y) iff non of the above.


Although very complex definition but I think it works.

Of course this definition requires Regularity, so it works in ZF, it
doesn't require choice.

However I have the guess, that this definition can be modified to
exclude Regularity also.

Zuhair





From: zuhair on 1 Jan 2010 05:08
On Jan 1, 4:37 am, zuhair <zaljo...(a)gmail.com> wrote:
> Hi all,
>
> In the last one month I've posted many topics on cardinality. This one
> is also another trial to define cardinality in ZF, i.e. without
> Choice.
>
> First from T. Jeck's paper, it appears that his proof can be
> generalized to every well orderable set x.
>
> So for every well order-able set x, there exist the set of all
> sets hereditarily subnumerous to x.
>
> This is a theorem of ZF.
>
> Now this time the main idea of the trial is to associate a unique
> ordinal with each set in ZF such that all sets equinumerous to each
> other have a corresponding unique ordinal.
>
> So for example lets take any set x, then all sets equinumerous to x
> would be associated with the same ordinal d(x), now every y that are
> strictly subnumerous to x would be associated with an ordinal
> d(y) that is also strictly subnumerous to d(x), same thing applies
> every set z that is strictly supernumerous to x would be associated
> with an ordinal d(z) that is strictly supernumerous to d(x).
>
> Next step we define for every x, the set of all sets hereditarily
> subnumerous to d(x) (i.e. the set of all sets that are subnumerous
> (injective) to d(x) were every member of their transitive closures is
> also subnumerous to d(x) )
>
> Lets denote this set as H(d(x))
>
> Then we define cardinality as:
>
> Cardinality (x) is the class of d(x) and of all subsets of H(d(x))
> that are equinumerous to x.
>
> The point is how to define d(x).
>
> This is a trial:
>
> Define(d(x)):
>
> A=d(x) <-> for all y ( y e A <->
>                  Exist u,z( u strictly subnumerous to x & z=d(u) &
>                                 & y is ordinal & y equinumerous to d
> (u))).
>
> This is a trick really,
>
> Now we start with x=0 i.e. x is the empty set.
>
> we'll see that d(0) = 0, because there do not exist any set u that is
> strictly subnumerous to 0
>
> so d(0)=0.
>
> Now d(x) were x is singleton would be 1 i.e. {0}
>
> So for every finite set x, d(x) would be the ordinal that is
> equinumerous to x, i.e. the Von Neumann cardinal of x.
>
> Also for every Countably infinite set x, d(x) would be Omega.
>
> However for Aleph_1 , d(x) = Aleph_1 itself.
>
> Actually we can conclude that for every ordinal x, d(x) is the Von
> Neumann Cardinal of x.
>
> Now lets take Power(omega) and lets assume it is incomparable to any
> of the uncountable ordinals.
>
> Now d(power(omega))=Aleph_1
> d(power(power(omega)))=Aleph_2
> etc....
>
> so we managed to define d(x) for every set x.
>
> Of course it is easy to prove that d(x) is not empty for every set x
> in ZF.
>
> So now we come to our Cardinal here.
>
> Lets take the Cardinality of Power(omega) and lets assume that power
> omega is not comparable to any of the uncountable ordinals.
>
> Now we have H(Aleph_1) as a set in ZF.
>
> So the cardinality of power(omega) is the class having Aleph_1 as a
> member and also having all subsets of H(Aleph_1) that are equinumerous
> to Power(omega) as members.
>
> Now The cardinality of Aleph_1 would be the class of all subsets of H
> (Aleph_1) that are equinumerous to Aleph_1.
>
> Clearly they are not the same cardinality, since all proper subsets of
> aleph_1 that are equinumerous to Aleph_1 would be members of the
> Cardinality of Aleph_1, but not of the Cardinality of
> Power(omega)).
>
> Now from the other hand, two sets that are equinumerous, it is obvious
> that they will have the same cardinality, because the will have the
> same d(x), and the rest of the sets in their cardinal are equinumerous
> to each of them. so they will have the same cardinal.
>
> two sets that are strictly non equinumerous will also have different
> cardinals also since their members would not be equinumerous.
>
> so:
>
> (1)Card(x)=Card(y) iff x and y have the same members(Extensionality).
>
> (2)Card(x) > Card (y) iff [(every member of Card(x) is strictly
> supernumerous to every member of Card (y)) and  (every
> subset of d(x) that is equinumerous to d(x) is a member of Card(x) iff
> every subset of d(y) that is equinumerous to d(y) is a member of Card
> (y)) ].
>
> (3)Card(x) < Card(y) <-> Card(y) > Card(x)
>
> (4)Card(x) incomparable with Card(y) iff non of the above.
>
> Although very complex definition but I think it works.
>
> Of course this definition requires Regularity, so it works in ZF, it
> doesn't require choice.
>
> However I have the guess, that this definition can be modified to
> exclude Regularity also.

An example of such modification is:

Card(x) is the set of d(x) and all subsets of d(x) that are
equinumerous to x.

However the problem with this definition would be sets that are not
well orderable that are not comparable at the same time.

If we stipulate that every two non well orderable sets are comparable
(having an injection from one to the other) then this definition seems
to work, but I don't know if this is equivalent to choice really.


>
> Zuhair

From: Rupert on 1 Jan 2010 06:02
On Jan 1, 8:37 pm, zuhair <zaljo...(a)gmail.com> wrote:
> Hi all,
>
> In the last one month I've posted many topics on cardinality. This one
> is also another trial to define cardinality in ZF, i.e. without
> Choice.
>
> First from T. Jeck's paper, it appears that his proof can be
> generalized to every well orderable set x.
>
> So for every well order-able set x, there exist the set of all
> sets hereditarily subnumerous to x.
>
> This is a theorem of ZF.
>
> Now this time the main idea of the trial is to associate a unique
> ordinal with each set in ZF such that all sets equinumerous to each
> other have a corresponding unique ordinal.
>
> So for example lets take any set x, then all sets equinumerous to x
> would be associated with the same ordinal d(x), now every y that are
> strictly subnumerous to x would be associated with an ordinal
> d(y) that is also strictly subnumerous to d(x), same thing applies
> every set z that is strictly supernumerous to x would be associated
> with an ordinal d(z) that is strictly supernumerous to d(x).
>

If ZF is consistent, then you cannot define such a function d(x) and
prove in ZF that it has the requisite properties.

Because, if ZF is consistent, then it is consistent with ZF that there
exists a set S of real numbers which is Tarski infinite but Dedekind
finite. Then if k and l are two natural numbers with k<l, the set S
with l elements removed is subnumerous to the set S with k elements
removed but not equinumerous with it. If it were possible to define
your function d(x) then this would yield an infinite descending
sequence of ordinals and so a contradiction.

So working in ZF alone it will not be possible to do this.

From: David Libert on 2 Jan 2010 03:32


zuhair (zaljohar(a)gmail.com) writes:
> On Jan 1, 4:37=A0am, zuhair <zaljo...(a)gmail.com> wrote:
>> Hi all,
>>
>> In the last one month I've posted many topics on cardinality. This one
>> is also another trial to define cardinality in ZF, i.e. without
>> Choice.
>>
>> First from T. Jeck's paper, it appears that his proof can be
>> generalized to every well orderable set x.
>>
>> So for every well order-able set x, there exist the set of all
>> sets hereditarily subnumerous to x.
>>
>> This is a theorem of ZF.
>>
>> Now this time the main idea of the trial is to associate a unique
>> ordinal with each set in ZF such that all sets equinumerous to each
>> other have a corresponding unique ordinal.
>>
>> So for example lets take any set x, then all sets equinumerous to x
>> would be associated with the same ordinal d(x), now every y that are
>> strictly subnumerous to x would be associated with an ordinal
>> d(y) that is also strictly subnumerous to d(x), same thing applies
>> every set z that is strictly supernumerous to x would be associated
>> with an ordinal d(z) that is strictly supernumerous to d(x).

Rupert already reponded on this point, for a Dedekind set the
strictly subnumerous sets below are not well-founded so this can't
be done all levels down in that case.


>> Next step we define for every x, the set of all sets hereditarily
>> subnumerous to d(x) (i.e. the set of all sets that are subnumerous
>> (injective) to d(x) were every member of their transitive closures is
>> also subnumerous to d(x) )
>>
>> Lets denote this set as H(d(x))
>>
>> Then we define cardinality as:
>>
>> Cardinality (x) is the class of d(x) and of all subsets of H(d(x))
>> that are equinumerous to x.

How do we show this cardinality is non-empty? If it can become empty
for 2 nonisomorphic x then we get the old problem of nonisomorphic
sets being assigned the same cardinality.

Inspired by your definition above I make these definitions.

Define a set is 0-well-orderable <-> it is well-orderable in the
usual sense.

For alpha an ordinal define inductively from 0 base case above
a set x is alpha-well-orderable <->
it x is isomorphic to
some set y such that for every member z of y
there exists beta < alpha such that y is beta-well-orderable.


If your Cardinality(x) above is nonempty, then x is isomorphic to
some set y a subset of H(d(x)).

Each element z of such a y is a member of H(d(x)), and so is subnumerous
to ordinal d(x) and hence well-orderable, ie 0-well-orderable in my new
terminology.

So x is isomoprphic to y with all members 0-well-orderable.

So x is 1-well-orderable.

ZF proves AC <-> every set is 0-well-founded.

Is it possible to have a ZF model with some set x which is not
1-well-founded?

I don't know. But if it were such x would have empty Cardinality
in the new definition.

So a proof would have to rule out this possibility. Show from ZF
or whatever extra axioms you want to use every set is 1-well-orderable.



>> The point is how to define d(x).
>>
>> This is a trial:
>>
>> Define(d(x)):


Somehow a system along the way has replaced spaces by other characters
which makes the original quote hard to read. I will manually edit those
back to spaces, but I might make mistakes and change your original
spacing.


>> A= d(x) <-> for all y ( y e A <->
>> Exist u,z( u strictly subnumerous to x
> & z=d(u) &
>> & y is ordinal & y equinumerous to d
>> (u))).
>>
>> This is a trick really,

The form of your defintion is a transfinite induction over strictly
subnumerous, since you invoke d(u). Rupert already gave examples
where this is not well-founded.

We could interpret your definition as just defining d for sets with
well founded strictly subnumerous relation below them. So maybe it
is only defining cardinality for a subclass of the universe.

This raises another interesting question. Is it possible to have in
a ZF model a set x which cannot be well-ordered, with well-founded
strictly subnumerous partial ordering below it?

I don't know.

Anyway, if it is and some cases of x get d(x) defined this way,
then my previous question for these of why Cardinality(x) is
non-empty remains.

Below you discuss example of familar small x. I will delete that
because it doesn't touch on the 2 trickier questions I just mentioned.

[Deletion}


>> Lets take the Cardinality of Power(omega) and lets assume that power
>> omega is not comparable to any of the uncountable ordinals.
>>
>> Now we have H(Aleph_1) as a set in ZF.

By the way, you are also using the generalized Jech result as you
mentioned, but that used regualrity. Below you will consider what
happens with definitions like this without regularity.

My first model of those discussed recently got H(= 1) a proper
class. So this is another difficulty for the version dropping
regularity.


[Deletion]

>> two sets that are strictly non equinumerous will also have different
>> cardinals also since their members would not be equinumerous.

Except the emptiness issue above if it goes the wrong way.


>> so:
>>
>> (1)Card(x)=3DCard(y) iff x and y have the same members(Extensionality).
>>
>> (2)Card(x) > Card (y) iff [(every member of Card(x) is strictly
>> supernumerous to every member of Card (y)) and =A0(every
>> subset of d(x) that is equinumerous to d(x) is a member of Card(x) iff
>> every subset of d(y) that is equinumerous to d(y) is a member of Card
>> (y)) ].
>>
>> (3)Card(x) < Card(y) <-> Card(y) > Card(x)
>>
>> (4)Card(x) incomparable with Card(y) iff non of the above.
>>
>> Although very complex definition but I think it works.
>>
>> Of course this definition requires Regularity, so it works in ZF, it
>> doesn't require choice.

Yes, about regularity as I mentioned above and you say now.


>> However I have the guess, that this definition can be modified to
>> exclude Regularity also.
>
> An example of such modification is:
>
> Card(x) is the set of d(x) and all subsets of d(x) that are
> equinumerous to x.
>
> However the problem with this definition would be sets that are not
> well orderable that are not comparable at the same time.
>
> If we stipulate that every two non well orderable sets are comparable
> (having an injection from one to the other) then this definition seems
> to work, but I don't know if this is equivalent to choice really.
>
>
>>
>> Zuhair


I think I have a proof over ZF that your last suggested property is
equivalent to AC.

AC -> everything is well-orderable, so your clause about non-well-orderable
set is vacuous. So AC -> your stipulation is easy.

For the other direction, your stipulation -> AC:

Assume your stipulation.

Suppose also A and B are arbitrary sets which cannot be well-ordered.
I will derive a property of them I will state after discussion.

Let alpha be the usual Hartog's number for B, defined by injections.
Namely alpha is the least ordinal which cannot inject into B. ZF (no
AC needed) proves there is such an ordinal alpha and it is a set, not a
proper class.

Without loss of generality I will assume A is disjoint from alpha.
(Else replace A by a suitable isomorphic copy).

Consider the sets B and A union alpha.

A union alpha cannot be well-ordered, otherwise this woud induce a
well-ordering on A, contrary to assumption on A.

So your stipulation applies to B and A union alpha, so one of these
must inject into the other.

But if A union alpha injects into B, this would induce an injection
of alpha into B, contrary to alpha being the injective Hartog numbwer
for B.

So B must inject into A union alpha.

Pulling back preimages of A and alpha along this injection.
we conclude the property I state now: B can be partitioned into
a subset isomorphic to a subset of A and a subset which is well-orderable.

This for any pair A, B both non-well-orderable.

Next, consider any A which cannot be well-ordered.

Let beta be the surjective Hartog number for A.

This is the least ordinal which cannot surject onto A.

ZF (no AC needed) proves this ordinal exists and is a set
and not a proper class.

I wrote abopit that in

[1] David Libert "A new definition of Cardinality"
sci.logic, sci.math Nov 24, 2009
http://groups.google.com/group/sci.logic/msg/23d5368fc03e61ca

I quote that:

> ZF proves for any set x there is a set of what I will call
>the surjective Hartog ordinal. The usual definition of the
>Hartog ordinal of a set x is the least ordinal which does
>not inject into x. ZF proves the so called Hartog ordinal
>exists and is a set.
>
> I take instead a surjecive version: the least ordinal
>alpha such that x does not surject onto alpha.
>
> ZF proves there is always such a set sized ordinal. Namely
>to see this, any surjection of x onto alpha induces an
>equivalence realtiion on x : x elements are equivalent
>if they are sent to the same ordinal.
>
> So any ordinal surejcted by x is isomorphic to a well-ordering
>on some subset of P(x), ie pull the wellordering onn the ordinal
>back to the equivalence class preimages.
>
> So all the ordinals less than the surjective Hartog ordinal of
>x are ismimorphic to various well-orderings on a single set
>P(x).
>
> So the collection of all well-orderings on P(x) has natural
>well ordeing greater than all these, so its von Neuman ordinal
>can't be surjected by x, so there is a least such.


That quote locally called that surjective Hartog ordinal
alpha, but I will resume calling the surjective Hartog ordinal
for A beta, to avoid confusion with the previous alpha I used
above in this proof.

So A is an arbitrary non-well-orderable set, and
beta is A's surejctive Hartog number.

Let B = A x beta.

If B could be well ordered, it would induce a well-ordering
on A by an isomporphic copy of A sitting as a slice in B.
This contrary to A not being well-orderable.

So apply my last statement to this A, B.

Conclude B has a subset isomorphic to a subset of
A and it compliment in B well-orderable.

Let A' be that subset of B, isomorphic to a subset
of A.

First suppose every A copy slice inside B has members
in A'. Ie for each gamma < beta, A x {gamma}
as a subset of B has nonempty intersection with A'.

A' is isomorphic to a subset of A. So for the A members
in that subset, map to A' and then map to the gamma
where they live.

For A members outside the subset if any just map to
ordinal 0.

Sonce we are for the moment assuming every slice gamma
has some A' members, this map is surjective onto
beta.

We just surjected A onto beta, contrary to beta being
the surjective Hartog ordinal for A.

We conclude some gamma slice of B is disjoint from
A'.

So the entire A copy on slice gamma was instead sent
to B - A', the set which is well-orderable.

This well ordering induces a well-ordering on its
subset the gamma'th slice, which being isomprphic to
A induces a well-ordering on A.

Contrary to A not being well-orderable.

We got this contradiction by assuming your stipulation
and also assuming some A cannot be well-ordered.

So every wset can be well-ordered, hence AC,
from the assumption of your stipulation.


Another point. I did my models of ZF - regualrity with
cardinality undefinable. For the momeent those seem to be
ok.

So what is this about seeking a definition of cardinality
in ZF - regularity? Do you mean to add some axioms to that?
Or do you mean really just ZF - regularity, and you are
still questioning those models?



--
David Libert ah170(a)FreeNet.Carleton.CA
From: zuhair on 2 Jan 2010 09:30
On Jan 2, 3:32 am, ah...(a)FreeNet.Carleton.CA (David Libert) wrote:
> zuhair (zaljo...(a)gmail.com) writes:

>   Another point.  I did my models of  ZF - regualrity with
> cardinality undefinable.  For the momeent those seem to be
> ok.
>
>   So what is this about seeking a definition of cardinality
> in ZF - regularity?  Do you mean to add some axioms to that?
> Or do you mean really just  ZF - regularity, and you are
> still questioning those models?

I need some time to study these models. And If I understand them, then
I shall
reply in a separate post to address them.

But let me clarify my point of view:

Suppose we add Cardinality symbolized by "| |" as a primitive to the
language of ZF minus Reg., so"| |" would be a primitive one place
function symbol. Let's
name this theory ZF minus Reg.(=,e,| |) to differentiate it from
ZF minus Reg.

And suppose we add the following axiom to the list of axioms of
ZF minus Reg.(=,e,| |).

Axiom of Cardinality:

For all x,y : |x|=|y| <-> Exist f ( f:x-->y , f is bijective )

So now we have the theory ZF minus Reg.+Axiom of Cardinality(=,e,| |).

Now according to your models, then ZF minus Reg.+ Axiom of Cardinality
(=,e,| |). is not equi-interpretable with ZF minus Reg.

What I want to come with is a definition of Cardinality that work in a
model of ZF minus Reg. that is equi-interpretable with
ZF minus Reg.+Axiom of Cardinality(=,e,| |).

So for example I want to come with a "definition of Cardinality" in ZF
minus Reg.
suppose that was, for a specific formula Phi(x):

Card(x) <-> Phi(x)

Then I will add the axiom:

Axiom of Cardinality: For all x Exist y ( y=Card(x) ).

So we'll have ZF minus Reg. + Axiom of Cardinality.

Now what I want is that

ZF minus Reg. + Axiom of Cardinality Equi-interpretable with
ZF minus Reg. + Axiom of Cardinality (e,=,| | ).

Can that be done?

Can we have a defined cardinality that is as general as the primitive
cardinality in
a model of ZF minus Regularity.

I noticed that the primitive concept of Cardinality can even work with
proper classes, something that I can hardly imagine defined
cardinality can achieve?

But for now I am speaking about Cardinality of sets and not of proper
classes.

In nutshell I want the most general definition of cardinality in ZF
minus Regularity one can get.

Zuhair








>
> --
> David Libert          ah...(a)FreeNet.Carleton.CA

 |  Next  |  Last
Pages: 1 2 3 4 5 6
Prev: Fitch's paradox and OWA
Next: Cardinality and Hereditary sets.