Godel: are all undecidable props in consistent math systems subsets of self-referent statements?

How do you create the smallest possible field? The one with only two members, {0,1}? By specifying a new axiom whose sole purpose is to state that there will be no more axioms? No. The smallest possible field consists of solely the axioms themselves.

But, specifically I took that set of axioms to be a proof system. One where it’s meaningful to ask if something is provable/unprovable. The axioms by themselves do form a complete proof system; the field with two members.

And specifically, I filled in the truth table for that proof system using the axioms. The last couple steps were completed from theorems created from the axioms, and won’t be true of every possible field. (e.g. in a field with more than two members, I couldn’t have done the 1+1=0 step the same, since there would be another possible way to make an additive inverse.)

I see now that he wasn’t taking the feld axioms as a proof system. So, his statement that it was provable in one proof system based on this, but not provable in another system based on this, doesn’t mean that they are both incomplete systems. They are separate systems.

Yes, I did. Because he had said that there was no absolute provable/unprovable, only provable/unprovable within a system, I took it to mean that talking about the axioms was talking about a proof system.

It feels to me like he’s claiming it’s a single proof system to show incompleteness, (since that only has meaning in a single system,) but using every possible extension to “prove” that incompleteness.

No, it doesn’t. but, I see how you thought I was saying that. Once again a conflict between what is and isn’t a proof system.

proving something only has meaning in a proof system, right? From the axioms alone as their own proof system, there is such an x.

I wasn’t talking about what was true for every field since that would be talking about multiple proof systems. I didn’t think we were talking about multiple proof systems. Since claiming incompleteness based on multiple systems doesn’t have meaning.

Claiming that the field axioms are incomplete and this shows incompleteness even without godel’s result, is claiming it as a single proof system. x*x = 1+1 is not a question that shows incompleteness in any possible field. (and that’s the only place incompleteness has meaning, within a field. “can I answer the question in this field? Yes. Can I answer it in that other field? Yes. But I came up with two different answers. Does that make them inconsistant? No, you take each field separately for questions of completeness and consistancy.”)

It appears the basic disagreement is over whether the following is true:

If you have a set of axioms A in a language L, and there is a statement S
expressible in L such that there are two models M1 and M2 each of which
satisfies A where S is true in M1 and false in M2, then S is undecidable
in A.

Indistinguishable, Half Man Half Wit and I think (with varying levels of justification) that it’s true. You (Ch4rl3s) think it’s false.

It certainly rings true to me, but I’m probably the least qualified person to argue the point among the four of us. But maybe someone else can show, from the definitions of the various terms in the statement, that it must be true (or false as it may be).

See, I’m pretty sure this is false. If your proof system consists solely in the field axioms themselves, then your proof system fails to decide whether there are elements /= to 0 and /= to 1.

But why do I think that? Because I see that there are models satisfying the axioms in which there are such elements, and other ones in which there are not such elements. So it comes down to the same statement I formulated in my previous post–you think it’s false, the rest of us think it’s true. How can the truth of the statement be determined?

My own reason for think it’s true is just because it “rings true” based on half-remembered logic courses and a general sense of familiarity I get when I read Indistinguishable’s posts as opposed to yours. But that’s hardly a reason for anyone else to accept it of course!

Also, I guess there’s also an even more basic disagreement: It looks like Ch4rl3s thinks the field axioms by themselves do not constitute a proof system, and it looks like the rest of us think otherwise.

Am I right to think there is that disagreement happening here?

For whatever it may be worth, just to check, I fired the following email to a randomly selected professor of Mathematics:

The professor’s reply was:

So by the well known axiom of Argument from Authority, looks like my side wins. :wink:

And that is exactly what ‘the question: “Is there an x in F such that x*x=1+1?” is undecidable from the field axioms’ means. If it were decidable from the field axioms, you’d get the same answer in every field. Hence, it’s undecidable.

I’m really struggling to see where the disconnect lies. Perhaps you think that adding axioms, in some way, changes the language? Because otherwise, since it’s possible to talk about 2 in first order theories, the fact that the field axioms alone can’t decide whether or not it has a square root is exactly equivalent to the fact that different fields give different answers to the question.

I don’t know, perhaps gaining a bit of distance to the concrete example will help. Let’s say we have a proposition, P, and three axiom systems, A, A’, and A’’. A’ and A’’ follow from A through extension, i.e. addition of one or more axioms; all added axioms use the same language as the axioms that make up A. P can be derived from A’; P can’t be derived from A’’. Since A’ (or A’’) can talk about P, P is a proposition in the language used to formulate its axioms; therefore, P is a proposition in the language the axioms of A are formulated in. If now both A’ and A’’ are consistent, it immediately follows that A can’t decide P; else, there would be a derivation of P (or not-P) within A, but, since all of A’s axioms are present in both A’ and A’’, the same derivation is valid in both augmented axiom systems, this means that in one of them, one could derive both P and its negation, leading to inconsistency. So A can’t decide P if A’ and A’’ differ on it.

This is exactly what happens, the way you phrase it: we start with the field axioms; we extend them, to get specific fields; that extension is wholly comprised of axioms in first order language (it’s true that not the whole structure of the reals can be captured with first-order logic, but, as you’ve demonstrated, there are other fields in which a square root of 2 exists); different fields answer the question of the existence of a square root of 2 differently; hence, the field axioms are incomplete with respect to that question.

That’s quite simply false. There’s no field that ‘consists’ of the field axioms; fields consist of their members and two binary operations that behave according to the field axioms. The smallest possible field is the mathematical structure with the least members that satisfies these axioms.

Then, they either do not follow from the field axioms, or fields, viewed as proof systems, are inconsistent.

One last post to augment what Half Man Half Wit and Frylock have been pointing out:

To reiterate, the current fundamental (and irrelevant) clusterfuck is this: ch4rl3s thinks, among other things, that it can be proven from the following axioms that all objects are either equal to 0 or equal to 1:

There exists a unique object called 0
For every two objects x and y, there exists a unique object called x + y
There exists a unique object called 1
For every two objects x and y, there exists a unique object called x * y
For every two objects x and y, it is the case that x + y = y + x and x * y = y * x
For every object x, it is the case that x + 0 = x and x * 1 = x
For every three objects x, y, and z, it is the case that (x + y) + z = x + (y + z) and (x * y) * z = x * (y * z)
For every three objects x, y, and z, it is the case that x * (y + z) = xy + xz
For every object x, there is an object y such that x + y = 0
For every object x, if and only if x is not equal to 0, then there is an object y such that x * y = 1

(This just happened to be the familiar set of axioms I chose to illustrate a point. There’s nothing special about them so far as that point goes, but they’re the ones the misunderstanding has now arisen around.)

Presumably, the reason ch4rl3s thinks it can be proven from these axioms that all objects are either equal to 0 or equal to 1 is because those are the only objects whose existence has been directly explicitly stated by the axioms. (So that, even were they pared down to just the first and third ones, he would think the same). But that is not the way these axioms are to be read. There is no implicit supposition in them that the particular objects called 0 and 1 are the only objects who exist; there is just the supposition that at least some objects exist filling those roles.

In fact, in precisely the same way as the axioms of Peano Arithmetic postulate a successor function S(n), so that in addition to the object 0, there are objects S(0), S(S(0)), and so forth, which are not required to be equal to 0, so do the above axioms postulate an addition function +, so that in addition to the objects 0 and 1, there are objects 1 + 1, (1 + (1 + 0)) + 1, and so forth, which are not required to be equal to 0 or 1. I don’t know why ch4rl3s sees a disanalogy here.

