Logic

Are first principles or the axioms of logic (such as identity, non-contradiction) provable? If not, then isn't just an intuitive assumption that they are true? Is it possible for example, to prove that a 4-sided triangle or a married bachelor cannot exist? Or must we stop at the point where we say "No, it is a contradiction" and end there with only the assumption that contradictions are the "end point" of our needing to support their non-existence or impossibility?

Comments

In any "complete" logical system, such as standard first-order predicate logic with identity, you can prove any logical truth. So you can prove the law of identity and the law of noncontradiction in such systems, because those laws are logical truths in those systems. But I don't think that answers the question you're really asking: Can we prove (for example) the law of noncontradiction using premises and inferences that are even more basic, even more trustworthy than the law of noncontradiction itself? No, or at least I can't see how we could. In that sense, then, the law of noncontradiction is bedrock. Pragmatically, we can explain the law of noncontradiction in terms of related notions such as inconsistency and impossibility, but I don't think we thereby "support" the law of noncontradiction by invoking something more basic than it.

To prove a proposition is to derive it syntactically (that is, by "symbol manipulation" that is independent of the proposition's meaning). A "good" (or syntactically valid) derivation is one that begins with "first principles" (axioms) and derives other propositions from them (and from other validly derived propositions) by rules of infererence. Ideally, the rules of inference should be "truth preserving": If you start with true axioms, then all of the propositions derived from them by the rules should also be true.

So, can you prove the axioms? If so, how? The uninteresting answer is, yes, you can prove them (in a technical, but trivial, sense) just by stating them, because they don't need to be derived by any rules from anything "more basic".

So, how do you know that they are true? Well, truth and proof are two different things. Proof has to do with syntax, or valid derivation. Truth has to do with semantics, or meaning.

Ideally, truth and proof should match up: A formal system (of logic) is "sound" if all (syntactically) derived propositions are (semantically) true; that's a desirable goal, especially if you start with true axioms and follow truth-preserving rules of inference. (Of course, garbage in, garbage out: If you start with false premises, or use non-truth-preserving rules, anything can happen—you're no longer guaranteed that your end product will be true.)

And a formal system is "complete" if all semantically true propositions are (syntactically) derivable. That's also a desirable goal, and both propositional and first-order logic are complete. But if you add Peano's axioms for arithmetic to first-order logic, you get a system that is incomplete: That's (roughly) Goedel's "incompleteness" theorem, that there are true propositions of FOL+Peano that are not provable.

Returning to your question, how do you know that the axioms are true? Not by formally proving them from more basic propositions, but by using semantic methods. In the case of axioms of propositional logic, you can use truth tables. For instance, suppose that "non-contradiction" is one of your axioms. I'll assume that this can be formalized as:

~(p & ~p)

That is: It is not the case that both p is the case and that not-p is the case.

A truth-table analysis will show that this is a tautology (that it is true no matter what truth-values you assign to p).

Have you thereby "proved" the principle of non-contradiction? In the technical, syntactic sense, no: A truth-table analysis is not a formal, syntactic proof from first principles by rules of inference. In an informal, everyday sense of "proved", perhaps yes, because you've shown by semantic methods that it must be true.

So, to answer your questions: First principles are syntactically provable, but only in a trivial, technical sense. But they're not just intuitive assumptions, either, because you can give a more substantive, semantic justification for them (at least, in the propositional case).

Read another response by Stephen Maitzen, William Rapaport

Read another response about Logic