2
$\begingroup$

I'm currently reading Ethan D. Bloch's book "Proofs and Fundamentals: A First Course in Abstract Mathematics". I know this is not a good book for learning logic, but this is not why I'm reading it. However, I came across some claims that are really bugging me and I would appreciate if someone more knowledgeable in formal logic could provide me some clarification. The claims in question are the following (section 1.4, pp. 28-29, emphasis mine):

This sort of justification, often referred to by logicians as a derivation, is a chain of statements connected by meta-statements (namely, the justifications for each line). If an argument has a derivation, we say that the argument is derivable. [...] We now face an important question: given an argument, we have two notions of whether the argument works, which are that it is or is not valid, and that it is or is not derivable. The former notion involves checking truth values (which is done with truth tables), the latter constructing a chain of statements linked by rules of inference. What is the relation between these two approaches? Though it is not at all obvious, nor easy to prove, it turns out quite remarkably that these two approaches, while different in nature, always yield the same result. That is, an argument is valid if and only if it is derivable. Hence, if we want to show that a given argument is valid, it will suffice to show that it is derivable, and vice versa. The equivalence of these two approaches is a major result in logic. That validity implies derivability is often referred to as the “Completeness Theorem,” and that derivability implies validity is often referred to as the “Soundness Theorem” or “Correctness Theorem.”