The claim to the contrary is manifestly false, but, alright, Put up or shut up. Present a proof from those axioms above that all objects are equal to either 0 or 1. But, of course, your proof will be some short variant on “Clearly, the axioms are meant to be read as stating that the only objects are 0 and 1, since no other objects are postulated within them”. But that is not the way they are meant to be read. We are at an impasse. Unless there is some sudden shift in ch4rl3s’s understanding, I intend to ignore him for the rest of this thread (not via board function; just via not spending time responding to them to the derailment of other conversation), if, indeed, anymore can be salvaged from it.

Put it this way: If the field axioms did indeed imply that all numbers were either zero or one, that would mean that the real numbers are not a field, since the real numbers are a system which has elements other than 0 and 1.

When you ask the question like that I could have told you that would be his answer. That isn’t where the disconnect is.

because Indistinguishable was claiming this as an example of incompleteness that was always known and basically made Godel’s result unimportant, (and even preceded it.) Too bad you said you wouldn’t bother him again or he could have answered the real question.

It was always known, but the kind of incompleteness he means would only be important within a particular field, so I took that to mean we were speaking of the field axioms as the particular field they actually describe.

And it isn’t true as he stated recently that the + operator implies numbers greater than 1, or we wouldn’t be able to create the field with two members, {0,1}, call it F[sub]2[/sub]. The operation of + is only minimally described, it does not constitute a tacit successor function.

And when we create a system, it consists of only the axioms described. If a successor function isn’t described, it doesn’t exist. And if the + operator as described does constitute a successor function, then F[sub]2[/sub] doesn’t exist. I claim F[sub]2[/sub] exists.

sorry, gotta go, more later.

Just to spare you some time, that’s not what he said; he said, effectively, that the + operator implies the existence of objects like 1+1, 1+1+1, 0+1+1+0, etc, which may, in any given field, be equal to 0 or 1 or not. The point is simply that they need not be either 0 or 1 (as is also shown by the existence of fields where they’re not), and hence, 1 + 1 = 0 can’t follow from the field axioms.

And Gödel’s result isn’t unimportant in so far as it proved that in any given axiom system (provided it’s sufficiently strong, yadda yadda), there will always be incompleteness – that was a novel result. That axiom systems may be incomplete wasn’t, as it’s readily apparent that most sets of axioms formulated in some given language will be incomplete – I mean, just pick a set of random axioms, formulated in some language L; would you really expect any old such set to be able to decide all sentences that can be formulated in L?

Most axiom systems are incomplete, and of most axiom systems, completeness isn’t expected – the field axioms, for instance, are there simply to tell you what is and what isn’t a field, more or less. That they are incomplete is absolutely unsurprising. That even axiom systems that are explicitly aimed at completeness remain necessarily incomplete if you want them to be strong enough to do anything really meaningful, that is surprising.

Not at all. He was correcting someone’s misunderstanding as to why Goedel’s results were important.

I could always go bother some other random professor.

The field axioms do not determinately describe any single particular field. If they did, then there would only be one set that satisfies them. There would only be one field.

He didn’t say the operator “implies” numbers “greater” than one. Rather, he said the axioms allow for the existence of objects other than zero and one.

And of course they do, or else no field would have any object other than zero and one.

I’ve lost track of something.

Take the statement There is an x such that x*x = 1+1.

Ch4rl3s, remind me whether you think the field axioms, all by themselves, turn out a truth value for that statement.

If you think they do, what is that truth value, and how do you deduce the statement from the axioms?

If you think they don’t, then how does that not amount to saying the statement is undecidable from those axioms?

Anyway. Sorry to have indulged the derailment; back to matters that matter

Yes, there are many theorems that establish that certain things are provable, depending on what you mean by this.

Many of these theorems take the form “If system S proves X, then system T proves Y”. (Even the incompleteness theorem can be presented in this form: “If system S proves ‘S doesn’t prove me’, then system S proves a contradiction [given the usual assumption that S has positive introspection]”.) But perhaps that’s not the sort of thing you’re looking for.

