Examples of non-trivial changes to automata

[Eray Ozkural]

[Excuse me, my last mail was sent due to these wonderful keyboard/mouse shortcuts on chrome browser. I pressed space and it went, sorry about that]

LBA:
http://en.wikipedia.org/wiki/Linear_bounded_automaton

Probabilistic automaton:
http://en.wikipedia.org/wiki/Probabilistic_automaton
(used in AIT)

These are significant/non-trivial from a mathematical point of view (and not a subjective, social or other point of view), because there are mathematical applications of them, they cause interesting/useful theorems. 

In general, extensions to Turing Machines add no power, however, and this is well known in theory of computation, it's something that every CS undergrad knows:

http://www.cs.ucc.ie/~dgb/courses/toc/handout39.pdf
http://web.science.mq.edu.au/~chris/langmach/chap09.pdf

There is no excuse to not know this since we have so many lectures on the net, even if one may have skipped lectures.

Usually, some restriction is discussed (like LBA). You could say, that you allow only one-way moves, etc. to discuss certain constrained scenarios.

You might remember that Schmidhuber also talked about various changes to TMs to talk about extending Kolmogorov complexity to computability in the limit (which is very interesting to think about):

http://www.idsia.ch/~juergen/ijfcs2002/node4.html
But these are quite valid ideas, AFAICT. They have a theoretical use in the paper. I do not object to such.

On the other hand, It's well known (has always been well known) that I/O can be simply represented by multiple tapes, and those are trivially/easily/without-significant-effort reducible to original TM as above links show. For instance, I suppose you can imagine that each tape can be virtualized by interleaving their cells. Then, you can simply state that one of the tapes is an input stream, and its ith cell is the result of the ith input from a serial device like keyboard. Or you can just state anything you'd like, since you can add any kind of device to a computer, it is easy to interface any of those devices with a TM model. For instance, just because robotic devices (like a robot arm) can be added to a computer, we do not go out of our way and try to include now robotic hardware specifications and physical equations in automata. Instead, we assume that it can interface with the device by writing and reading to memory, which is how it is actually done in a lot of computer architectures. The details of I/O devices are merely that: details. 

Since we have mathematicians here, they might also appreciate that monadic I/O is a mathematically interesting way to model I/O in a pure functional PL like Haskell/Pure.  Which is, indeed, a significant technique, because you do not need to define clumsy commands like READ and PRINT. That is mathematically significant, for instance. There is serious clarity gained by not having to specify any non-functional behavior.  
http://en.wikipedia.org/wiki/Monad_(functional_programming)#I.2FO

I am hoping that this post clarifies what I mean by mathematically significant. 

For instance, in his paper on Optimum Sequential Search, Solomonoff refers to a KUSP machine that stores programs. He is just trying to make a simple idea precise in a line or two, since we already know from UTM's that any program can be encoded, so it's rather straightforward to design a universal computer that can store procedures (although database researchers can make a big deal out of that). In reference to that paper, I defined and used it in just one place (although I could find no refs about it), but it is not a big issue that requires us to write volumes on the subject, that is what I mean by spin. If it's something obvious (I couldn't find any other word instead of this, sorry), you just write in the passing a line or two about it, and you are done.

Regards,

--
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
 

[Tom Everitt]

For the joy of a good debate, I'm gonna argue a bit :)

On Sun, Jan 15, 2012 at 12:49 AM, Eray Ozkural <exama...@gmail.com> wrote:

On the other hand, It's well known (has always been well known) that I/O can be simply represented by multiple tapes, and those are trivially/easily/without-significant-effort reducible to original TM as above links show. For instance, I suppose you can imagine that each tape can be virtualized by interleaving their cells. Then, you can simply state that one of the tapes is an input stream, and its ith cell is the result of the ith input from a serial device like keyboard. Or you can just state anything you'd like, since you can add any kind of device to a computer, it is easy to interface any of those devices with a TM model. For instance, just because robotic devices (like a robot arm) can be added to a computer, we do not go out of our way and try to include now robotic hardware specifications and physical equations in automata. Instead, we assume that it can interface with the device by writing and reading to memory, which is how it is actually done in a lot of computer architectures. The details of I/O devices are merely that: details. 

I agree that the Turing machine captures the idea of computation quite well. But as it was formalized, it takes an input, computes, and returns an output by stopping. And in many cases, as is noted in the paper, this isn't a good model - we need interaction. It may be "easy" to see how the TM-formalization can be extended to handle that, but it's not trivial. For example:

- In a PTM the persistent tape is not visible, which is an important point when it comes to equivalence between PTMs. Two PTMs are considered equivalent when they have the same input-output-behavior, regardless of their inner tape states. This is indeed the intuitive definition of equivalence between interactive systems, and it cannot trivially be achieved by interleaving tapes of a TM (which is mentioned in the article).

Other differences, such as the inconvenience of describing a data structure in terms in an ordinary TM, I can have some understanding for disregarding as "trivial".

But, all in all, I don't quite see the harm in someone doing the work of formalizing something we vaguely allude to all the time. It will just make it more convenient the next time we want to use the idea of a PTM. Instead of needing to think of a few sentences justifying its obviousness (it can be quite tedious to come up with something neither be too long nor too unconvincing), we can just refer to the formalization. Also, it has the benefit that people that haven't studied the theory of computation enough to see that its "obvious" can easily buy the point.

In fact, even if you have studied the theory of computation, you may still need to put hours into convincing yourself that nothing crazy happens. After all, it's not uncommon that what seems like a trivial modification of a definition has surprising effects that can be very easy to overlook.


I also saw in another thread that you criticized Goldin and Copeland for using the idea of an infinite number of states. In Goldin's case she definitely doesn't violate the idea of computation - it is just that the internal tape, the memory, can have infinitely (countably) many states, and thus also the PTM. A regular TM also has an infinite number of states if you include "the state of the tape" in the state.

Also, I haven't read Copeland, but even if he thinks of uncountably infinite number of states (like general STS), I have to defend him on the basis that generalizations of a theory often leads to useful insights, even if the generalization has nothing to do with "the real world". Just consider abstract algebra: it may seem to have little to do with the "reality of numbers", but making it more abstract made patterns come clear, which had substantial implications for number theory.


Cheers,

Tom

[Eray Ozkural]

On Tue, Jan 17, 2012 at 12:28 PM, Tom Everitt <tom4e...@gmail.com> wrote:

Also, I haven't read Copeland, but even if he thinks of uncountably infinite number of states (like general STS), I have to defend him on the basis that generalizations of a theory often leads to useful insights, even if the generalization has nothing to do with "the real world". Just consider abstract algebra: it may seem to have little to do with the "reality of numbers", but making it more abstract made patterns come clear, which had substantial implications for number theory.

Well, I'm a constructivist, in particular I subscribe to Markov's Recursive Constructivism, that's why I don't view even real numbers as proper mathematics.

Abstract algebra is very different. It is useful and acceptable for a constructivist I think.

Regards,

 

[Laurent]

On Wed, Jan 18, 2012 at 15:17, Eray Ozkural <exama...@gmail.com> wrote:

On Tue, Jan 17, 2012 at 12:28 PM, Tom Everitt <tom4e...@gmail.com> wrote:

Also, I haven't read Copeland, but even if he thinks of uncountably infinite number of states (like general STS), I have to defend him on the basis that generalizations of a theory often leads to useful insights, even if the generalization has nothing to do with "the real world". Just consider abstract algebra: it may seem to have little to do with the "reality of numbers", but making it more abstract made patterns come clear, which had substantial implications for number theory.

Well, I'm a constructivist, in particular I subscribe to Markov's Recursive Constructivism, that's why I don't view even real numbers as proper mathematics.

Genuine question:

Do you mean "all real numbers"? Since some of them at least are estimable, like Pi and sqrt(2).

Or do you mean something stronger like: the real number Pi as an infinite digit number does not exist, only approximations of it exist? (though you could still say that we can define it entirely (well-defined number?) by a finite program).

Also, a related question for you Eray (also genuine):

Let's say that someone builds some math tools around some non-semi-computable thing. As is, there is nothing we might be able to do with all that in the real world and we could just say it's merely intellectual stimulation and has no "reality", or no significance.

But what if some day we find a sort of "kernel trick", and analogously to complex numbers (which reality was very discussed at the time they were "invented"), where we find a very nice way to solve some computable problems, by projecting normal computations into the incomputable realm, do some math there, and then projecting the result back to computable world to get the answer; As a constructivist, would it be something that you would object to?

Laurent

[Eray Ozkural]

On Wed, Jan 18, 2012 at 4:49 PM, Laurent <laurent...@gmail.com> wrote:

On Wed, Jan 18, 2012 at 15:17, Eray Ozkural <exama...@gmail.com> wrote:

On Tue, Jan 17, 2012 at 12:28 PM, Tom Everitt <tom4e...@gmail.com> wrote:

Also, I haven't read Copeland, but even if he thinks of uncountably infinite number of states (like general STS), I have to defend him on the basis that generalizations of a theory often leads to useful insights, even if the generalization has nothing to do with "the real world". Just consider abstract algebra: it may seem to have little to do with the "reality of numbers", but making it more abstract made patterns come clear, which had substantial implications for number theory.

Well, I'm a constructivist, in particular I subscribe to Markov's Recursive Constructivism, that's why I don't view even real numbers as proper mathematics.

Genuine question:

Do you mean "all real numbers"? Since some of them at least are estimable, like Pi and sqrt(2).

I mean the set R.

 

Or do you mean something stronger like: the real number Pi as an infinite digit number does not exist, only approximations of it exist? (though you could still say that we can define it entirely (well-defined number?) by a finite program).

I suppose you know this concept, this is what constructivists developed as a replacement for R, originally Turing devised it, of course:

http://en.wikipedia.org/wiki/Computable_number

Weihrauch wrote a book on computable analysis, so all analysis can be done with it. There is nothing important in the rest of R, which is entirely composed of (imaginary) random reals. 

Furthermore, computable analysis actually has some additional very good properties....

http://www.fernuni-hagen.de/weihrauch/

I suggest you read his book if you are truly interested, I read a good portion of it, wonderful work. Weihrauch is a leading constructivist of our age. But of course, people who make the truly important intellectual contributions are never known.

Pi is a computable real, for instance. (Obviously so?)

 

Also, a related question for you Eray (also genuine):

Let's say that someone builds some math tools around some non-semi-computable thing. As is, there is nothing we might be able to do with all that in the real world and we could just say it's merely intellectual stimulation and has no "reality", or no significance.

But what if some day we find a sort of "kernel trick", and analogously to complex numbers (which reality was very discussed at the time they were "invented"), where we find a very nice way to solve some computable problems, by projecting normal computations into the incomputable realm, do some math there, and then projecting the result back to computable world to get the answer; As a constructivist, would it be something that you would object to?

Do you remember the Lowenheim-Skolem theorem?

 http://mathworld.wolfram.com/Loewenheim-SkolemTheorem.html

Wikipedia page is blacked out today.

So I have good reason to think the other way around, those uncountable domains are superfluous they can always be represented with countable domains.

The reason is actually very simple, without even doing formal metamathematics or model theory.

How exactly do you propose to "do math in the incomputable realm"? If you consider this seriously, you will perhaps see that all of your brain operations can, at most, be computable, and what you are doing is, ultimately manipulating mathematical symbols, physically in your head or on paper. So, it always, and necessarily so, collapses to computation, whether you realize it or not. Otherwise, it is not mathematics. And this is the best understanding of constructivism: to construct any mathematical idea in your head, you are performing computations.

Naturally, a scientifically minded person thinks like this, mathematics is just a language and method of reasoning, it is not referring to things that don't exist. It is only by virtue of computation that mathematics can be performed.

Now, I am naturally surprised. If Markov realized this fact in 60's, and Turing in 50's, surely others would have understood it by now. But they have not, why?

Even Godel understood it, and he had to assume that the brain was more than a finite mechanism despite all appearances to support his superstitious views about mathematics. Which is, of course, assuming that the brain is a magical device, or that it contains an extra, magical soul. All of which are scientifically invalid ideas.

The current batch of Platonists are unfortunately very backwards minded, and they will simply assert such foolish philosophical positions and publish insane articles on journals about this. For instance, the clueless pseudo philosophers babbling about it:

http://www.mv.helsinki.fi/home/praatika/chaitinJPL.pdf