What I understand about the above text is that it's not obvious or easy to see that derivation and validity are equivalent notions. That is, someone must've thought that it would be possible, at least in theory, that we could find a derivation for an invalid argument, thus the need for the so called "Soundness Theorem". However (and this is the part that I'm struggling to understand), if the rules of inference are already proved to be valid arguments and we use them to come up with a derivation for a certain argument (i.e., we can "transform" the premises into the conclusion), then, certainly, the argument in question must be valid, right? And this is what's bugging me; contrary for what the author is asserting in the above text, I find it easy to see a relation between these two notions, so there's certainly something that I'm misunderstanding.

I know it's impossible to come up with an example of a derivation for an invalid argument, but can somebody help me better understand how the notion of validity is (or could be) independent from the notion of derivation.

PS: I also consulted these two questions on the web, but I'm still struggling to understand the separation between these two notions:

What is the meaning of the double turnstile symbol ($\models$)?

what's the difference between Syntactic consequence ⊢ and Semantic consequence ⊨

$\endgroup$

3 Answers 3

1
$\begingroup$

From the soundness theorem, it's clear that whatever you can derive will be valid. The non-obvious part (the completeness theorem) is that every valid statement can be derived.

$\endgroup$
2
  • $\begingroup$ But my question was actually about the soundness theorem (that if something is derivable then it is valid), I mean if the author claims that the soundness theorem was such an important result in logic, certainly it should be something that wasn't obvious or easy to prove, right? $\endgroup$
    – OldCrow
    Commented Jun 3, 2022 at 3:37
  • $\begingroup$ The passage that you quoted says “The equivalence of these two approaches is a major result in logic” (my emphasis). One direction is nearly trivial (the soundness theorem), but the other direction is not (the completeness theorem, proved by Gödel in his doctoral dissertation). $\endgroup$ Commented Jun 3, 2022 at 5:29
1
$\begingroup$

It might be easier to consider a well-known independent axiom system and semantics first, which is known to be both complete and sound. We'll call such a system A. Then, if such a system has more than one axiom as most do, one could consider the axiom system with the same semantics, but drop one of the axioms and call it A-. A- will still satisfy soundness, since everything derivable in A- will also come as derivable in A. However, there will exist valid statements in A- which will not come as provable in A-, since it has the same semantics as A, but the dropped axiom will not enable A- to derive some theorem that appears in A.

For example, (in Polish notation), Lukasiewciz's axiom set that he used in his textbook was:

  1. CCpqCCqrCpr
  2. CCNppp
  3. CpCNpq

the rule of detachment: from a meaningful expression (well-formed forumla) of the type 'Cab', along with a meaningful expression of the type 'a', we may infer a meaningful expression of the type 'b', the rule of uniform substitution in that we may substitute any lower case letter with any meaningful expression so long as that substitution applies to every instance of that lower case letter in the original meaningful expression,

and the semantics was that of classical two-valued logic:

C00 = 1, C01 = 1, C10 = 0, C11 = 1;

N0 = 1, N1 = 0.

Now, let's keep those semantics, but consider the system which only has the first two axioms:

  1. CCpqCCqrCpr
  2. CCNppp

The system still produces only correct theorems, in that everything which can get proved will hold true for its semantics. We still could prove, for example, CCprCCNppr. And that still holds for the semantics of this two-axiom system.

But, we won't have the ability to prove the third meaningful expression from the first system CpCNpq, and Cpp won't be derivable also. And also, CpCNpq still holds for the semantics of the two-axiom system. Cpp also holds for the semantics of the two-axiom system. Thus, the two-axiom system has meaningful expressions which are valid for it's semantics, but are not derivable.

So, the notions of validity and derivability come as independent, since we can show that validity can hold for some expressions in a system, but derivability won't hold for those same expressions in the same system.

$\endgroup$
3
  • $\begingroup$ Wow, I think this is the kind of answer I was looking for. I'm sorry, but I'm a little slow to understand things so I think it'll take me a day or two to fully understand your answer, but I think you nailed it. Also, I'll have to check the notation you used, since it's the first time I've seen it, but I think I get what it means. Thank you for your explanation. $\endgroup$
    – OldCrow
    Commented Jun 3, 2022 at 3:21
  • $\begingroup$ Something just occurred to me. Your example shows that it could be theoretically possible to have a valid argument that isn't derivable, thus showing that both notions are separate. But, my confusion is more about the Soundness Theorem (i.e., if it could be possible for an argument to be derivable and invalid). My reasoning (and the cause of my confusion) is that, if the Soundness Theorem was such an important achievement for logic, then certainly it wasn't something obvious or easy to prove. But I think it's obvious that if an argument is derivable then it's also valid. What am I missing? $\endgroup$
    – OldCrow
    Commented Jun 3, 2022 at 4:03
  • $\begingroup$ @OldCrow Derivable just means that we can make some proof that follow some rule(s) of inference. We could have the rule of inference "from CCpqCCqrCpr, infer p", for example in say a system where CCpqCCqrCpr is not an axiom, but provable. Then we could have the argument that CCpqCCqrCpr can get proved by the other axioms, and then we can infer p. Such would make anything valid in the semantics derivable (since every meaningful expression is derivable), but it wouldn't be sound, since 'p' is false. $\endgroup$ Commented Jun 4, 2022 at 19:04
0
$\begingroup$

Derivability is what we call a purely syntactic notion, i.e. it is a manipulation of finite strings of symbols, without any meaning. Validity, on the other hand, is about models, about the meaning of the strings of symbols.

Think about it in terms of natural languages. Knowing, for example, how to read English, but not understanding a single word, is the syntactic view of the language. Knowing the language, but not knowing how to read it, is the semantic point of view.

We can easily see that natural languages are definitely not sound nor complete. For I can form a sentence without meaning and I can find meaning without being able to form a sentence to express it.

Back to formal mathematics, it is not at all obvious that validity and derivability are equivalent. They are definitely strongly related, but not in all cases equivalent. Granted, for simple formulae, they are.

Edit; For a simple proof that English is not sound, Chomsky takes it all with "Colourless green ideas sleep furiously".

$\endgroup$
3
  • $\begingroup$ Ok, but is the application of the rules of inference really a purely syntactic operation? As I mentioned, we already know that the rules of inference are valid so anything that one can deduce from them, if it turns out that the premises are true, then such deduction must also be true. For example, let's talk about algebra. I can apply identities like (a+b)^2 = a^2+2ab+b^2 to substitute parts of an algebraic expression. But this substitutions are not meaningless, we know that the original expression and the new expression mean the same thing. Am I wrong? What am I missing? $\endgroup$
    – OldCrow
    Commented Jun 2, 2022 at 1:53
  • $\begingroup$ I'm trying to look at this from a different angle. Maybe it has something to do with the fact that we don't know a priori that the syntactic transformations we're applying will entail the desired result/meaning? For example, if I'm writing down the derivation for a given argument, by using truth tables alone I can't really know if I can transform the premises into the conclusion using rules of inference. And if I fail in this task, I cannot conclude that the derivation doesn't exist. Is this an effect due to the fact that the rules of inference are merely syntactic operations? $\endgroup$
    – OldCrow
    Commented Jun 2, 2022 at 1:59
  • $\begingroup$ Your question falls under the large category of totally equivalent questions regarding the distinction between studying a formal language using mathematics and doing mathematics using a formal language. I would suggest looking into that. About the second comment, the answer is yes. Technically yes. $\endgroup$
    – Jason
    Commented Dec 30, 2022 at 12:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .