the formatting was bad…
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.
I’m trying to get a handle on the significance of Godel’s work, btw. Along those lines, why doesn’t the incompleteness theorem apply to Boolean logic? Am I correct in understanding that Boolean algebra is both complete and consistent? Why doesn’t it succumb to some sort of self-referential proof?
Tangential observation: Boolean logic is actually pretty damn powerful.
Ch4rl3s, do you think the following is true or false?:
Any field other than F[sub]2[/sub] is defined only by extending the field axioms with the addition of one or more existence axioms.
To respond more directly to your post (but the above may be the most important question here):
So that’s where you’re explicitly not deriving the statement from just the field axioms themselves. You’re explicitly adding an axiom to them.
I’m not sure how to argue for a point here. You’ve just baldly stated “here I’m adding an axiom” when what I asked was what happens when you don’t add an axiom.
What do you think happens when you don’t add that axiom? That’s what I was trying to ask.
Do the field axioms, all by themselves, turn out a truth value for that statement?
(Emphasis added.)
For something to validly follow from a set of axioms, it must be deducible from those axioms without any other assumptions. If some other assumption is required to deduce it, then it doesn’t validly follow from the axioms.
There’s some wiggle room in “deducible” here. Deducible using what rule set?
In this discussion over the field axioms we’ve not done anything funny here–we’re all just using the rules of classical predicate logic. But nowhere in the rules of classical predicate logic will you find a deduction rule that amounts to saying “assume nothing exists other than what is specifically named (not just described but named) and stated explicitly to exist in an axiom.” And nowhere in the field axioms do we find a statement to that effect either.
Well, in the sense that any proposition built up out of purely the constants and operations of Boolean algebra and the binary predicate of equality is precisely one of provably true or provably false, it is complete and consistent. This doesn’t violate Goedel’s incompleteness theorem because there is no binary predicate definable in said language of Boolean algebra which represents provability/disprovability of statements of the form “The predicate represented by object1 holds of object2” in the appropriate ways. In fact, there are too many definable sets of objects and too few definable objects to code the former in terms of the latter in the appropriate way; there are, modulo provable equality, only two definable objects (1 and 0, we can call them), but, modulo equiprovability on all of those inputs, there are a full four definable predicates on/subsets of those (all four subsets being definable).
One way I wanted to state for how to view it is as a more careful statement of Cantor’s theorem/proof:
The conventional presentation of Cantor’s theorem, written out, tells us that if there is a function f from X to subsets of X such that for every subset S of X, there is some object x in X such that the elements contained in f(x) are precisely the same as the elements contained in S, then there is some sentence which is true if and only if its negation is (i.e., this can never happen).
But looking at the proof, we can actually be a bit more careful about stating this, and get a result which is more widely applicable: for any notions of provability and definability, if there is a definable function f from X to subsets of X such that for every definable subset S of X, there is some definable object x in X such that the elements provably contained in f(x) are precisely the same as the elements provably contained in S, then there is some sentence which is provable if and only if its negation* is (i.e., if this happens, the proof system is not simultaneously consistent and complete).
This is essentially GIT1, but presented slightly differently. As I said, it is naught but a more careful presentation of Cantor’s theorem and proof. Perhaps it makes things clearer to some, the same as the Halting Problem presentation perhaps makes it clearer to some. Anyway, there you have it.
*: By “negation”, I mean any definable logical operator (aka, function from truth values to truth values; natural transformation on subsets) you choose to call “negation”
OK, then, what if instead of adding an axiom that asserts that S-prime is consistent, what if we just add an axiom that asserts that S is consistent (and S-prime, which contains this axiom, therefore does not have any axiom about its own consistency, just about that of a closely-related system). Does this cause any problems?
Nope. [Well, it can lead to inconsistency if S already falsely proved its own inconsistency, but if S is true (on some interpretation which interprets the language’s S-provability predicate as actual S-provability), then S-prime will, of course, be true as well]. Naturally, S-prime still cannot consistently prove its own consistency; it just happens to prove the consistency of its subsystem S.
If the field axioms did, in fact, define this truth value, then it would be the same in every possible field, or there would be inconsistency in every field where 1+1 isn’t 0.
If the field axioms proved that 1+1=0, then this means that there exists a derivation relying exclusively on these axioms for 1+1=0. Whatever you then add to the field axioms, that derivation would not cease to be valid; hence, if you added anything in such a way that you create a derivation for 1+1 not being equal to 0, you would have created an inconsistent system. But since there are fields for which 1+1 isn’t equal to 0 (and in fact, in those fields, there is no derivation for 1+1=0), the field axioms don’t prove 1+1=0; and by the same token, they don’t ‘specify’ F[sub]2[/sub] anymore than they do any other field, even though it is the smallest possible one. The fact that 1+1=0 is true in F[sub]2[/sub] has absolutely no bearing on the issue, or at least not anymore than the fact that it isn’t true in other fields has, which is to say that it’s undecidable from the field axioms.
There’s just no way around it. If the field axioms decided the issue, they’d decide it for every possible field; since they don’t, they’re incomplete.
usually one or more existence axioms, and some to describe how they will interact with the operators. But, basically, yes.
I specifically added it to make sure everyone agreed we have the field F[sub]2[/sub] with that in place. I intend to remove it as uneccessary. That is a question I would ask a random professor. Is that assumption necessary?
If it is, then every system needs it to be a “proof system” and not just a set of axioms. starting from an axiom set that describes the integers and the operator +, is there a number between 1 and 2? Well, it must be undecided, unless you explicitly state that we aren’t later going to create the rational numbers, or some other set with a value between 1 and 2. (personally, I’ve been saying that there is no value between 1 and 2 unless we specifically define the rational numbers, or some other set, and not that we have to assume they can exist unless we specifically exclude them. Does that number exist using just the axioms? No. But it can exist if we add axioms. Using just the axioms, there is no way to describe a number between 1 and 2.)
The same thing. I don’t think that axiom is required.
Actually, that isn’t the one that uses the assumption. (It’s the trickiest to prove, but it follows directly from the axioms, and I don’t believe it can have a different value in any field.) Take a look, that statement is derived using only the additive and multiplicitive identities and the commutative property of addition. The only one that needed the assumption was 1+1=0.
So let’s be sure I have you right.
This is what you think, correct?:
Is that what you think?
Meanwhile, here’s what I think:
That is something you disagree with, correct?
How do you respond, by the way, to Half Man Half Wit’s argument? Specifically, the one where he points out that if the field axioms specify F[sub]2[/sub], then the addition of further axioms stating the existence of elements other than 1 and 0 must lead to an inconsistent axiom set? For if the field axioms by themselves specify there are no elements other than 1 and 0, then the addition of an axiom “2 is an element” leads to immediate contradiction.
Let F stand for the field axioms. Let FX (for any X) stand for any extension of F. If F proves P, then FX also proves P. On your account, F proves S: “No x other than 1 or 0.” This means that FX (for all X) also proves S. But take FA, which is the extension of F that includes just the one additional axiom “There is an object equal to 1+1 distinct from both 1 and 0.” Since F proves S, FA must also prove S. But the additional axiom in FA directly contradicts S, so FA also proves not-S. FA proves both S and not-S. So FA is inconsistent. Do you really think, then, that any extension of F that specifies the existence of elements other than 1 and 0 is necessarily inconsistent? This amounts to saying there are no fields other than F[sub]2[/sub]. But you don’t really think that, do you? Why not, given the reasoning I just gave starting from premises you believe?
The value of 1+1 is derived from the axioms. Not stated, so it can change.
Here is a statement that has a different value depending on which field we are using.
if we had defined numbers other than 0 and 1, then the additive inverse of 1 could be something else other than 0 or 1. If we had specifically added the axiom, “2 also exists,” I wouldn’t be able to fill the truth table without an idea of how 2 interacts with the + operator and all the other numbers. Then that would be an incomplete system.
But that derivation does cease to be valid as soon as you define the number 2. When the only numbers defined or derived are 0 and 1, then 1+1 must be either 0 or 1. (and you can’t use 1+1 to derive a number other than 0 or 1.)
That doesn’t actually follow.
I will give you the integers, and the typical definition of +. (so that we have the typical situation where -1<0<1<2<3 etc.) This will be our axiom set.
Now, the statement, “there is no number between 1 and 2.” Is it true or false or undetermined? Not going to try and trick you here. I would say that it’s true… But wait, I haven’t specifically excluded the rational numbers. The rationals can be defined from this axiom set by adding the proper axioms, (you can do it with some notiion of “a/b is in A for all a,b in A.”) But, if you assume the rationals exist, this statement is false. So, you must be saying that the statement “there is no number between 1 and 2,” is undetermined, unless you exclude rationals or any other possible expansion of the set I gave.
So, I would have to add to this axiom set the axiom, “assume no other symbols, operators or axioms exist,” in order to make this a proof system. Like I said, you must be claiming that this axiom is added to every axiom set before it can be a proof set.
Using the field consisting of the real numbers, (an expansion of the field axioms,) there is a possible expansion of this field called the field consisting of the real numbers and the complex numbers. Let’s call them FR and FRC.
FR does not have a square root of -1. FRC does. From FR can you say that the statement “There is no square root of -1” is true? I say you can. But by adding axioms to FR I can create FRC, in which there is a square root of -1. So, you must be claiming that FR without the axiom “assume no other axioms, etc.” is only an axiom set and does not describe any particular field that also includes the real numbers. That it only describes FR when we add that axiom. That any axiom set does not describe a specific example unless we add that axiom.
that would be a question I would ask some professor, “do we need to specifically add that axiom to an axiom set to describe a specific example? Or is that the default assumption in mathematics?” The axiom being, “assume no other symbol, operator or axiom exists in this system.”
See, Frylock didn’t mention to that professor that A might decide the statement S even if M1 and M2 describe it differently. A is a possible example of an axiom system that fulfills the axioms, A; the smallest one. M1 is another, M2 a third. That might be one of the caveats he mentioned.
the implication from what everyone else is saying is that… If A is extensible, (you can add axioms to create multiple systems that fulfill A, ) then A can not be an example of a system that fulfills the axioms of A. That sounds ludicrous
to me. It seems to me that A is usually the smallest example of a system that fulfills the axioms of A.
If you have left A it open to create other numbers or other operators, etc. then there are always multiple ways to extend it. Is A still the smallest possible example of a system that fulfills the axioms of A.
For instance, Presburger arithmetic is a complete and consistant system. Correct? It can answer any question that can be asked in the system. And it is the smallest set that fulfills the Presburger axioms. Yet, Peano arithmetic is a possible extension of it. It can be further extended to include real numbers. In Presburger, what is the answer to the question, “is there a number between 1 and 2?” guess what, it’s complete and able to answer that question. but, the two extensions mentioned answer it differently. (just like Frylock’s question to the professor.) So, from what you’ve been claiming, Presburger must not be able to answer that question.
From Frylock’s question:
A is Presburger. S is the statement, “there is no number between 1 and 2.” M1 is Peano. And M2 is the real numbers. But, since S is true in M1, Peano, and false in M2, the real numbers, then S is undecidable in A, Presburger. but we know that Presburger can answer that question. It’s true.
So, where is the problem? Is it in my statement that Presburger can be extended in muliple ways, or in your assumption that this doesn’t fall within the caveats?
Ah hmm. This may be the real disconnect.
Did you know that if an axiom set proves P, then every extension of that axiom set also proves P?
That means that if the field axioms prove 1 + 1 = 0, then every extension of the field axioms also proves 1 + 1 = 0.
Did you know that?
F does not prove S: “No x other than 1 or 0 exists.” But in F, with no extension, S is true. There’s a difference.
In the system F, it is true that there is no number other than 0 or 1.
In the system Presburger, it is true that there exists no number between 1 and 2. Why? because from the axioms there is no way to create that number.
From the axioms of F, there is no way to create numbers other than 0 and 1. If there is no way to create it from axiom, I claim it doesn’t exist.
I claim that the rules of mathematical logic prove S in F. no x other than 0 or 1 can be created from the axioms of F, therefore, they don’t exist. in F[sub]rationals[/sub], numbers other than 0 and 1 can be created from the axioms, therefore, they exist.
It was that that allowed me to deduce that 1+1=0 in F. And not neccessarily in any extension.
I’ll give you 0<1<2. (This is our axiom system A.) what is 3? is 2<3? wait, 3 can’t be created from our axiom(s.) From the axiom(s) what is 2 less than? guess what, it’s “nothing.” I can extend the axioms to include things greater than 2. but until I do, I deduce from the axiom, that there is nothing greater than 2.
I thought that undecidability has to do with what is provable from axioms, not what is provable about them in a metalanguage.
Regarding the presberger stuff, I guess the way to put “there’s a number between 0 and 0’s successor” is
There is an x and y, neither equal to zero, such that 0 plus x plus y = 1.
I’m actually not so sure the presberger axioms do turn out a truth value for that, but it’s my first time to look at them.
But the meaning of “turn out a truth value” is at dispute, now, given your latest post. I thought that what matters with undecidability is whether something can be proven from a set of axioms, not whether it can be proven about them in a metalanguage.
In other words, just because something can be proven true in a metalanguage including L, this does not mean that that thing is decidable in L.
Or so I thought.
I can create two extensions, (at least,):
M1: A and -1<0.
M2: A and 2<3
In M1, nothing is greater than 2. in M2 3 is greater than 2. Oh, but wait, M1 is extendible. (so is M2.)
M1a: M1 and -2<0 … and nothing is greater than 2.
M1b: M1 and 2<3 … and 3 is greater than 2.
but M1a can be extended. (etc.) You are saying that A does not answer the question, M1 doesn’t answer it, M1a doesn’t answer it. etc. This can be done infinitely. And none of these systems in which it is **not possible to create **a number greater than 2 can answer the question, “**is there **a number greater than 2?” Ludicrous.
Presburger is complete and consistent. It can answer any question it can ask, (that’s complete.) [Any question it answers, it answers uniquely, (that is consistent.) But we won’t worry about that now.] It can ask the question, “is there a number between 1 and 2.” Or, in more precise language: “is there an x in P such that 1<x<2.” Or, “is there an x in P such that x+x=3?” If these are ways of asking questions in Presburger, then Presburger must answer them.
But I can make extensions of Presburger that answer these questions differently.
You and Half Man must be saying that these questions are unanswerable in Presburger. (that would be another question to ask a random professor.)
you’ll notice that x+x=3 in Presburger is exactly of the form 1+1=? in the Field axioms. Nobody has claimed that the Field axioms can’t ask that question.
Eschewing discussion of numbers being “greater than” each other (the field axioms don’t specify that relation) the question is just whether those various extensions allow for the existence of numbers other than those explicitly named in axioms. And the answer has to be yes, since if they didn’t allow for that existence, then the extension of those axiom sets into new sets that do specify that existence would necessarily lead to an inconsistent axiom set.
Only that the Field axioms can’t answer it because 2 possible extensions answer it differently, and is therefore incomplete.
the Presburger axioms can ask a similar question, and has at least 2 extensions that answer the question differently. therefore, from your logic, I conclude that Presburger can not answer that question and is incomplete. But, mathematicians agree that Presburger is complete.