The above is a sure test of whether you understand AIT or not. If one agrees with Panu Raatikainen, it does mean that one does not understand algorithmic information theory in a fundamental way (merely understanding the correctness of proofs is not sufficient). Since it is part of the test, I will not explain why, but you can search google groups archives where I grinded his poor philosophy down to mere nothingness (invalidating the test). You can also take a look at his other ignorant papers on the subject. The sad part is he has ably made a career out of such falsehood. And now he talks of reductive physicalism, God knows what perversion he has made out of physicalism. :( And you wish me to not call these people incompetent, they are very competent in making a career out of nothing, I grant that.

Please understand my reluctance to discuss these matters. It is impossible to discuss philosophy of mathematics intelligibly nowadays, because mathematicians and philosophers are not what they used to be, they are a pale reflection of the older academics that made the important discoveries. I do not know if I should pity or despise the Platonists on Foundations of Mathematics list. They do not know what they talk of. Not even in the slightest, except for very few participants that I could detect there. I have written a mail explaining the origin of mathematics from a computationalist perspective, and they have censored my mail numerous times. Imagine what would happen if I sent a paper to the journals they are "guarding" with their superstition. Allow me to protest them: old fools, you have no idea!

Regards,

 

[Laurent]

Thanks Eray, that was a very good, argumented and clear answer.

I'd forgotten about the Lowenheim-Skolem theorem, thanks for the reminder. And anyway, as you say, no one should forget that our brain is merely a computation device, so that there is nothing we can do or prove that a computer could not.

Laurent

--
Before posting, please read this: https://groups.google.com/forum/#!topic/magic-list/_nC7PGmCAE4
To post to this group, send email to magic...@googlegroups.com
To unsubscribe from this group, send email to
magic-list+...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/magic-list?hl=en?hl=en

[Eray Ozkural]

Thanks Laurent. I hope you liked the train of thought there.

It is also worth remembering that, Turing's model of a computer modeled a human computer working with pen and paper, but it apparently also applies to a mathematician working on a mathematical proof. Otherwise, Turing would *not* have written of computable numbers. (What would the significance be?)

That is why it is important to understand that in his model, the number of states is finite (the brain, the basic mechanism), and that the tape (supply of paper, memory) is unlimited, but only *potentially* infinite. At any time, it *is* finite. It is not, as Tom seems to think (?), actually, countably infinite. That's a misunderstanding of the kind of infinity employed in the definition.

And what is the consequence of that definition: that the Instantaneous Description (ID) of a TM is at all times *finite*. That is all that matters, actually. And ID always corresponds to a rigid physical state of the computer. Which should be always finite. And each ID must follow mechanically from the previous.

A computer is *always* a finite mechanism. If something is not a finite mechanism, it is *not* a computer.

Does Tom Everitt know about this, I wonder, or was he ignoring theory on purpose for the "joy of argument"? What is the point of making the set of states infinite, if that will corrupt the most important property of TM ID's? Perhaps he will now contrive an answer to that, which has nothing to do with the variant I criticized out of his willingness to argue for the sake of argument (saying that if we take the tape to be potentially infinite then we could add it to memory, etc., that doesn't make sense, and isn't an answer to the criticism, let me say that pre-emptively). Are we going to discuss this at the level of Chalmers, handwaving about infinite state Turing Machines as if he knows a thing?

http://consc.net/notes/analog.html

I prefer not to! Purportedly, we should have at least an undergraduate level understanding of theory of computation.

Where are these infinite state computers? *How* do they work? Theory of computation is *always* about real, physical computers, in *idealized* fashion. It is not about physically *impossible* computers, and I think that such will never really advance our understanding of computation. If anything, it will *obfuscate* it. (Because it is metaphysics, not science)

There is another reason why foundational thinking is so important. Which is it allows us to examine and criticize our very basic assumptions.

Best,

On Wed, Jan 18, 2012 at 6:03 PM, Laurent <laurent...@gmail.com> wrote:

Thanks Eray, that was a very good, argumented and clear answer.

I'd forgotten about the Lowenheim-Skolem theorem, thanks for the reminder. And anyway, as you say, no one should forget that our brain is merely a computation device, so that there is nothing we can do or prove that a computer could not.

Laurent

 

[Laurent]

On Wed, Jan 18, 2012 at 17:39, Eray Ozkural <exama...@gmail.com> wrote:

Thanks Laurent. I hope you liked the train of thought there.

I did.

 

It is also worth remembering that, Turing's model of a computer modeled a human computer working with pen and paper, but it apparently also applies to a mathematician working on a mathematical proof. Otherwise, Turing would *not* have written of computable numbers. (What would the significance be?)

That is why it is important to understand that in his model, the number of states is finite (the brain, the basic mechanism), and that the tape (supply of paper, memory) is unlimited, but only *potentially* infinite. At any time, it *is* finite. It is not, as Tom seems to think (?), actually, countably infinite. That's a misunderstanding of the kind of infinity employed in the definition.

And what is the consequence of that definition: that the Instantaneous Description (ID) of a TM is at all times *finite*. That is all that matters, actually. And ID always corresponds to a rigid physical state of the computer. Which should be always finite. And each ID must follow mechanically from the previous.

A computer is *always* a finite mechanism. If something is not a finite mechanism, it is *not* a computer.

With all the above, I completely agree with you Eray. That's why I prefer to refer to "unbounded" tapes, rather to infinite tapes, just like for any resource for that matter. Unbounded means there is no upper bound, and you can have more upon request, but you will never have more than a finite number.

  

Where are these infinite state computers? *How* do they work? Theory of computation is *always* about real, physical computers, in *idealized* fashion. It is not about physically *impossible* computers, and I think that such will never really advance our understanding of computation. If anything, it will *obfuscate* it. (Because it is metaphysics, not science)

I understand your point, but I differ slightly: I'm only human, and there is no way for me to know anything with absolute certainty. So what if someday we happen to find a "magical" device that allows us to play with infinite numbers and hyper-computation, even though today it seems *highly* improbable that we will ever find such a thing (thus the current relevance is close to zero)? I allow for such a possibility, just in case, but I find it quite unreasonable given today's knowledge. That would be as magical as smartphones would have been 200 years ago (or closer). And if something like that ever happens, I really don't want to keep this door shut.

Though, I insist, being reasonable, I consider such things only with a very low probability (e.g., lower than an 3rd type encounter during my life time).

Laurent

[Abram Demski]

Eray,

Being a somewhat silly person (perhaps), I would like to provide a model of mathematical reasoning which is acceptable to constructivists yet captures classical reasoning.

(Perhaps I will buy the Klaus book...)

One important point which Hartry Field makes well in his book Saving Truth from Paradox is that it's more important to think about what a logical theory looks like "from the inside" than "from the outside". Looking at a theory from the outside means hanging a semantics on its terms in the Tarskian way. Looking at it from the inside means asking what it says; perhaps most importantly, what it says about itself.

Skolem pointed out that Zarmelo's set theory, and any theory really, can be given a countable semantics in this way. This seems to say that there is no way to really refer to uncountable structures. However, from the inside, Zarmelo's theory really does prove that there are uncountable sets.

The reason we should focus on what the theory looks like from the inside is that if we really propose to use that theory (if we claim it could provide a foundation for mathematics or, even more, if we claim it could be a foundation for human thought) then the inside is the view we'd be using. The outside view (as Tarski showed) always requires some *other* logic to formalize. We might accept the inside logic while being very skeptical of the outside logic... in fact, this seems to be required of us.

The same problem faces constructivist foundations, though the possible responses are a bit different: it's equally impossible for constructivists to specify the semantics which they accept as meaningful, without using language beyond that specification. However, perhaps it is more plausible for a constructivist to say that an incomplete semantics is OK.

This is a pragmatist view: it says to focus on the actual differences for inference, letting semantics be secondary. It is not the attitude I am used to: I usually want to know the semantics before determining the correct inferences.

Note, I am not claiming that ZFC is "correct" when it claims that uncountable sets exist. Rather, I am claiming that uncountability is a legitimate inference structure (a conceptual object, ie, a computation) which we should be able to capture.

In particular, I'm interested in treating the continuum (and any 2nd-order quantification, really) as a kind of "unbounded" specification... we know a bunch of sets that *are* in it (such as computable reals), but we also respect the rule that any new predicate we can form would automatically go into the set. So, diagonalization proves that the set is uncountable in the sense that *if* we could enumerate the members of the set, *then* we could form some new predicate which would get added to the set, breaking the enumeration.

One might argue that this only proves *we* cannot enumerate the set, because of self-reference problems; some outside being could apply Skolem's result to enumerate all the sets we would eventually add. But, what is that supposed to prove? After all, by a similar argument we could show that the set only contained a finite number of elements: we'll only ever enumerate a finite number, so the set is arguably no different from one which only contained those instances. But, this is a wrong argument. The structure of inference around the set doesn't match that description, and that's what matters. Imposing an external semantics like that makes no difference for how inference proceeds.

From this perspective, uncountability seems to be a pragmatically explainable concept: it just means that we allow a set to be expanded in a particular way (related to diagonalization). Or, more simply, it's the statement that there can be no one-to-one mapping to the natural numbers...

--Abram

--
Before posting, please read this: https://groups.google.com/forum/#!topic/magic-list/_nC7PGmCAE4
To post to this group, send email to magic...@googlegroups.com
To unsubscribe from this group, send email to
magic-list+...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/magic-list?hl=en?hl=en

--
Abram Demski
http://lo-tho.blogspot.com/

[Eray Ozkural]

Hi there,

On Tue, Jan 24, 2012 at 1:57 AM, Abram Demski <abram...@gmail.com> wrote:

Eray,

Being a somewhat silly person (perhaps), I would like to provide a model of mathematical reasoning which is acceptable to constructivists yet captures classical reasoning.

You are not a silly person at all, the members on this list seem to be extraordinarily skilled people, and what's even more important than great skill is the right area of interest!

Actually, I think mathematicians pay a good deal of attention to constructivism, as arguments invalid in constructivist mathematics would be naturally weaker.

(Perhaps I will buy the Klaus book...)

I strongly recommend it, and I think there should be a pdf of it somewhere, I believe I had downloaded it from his web page.

People didn't think that analysis could be carried that far in a constructivist setting, so I think it's actually very important. There are also some fairly interesting theorems in it, IIRC, he was showing that there were no discontinuous computable real functions... (again just stating from fallible memory!)

 

One important point which Hartry Field makes well in his book Saving Truth from Paradox is that it's more important to think about what a logical theory looks like "from the inside" than "from the outside". Looking at a theory from the outside means hanging a semantics on its terms in the Tarskian way. Looking at it from the inside means asking what it says; perhaps most importantly, what it says about itself.

That's right, but you'll always be limited by incompleteness in that view (?).

 

Skolem pointed out that Zarmelo's set theory, and any theory really, can be given a countable semantics in this way. This seems to say that there is no way to really refer to uncountable structures. However, from the inside, Zarmelo's theory really does prove that there are uncountable sets.

I know the first theorem, but I don't know what exactly you mean by the latter, care to explain a bit?

 

The reason we should focus on what the theory looks like from the inside is that if we really propose to use that theory (if we claim it could provide a foundation for mathematics or, even more, if we claim it could be a foundation for human thought) then the inside is the view we'd be using. The outside view (as Tarski showed) always requires some *other* logic to formalize. We might accept the inside logic while being very skeptical of the outside logic... in fact, this seems to be required of us.

That's right, but it's also impossible to define truth without correspondence? I mean, in classical semantics, you always have these theories that give an interpretation to logic. In the case of being a "foundation for human thought", what you say makes an awful lot of sense, of course, we have to make sure that theory does not have any unreasonable limitations to thinking.

 

The same problem faces constructivist foundations, though the possible responses are a bit different: it's equally impossible for constructivists to specify the semantics which they accept as meaningful, without using language beyond that specification. However, perhaps it is more plausible for a constructivist to say that an incomplete semantics is OK.

I don't understand what you mean by the latter ("incomplete semantics is OK").

 

This is a pragmatist view: it says to focus on the actual differences for inference, letting semantics be secondary. It is not the attitude I am used to: I usually want to know the semantics before determining the correct inferences.

Ok, I wanted to say that, surely you are aware of the formalization of theory in Godel, i.e. formal axiomatic theory, so that's just a non-terminating program.

The formal point of view forces us to be objective, I think. And I don't think you can manage foundations without very rigorous formalization so we agree. In fact, foundational work really started when we could formalize bits of mathematics itself, right?

Note, I am not claiming that ZFC is "correct" when it claims that uncountable sets exist. Rather, I am claiming that uncountability is a legitimate inference structure (a conceptual object, ie, a computation) which we should be able to capture.

Ok.

What happens is, intuitionists reject law of the excluded middle (LEM).

However, to define uncountable sets, you don't need LEM. It depends crucially (also the set R, naturally) on the axiom of infinity.

So, I guess it is about accepting or rejecting axiom of infinity.

I personally reject axiom of infinity, because it causes several semantic paradoxes. You'd say that's a view from outside I suppose? But it's actually from my subjective point of view. I'm not looking at mathematics from inside, I'm trying to follow inferences, and they result in paradoxes.

In particular, I'm interested in treating the continuum (and any 2nd-order quantification, really) as a kind of "unbounded" specification... we know a bunch of sets that *are* in it (such as computable reals), but we also respect the rule that any new predicate we can form would automatically go into the set. So, diagonalization proves that the set is uncountable in the sense that *if* we could enumerate the members of the set, *then* we could form some new predicate which would get added to the set, breaking the enumeration.

It's a bit more complex than that, I think,  Cantor's theorem crucially depends on the axiom of infinity, you can't prove it with counting alone.

 http://en.wikipedia.org/wiki/Controversy_over_Cantor's_theory#Objection_to_the_axiom_of_infinity

Specifically, Cantor's "assumption" is a metaphysical one, not a logical one. He assumes that infinities can be completed, many people do not agree such. I don't agree as a constructivist, because I can't complete infinity in my mind. That's actually what constructivism really means, but with the several variants of constructivism, one may think this is not essential (you might say that just intuitionistic logic is enough).

One might argue that this only proves *we* cannot enumerate the set, because of self-reference problems; some outside being could apply Skolem's result to enumerate all the sets we would eventually add. But, what is that supposed to prove? After all, by a similar argument we could show that the set only contained a finite number of elements: we'll only ever enumerate a finite number, so the set is arguably no different from one which only contained those instances. But, this is a wrong argument. The structure of inference around the set doesn't match that description, and that's what matters. Imposing an external semantics like that makes no difference for how inference proceeds.

From this perspective, uncountability seems to be a pragmatically explainable concept: it just means that we allow a set to be expanded in a particular way (related to diagonalization). Or, more simply, it's the statement that there can be no one-to-one mapping to the natural numbers...

It actually really only means that actual infinity has been accepted. It's a rather strong assumption, compared to other axioms in ZF or PA that we can *verify* logically, i.e. from the inside.

In fact, I will now claim that the inside view that you mention amounts to constructivism (of a good kind), and you should reject axiom of infinity if you subscribe to that view.

The problem with the axiom of infinity is that, it does require external semantics, in this case, a metaphysical world-view that alludes to the *existence* of *every* kind of actual infinity (otherwise, you wouldn't think that Hilbert space would exist).

Now, otherwise, if we viewed actual infinity as *definability* it fails that criterion, you can't really define it, it's just a symbol. Thus, as my bright colleague Bhupinder Singh Anand rightly complained elsewhere, it's the *abstraction of infinity* that is the crux of the problem. (Although I suspect nobody really understood what he said)

Otherwise, Z suffers from no such problem, to define Z we need not abstract infinity. 

So, although I was barred from presenting my theory of mathematics at the FOM list, we were still allowed to talk about constructivism, as long as we did not threaten to destroy Platonism!

Cheers,

 

[Eray Ozkural]

On Wed, Jan 25, 2012 at 9:52 PM, Eray Ozkural <exama...@gmail.com> wrote:

I personally reject axiom of infinity, because it causes several semantic paradoxes. You'd say that's a view from outside I suppose? But it's actually from my subjective point of view. I'm not looking at mathematics from inside, I'm trying to follow inferences, and they result in paradoxes.

Sorry for the stupid mistake here. I mean to say, I'm looking at mathematics from the inside, but when I follow those inferences, I arrive at several semantic paradoxes! Platonists keep telling us that mathematics is *supposed* to be counter-intuitive, by which they mean that "their intuition is better than constructivists", but with their permission we disagree. At least some constructivists, because there are constructivists who accept infinity. And then, you end up with all sorts of nonsense, for instance, the paradoxes in set theory, and if you use axiom of choice, you get:
http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox

However, there is also the benefit of constructivism in that you don't really have to subscribe to an axiom. Like in the case of Euclidian and Non-Euclidian geometry you can use both, you don't have to choose one. I think the formal minded mathematician (not necessarily a Formalist) would simply pay attention to his basic assumptions. It would be important if he is assuming classical logic or intuitionistic logic, etc.

In the case of set theory, an interesting case with regards to that is, thanks to Ben Goertzel for making me notice, non well-founded set theories:

http://en.wikipedia.org/wiki/Non-well-founded_set_theory

That's extremely interesting, and it provides the kind of departure from set theory that Non-Euclidian geometry provides from classical geometry. Now, what do you think about these axioms?

1) foundation

2) infinity

