[FOM] Micro Set Theory

joeshipman at aol.com joeshipman at aol.com
Fri May 17 12:56:44 EDT 2013

I'm not disagreeing with what you say, but it doesn't really address the question I am asking. 

By the way, V7 has 2^(2^65536) elements, not 2^65536 elements as you stated: the elements of V7 are themselves subsets of the (2^65536)-element set V6, and each one of them requires an infeasibly large amount of information to specify and can code up anything of feasible size that we care about, such as proofs of the Riemann Hypothesis small enough to fit in our physical universe.

What I want to know is rather simple:

(a) would an oracle for V5 would allow us to answer an interesting mathematical question we don't currently know the answer to?

(b) Would an oracle for V6 NOT allow us to answer some interesting mathematical question, if we regard any such question as being "answered" by knowing there is no feasible proof or disproof of it from ZFC + your favorite large cardinal axiom?

To reiterate -- "answer" is not the same as "understand", I am just asking for answers assuming that the oracle is correct. I am looking for a finite object such that to understand this object is comparable to understanding mathematics in general, noting that V7 appears to be such an object, asking if V6 is such an object, and asking if V5 partakes of any of the difficulty of "mathematics in general" or whether it is instead "easy to understand".

-- JS

-----Original Message-----
From: Andrej Bauer <andrej.bauer at andrej.com>
To: Foundations of Mathematics <fom at cs.nyu.edu>
Sent: Fri, May 17, 2013 10:45 am
Subject: Re: [FOM] Micro Set Theory

I would say that size is not the only thing that matters, the structure is important too.

It is important that a formalization respects, or at least does not mutilate, the inherent structure of the thing you're formalizing. For example, it may be cool to represent lists of numbers as a product of powers of prime numbers, but that sort of thing is going to be thoroughly useless in practice. In practice, the formal language must allow direct and abstract expression of the concepts involved.

Which is why the 2^65536 elements of V_7 will be of little help when you try to encode a list of 9 elements.

Suppose that we lived in a world of fantasy where someone gave us an oracle for V_7. We would devise (unnatural) encoding schemes for asking the oracle all sorts of questions, and it would give us answers. Soon there would be just one question we cared about: how does it work? We would take it apart and study its inner mechanism to learn --- about the structure of V_7! Because, to understand how such a magnificent piece of machinery could answer everything there is to know about V_7, it to understand the structure of V_7. Not the size.

With kind regards,


On Tue, May 14, 2013 at 3:53 PM, Joe Shipman <JoeShipman at aol.com> wrote:

If V_0 is the empty set and V_(i+1) is the power set of V_i, then the elements of V_7 have infeasible size and can code objects smaller than 2^65536, so that an oracle for the theory of V_7 would allow answers to any mathematical question we care about (for example "Does the Riemann Hypothesis have a proof from ZF + your favorite large cardinal axiom of length < 10^1000 ?"), thereby rendering mathematicians obsolete.

V_4 is trivially uninteresting; it has only 16 elements so brute force programming will let us answer any question about it involving up to 10 or so quantifiers.

An oracle for V_6 would be very helpful since it would (I think but need to verify) let us solve instances of PSPACE-complete problems of length in the thousands of bits, for example calculating Ramsey numbers, but would it make mathematicians almost as obsolete as an oracle for V_7 would?

Would an oracle for V5 tell us anything interesting at all?

-- JS

Sent from my iPhone
FOM mailing list
FOM at cs.nyu.edu

FOM mailing list
FOM at cs.nyu.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130517/5c8a1eb8/attachment.html>

More information about the FOM mailing list