Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: PA and Axiom of Choice
Posted:
Jun 25, 2012 9:04 PM
|
|
On Jun 25, 11:47 am, George Greene <gree...@email.unc.edu> wrote:
> On Jun 25, 12:11 am, RussellE <reaste...@gmail.com> wrote:
>
> > PA doesn't know or care about "finite".
>
> We've been here a lot of years. I'm sure I told you this before you
> told me.
Probably.
> > Non-standard models of PA can have sets
> > of natural numbers ZF thinks are infinite.
>
> It isn't really reasonable to talk about what "ZF thinks".
I should have said ZF proves these sets have
a bijection with a proper subset of themselves.
> ZF is the model construction language. It doesn't "think"
> things about the objects. ZF just constructs the objects
> and then THE ORIGINAL theory (PA or whatever) "thinks"about them.
> The fact that PA doesn't know the difference between finite and
> infinite
> means that using these larger (I like to call them "supernatural")
> numbers,
> will, on some level, NOT HELP. The sets encoded by these numbers
> "are" infinite
> but PA is not properly able to appreciate that fact.
Or, ZF is just wrong.
> > If x is an "infinite" non-standard natural
>
> It's not in the literature, but again, I prefer "supernatural" because
> all of these
> non-standard naturals must in fact be greater than all of the standard
> ones.
"Supernatural" works for me.
It makes these numbers sound spooky,
which they are.
> > number and Set(x) is Ay(y<x) then
>
> Oh, SHUT UP.
> If Set(x) is Ay[y<x] then THERE ARE NO SETS
> because THERE IS NO x with the property that all y's are less than it.
> In particular x+1 is not < x.
Set(x) is a function, not a predicate.
I found an interesting paper (pdf) that answers
many of the questions I have been asking.
On interpretations of arithmetic and set theory -
Richard Kaye and Tin Lok Wong
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.2330&rep=rep1&type=pdf
"Folklore Result. The first-order theories Peano arithmetic
and ZF set theory with the axiom of infinity negated are
equivalent, in the sense that each is interpretable in the
other and the interpretations are inverse to each other."
Of course, there are details.
PA is really PA+exp where exp is:
AxEy(y=2^x)
This says exponentiation is a total function.
PA+exp -> ZF+(~Inf)+TC
where ~Inf is the negation of the axiom of infinity
and TC is transitive containment. TC says every
set is a member of some transitive set.
They explain TC is equivalent to every set
has a transitive closure and epsilon induction.
I find it interesting we can have epsilon
induction in a theory with an axiom that
says there are no inductive sets.
This paper answers my question about
"supernatural" ordinals. An example of a
supernatural ordinal would be an ordinal
with an order type like the order type
of the universe of a non-standard ,model of PA.
Actually, such a supernatural order would
have an order type exactly like the order
type of the universe of an infinite model of MA.
I have repeatedly asked what the order type
of a countably infinite model of MA would
look like. I still have never gotten an answer.
I have never seen a description of the
order type of an uncountable model of PA.
I guess this means there are supernatural
ordinals with order types we can't even describe.
At the end of the article they explain that
ZF+(~Inf)+TC |- AoC
This means PA+exp |- AoC.
So, PA does prove the Axiom of Choice
for all sets of natural numbers definable
in PA.
This paper uses the same method for defining
sets I gave originally. Sets are encoded as
sums of powers of 2.
x is a member of m if the xth bit is true
in the binary representation of m.
The cardinality of set m is the number
of true bits in the binary representation of m.
If PA+exp |- ZF+(~Inf)+TC doesn't this mean
PA proves infinite sets don't exist?
Russell
- 2 many 2 count
|
|
|
|