3) choice

Which do you regard essential for a "foundation of human thought"? I had considered it before, so I have a ready answer: none of them are required.

Best,

  

[Abram Demski]

Eray,

Thanks for the reply, some of these observations are quite helpful to me.

If you asked me directly what working on foundations "from the inside" is supposed to look like, I would not be able togive a full answer. I can only say that at first, I found Fields insistence on this viewpoint to be superficial nitpicking. After a while of reading, I realized that it was much more than that; it is essential, and it is something which everyone else seems to have missed. Still, I don't feel I've grasped the full implications.

The main point here is that something can behave like the concept R while having an external semantics which is very different. (It is noteworthy that Field does not reject the practice of giving a (classical) semantics; he finds it useful, so long as it is "not taken too seriously" in some respects.) So, one thing I am generally interested in is a system which defines "sets" (or "classes") as being just predicates (by which I mean, sentences with blanks to fill in) but with extensionality enforced (so that our notion of "set equality" views two predicates to be equal when they mutually imply one another-- going beyond literal predicate equality, which would be syntactic). In other words, a set is given by a description, but ignoring re-wording.

It is with this kind of thing in mind that I talk about trying to re-create the behavior of uncountable sets like R.

So, I am already:

-- Rejecting the foundation axiom (in particular, this sort of system will *usually* have a set of all sets)