There are cases like where we know in principle how to settle the answer to a question by brute-force, but it would take so astronomically long that we haven’t done so. E.g., in principle, we could determine whether or not white could force a win in chess by enumerating the entire finite tree of possible chess games, but that’s a very airy sort of “in principle”. No one actually knows the answer to this question… however, in any reasonable proof system, it’s provable one way or another, just by carrying out that gigantic method of establishing it one way or another. Similarly, no one knows whether there exists an even number > 2 which can’t be written as the sum of two primes, but if there does, one can prove that there does (by explicitly exhibiting it). [However, if there doesn’t, this may or may not be provable in whatever particular system]. Statements which can be expressed as “Such and such a computer program eventually halts” are called Sigma_1 statements, and are always provable when they’re true; conversely, statements which can be expressed as “Such and such a computer program runs forever” are called Pi_1 statements, and are always disprovable when they’re false. But this is all sort of trivial and perhaps not that interesting.

So, perhaps a more interesting result would be a cute one due to Rohit Parikh: let’s say X is “feasibly provable” if it can be proven in less than a hobajillion steps, where a hobajillion is whatever large number of your choice. Using the same trick from before for how to encode self-referential statements, we can construct the statement X = “System S doesn’t feasibly prove me”. Assuming S is the sort of system where one can mechanically enumerate all the proofs up to a given length and check whether or not a particular statement is among their conclusions, then X is S-provable if true and S-disprovable if false. However, if X is false, then, by definition, X is also S-provable (in less than a hobajillion steps, even). So, whether or not X is true, X is S-provable; however, if S is consistent, then X is true, but cannot be feasibly proven within S.

Even S can carry out this reasoning, so S can give a short proof of “X is provable within S”. However, as noted, assuming S is consistent, S cannot give a feasible proof of X; its shortest proof of X will be at least a hobajillion steps long. So, here’s a case where you can easily prove that a statement is provable without being able to easily prove the statement itself.

That having been said, S can also carry out the reasoning that establishes “If S is consistent, then X is true”. So, just adding to S the assumption that S is consistent lets one give a feasible proof of X. So perhaps this, again, isn’t the sort of thing you were looking for.

That having been said, this also establishes that S cannot provide a feasible proof of its own consistency. But this makes sense, as, by Goedel’s second incompleteness theorem (the reasoning of which is rather similar to this, actually), S cannot prove its own consistency at all (unless it actually is inconsistent). More generally, whenever S proves “If S proves A, then A is true” then S actually proves A. Which is interesting, but now we’re back to results which perhaps have more of an impossibility flavor than a possibility flavor. Oh well…

So what happens, then, if we take some system S, and create from it system S’, by adding to S the axion “S’ is consistent”? S’ can then very easily prove its own consistency, in a single step even (and I would hope that 1 < a hobajillion). Is there some reason this can’t be done?

Well, it takes some trickiness to even express that statement, of course, but not any trickier than the self-referential statements we’ve used so far (it would be “S + this statement is consistent”).

The problem? S + “S + this statement is consistent” is inconsistent [given reasonable assumptions about S]. So, yes, it can prove its consistency very quickly. It just happens to also be wrong about it.

More generally, we’ll show that, under reasonable assumptions, any system which can prove its own consistency is inconsistent. (This is GIT2)

The assumptions we’ll make of S are, first, a refinement of positive introspection which I’ll call the box condition: if S + the premises X[sub]1[/sub] through X[sub]n[/sub] proves W, then S + the premises “S proves X[sub]1[/sub]” through “S proves X[sub]n[/sub]” proves "S proves W’. (Positive introspection being the special case where n = 0). And, secondly, we’ll assume that S also proves “S has positive introspection”. (This actually suffices to establish that S proves it has both of these conditions in full, and furthermore gives us a fancy K4 modal logic, but I won’t go into that right now.)

Proof:

Alright, now, with the general diagonalization technique as before, construct the Goedel statement H = “S disproves H”.

