Cardinality once more
zuhair
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
zuhair
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
Rupert
> 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.
David Libert
zuhair (zalj...@gmail.com) writes:
> On Jan 1, 4:37=A0am, zuhair <zaljo...@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 ah...@FreeNet.Carleton.CA
zuhair
> zuhair (zaljo...@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...@FreeNet.Carleton.CA
zuhair
Agreed. Yes that is correct.
Thanks.
Zuhair
zuhair
Because we must define d(x) to exist for every x, that's the idea, so
Cardinality(x) would also have d(x) as a member so it cannot be empty.
NO Rupert gave an example when this is contradictive, since d(x) would
be a set of ordinals, and thus must be well-founded, and at the same
time we'll have a non well founded set of them with the case of non
Dedekinds sets, so it would be contradictive.
We may resolve this contradiction of I remove the condition " d(x) is
ordinal"
and replace it by another condition, like d(x) is hereditarily
hereditary etc..
this would solve it, but as far as d(x) is ordinal then this would
lead to the contradiction that Rupert referred to.
>
> 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.
Yea, that my be case indeed.
>
> 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.
see above.
nice.
> ...
>
> read more »
zuhair
zuhair
Actually I don't see why d(x) would be non well founded, d(x) is
contradictive
because it is a set of ordinals so it must be well orderable, and at
the same time
it would be NON WELL Orderable, so the conflict is all about "well
orderability" and not about well foundedeness.
> ...
>
> read more »- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -
MoeBlee
> 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,| |).
Okay, so far. You can find this (Tarskian, if I recall) approach (even
whether or not we have regularity) in certain textbooks as a temporary
way of dealing with cardinality without using choice (or even
regularity):
card(x) = card(y) <-> x equinumerous with y
It may be adopted as a temporary axiom (let's call it "Tarski's
axiom") until we add choice to prove a corollary of the numeration
theorem (consider all formulas closed as appropriate):
E!y(y is an ordinal & y equinumerous with x & Az((z ordinal & z
equinumerous with x) -> ~zey))
(i.e, there is a unique y that is the least ordinal equinumerous with
x)
or it may be added as a temporary axiom until we add regularity (if we
didnt' already have regularity) to prove:
E!yAt(tey <-> (t equinumerous with x & Az(z equinumerous with x -> ~
rank(z) e rank(t))))
(i.e. there exists the set of all sets that are equinumerous with x
and are of lowest rank among sets equinumerous with x)
I gather that you pretty much already know that, but I'm including it
for context, along with mentioning, that with choice and regularity
combined, the two approaches above pick out the same set to serve as
card(x).
> 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)
That is not a definition of a function symbol. It is not even a well
formed formula. On the left of the biconditional you have a TERM but
the left of a biconditional must be a FORMULA.
One form for definining a function symbol is:
card(x) = y <-> Phi(x y)
where we have the thereom already proven:
E!y Phi(x y)
In case you don't have that theorem already proven, then (in a theory
with '0' as a (primitive or defined) 0-place function symbol) you can
use "the Fregean method":
card(x) = y <-> ((AxE!y Phi(x y) & Phi(x y)) or (~AxE!y Phi(x y) &
y=0))
So let's assume you've adopted such an approach.
> Then I will add the axiom:
>
> Axiom of Cardinality: For all x Exist y ( y=Card(x) ).
If 'card' (primitive or defined) is now in the language (primitive or
extended by definitions), then the above formula is a theorem of logic
alone anyway; you don't need it as an additional axiom. This has been
mentioned many many times in discusssions on sci.logic that I think
you probably have read.
> 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?
If we correct your formulation, then, if I correctly understand your
intent, your question becomes:
Is there a formula Phi (in the language of set theory extended to
include 'card') such that:
ZF(minus regularity)+"card(x) = y <-> ((AxE!y Phi(x y) & Phi(x y)) or
(~AxE!y Phi(x y) & y=0))"
=
ZF(minus reguarity)+Tarski's axiom ?
MoeBlee
zuhair
Welcome Moe, It has been long time since I've read anything for you.
This matter with Cardinality has been going on for around one month
here.
Let me present my idea in cross manner,
Cardinality is a one place function on sets such that for every set
x , every set y
we have
Card(x)=Card(y) <-> Exist f (f:x-->y, f is bijective)
Lets call this: the *basic requirement for Cardinality*.
Now Cardinality can be *defined* or can be a *primitive* concept.
With defined cardinality here I am referring specifically to a
definition by a formula in first order logic with identity and epsilon
membership as the sole primitives i.e.
in FOL(=,e).
This as you said takes the form
Card(x)=y <-> Phi (x,y)
So lets say that Phi(x y) is a *cardinality defining formula* if card
(x) defined after this formula will satisfy the basic requirement for
Cardinality.
remember Phi(x y) is a formula in FOL(e,=)
Now my question was the following:
Is their a cardinality defining formula Phi(x y) such that
ZF(minus Reg.) + "For all x Exist y ( y=card(x) ) were card(x) <-> Phi
(x y)"
is Equi-interpretable with
ZF(minus Reg.) + Tarski's axiom.
Of course the first theory is in FOL(e,=)
While the second is in FOL(e,=,| |).
Is that possible?
Zuhair
MoeBlee
> Is there a formula Phi (in the language of set theory extended to
> include 'card') such that:
>
> ZF(minus regularity)+"card(x) = y <-> ((AxE!y Phi(x y) & Phi(x y)) or
> (~AxE!y Phi(x y) & y=0))"
> =
> ZF(minus reguarity)+Tarski's axiom ?
Correction: I didn't mean that Phi may have the symbol 'card' in it.
I should have said:
Is there a formula Phi (in the language of set theory) such that:
MoeBlee
> Cardinality is a one place function on sets such that for every set
> x , every set y
> we have
>
> Card(x)=Card(y) <-> Exist f (f:x-->y, f is bijective)
>
> Lets call this: the *basic requirement for Cardinality*.
Yes, as I said, that is a well-known idea, going back at least to
Tarski.
> Now Cardinality can be *defined* or can be a *primitive* concept.
>
> With defined cardinality here I am referring specifically to a
> definition by a formula in first order logic with identity and epsilon
> membership as the sole primitives i.e.
> in FOL(=,e).
>
> This as you said takes the form
>
> Card(x)=y <-> Phi (x,y)
>
> So lets say that Phi(x y) is a *cardinality defining formula* if card
> (x) defined after this formula will satisfy the basic requirement for
> Cardinality.
Yes, I said I'm with you there, still a basic set theoretical path.
> remember Phi(x y) is a formula in FOL(e,=)
Right.
I shouldn't have said 'card' can be in Phi.
So I just corrected my post in this way:
Is there a formula Phi (in the language of set theory) such that:
ZF(minus regularity)+"card(x) = y <-> ((AxE!y Phi(x y) & Phi(x y)) or
(~AxE!y Phi(x y) & y=0))"
=
ZF(minus reguarity)+Tarski's axiom ?
> Now my question was the following:
>
> Is their a cardinality defining formula Phi(x y) such that
>
> ZF(minus Reg.) + "For all x Exist y ( y=card(x) ) were card(x) <-> Phi
> (x y)"
>
> is Equi-interpretable with
>
> ZF(minus Reg.) + Tarski's axiom.
Your formulation is not correct.
(1) You ignored what I reminded you of:
card(x) <-> Phi(x y)
is not well formed.
(2) If I'm not mistaken (I'd welcome someone more expert commenting),
equi-interpretability would be of concern if the two theories have
different languages. But your theories do have the same language.
Whether you consider 'card' as primitive in one language but
"defined" (yours is not in a correct definitional form) and thus added
to another language, they end up both being the same language. So, if
I'm not mistaken, to ask a substantive equi-interpretability question,
you need one theory to have 'card' in its language' and the other
theory not to mention 'card' at all (if that theory is adding 'card'
as DEFINED, then any axiom would not NEED to use the symbol 'card').
Now, please, take it a step at a time.
We know what one theory is. ZF(-regularity)+Tarski's axiom, with
'card' as primitive.
But you must reformulate your definition of 'card' for the other
theory. Then you can also add any axioms you want with 'card' in it
(though, of course, with 'card' DEFINED, those axioms can also be
written withOUT 'card').
Thanks for the welcome back. I hope all is well with you these days.
(I actually need not to post so I can concentrate on other things
right now, but I couldn't resist this time as I saw a basic mistake
you need to correct before you can advance with your question. But now
that I've posted, I'm probably headed back to the same old time-eating
posting routine!)
MoeBlee
MoeBlee
> card(x) <-> Phi(x y)
>
> is not well formed.
Maybe you typoed? Maybe you meant
card(x) = y <-> Phi(x y).
So your other theory is?:
ZF(-regularity)+"AxEy(y = card(x) & Axy(card(x) = y <-> Phi(x y))"
(Some of those quantifiers might be redundant, but I put them in for
clarity.)
But, as I mentioned, the part about Ey y = card(x) doesn't add
anything substantive. So you might as well just make it:
Axy(card(x) = y <-> Phi(x y))
Thus your theory:
ZF(-regularity)+"Axy(card(x) = y <-> Phi(x y))"
MoeBlee
zuhair
> On Jan 2, 6:10 pm, MoeBlee <jazzm...@hotmail.com> wrote:
>
> > card(x) <-> Phi(x y)
>
> > is not well formed.
>
> Maybe you typoed? Maybe you meant
>
> card(x) = y <-> Phi(x y).
Yes, of course. Yea, I myself didn't notice this typo really.
Thanks for the correction.
>
> So your other theory is?:
>
> ZF(-regularity)+"AxEy(y = card(x) & Axy(card(x) = y <-> Phi(x y))"
>
> (Some of those quantifiers might be redundant, but I put them in for
> clarity.)
>
> But, as I mentioned, the part about Ey y = card(x) doesn't add
> anything substantive. So you might as well just make it:
>
> Axy(card(x) = y <-> Phi(x y))
>
> Thus your theory:
>
> ZF(-regularity)+"Axy(card(x) = y <-> Phi(x y))"
were Phi(x y) is a cardinality defining formula of course.
Yes, that is the theory.
>
> MoeBlee
zuhair
Sorry as you said in the other post, this was a typo
I meant
Card(x)=y <-> Phi (x y)
>
> (2) If I'm not mistaken (I'd welcome someone more expert commenting),
> equi-interpretability would be of concern if the two theories have
> different languages. But your theories do have the same language.
> Whether you consider 'card' as primitive in one language but
> "defined" (yours is not in a correct definitional form) and thus added
> to another language, they end up both being the same language. So, if
> I'm not mistaken, to ask a substantive equi-interpretability question,
> you need one theory to have 'card' in its language' and the other
> theory not to mention 'card' at all (if that theory is adding 'card'
> as DEFINED, then any axiom would not NEED to use the symbol 'card').
I need to check that issue.
We have one theory were the language contain an extra primitive sybmol
that is
| | denoting cardinaity i.e. its language has three primitives e,=,|
|.
The other theory contain a defined which as you said we can dispense
with it altogether.
How come these two theories have the same Language, while the first
contain
addition primitive symbol?
They seem to have two different languages, that's why I said Equi-
interpretable instead of saying Equivalent.
Zuhair
zuhair
Yes, but let us be clear here, this theory is in FOL(e,=), I can
dispense with
the symbol card(x) altogether.
>
> MoeBlee
zuhair
Let me repeat the question again without using this symbol in the
defined version.
Can we have a formula Phi(x y) in FOL(=,e) such that
ZF(-regularity) + A x1 x2 y ((Phi(x1 y) & Phi(x2 y)) <-> x1
equinumerous to x2)
is Equi-interpretable with
ZF(-Regularity) + Tarski axiom.
Zuhair
>
>
>
>
>
> > MoeBlee- Hide quoted text -
zuhair
> On Jan 2, 8:44 pm, zuhair <zaljo...@gmail.com> wrote:
>
>
>
>
>
> > On Jan 2, 7:20 pm, MoeBlee <jazzm...@hotmail.com> wrote:
>
> > > On Jan 2, 6:10 pm, MoeBlee <jazzm...@hotmail.com> wrote:
>
> > > > card(x) <-> Phi(x y)
>
> > > > is not well formed.
>
> > > Maybe you typoed? Maybe you meant
>
> > > card(x) = y <-> Phi(x y).
>
> > > So your other theory is?:
>
> > > ZF(-regularity)+"AxEy(y = card(x) & Axy(card(x) = y <-> Phi(x y))"
>
> > > (Some of those quantifiers might be redundant, but I put them in for
> > > clarity.)
>
> > > But, as I mentioned, the part about Ey y = card(x) doesn't add
> > > anything substantive. So you might as well just make it:
>
> > > Axy(card(x) = y <-> Phi(x y))
>
> > > Thus your theory:
>
> > > ZF(-regularity)+"Axy(card(x) = y <-> Phi(x y))"
>
> > Yes, but let us be clear here, this theory is in FOL(e,=), I can
> > dispense with
> > the symbol card(x) altogether.
>
> Let me repeat the question again without using this symbol in the
> defined version.
>
> Can we have a formula Phi(x y) in FOL(=,e) such that
>
> ZF(-regularity) + A x1 x2 y ((Phi(x1 y) & Phi(x2 y)) <-> x1
Even more precisely:
ZF(-Regularity) + "AxE!y Phi(x y) &
Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)"
David Libert
> zuhair (zalj...@gmail.com) writes:
>> On Jan 1, 4:37=A0am, zuhair <zaljo...@gmail.com> wrote:
[Deletion]
Those last 2 references to well-founded were supposed to be
well-orderable.
> 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.
Since posting the above, I think I have found proofs. I haven't checked
all details, but think they are probably ok.
ZF proves for every set x x is rank(x)-well-orderable. Namely
the isomorphic set can be x itself, and the isomorphism can be the
identity.
This proof uses regularity. So over ZF - regularity there remains
the possibility of a set x not alpha-well-orderable for any ordinal
alpha. In fact below I will claim there are models like this.
I give some defintions for ZF and ZF - regularity. So I don't
assume for all x there exists alpha x is alpha-well-orderable.
For an x which is is alpha-well-orderable for some ordinal alpha,
define wo-rank(x) to be the least alpha such that
x is alpha-orderable.
For x not alpha-well-orderable for any alpha (ie a case that
hasn't yet been ruled out for ZF - regularity) define
wo-rank(x) = OR, ie all ordinals, just a formal symbol.
For a model of ZF or ZF - regularity,
define the wo-rank of the model to be the least alpha if it exists
(an ordinal in the model) such that for every set x in the model
exists ordinal beta in the model beta < alpha and
x is beta-well-orderable.
If every set x in a ZF or ZF - regularity model has an ordinal
wo-rank but they are unbounded in ordinals as x varies,
define the wo-rank of the model to be OR.
If a ZF - regilarity model has some set x such that for all
ordinals alpha in the model x is not alpha-well-orderable,
define wo-rank of the model to be OR + 1 . (Just a formal
symbol).
Then my new constructions. Start from a ZFC base model.
We will be constructing symmetric models, using forcing.
For any alpha an ordinal we can construct ZF and
ZF - regularity models with wo-rank exactly alpha.
We can construct ZF and ZF - regularity models with
wo-rank OR.
We can construct ZF - regularity models with wo-rank
OR + 1.
--
David Libert ah...@FreeNet.Carleton.CA
zuhair
> David Libert (ah...@FreeNet.Carleton.CA) writes:
There is no such possibility, that is very clear. Cardinality
according to the new definition is always not empty, because it will
always contain d(x) by definition,
and for every set x we have d(x), that's clear.
However there are lots of reasons why this definition doesn't work,
that's why I already shied away from it.
But as to the question weather cardinalities can be empty according to
this definition, the answer is straightforwards actually.
IT CANNOT.
That's clear.
Zuhair
zuhair
To add to my previous reply that there cannot be an empty cardinality.
The reason why I said that is because of the very basic methodology
adopted here.
I said we ought to define a function d(x) on all sets in ZF
such that all equinumerous sets have the same d(x)
and for any two sets x and y if x is strictly subnumerous to y
then d(x) is strictly subnumerous to d(y), and the same thing applies
with strict supernumerous.
Now my definition of d(x) as an ordinal was erroneous, so I must drop
this property, so what I am saying here if we can define such a
function, then this mean that for every set x there exist d(x)
Now the cardinality of x was defined as the set that has d(x) as a
member and all hereditarily strictly subnumerous to d(x) sets that are
equinumerous to x (I already defined what I meant by hereditarily)
So there is no way whereby these cardinals can be empty because they
will always contain d(x).
Anyhow, as I said this definition doesn't work as a cardinal outside
Choice. So it better be dropped.
Zuhair
MoeBlee
> How come these two theories have the same Language, while the first
> contain
> addition primitive symbol?
One theory is in a language that has 'card' as primitive.
(If you properly form by only definitions), then the other theory is a
theory extended by definitions. The language of the theory extended by
definitions includes 'card' but its source language (the language of
the the theory that was extended by definitions) does not include
'card'.
> They seem to have two different languages, that's why I said Equi-
> interpretable instead of saying Equivalent.
That's fine IF your second theory is TRULY merely an extension by
definition.
By the way, 'equivalent' is actually 'equal' in this sense, since
theories in the same language with all the same theorems are just the
same theory (if we take 'theory' in the sense of 'a set of sentences
closed under entailment').
MoeBlee
MoeBlee
> Yes, but let us be clear here, this theory is in FOL(e,=), I can
> dispense with
> the symbol card(x) altogether.
Whether that is the case depends on your exact reformulation now.
MoeBlee
MoeBlee
> ZF(-Regularity) + "AxE!y Phi(x y) &
> Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)"
>
> is Equi-interpretable with
>
> ZF(-Regularity) + Tarski axiom.
Yes, NOW you've got a precise mathematical question and it is indeed
equi-interpretability that it s appropriate to ask about.
MoeBlee
zuhair
Yes, thanks Moe, for letting me put my question into exact formal
detail.
Why I am asking this question?
Two matters, first David Libert has presented a model of ZF minus
Regularity in which we cannot *define* cardinality.
also T.E.Forster spoke about Gaunett's models, although these models
violate Extesnionality, yet they do prove that we cannot come with a
defined concept of Cardinality in ZF minus Regularity .
This was T.E.Forster's reply:
Further to my last: a modifcation rather than an outright retraction.
Gauntt's model violates extensionality rather than foundation beco's
it
has distinct empty sets (urelemente). What would be needed to answer
Zuhair's question is a Gauntt model with Quine atoms (objects x = {x})
instead. I am 99% certain that Gauntt's construction works with
these
objects instead but we live in an imperfect world and i should check
it -
unless some other list member does it first!
From these replies I had two questions in my mind
(1) is ZF(minus Regularity) + Tarski's axiom
Equi-interpretable with
ZF minus Regularity.
(2) Can we have a formula Phi(x y) in FOL(=,e) such that:
ZF(-Regularity) + "AxE!y Phi(x y) &
Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)"
is Equi-interpretable with
ZF(-Regularity) + Tarski's axiom.
These were the two questions in my mind.
Zuhair
David Libert
> On Jan 3, 5:16=A0pm, MoeBlee <jazzm...@hotmail.com> wrote:
>> On Jan 2, 6:51=A0pm, zuhair <zaljo...@gmail.com> wrote:
>>
>> > ZF(-Regularity) + "AxE!y Phi(x y) &
>> > Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)"
>>
>> > is Equi-interpretable with
>>
>>
>> Yes, NOW you've got a precise mathematical question and it is indeed
>> equi-interpretability that it s appropriate to ask about.
>>
>> MoeBlee
>
> Yes, thanks Moe, for letting me put my question into exact formal
> detail.
>
> Why I am asking this question?
>
> Two matters, first David Libert has presented a model of ZF minus
> Regularity in which we cannot *define* cardinality.
>
> also T.E.Forster spoke about Gaunett's models, although these models
> violate Extesnionality, yet they do prove that we cannot come with a
> defined concept of Cardinality in ZF minus Regularity .
>
> This was T.E.Forster's reply:
>
> Further to my last: a modifcation rather than an outright retraction.
> Gauntt's model violates extensionality rather than foundation beco's
> it
> has distinct empty sets (urelemente). What would be needed to answer
> instead. I am 99% certain that Gauntt's construction works with
> these
> objects instead but we live in an imperfect world and i should check
> it -
> unless some other list member does it first!
As T.E.Forster was indicating, in general you can replace urelements from
a ZFU model by Quine atoms and make a ZF - regularity model. The other
sets of the original ZFU model can retain their old membership, and no
new sets need be added. So this provides lots of transfer between ZFU and
ZF - rerularity.
Similarly, you can replace each urelement from a ZFU model by a new
downward chain of recursive singletons, in similar fashion, changing
nothing else in the model.
Or similarly by higher cardinality than singletons. A downward binary
tree of recursive doubeltons, or any other cardinality from the starting
ZFU model. I discussed a similar point in my first detailed presentation
with cardinality undefinable below. Well that wasn't working from ZFU
to start but same idea of using recursive doubletons instead of recursive
signletons and so on.
> From these replies I had two questions in my mind
>
> (1) is ZF(minus Regularity) + Tarski's axiom
> Equi-interpretable with
> ZF minus Regularity.
>
> (2) Can we have a formula Phi(x y) in FOL(=3D,e) such that:
>
> ZF(-Regularity) + "AxE!y Phi(x y) &
> Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)"
>
> is Equi-interpretable with
>
> ZF(-Regularity) + Tarski's axiom.
>
> These were the two questions in my mind.
>
> Zuhair
I will be discussing these questions below, and realting them to
some of my earlier constructions of models.
Before I begin that, this seems like a good time to collect
references to those previous articles about models, since I will
be referring to some of them. So I will note references then return
to the questions.
I first had five models. General references for these and the main
articles discussing them were collected in
[1] David Libert "Recursive Cardinals"
sci.logic, sci.math Dec 31, 2009
http://groups.google.com/group/sci.logic/msg/c26de32a0acd6dd2
Since then I noted some further models about alpha-well-orderability:
[2] David Libert "Cardinality once more"
sci.logic, sci.math Jan 3, 2010
http://groups.google.com/group/sci.logic/msg/6eca3be8b1e319f9
In [1] I noted a previous article collecting the core refernces about
those first four of those give models ([1] also added some additional
later discussions):
> I have had some other models besides [1].
> These and [1] and background were referenced in
> [2] David Libert " Extensionality and Circular objects"
> sci.logic, sci.math Dec 23, 2009
> http://groups.google.com/group/sci.logic/msg/f3ed79cb6bf9fb5e
In that [1] reference to "[2]" (as opposed to the current [2])
I noted the specfic four models, including two I want to single out
now:
> In
>
>[4] David Libert "Why Define Cardinality?"
> sci.logic, sci.math Dec 10, 2009
> http://groups.google.com/group/sci.logic/msg/0803f45348c83967
>
>I posted a proof outline of a claimed construction of a ZF - regularity
>model in which cardinality is undefinable.
>
> In
>
>[5] David Libert "The General Backround of Cardinality"
> sci.logic Dec 22, 2009
> http://groups.google.com/group/sci.logic/msg/16dc3c6329a74e35
>
>I wrote the [4] proof in more detail, also modifying the definition
>to make the proof go through.
>
> In
>
>[6] David Libert "The General Backround of Cardinality"
> sci.logic Dec 22, 2009
> http://groups.google.com/group/sci.logic/msg/b11fcb00f55fa7ff
>
>I wrote a variant of [5] which also had all H_(x) being sets.
That concludes the previous references.
I return to your questions, which I will repeat:
> From these replies I had two questions in my mind
>
> (1) is ZF(minus Regularity) + Tarski's axiom
> Equi-interpretable with
> ZF minus Regularity.
>
> (2) Can we have a formula Phi(x y) in FOL(=3D,e) such that:
>
> ZF(-Regularity) + "AxE!y Phi(x y) &
> Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)"
>
> is Equi-interpretable with
>
> ZF(-Regularity) + Tarski's axiom.
>
> These were the two questions in my mind.
You reformulated these questions in this theread over several articles in
discussion with Moe Blee. Your original article asked these differently, in
what I interpreted as different questions than these.
I think the original version is probably more illumonating. I will
discuss all of these.
First off, I think the questions as phrased now, as I understand them
have a sort of dodge answer which makes them not so interesting.
I am considering interpretabilty to be as in Tarski. So into the
interpeting theory we interpret the universe of the interpeted theory
as a definable subclass of the universe (or sometimes even a Cartesian
product of the universe if we use a tuple of variables to interpret
one variable.
We interpret the relation and function symbols of the interpreted theory
as definable relatiins and functions on that defined universe, definable
in the interpreting theory.
So the interpreting theory is allowed to make nonstandard interpetations
of the relation and function symbols, and as such can construct models very
different from itself.
Reading your (1) and (2) questions this way, we can make literal answers
to them that are trick answers, not really getting to an illuminating relation
between definable cardinality and your Tarski axiom.
Note that ZF - regularity is a subtheory of ZF ie regularity added back
in.
So if I construct a model of ZF I have constructed a model of ZF - regularity.
In any ZF - regulariyu model, there is the definable class of all well-founded
sets. This is a ZF model. So every ZF - regularity model has a definable inner
submodel of ZF.
So ZF interprets into ZF - regularity.
But ZF can do Scott's trick to define cardinality.
So we can interpret ZF - regularity + Tarski's axiom into ZF - regularity.
(A sort of cheat interpretation, since our intepretation actuially adds
regularity back).
So this trick gets an answer to
> (1) is ZF(minus Regularity) + Tarski's axiom
> Equi-interpretable with
> ZF minus Regularity.
namely adding Tarski's axiom back in. And dropping Tarski's axiom
direction is more trial: just reduce back throwing away the
Card symbol.
So both directions are yes, by a sort of trick answer to
interpret Tarski's axiom in.
As for
> (2) Can we have a formula Phi(x y) in FOL(=3D,e) such that:
>
> ZF(-Regularity) + "AxE!y Phi(x y) &
> Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)"
>
> is Equi-interpretable with
>
> ZF(-Regularity) + Tarski's axiom.
To go from the first (definable cardinality) to Tarski's axiom
just interpret card in Tarski's axiom by that definition.
In general the hard direction should be from Tarski's axiom
to the definable version, other direction.
But there is trick answer to that too. From Tarski's axiom
just cut back same way to well-founded and get back ZF and from
there Scott's trick and use that as the Phi.
We could try to rule out these trivial answers I just gave by
replacing ZF - regularity by ZF - regularity + ~regularity
everywhere.
That would rule out my cheat answers above.
But I can still do something similar to get around that. Cut
back to well-founded sets again and get ZF, then inside there
make a construction of a model with one maximal chain of
recursive singletons only. That is similar to the first model
in [1].
Everything in this model is well-founded over that maximal
chain. So we can still make a growing hierarchy through the
universe like the V_alphas from ZF, except start with the
maxinal chain instead of {}. This is enough to do as Scott's
trick with this hierarchy and define cardinality that way.
So this also gets trivial yes answers to both (1) (2)
even over ZF - regularity + ~regularity.
There would be more complex versions of this than one
maxinal chain of recursive singletons, to get around a
new version of the questions blocking that case.
I think the interesting questions like (1) and (2)
should be asking about closer connections between the
definable cardinality and the axiomatized one.
So I think the interesting version of (1) ands (2)
should ask this when the interpretation is not allowed
to redfine the universe, or = or epsilon.
So to interpret Tarski axiom, we insist on an
interpretation of Card over the original
=, epsilon and the original universe.
And for the other direction in (2), the defined
cardinality should be using the underyling universe
behind Tarski's axiom.
So to repeat (1) and (2) :
> (1) is ZF(minus Regularity) + Tarski's axiom
> Equi-interpretable with
> ZF minus Regularity.
>
> (2) Can we have a formula Phi(x y) in FOL(=3D,e) such that:
>
> ZF(-Regularity) + "AxE!y Phi(x y) &
> Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)"
>
> is Equi-interpretable with
>
> ZF(-Regularity) + Tarski's axiom.
The reworked version would say, can we interpret Tarski's axiom
over those base theories by just an defining Card.
And for the other direction it would say: (for (2))
in the big language with Card and the theory with Tarski's
axiom, can we prove the statement above about Phi for some
Phi from the smaller sublangyuage not mentioning Card.
These are questions about a more direct connection between
defined and axiomatized cardnality.
So I turn to that now.
In the revised (1), to drop Tarski's axiom is trivial.
It is the identity interpretation where every formula translates
to itself.
For the other direction, can we interepret
ZF - regularity + Tarski's axiom into ZF - regularity in this
special form of interpretation, just to interpret Card as a definition,
my [5] & [6] models are a counterexamples.
([5] itself included several variant versions. And [6] was a further
variatiant. The reason to have these alternatives was to have examples
with various additional side properties.)
So that direction the answer is no. ZF - regulairty + Tatrski's
axioms can't interpret in this restiricted sense into ZF - regularity.
Regarding:
> (2) Can we have a formula Phi(x y) in FOL(=3D,e) such that:
>
> ZF(-Regularity) + "AxE!y Phi(x y) &
> Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)"
>
> is Equi-interpretable with
>
> ZF(-Regularity) + Tarski's axiom.
One direction is easy. Given any formula Phi, starting with
theory
> ZF(-Regularity) + "AxE!y Phi(x y) &
> Ax1x2y ((Phi(x1 y) & Phi(x2 y)) <-> x1 equinumerous to x2)"
we can interpret ZF - regularity + Tarski's axiom into that
by interpreting Card by Phi.
(This even if that theory with Phi is inconsistent. For
example, suppose ZF - regularity proves Phi does not
define cardinalitry, ie the negation of the extra axiom
you gave above about Phi. We can still add your axiom
to ZF - rgularity and get an inconsistent theory. This
still interprets ZF - regualrity + Tarski's axiom
by making any definition for Card, and this is indeed
an interpretation since the interpretation of every axiom
is probable in ZF - regulairty + your Phi axiom since
that is inconsistent.)
The hard direction is to go the other way:
Is there is Phi so the Phi theory interprets in the revised
sense to ZF - regularity + Tarski's axiom.
Namely in the revised reading of (2) this is asking if
ZF - regularity + Tarski's axiom actually shows some formula
Phi not mentioning Card defines cardinality.
This is not immediately obvious from any of the previous writing
or models.
If we want to prove no, one way would be to find models where
cardinality is undefinable in = , epsilon.
So far we have models [5] & [6]. But it is not clear how
Tarski's axiom relates to these. (For one thing it is not in
the same language. And it looks dubious to expand the language
and add Tarski's axiom, since the thigns built into the model to
make cardinality undefinable look like they will mess up Tarski's
axiom.) So its not immediately obvious how to get
a counterexample to an implication here.
I think I have found how to modify the [5] and [6] definitions,
to be still similar enough to the original [5] & [6] to still
let me argue cardinality is undfinable just using =, epsilon,
but I can make these exapnded models with Card built into the model
to satisfy Tarski's axiom.
I turn to that now.
Recall [5] and [6] have their definitions over a base model
of ZFC.
I will add the assumption that this base is a GB model,
including global choce. You can get that with Godel's L.
Recall [5] and [6] had proper classes A_n (n in omega
in the base model).
Each A_n had members A_n,alpha, as alpha varied in the
base model pver all ordinals.
Each A_n,alpha had members A_n,alpha,m,l as m,l varied
over omega in the base model. (The first singleton towers model
in [5] took l > 0, the other models of [5] and the [6] model
took all l in omega as A_n,alpha members).
All these models made finite support permutation models based
on simul;taneous permutations on all of n, alpha, m.
My new proposed models will be as before, except don't permute
the alphas.
Also make these GB models, except without regularity and choice.
I will call that theorty GB-.
(GB as normally formulated includes global choice, which is
strictly stronger than makng set many choices at a time as usual
AC from ZFC. So I am leaving this off as well).
So we define the classes of the GB- model to be ther classes
over the iner set model with finite support under the group
action, lifting the group action from sets to classes by
extensionalilty.
By leaving off the alpha permutation, I gave myself back
choice functions in the cosntructed inner model, picking
A_n,0 for each A_n, ie to pick among the alphas.
So the [5] and [6] original models were not able to
make a definition of cardinality over all the A_n,alpha 's.
Now we can do this much by making
C(A_n,alpha) = A_n,0 .
To see how to define Card for all sets of the constructed model,
not just A_n,alpha.
I will define in the base model a class defining an OR length
sequence of sets, which union to the universe. I will argue this
class has empty support, so it becomes a class in the constructed
GB- model.
I will not be doing this definition inside the constructed model.
Instead I work in the base model, the starting ZFC model where we
defined the construction.
This model has access to the indexing of the labelled constructed
sets by the n,alpha,m,l .
Any definition using this indexing has the potetial to define an
object outside the conteructed model.
But that's why I check the support at the end.
So here is the definition. We use global choice in the base GB
model to enumerate the universe in type OR (the ordinals), and
so induce an enumeration of the sets of the constructed inner model.
(We phave already constructed the inner model, I am cpnstructing
a specfic class within in).
Reindex the subsequence that just enumerates the inner model,
to still be over OR.
Suppose this sequence at ordinal alpha enumerated set a.
I now form the set, the orbit of a, under the full action
of ther permutation group. All permutations of n,l.m .
Since I no longer permutate a proper class of alphas,
these each vary over omega, these orbits are each sets and not
proper classes.
(If I tried the corresponding over the original [5] and [6]
some of the corresponding orbits would be proper classes.
That's why I modified the defnition.)
So consider the class sized function, enumerating in type
OR all these orbits.
This class is fixed by any permutation. Any orbit just
has its members moved around inside by any permutation.
So this class is in our constructed GB- model.
So the universe of this GB model is an OR indexed union
of sets. Since every set was originally enumerated, so
gets into the the orbit there.
(The OR listing of orbits will not be 1-1 but that
doesn't matter).
So this is enough to use that class as parameter
and do as Scott's trick on that hierarchy to make a
definition in class parameter of class Card
and satisfying Tarski's axiom.
So make this class interpret Card, and we have
a model of ZF - regularity + Card.
It remains to be seen in this model that no formula
in = , epsilon only can define cardinality.
Here is the big point. I used a small permutation group
not moving the alphas to define this model.
But now that the model is in place, I can consider a bigger
permutation group acting on it.
Go back to the original permutation group from [5] and [6],
including permuting the alphas.
We can still make this act on the atoms of our new model
and so by extensionality lift to the sets and classes.
These new permutatiions, will in general move Card.
But they just move it to another class in the GB- model.
But we are interested in definitions of cardinality
that don't use Card, only = and epsilon.
This bigger group action reosects = and epsilon.
To define our model with Card, I went to a GB-
model, to give me other classes to give me something
to send Card to.
But if the theory with =, epsilon, Card had a defintion
of cardinality only using =, epsilon, then the GB model
would also have such a definition, only using =, epsilon.
The theory under discussion for Tarski's axiom was
ZF - reguilaroity style not GB- style.
It didn't have many proper classes. Instead it just had
one new function symbol that was like a proper class sized
function : Card.
I constructed a model for that by constructing a full GB-
model, and interpreting Card as a proper class in that
GB- model.
But we are interested in the Tarski axiom thery, with
only set quiantification, and Card the only symbol beyond
= epsilon and sets, and we want definitions only using
=, epsilon.
So to relate this to the GB- theory, what this amounts
to is a definition in =, epsilon only and no class parameters.
I will argue there is no definition of cardinality definable
in the GB- model by a formula with only set paraters and
=, epsilon.
By the discussion this shows in the Tarski axiom theory
with =, epsion, Card there is not definition of cardinality
in set parameters usnig only =, epsilon not Card.
I will be using the bigger group action on the GB- model.
That moves Card but that's ok since our definition didn't
use Card.
So for contradiction suppoose C is a cardinality
definition defined in the GB- model by a formula
with set parameters but no class parameters and
=, epsilon but no Card.
Find an n outside the finite unions of the supports
of all parameters in the C defintion. By n ourside
I mean no A_n,alpha,m,l is in and no
f_n,alpha1,alpha2 is in.
(Actuallty I could even drop those from the definition
since we don't permute alpha's any more).
Consider C(A_n,0).
In our constucted GB- model consider TC(A_n,0).
I claim this must contain some member of form
A_n',alpha',m'.l' for some n' in omega also completely
outsude the support of C, and alpha' ordinal,
m', l' in omega.
If not, it has no such members with n' = n, since
n is also outside the support.
The support is finite, so we could find another n'
completely outside of it.
The TC(C(A_n,0)) wouldn't contain anything of form
A_n,alpha,m,l or of form A_n,alpha',m',l'.
So consider the permutation n <-> n' and nothing
else.
These are both outside support C, so it is not moved.
Nothing on TC(C(A_n,0)) is moved, so C(A_n,0)
isn't moved.
So permuting on the equation
C(A_n0) = the C definition applied to A_n,0
and treating LS as constant we get
C(A-n,0) = the C definition applied to A_n',0
So C(A_n,0) = C(A_n',0).
As in [5] I argued members from proper classes
A_n, A_n' for n ~= n' have are not isomorphic.
This depended on the permutations on the n's and is
not affected by the new change droping the alpha
permutations.
So A_n,0 and A_n',0 are not isomporphic,
so C defining cardinality was not supposed to assign
them same value.
So TC(C(A_n,0)) must contain as member some set of form
A_n',alpha',m',l' for n' completely outside support
C.
I don't want the 0 in A_n,0 to match that alpha'.
But if it did I can find some other alpha ~= 0.
Then A_n,0 and A_n,alpha are isomorpjic since the
model coonstuction in [5] made it so.
So C defining cardinality would assign A_n,0 and
A_n,alpha the same.
So I conclude TC(C(A_n,alpha)) has member
A_n',alpha',m',l' , where alpha ~= alpha' one way
or other.
Now inside A_n' we can permute this alpha'.
This permutation is no longer part of the permutation
group defining the inner model, but it still
acts on that model.
n' was completely outside the support of C,
so the C definition is not moved.
As I write this I realize this new model has cross
connections between the A_n 's not in the old
[5] anf [6].
So permute alpha' to alpha'' also out of support
C in any coordinate, ie even for diff n's. Still only
finitlely many to avoid
A_n,alpha only depends on n and alpha, so permute
alpha' <-> alpha'' and leave A_n,alpha fixed.
Also avoid support C.
We can still send alpha' to a proper class of different
alpha'', one at a time with alpha' <-> alpha''.
Apply these in turn to
A_n',alpha' member TC(C(A_n,alpha))
and get a proper class of different A_n'_alpha''
to be members of TC(C(A_n,alpha)).
Contradicting that TC(C(A_n,alpha)) is a set
since C(A_n,alpha) is a set.
So we got a contradiction from assumuing the constructed
GB- model had a definition C of cardinality from
=. epsilon, even using set parameters.
That concludes the proof.
I haven't reread it recently, but from memory this argument
is similar to the permutation argument in [5].
The idea is the same, maybe I used different variable labelling.
So basically, the [5] argument was never maknig heavy use of
support facts about alpha.
Also, [5] was arguing that actuially no set could act on
vertain elements in this fashion.
Now I just arguing no definition can so act.
In this new model there are sets doing it, they just aren't
definable.
[5] and [6] have several variant models. They were adjusted
to have different side properties. The point was these
adjustments did not affect the undeyling permutation argument
as above.
So the same will apply now. Each of those various versions
in [5] and [6] could copy over into this reworking, and so
get special versions in which those extra properties could be
added to the theories under discussion here, as extra axioms.
And with those, there is still the constructiion above
against getting a cardinality definition from the
axiomatic Card in Tarski's axiom.
--
David Libert ah...@FreeNet.Carleton.CA
zuhair
Thanks a lot David. I understand that the answer is no, hmmm,...; the
outstanding question here would be if we can have a maximal definition
of cardinality, informally speaking a definition of cardinality in ZF-
Reg.(=,e) that is the nearest to
the primitive cardinality, can there be such a thing?
Lets say that "D is a Cardinal proper class", to mean that D is a
proper class
having every member as an ordered pair <x,card(x)>
so we have the cardinal proper class of primitive cardinality which is
the same as D above were card is a primitive symbol,
also we can have a cardinal proper class were card is a defined symbol
after some cardinality defining formula phi (in FOL(e,=)).
Can we have a maximal cardinal proper class with card being defined in
FOL(e,=)
what I mean by maximal is supernumerous to any cardinal proper class
having card defined in FOL(e,=).
Is this possible?
Zuhair