- #1

roygabv

- 1

- 0

I am working on a paper detailing Godel's Incompleteness Theorm and I came across this statement.

"An axiomatic base where all the axioms are true cannot prove anything to be false."

Is this correct?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter roygabv
- Start date

- #1

roygabv

- 1

- 0

I am working on a paper detailing Godel's Incompleteness Theorm and I came across this statement.

"An axiomatic base where all the axioms are true cannot prove anything to be false."

Is this correct?

- #2

honestrosewater

Gold Member

- 2,136

- 5

What's an axiomatic base?

- #3

Dooga Blackrazor

- 253

- 0

I think the sentence leaves one open to broad interpretations, but I would agree with the statement.

- #4

inquire4more

- 45

- 0

roygabv said:"An axiomatic base where all the axioms are true cannot prove anything to be false."

Is this correct?

I'm assuming by axiomatic base they mean those axioms which a system needs and no more . The irreducibles, I suppose. But, in ANY system, any that I'm aware of any ways, the axioms are taken to be self-evident truths. We speak of axiomatic set-theory, and we hold that its axioms are both self-evidently true and not reducible to any combination of the other axioms. And yet, we prove statements to be either true or false using the rules of logic and these suppositions. Or, I suppose, they are found to be either consistent or inconsistent within our system. But we generally take inconsistency to be falsity, at least within the system. It seems to me that this statement should read "An axiomatic base where the axioms are false cannot prove the truth of a statement." I'm a bit confused, though, and may be entirely wrong. Still...

- #5

inquire4more

- 45

- 0

- #6

honestrosewater

Gold Member

- 2,136

- 5

i) The axioms of S are theorems of S;

ii) If all hypotheses of a rule of S are theorems of S, then the rule’s conclusion is a theorem of S.

Then define a proof in S as follows:

If all rules in S are finite, a proof in S is a finite sequence of formulas, each of which is either an axiom or the conclusion of a rule whose hypotheses precede the formula in the proof.

If L is the last formula in proof P, then we say P is a proof of L.

Thus L is a theorem of S iff there is a proof of L in S. (An axiom is a proof of itself.)

You can then add two distinct objects, “T” and “F”, called truth-values. These objects just have to be distinct, but we can let them mean "truth" and "falsehood". T and F are assigned to formulas. Say we've designed our inference rules so that if T is assigned to all hypotheses of rule, then T is also assigned to the conclusion of the rule. Assign T to all axioms. Then T is assigned to all theorems of S. Recall that L is a theorem of S iff there is a proof of L in S. So no proof of L in S results in F being assigned to L. IOW, we can't prove any formula is false. Well, I skipped over a lot of things, but I think that works.

- #7

inquire4more

- 45

- 0

I think I follow what you are trying to state here. But, more to the point, it seems to me that no value of F would ever be assigned to an L. By your definition, L would be arrived at, in a purely mechanistic fashion, from axioms assigned T, by accepted inference rules. L would only be arrived at in the case that L is T. It is not that we may say the assertion L is F. We may not make the assertion L at all, unless of course L is T. Only L which are T may be stated, no others would occur, not in this fashion. I agree with your point here, at least in reference to roygabv's assertion.honestrosewater said:If L is the last formula in proof P, then we say P is a proof of L.

Thus L is a theorem of S iff there is a proof of L in S. (An axiom is a proof of itself.)

You can then add two distinct objects, “T” and “F”, called truth-values. These objects just have to be distinct, but we can let them mean "truth" and "falsehood". T and F are assigned to formulas. Say we've designed our inference rules so that if T is assigned to all hypotheses of rule, then T is also assigned to the conclusion of the rule. Assign T to all axioms. Then T is assigned to all theorems of S. Recall that L is a theorem of S iff there is a proof of L in S. So no proof of L in S results in F being assigned to L. IOW, we can't prove any formula is false.