Remember the reasoning from before: if S disproves H, then, given positive introspection, S proves that S disproves H. But this means S proves H, and thus S is inconsistent. Ergo, if S has positive introspection and is consistent, then H is false.

That reasoning is simple and can be carried out in S as well, so that S proves “If S has positive introspection and is consistent, then H is false”.

Since, by assumption, S proves “S has positive introspection”, we can use the box condition on a simple case of modus ponens to establish that S proves “If S is consistent, then H is false”.

If, at this point, it turned out that S proves “S is consistent”, we could again use the box condition on a simple case of modus ponens to establish that S proves “H is false”; i.e., that S disproves H. But, as shown above, it would follow from this that S is inconsistent.

Accordingly, S can only prove “S is consistent” if it is in fact inconsistent. Q.E.D.

Addendum: An immediate corollary and generalization of this result is that S can only prove its soundness with respect to some statement A (i.e., S can only prove “If S proves A, then A is true”) if S in fact proves A. This is called Loeb’s theorem; GIT2 is just the special case where A is a manifest inconsistency. That Loeb’s theorem in full follows from the special case GIT2 can be seen by noting the (classical) equivalence of “S proves A” and “S plus the premise (NOT A) is inconsistent”, and the fact that S plus the premise (NOT A) automatically inherits all the properties S was assumed to have.

Addendum of perhaps lesser interest: That demonstration of Loeb’s theorem as a corollary of GIT2 depends on the proof systems being ones in classical logic (as opposed to, e.g., intuitionistic logic). But even without double negation elimination, Loeb’s theorem can still be proven just as easily, by taking the above proof and replacing all talk of inconsistency with talk of proving A, talk of disproving X with talk of proving that X entails A, etc.

I agree with all that. (and most of the rest of that post,) I only have a problem with the following.

They need not be 0 or 1, in any field that has more members than 0 and 1. In the smallest possible field, F[sub]2[/sub], as I showed, 1+1 must be 0.

(as an aside, if + implies numbers other than 0 and 1, then the field with 2 elements, F[sub]2[/sub], can’t exist.)

Now, are we really only arguing about how to construct the smallest possible field? Does anyone deny that F[sub]2[/sub] is unique and is the smallest field possible, (one with only the elements and operators defined in the axioms.)

If you don’t believe that the axioms define this field, can someone tell me what axioms are needed to do so? Would any one deny that the field F[sub]2[/sub] exists if we add the axiom, “don’t assume that anything exists in this field except what is currently defined.”

Does everyone agree that the entire truth table can be filled logicically from there? Now, if you agree that that would create the field F[sub]2[/sub], Why do I have to tell you not to assume any axioms, symbols, or definitions other than the ones I’ve already given?

Grade school math, using + and * and the integers, allows for the existance of the rational numbers, and that allows for the existance of the real numbers and that allows for the existance of complex numbers, etc. And yet, each one of those is a specific instance of mathematics involving integers. The smallest specific example that fulfills the requirements of an axiom set is often just that set of axioms.

An axiom set can describe a specific proof system and still allow for other examples. You can add new axioms to any proof system any time you want. I can take any set of axioms that describes a valid proof system and imagine all the possible ways I could add axioms to it. each of them would be examples of systems that fulfill the base axioms, and yet, the base axioms would still describe the smallest possible system that fulfills all the axioms.

Allowing for numbers greater than 1, is not the same as defining them. The only things that exist in a system are those things that are defined and those things that can be proven from that.

If the statement in bold were true:

Math would be impossible, because every set of axioms can be taken to be the starting point for a set of systems, all of which fulfill those axioms. The smallest system that fulfills a given set of axioms certainly can be the system described by just those axioms alone.

(I’ll give a list of questions for a random professor if anyone wants.)