-- Accepting some kind of axiom of infinity (in particular, being able to define the set of finite numbers is one of my target requirements)

However, I will think about it. :)

In any case, I'll try and compose a more thought-out reply to the earlier email.

--Abram

--
Before posting, please read this: https://groups.google.com/forum/#!topic/magic-list/_nC7PGmCAE4
To post to this group, send email to magic...@googlegroups.com
To unsubscribe from this group, send email to
magic-list+...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/magic-list?hl=en?hl=en

[Eray Ozkural]

A quick remark:

If you accept the axiom of infinity, and reject foundation, I think there should already be some papers on that. I would like to learn more about that subject, as well.

And secondly, why do you need the axiom of infinity to define the set of finite numbers? (Maybe I didn't quite understand what you meant, I might be missing a point). I think it is really needed for certain "large" sets.

The problematic thing about set theory for me is that the concept of cardinality, to me, provides little ability of comparing infinite sets. I tried to develop my own understanding of the "size" of infinite sets, for that reason, if you know any pointers about such work as alternative to cardinality / ordinal numbers, I would be interested.

IOW, how do you reason about the size of such sets (without foundation and choice axioms)? I suppose there is still a lot to learn about set theory for me. Just when I thought I knew all the variants. I don't really think classes were a good solution, so I am eager to consider the rejection of axiom of foundation. As Ben Goertzel explains, it also makes a lot of sense from a representation point of view (you can construct these self-referencing graphs, wonderful idea.). There was a good paper summarizing all the different set theories, but I cannot remember its title. In any case, it would be nice if we found such a survey paper and referenced it here for all the other members who might be thinking we are terribly deluded at this point.

http://mathworld.wolfram.com/CardinalNumber.html

Best,

http://myspace.com/arizanesil http://myspace.com/malfunct

[Abram Demski]

Eray,

And secondly, why do you need the axiom of infinity to define the set of finite numbers? (Maybe I didn't quite understand what you meant, I might be missing a point). I think it is really needed for certain "large" sets. 

I believe you are simply misinformed on that point:

http://en.wikipedia.org/wiki/Axiom_of_infinity

In other words, the (usual) axiom of infinity just says that there is a set containing the finite numbers.

The problematic thing about set theory for me is that the concept of cardinality, to me, provides little ability of comparing infinite sets. I tried to develop my own understanding of the "size" of infinite sets, for that reason, if you know any pointers about such work as alternative to cardinality / ordinal numbers, I would be interested.

I'm not sure what this should mean. Cardinality is the loosest notion of size, because it does not depend on the structure of the set at all. Ordinality lets us get more precise based on an ordering. Similarly, we could impose any kind of structure we like, and talk about size comparisons for that structure (based on structure-preserving injections). However, this doesn't fundamentally change the game; if you find cardinality unsatisfying, what properties are you looking for?

IOW, how do you reason about the size of such sets (without foundation and choice axioms)?

Why do you need those? What do they have to do with size?

 

I suppose there is still a lot to learn about set theory for me. Just when I thought I knew all the variants. I don't really think classes were a good solution, so I am eager to consider the rejection of axiom of foundation. As Ben Goertzel explains, it also makes a lot of sense from a representation point of view (you can construct these self-referencing graphs, wonderful idea.).

Personally, I'm not interested in the set theories Ben is interested in. I want sets to arise from definitions, IE a comprehension principle, not from allowing arbitrary graphs. Sets for arbitrary graphs might naturally arise from self-referential definitions, whether/how that works will depend on how we resolve the paradoxes of naive set theory... which in my view depends on how we resolve the paradoxes of the truth predicate.

For a set theory that is much closer to what I'm suggesting, you can study NFU; here is a book:

http://math.boisestate.edu/~holmes/holmes/head.pdf

Cheers,

Abram

[Abram Demski]

Eray,

A well-timed blog post relevant to our discussion!

http://lukepalmer.wordpress.com/2012/01/26/computably-uncountable/ 

--Abram

[Eray Ozkural]

On Thu, Jan 26, 2012 at 9:04 AM, Abram Demski <abram...@gmail.com> wrote:

Eray,

And secondly, why do you need the axiom of infinity to define the set of finite numbers? (Maybe I didn't quite understand what you meant, I might be missing a point). I think it is really needed for certain "large" sets. 

I believe you are simply misinformed on that point:

http://en.wikipedia.org/wiki/Axiom_of_infinity

In other words, the (usual) axiom of infinity just says that there is a set containing the finite numbers.

 

I don't think I'm misinformed about that, and that's not as innocent as it sounds. I'm pretty sure you don't need the axiom of infinity to define Z. k, k+1, that's all you need for defining Z in set theory, and it's a simple inductive definition that doesn't need the axiom of infinity. Now, if you claim that induction is not enough, or not a good kind of proof, that would be misinformation. :) Axiom of infinity is needed for something else altogether. Have you read ZF's book on set theory? That's where they tell the basic constructions of mathematical objects, including, of course, integers, and real numbers, and sets of such numbers, functions, etc.

(Why are foundation and choice so badly desired? Well, that's another hairy issue, if you looked at the mathworld link I gave, it might provide a clue as to why!)

Cheers,

[Abram Demski]

Eray,

On Thu, Jan 26, 2012 at 1:48 PM, Eray Ozkural <exama...@gmail.com> wrote:

On Thu, Jan 26, 2012 at 9:04 AM, Abram Demski <abram...@gmail.com> wrote:

Eray,

And secondly, why do you need the axiom of infinity to define the set of finite numbers? (Maybe I didn't quite understand what you meant, I might be missing a point). I think it is really needed for certain "large" sets. 

I believe you are simply misinformed on that point:

http://en.wikipedia.org/wiki/Axiom_of_infinity

In other words, the (usual) axiom of infinity just says that there is a set containing the finite numbers.

 

I don't think I'm misinformed about that, and that's not as innocent as it sounds. I'm pretty sure you don't need the axiom of infinity to define Z. k, k+1, that's all you need for defining Z in set theory, and it's a simple inductive definition that doesn't need the axiom of infinity.

How do you justify an inductive definition in set theory without infinity? Are you sure you can do it?

You seem to be flatly contradicting the wikipedia page on the axiom of infinity, which gives it as just the assertion that there is a set containing the natural numbers (or rather, their usual set-theoretic counterparts).

So, if you can justify inductive definitions from the other axioms, it seems you would not need the axiom of infinity at all (you could simply prove it, rather than taking it as an axiom).

In ZFC minus the axiom of infinity, you could only prove the existence of sets by iteration of pairing, union, replacement, separation, power set, and choice on the finite sets which you can obtain by starting with the empty set. All of these would still be finite!

http://en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory#The_axioms

--Abram

Now, if you claim that induction is not enough, or not a good kind of proof, that would be misinformation. :) Axiom of infinity is needed for something else altogether. Have you read ZF's book on set theory? That's where they tell the basic constructions of mathematical objects, including, of course, integers, and real numbers, and sets of such numbers, functions, etc.

(Why are foundation and choice so badly desired? Well, that's another hairy issue, if you looked at the mathworld link I gave, it might provide a clue as to why!)

Cheers,

--
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy

--
Before posting, please read this: https://groups.google.com/forum/#!topic/magic-list/_nC7PGmCAE4
To post to this group, send email to magic...@googlegroups.com
To unsubscribe from this group, send email to
magic-list+...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/magic-list?hl=en?hl=en

[Eray Ozkural]

On Fri, Jan 27, 2012 at 12:07 AM, Abram Demski <abram...@gmail.com> wrote:

Eray,

On Thu, Jan 26, 2012 at 1:48 PM, Eray Ozkural <exama...@gmail.com> wrote:

On Thu, Jan 26, 2012 at 9:04 AM, Abram Demski <abram...@gmail.com> wrote:

Eray,

And secondly, why do you need the axiom of infinity to define the set of finite numbers? (Maybe I didn't quite understand what you meant, I might be missing a point). I think it is really needed for certain "large" sets. 

I believe you are simply misinformed on that point:

http://en.wikipedia.org/wiki/Axiom_of_infinity

In other words, the (usual) axiom of infinity just says that there is a set containing the finite numbers.

 

I don't think I'm misinformed about that, and that's not as innocent as it sounds. I'm pretty sure you don't need the axiom of infinity to define Z. k, k+1, that's all you need for defining Z in set theory, and it's a simple inductive definition that doesn't need the axiom of infinity.

How do you justify an inductive definition in set theory without infinity? Are you sure you can do it?

I don't need to justify that, I think, because it is not turtles all the way down.  

That is to say, somebody who rejects the axiom of infinity, surely thinks that there is *no* singular set Z that actually has an infinitely many members!

Cheers,

--
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy

http://myspace.com/arizanesil http://myspace.com/malfunct

[Abram Demski]

Eray,

Right, that is what I was saying. I am a little confused here, how is it that we are talking past each other? Your statements have been:

And secondly, why do you need the axiom of infinity to define the set of finite numbers? (Maybe I didn't quite understand what you meant, I might be missing a point). I think it is really needed for certain "large" sets.

I'm pretty sure you don't need the axiom of infinity to define Z. k, k+1, that's all you need for defining Z in set theory, and it's a simple inductive definition that doesn't need the axiom of infinity.

That is to say, somebody who rejects the axiom of infinity, surely thinks that there is *no* singular set Z that actually has an infinitely many members!

My point has been that the first two statements were mistaken and the last is correct.

--Abram

--
Before posting, please read this: https://groups.google.com/forum/#!topic/magic-list/_nC7PGmCAE4
To post to this group, send email to magic...@googlegroups.com
To unsubscribe from this group, send email to
magic-list+...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/magic-list?hl=en?hl=en

[Eray Ozkural]

On Fri, Jan 27, 2012 at 1:21 AM, Abram Demski <abram...@gmail.com> wrote:

Eray,

Right, that is what I was saying. I am a little confused here, how is it that we are talking past each other? Your statements have been:

And secondly, why do you need the axiom of infinity to define the set of finite numbers? (Maybe I didn't quite understand what you meant, I might be missing a point). I think it is really needed for certain "large" sets.

I'm pretty sure you don't need the axiom of infinity to define Z. k, k+1, that's all you need for defining Z in set theory, and it's a simple inductive definition that doesn't need the axiom of infinity.

That is to say, somebody who rejects the axiom of infinity, surely thinks that there is *no* singular set Z that actually has an infinitely many members!

My point has been that the first two statements were mistaken and the last is correct. 

Thanks. That's correct, but I have been tacitly assuming that we can define an unbounded set instead of a truly infinite set, cannot we?  Excuse me for the confusion.

That is to say, cannot "a" set theory accomodate that notion? An inductive set, that is, without assuming that the induction over Z is completed or closed.

I think assuming that there are actually infinitely many members introduces semantic paradoxes (mostly due to infinite graph theory and other non-trivial applications of uncountably infinite sets), however, here your objection is that, then we cannot prove that there is a set Z, that has infinitely many members. (And in fact it has many other consequences). I think, in practice, it is not necessary for such a "set" to have infinitely many members, it would be sufficient for carrying out analysis, AFAICT, if you could only have an inductive one, that would enable you to define limits, etc. I mean to say, perhaps define a class of sets, rather than a set. I know that people do not enjoy types (and they seem inelegant to me, as well), but perhaps it is a useful concept after all.

 

Can it be done at all? Just consider it out of curiosity, something a Formalist may wonder, a mortal curiosity. While proving the independence of the axiom of infinity, they've come upon this theory:

http://en.wikipedia.org/wiki/Hereditarily_finite_set

I remembered that "non-standard" mathematics received some attention lately. An example:

http://onlinelibrary.wiley.com/doi/10.1002/malq.19930390138/abstract

"A theory of sets with the negation of the axiom of infinity"

What do you think, crackpottery, or good old mathematical logic?

And then, when you do that, how far can you go, with either classical or intuitionistic logic? That is to say, are large cardinal axioms truly necessary (per Friedman)?

I believe, you are accusing me of being a "strict finitist", because if I reject the axiom of infinity, then I would have rejected the provability of even countably infinite sets. Is that right?

http://en.wikipedia.org/wiki/Finitism

And how would you think that could be salvaged? Perhaps, it is a case of my child-mathematician self trying to fit a square block into a round hole. As you know, in situations like this, I tend to revisit my very basic assumptions. As a reaction to this conundrum, I had set out (a long time ago) to develop what I called "algorithmic set theory", that is to say, I can define a set as:

  "an unordered list of unique bitstrings, generated by a program".

If the program is non-terminating, it is a countably infinite set. (Correct by our present intuition about infinity!)

Very down-to-earth, and something a humble computer scientist like myself could get his tiny head around! This is a formalization of my personal idea of "realization". If I have no way of ever expanding a set in that manner, even in theory, then, it is probably not a set, because no finite mechanism could conceive of it, or "intuit" it (even in principle). I believe it would be seen as too simple by Platonists and Formalists alike, however, with the (mostly trivial) fact that by definition, all such sets can be encoded as bit-strings, it is not simple expressively, only theoretically simple. (And proving facts about such sets is still not simple.)

[A side thought: I seem to miss only truly-uncomputable sets, but you disagree with that, as well?]

This conveniently gave me countably infinite sets, and even some elegant operations over them, but you seem to imply I am going to miss an important mathematical fact, something that all mathematicians would be forced to accept, if I do that. What exactly is that fact do you believe?

Note that I have no immediate objection to realism, I find myself in alignment with the idea of "Aristotelian Realism", in the sense that there may be a preferable language of mathematics to describe physical phenomena. However, I tend to think that language is *computation*, that is why I try to base everything on computation.

Regards, 

PS: And thanks for your very careful exchange. It is much appreciated. Sorry for the occasional muddling of my language.

[Abram Demski]

Eray,

On Thu, Jan 26, 2012 at 5:36 PM, Eray Ozkural <exama...@gmail.com> wrote:

On Fri, Jan 27, 2012 at 1:21 AM, Abram Demski <abram...@gmail.com> wrote:

Eray,

Right, that is what I was saying. I am a little confused here, how is it that we are talking past each other? Your statements have been:

And secondly, why do you need the axiom of infinity to define the set of finite numbers? (Maybe I didn't quite understand what you meant, I might be missing a point). I think it is really needed for certain "large" sets.

I'm pretty sure you don't need the axiom of infinity to define Z. k, k+1, that's all you need for defining Z in set theory, and it's a simple inductive definition that doesn't need the axiom of infinity.

That is to say, somebody who rejects the axiom of infinity, surely thinks that there is *no* singular set Z that actually has an infinitely many members!

My point has been that the first two statements were mistaken and the last is correct. 

Thanks. That's correct, but I have been tacitly assuming that we can define an unbounded set instead of a truly infinite set, cannot we?  Excuse me for the confusion.

How do you define it? I am worried that it might be a distinction without a difference. I mean to say: what if I claim that existing notions of infinite sets are already like that? If I claimed that ZFC only talked about unbounded sets, how would you refute me?

 

That is to say, cannot "a" set theory accomodate that notion? An inductive set, that is, without assuming that the induction over Z is completed or closed.

I think assuming that there are actually infinitely many members introduces semantic paradoxes (mostly due to infinite graph theory and other non-trivial applications of uncountably infinite sets), however, here your objection is that, then we cannot prove that there is a set Z, that has infinitely many members. (And in fact it has many other consequences).

Right.

 

I think, in practice, it is not necessary for such a "set" to have infinitely many members, it would be sufficient for carrying out analysis, AFAICT, if you could only have an inductive one, that would enable you to define limits, etc.

I am not sure what the difference is.

 

I mean to say, perhaps define a class of sets, rather than a set. I know that people do not enjoy types (and they seem inelegant to me, as well), but perhaps it is a useful concept after all.

It is a way to resolve some paradoxes, at least, but I'm not sure how "class rather than set" captures your idea of "unbounded rather than completed infinity".

 

 

Can it be done at all? Just consider it out of curiosity, something a Formalist may wonder, a mortal curiosity.

I can't exactly be curious without a better sense of what you mean; so till then, just assume my position is that ZFC already satisfies your request.

 

While proving the independence of the axiom of infinity, they've come upon this theory:

http://en.wikipedia.org/wiki/Hereditarily_finite_set

I remembered that "non-standard" mathematics received some attention lately. An example:

http://onlinelibrary.wiley.com/doi/10.1002/malq.19930390138/abstract

"A theory of sets with the negation of the axiom of infinity"

What do you think, crackpottery, or good old mathematical logic?

And then, when you do that, how far can you go, with either classical or intuitionistic logic? That is to say, are large cardinal axioms truly necessary (per Friedman)?

I believe, you are accusing me of being a "strict finitist", because if I reject the axiom of infinity, then I would have rejected the provability of even countably infinite sets. Is that right?

I may have accused you of that in the past, but not today. :) Today my impression is that you want to find a way to reject the axiom of infinity while keeping some weaker notion of infinity.

With the axiom of infinity plus the powerset axiom, we can carry out the proof that there are uncountable sets. So, perhaps you could question the powerset axiom rather than the axiom of infinity. However, to go along with my (facetious) claim that ZFC satisfies your request, I'll point out that the axiom of infinity just gives us a way to generate members of N, and the powerset axiom just gives us a way to generate members of the powerset. So, combined, we're still dealing with a description of how to generate (some?) members of 2^N.

 

http://en.wikipedia.org/wiki/Finitism

And how would you think that could be salvaged? Perhaps, it is a case of my child-mathematician self trying to fit a square block into a round hole. As you know, in situations like this, I tend to revisit my very basic assumptions. As a reaction to this conundrum, I had set out (a long time ago) to develop what I called "algorithmic set theory", that is to say, I can define a set as:

  "an unordered list of unique bitstrings, generated by a program".

If the program is non-terminating, it is a countably infinite set. (Correct by our present intuition about infinity!)

Very down-to-earth, and something a humble computer scientist like myself could get his tiny head around! This is a formalization of my personal idea of "realization". If I have no way of ever expanding a set in that manner, even in theory, then, it is probably not a set, because no finite mechanism could conceive of it, or "intuit" it (even in principle). I believe it would be seen as too simple by Platonists and Formalists alike, however, with the (mostly trivial) fact that by definition, all such sets can be encoded as bit-strings, it is not simple expressively, only theoretically simple. (And proving facts about such sets is still not simple.)

[A side thought: I seem to miss only truly-uncomputable sets, but you disagree with that, as well?]

It just depends what you mean here. You've given a definition which corresponds to computably enumerable sets. What about co-enumerable sets (sets for which I can enumerate the non-members)? You could call those "truly uncomputable", but it's just a question of what definition of "uncomputable" you like.

We could also restrict our attention to decidable sets, for which we can enumerate both members and non-members.

 

This conveniently gave me countably infinite sets, and even some elegant operations over them, but you seem to imply I am going to miss an important mathematical fact, something that all mathematicians would be forced to accept, if I do that. What exactly is that fact do you believe?

This is the kind of proposal which interests me.

The theory has some nice properties. For example, it's actually possible to enumerate all sets. (There will just be a lot of empty sets, thanks to the halting problem. And, as a direct consequence of that, it will not be possible to define equality.) We'll also get a lot of non-well-founded sets, since programs can enumerate each other.

We can't do computable analysis, though, because we can't define the computable reals. So, it seems like it would be a good idea to at least figure out a way to extend it to computable analysis.

Remember, though, in computable analysis we can already prove that the (computable) reals are (computably) uncountable (as per Luke Palmer's post mentioned earlier, http://lukepalmer.wordpress.com/2012/01/26/computably-uncountable/). So, it seems like uncountability from the inside view will be a very robust property of the reals, however we define them.

(With this in mind, I will again ask what is unsavory about the treatment of infinity in ZFC!)

Cheers,

Abram

 

Note that I have no immediate objection to realism, I find myself in alignment with the idea of "Aristotelian Realism", in the sense that there may be a preferable language of mathematics to describe physical phenomena. However, I tend to think that language is *computation*, that is why I try to base everything on computation.

Regards, 

PS: And thanks for your very careful exchange. It is much appreciated. Sorry for the occasional muddling of my language. 

--
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy 

--

Before posting, please read this: https://groups.google.com/forum/#!topic/magic-list/_nC7PGmCAE4
To post to this group, send email to magic...@googlegroups.com
To unsubscribe from this group, send email to
magic-list+...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/magic-list?hl=en?hl=en

[Lukasz Stafiniak]

On Fri, Jan 27, 2012 at 4:41 AM, Abram Demski <abram...@gmail.com> wrote:
>
> (With this in mind, I will again ask what is unsavory about the treatment of
> infinity in ZFC!)

I think you should also use the occasion to discuss the distinction
between FOL + finitely axiomatizable theories, FOL + theories with
axiom schemes (like Peano or ZFC), and SOL / HOL, which can themselves
talk about numbers (without needing "external" theory) and can force
cardinality on their models. (The discussion is offtopic for this
list, but I don't mind.)

Regards.

[Eray Ozkural]

That's correct, but personally speaking, I am not much disturbed by

axiom schemas. I would find them counter to inquiry if they such axiom

schema were not finitely describable.

Which formalization of number theory do you hold in favor? HA?

Regards,