It is here that I disagree. That a theorem may follow from another theorem by a rule, I take as a true statement. That an axiom may follow from an application of a rule on a set of expressions or formulas, I do not. As a rule, an axiom is an irreducible, an underivable assertion. Though you may not call a primitive expression an axiom, it is still nonetheless. Your axioms then, as defined in your statement, would really more aptly be called theorems, as they follow from the application of some set of procedures on these primitives. If, by chance, you are referring to metastatements, as preceding statements, then I think we must treat the metacase as a different case. If I missed your point, or misinterpreted you in any way, let me know.honestrosewater said:It depends on how you set up the axiom system S. Say you start with a set of symbols, then string symbols together to get a set of expressions, then pick out some special expressions to get a set of formulas. Then you pick out some special formulas to get a set of axioms. Then you add rules of inference. A rule of inference (rule, for short) states that some formula (conclusion) can be inferred from a set of formulas (hypotheses). A rule is finite if it has finitely many hypotheses. Then define theorems as follows:

i) The axioms of S are theorems of S;

ii) If all hypotheses of a rule of S are theorems of S, then the rule’s conclusion is a theorem of S.

- #8

honestrosewater

Gold Member

- 2,136

- 5

Right, because S has been set up precisely so that we can't prove any formula unless it's true- it has been set up to be sound (and complete BTW). There certainly are false formulas; The negation of each theorem in S, by the axioms and rules of S, are false- we just can't derive them in S. With different axioms or rules, we could derive false formulas, as you noted about inconsistent axiom systems.inquire4more said:I think I follow what you are trying to state here. But, more to the point, it seems to me that no value of F would ever be assigned to an L. By your definition, L would be arrived at, in a purely mechanistic fashion, from axioms assigned T, by accepted inference rules. L would only be arrived at in the case that L is T. It is not that we may say the assertion L is F. We may not make the assertion L at all, unless of course L is T. Only L which are T may be stated, no others would occur, not in this fashion. I agree with your point here, at least in reference to roygabv's assertion.

Good because you couldn't disagree with that- it's how theorems were defined. :tongue2:It is here that I disagree. That a theorem may follow from another theorem by a rule, I take as a true statement.

We have to build up a language before we can even state an axiom. That's what the symbols, expressions, and formulas are for- they tell us how the language works and allow us to actually say things in the language. We may create a rule- not an inference rule though, those are different- that decides which formulas are axioms, or we can just state each of them (if there are finitely many, of course). What I outlined above is the usual way of building axiom systems. Well, it's the syntactic side of axiom systems, dealing with the formal aspects, symbols, and such; There's also a semantic side, dealing with concepts, meaning and such, but I'll get to that.That an axiom may follow from an application of a rule on a set of expressions or formulas, I do not.

From your experience, axioms may be what you say. But as defined in this system, axioms are formulas. They really have to be- you can't state them otherwise. And axioms don't have to be irreducible. Here are a few examples of axiom schemas of axiom systems for propositional logic- don't worry if you don't understand them- a B alone is a formula, as are ~B and (B -> C), so these are certainly reducible:As a rule, an axiom is an irreducible, an underivable assertion.

A1) (B -> (C -> B))

A2) ((B -> (C -> D)) -> ((B -> C) -> (B -> D)))

A3) (((~C) -> (~B)) -> (((~C) -> B) -> C))

__

B1) B v B -> B

B2) B -> B v C

B3) B v C -> C v B

B4) (C -> D) -> (B v C -> B v D)

__

C1) B -> (B & B)

C2) B & C -> B

C3) (B -> C) -> (~(C & D) -> ~(D & B))

__

D1) [(((B -> C) -> (~D -> ~E)) -> D) -> F] -> [(F -> B) -> (E -> B)]

-taken from Mendelson's "Intro to Mathematical Logic", 4th. Notice they also use different symbols; That's part of the language. :)

On the semantic, conceptual side of axiom systems, you may want your axioms to be as simple as possible, but it isn't necessary. Simpler axioms may make the rest of your work easier. You may also want other people to understand what you're talking about without having to explain a lot or for people to accept that your axioms are true "outside" of the system. But none of these are necessary. You only need to consider your choice of axioms if you want your axiom system to behave in a certain way, and even then, you may have several axiom sets that do the job equally well, as is the case above.

Ah, but axiomsThough you may not call a primitive expression an axiom, it is still nonetheless. Your axioms then, as defined in your statement, would really more aptly be called theorems,