I’ll agree that F[sub]2[/sub] is the smallest field possible. I’ll disagree that the axioms “define” this field in the sense I think you mean. I think you mean they “define” this field in the sense that this field somehow uniquely satisfies them–that other fields somehow satisfy them in some extended sense only. (Do I have you right there?) I do think that adding an axiom that says “there are no objects other than 0 or 1” would create a system that “defines” F[sub]2[/sub] in the sense I think you’re using.

Do you mean including the additional one about there not being any objects other than 0 and 1?

Yes, they would describe that system, and they would describe a bunch of other systems as well. The field axioms do describe the smallest possible field. They also describe the rational numbers. They also describe the real numbers. It looks like you think the field axioms really only describe the smallest possible field, and that they “describe” other fields only in some extended sense. Do I have you right?

Okay, but all Indistinguishable needed to make his point was for it to be true that the field axioms *allow/i] for objects other than 0 and 1. He doesn’t need them to be defined in the sense of being determinately identified with particular objects in some particular set, and he doesn’t need them to be numbers greater than one either.

The field axioms define an object described as 1+1, and they fail to specify that “1+1 = 1 or 1+1 = 0”.

Reasoning as you do in the just quoted line, it seems like nothing can exist in a system that is not specifically named (not just described but named) in an axiom. But that’s not how it works.

If the set of axioms *determinately, uniquely defines one particular system (which, by the way, what do you mean exactly by “system”? I read you as meaning basically “model” though you might mean “extended set of axioms”.) then, by definition of “determinately, uniquely” it defines no other system. If all sets of axioms uniquely, determinately define one particular system, then you’re right that mathematics is impossible. But your reasoning seems to rely on that very idea–that a set of axioms determinately, uniquely defines some particular system, and other systems “satisfy” that set of axioms only in some extended sense. You are right that this makes mathematics impossible–and that is why you should stop reasoning according to that maxim.

Since I am in the mood to annoy academics right now, I’ll take the offered list. Let’s have it!

Hey, you really just gotta answer my post #53. I think it’s important to the discussion anyway. Re-posted below:

I think they do define a truth value, I think they describe the smallest field, F[sub]2[/sub].

Here’s how I went about it. I did it once, I can do it again in more detail.
We know 0 and 1 exist and have certain properties. we know the operators + and * exist and have certain properties. I assumed that no symbol or operator **that wasn’t defined **in the axioms didn’t exist. (I didn’t think I had to, I thought that was the basis of logical systems. But, even if you don’t buy that, let’s assume that we’re talking about F[sub]2[/sub].)

What can I prove about the truth table strictly from the axioms? for every x,y in F, x+y and xy is also in F. Well F only contains 0 and 1, so x+y must be 0 or 1, and xy must be 0 or 1. (Basically, + and * work on every element and the result is an element. That’s the closure property.http://en.wikipedia.org/wiki/Field_axioms)

statement… reason
0+0=0… (0 is the additive identity element, a+0=a. by axiom this is true.)
1+0=1… (same reason)
0+1=1… (Commutative property a+b=b+a, [by axiom again] along with statement 2)
1+1=0… (there is defined to be an additive inverse one (-a) for every a such that a+(-a)=0, and we already know 1+0 doesn’t equal 0, and that it must be an element, and the only other element it can be is 1.) That fills the addition table.

statement… reason
11=1… (1 is the multiplicitive identity element, a1=a)
01=0… (same reason)
1
0=0… (Commutative property ab=ba, along with statement 2 of this set.)
0*0=0… (This is the tricky one, I’ll expand it.)

Distributivity of multiplication over addition is also an axiom… such that a*(b+c)=(ab)+(ac) for all a,b,c in F. Take a=0, b=0, and c=1.
0*(0+1) = (01) + (00)… (0+1)=1, (01)=0 from previous, so substitute.
0
(1)… = (0)… + (00)… (01)=0 (left side of equation,) and 0+a=a, (right side of equation.)
0… =… (0*0)… and all using only the field axioms, (first order logic,) and the assumption that nothing other than the axioms exist.