You would be right if they were metastatements, but they aren't. We wouldn't have to build the language then; We could just start talking about axioms right away.as they follow from the application of some set of procedures on these primitives. If, by chance, you are referring to metastatements, as preceding statements, then I think we must treat the metacase as a different case. If I missed your point, or misinterpreted you in any way, let me know.

Oh, BTW, you actually use some of the properties of expressions and formulas to prove things

Last edited:

- #9

hitssquad

- 926

- 0

Premises?inquire4more said:Following from false pretenses

.

- #10

inquire4more

- 45

- 0

I've been busy the last two days but I've had a minute or two to look at your statement. First, your axiom systems seem to me to be roughly, or perhaps exactly, equivalent. I understand your point here. Still, I need to see the actual method of their construction before I decide for myself whether or not axioms may follow, as well as precede, and I do not count equivalent statements, or restatements, as developments of seperate axioms. Can you point me to where I might find these constructions? And you're saying these constructions are done in the system, without use of some meta-system?honestrosewater said:You would be right if they were metastatements, but they aren't. We wouldn't have to build the language then; We could just start talking about axioms right away.

Oh, BTW, you actually use some of the properties of expressions and formulas to prove things about not in the axiom system. For instance, you may use the length of a formula (the number of symbols in it) to prove something about the system. So you don't just use them at the beginning and forget them.

- #11

honestrosewater

Gold Member

- 2,136

- 5

I take it you mean the specific axiom sets I listed. This is bordering on my comfort zone; I'll try to be careful, but take this with a grain of salt. The axiom sets are similar in that they are all axiom sets of a formal axiomatic theory for the propositional calculus. (You may already know there are different axiomatizations for set theory, but they are all still recognized as axiomatizations for set theory. Same general idea.)inquire4more said:I've been busy the last two days but I've had a minute or two to look at your statement. First, your axiom systems seem to me to be roughly, or perhaps exactly, equivalent.

Some things those axiomatizations for propositional calculus have in common: a finite set of connective symbols, a countably infinite set of propositional symbols, an effective procedure for determining formulas, a finite set of axiom schemas, and a finite set of inference rules (all sets are non-empty). It's the specific symbols, axioms, etc. in which they may differ.

I'm not sure how equivalency would apply to axiom sets, sorry. The first axiom set I listed is part of a sound, complete axiomatic theory for propositional calculus. I presume the others are also.

Sure. The examples I gave were from Mendelson's "Introduction to Mathematical Logic", 4th ed. You can find this info in just about any other mathematical logic book or site; Two books I like are Shoenfield's "Mathematical Logic" and Machover's "Set theory, logic and their limitations" (though IIRC Shoenfield skips this for propositional logic and goes straight into first-order logic).I understand your point here. Still, I need to see the actual method of their construction before I decide for myself whether or not axioms may follow, as well as precede, and I do not count equivalent statements, or restatements, as developments of seperate axioms. Can you point me to where I might find these constructions?

By all means, try those if that's what you want, but you don't really need them. I've pretty much told you how the axioms are constructed, beginning with sets of symbols. If you want more details, I can handle that. If you want to know how an author goes about choosing axioms or how propositional logic developed historically, those books aren't the place to look. Try this article. If you're really interested, you could check out Boole's "Laws of Thought".

(As you'll see if you read those books, especially Machover) The line is clearly drawn between the metalanguage (English, for me) and what's called the object language. Of course, the metalanguage is used to describe the object language, and the symbols we use in the metalanguage onlyAnd you're saying these constructions are done in the system, without use of some meta-system?

Share:

- Last Post

- Replies
- 13

- Views
- 531

- Last Post

- Replies
- 5

- Views
- 1K

- Last Post

- Replies
- 15

- Views
- 2K

- Replies
- 9

- Views
- 1K

- Replies
- 6

- Views
- 1K

- Replies
- 6

- Views
- 1K

- Replies
- 2

- Views
- 2K

- Replies
- 1

- Views
- 1K

- Replies
- 56

- Views
- 7K

- Replies
- 4

- Views
- 770