1
$\begingroup$

Really confused on the terminology here.

According to a few resources as-linked:

Valid is defined as a logical form where it is impossible to have true premises leading to a false conclusion. It doesn't mean the premises are necessarily true. Just that if they were true, the conclusion would need to be true as well.

Sound is defined as a valid logical form where the premises are indeed true.

But then we also have "semantic consequence" denoted $\Gamma \vDash \varphi$ which normally means "if everything on the lefthand side is true, then the stuff on the righthand side is true." Sometimes this is also referred to as "validity" or "tautology."

But this also seems like it is clashing with the definition of "sound" as well.

So I'm really quite confused how we're supposed to be defining and separating these terms out. I'm seeing different answers on Wiki, different answers in books, different answers in other Math StackExchange posts, etc.

I'm going nuts over here trying to separate all these concepts (metalogic vs. logic, soundness vs. validity, semantic vs. syntactic, etc) when every other resource is constantly merging stuff together in vague ways.

Once and for all what is the definition of validity? Soundness? Completeness? Syntactic consequence? Semantic consequence? Logical consequence? Tautology? Theorem? Axiom? Inference? Formula? Sentence? Expression? Proposition? Statement? Relation? Connective? Operator? Are any of these actually synonyms of each other? How are they different?

$\endgroup$
  • 1
    $\begingroup$ The definitions you're asserting here certainly don't match how I usually see the words used. $\endgroup$ – Henning Makholm Sep 10 '18 at 23:32
  • 2
    $\begingroup$ @user525966 The definitions you give for "valid" and "sound" strike me as more common in philosophical literature than in mathematics or (formal) logic. Obviously there is some connection intended between these more "philosophy" definitions and the mathematical ones, but they aren't the same. Personally, I find a lot of "logic for philosophy" to be quite bad and to create more confusion than it dispels. $\endgroup$ – Derek Elkins Sep 10 '18 at 23:59
  • 1
    $\begingroup$ I have literally never heard the $\vDash$ relation referred to as a "tautology". A tautology is the same thing as a valid formula of propositional logic. $\endgroup$ – Henning Makholm Sep 11 '18 at 0:01
  • 2
    $\begingroup$ In $\vDash\varphi$ is is not $\vDash$ that is a tautology. Rather, $\vDash\varphi$ asserts that $\varphi$ is a semantic consequence of nothing -- which happens to be the case when $\varphi$ is a tautology. $\endgroup$ – Henning Makholm Sep 11 '18 at 0:39
  • 1
    $\begingroup$ @user525966: It means that $\varphi$ is "valid" and "always true" and "a semantic consequence of the empty set". If $\varphi$ is a propositional formula this is also expressed by the word "tautology". The word "sound" is not used about formulas. $\endgroup$ – Henning Makholm Sep 11 '18 at 11:00
4
$\begingroup$

It is important to stick to mathematical logic here as opposed to the definitions from philosophy. The first sentence of the wikipedia

In mathematical logic, a logical system has the soundness property if and only if every formula that can be proved in the system is logically valid with respect to the semantics of the system.

while not fully precise, is the sense in which 'sound' is generally used in mathematical logic. This corresponds to a system having valid axioms and validity-preserving rules of inference, so you can see how it corresponds loosely to the philosophical notion of true premises and correct (i.e. truth-preserving) argumentation.

As for validity, the wikipedia sentence

A formula of a formal language is a valid formula if and only if it is true under every possible interpretation of the language. In propositional logic, they are tautologies.

uses 'valid' in the way it is used in mathematical logic. Here the connection to the philosophical notion of a valid argument that you cite is a little less direct. Let $A$ and $B$ be your premises and $C$ your conclusion. And say $$ (A\land B) \to C $$ is valid in the mathematical sense. That means that $A\land B \to C$ is true in any interpretation, which means that it is impossible for $A$ and $B$ to be true and for $C$ to be false. So the two notions of validity connected, but even more loosely than was the case for soundness.

Note that the validity of $(A\land B)\to C$ is the same thing as $C$ being a semantic consequence of $A$ and $B,$ i.e. $$ A,B\models C$$ which has more of the flavor of "a valid argument from $A$ and $B$ to $C$," though strictly speaking, there's no 'argument' here. (However, the syntactic variation $A,B\vdash C,$ which is equivalent in the presence of a completeness theorem, means there's a proof of $C$ from assumptions $A$ and $B$... that's more of an 'argument'.)

I've tried to be conciliatory to the philosophical definitions here, but in math it's important to get comfortable with the fact that precise definitions vary from treatment to treatment. (Heck, the other day I learned that not all books have the same definition of 'compact set' in a general topological space, which was a definition that I thought was more or less sacrosanct.) It should also go without saying that the definitions don't need to conform to the colloquial meaning of the words, though it's nice when they're at least not wildly misleading.

In a field with as many moving parts in mathematical logic we will often need to adjust and adapt our terminology as we develop new ideas and try to apply mathematical logic to more exotic situations. Even in the beginning of my answer where I gave some 'general purpose' definitions and remarks, I had some particular contexts in mind, and we will need to make these things fully precise in any detailed treatment. For instance, when we move to the specific context of classical propositional logic, "valid" becomes synonymous with "tautology" and we make precise the ideas of "interpretation" and "truth" in a given interpretation. When we flesh things out in a given context (especially when working in more exotic situations than, say, classical propositional or predicate logic) everything I said is subject to revision.

$\endgroup$
  • 1
    $\begingroup$ As a rough guideline, if you see words like "argument", "logical form", "syllogism" or a heavy emphasis on "premises" and "tautology", you are probably in "philosophy logic" land. In mathematical logic land, you'll more see "(well-formed )formulas", "proof", "derivation", "rules( of inference)", "model", "semantics", and, obviously, a heavy emphasis on symbolic expressions. This isn't a perfect discriminator though, especially for older works. $\endgroup$ – Derek Elkins Sep 11 '18 at 0:31
  • $\begingroup$ @Derek Agree with all of these except “tautology” is used quite a bit in mathematical logic. $\endgroup$ – spaceisdarkgreen Sep 11 '18 at 17:46
0
$\begingroup$

The notation $\Gamma \models \varphi$ means $\varphi$ is true in every structure in which all statements in $\Gamma$ are true.

The notation $\Gamma \vdash \varphi$ means $\varphi$ can be proved by using the statements in $\varphi$.

The latter depends on some notion of proof. One wants such a notion to satisfy three desiderata:

  • Soundness, i.e. if $\Gamma\vdash\varphi$ then $\Gamma\models\varphi.$
  • Completeness, i.e. if $\Gamma\models\varphi$ then $\Gamma\vdash\varphi.$
  • Effectiveness, i.e. there is a proof-checking algorithm, which will correctly identify its input as either a valid proof or not.

Note that $\Gamma$ is allowed to be a set of statements whereas $\varphi$ is just one statement. So why not conjoin all the statements in $\Gamma$ into one? The problem here is that if one is allowed to join infinitely many statements into one, then putting such an infinite conjunction in the role of $\varphi$ has the result that one cannot satisfy all three desiderata simultaneously. Any proof of that takes a lot of work.

$\endgroup$
  • $\begingroup$ Does $\vDash \varphi$ (empty left-hand side) mean $\varphi$ is a tautology? $\endgroup$ – user525966 Sep 11 '18 at 7:45
  • $\begingroup$ @user525966 : It means $\varphi$ is true in every "structure" (I haven't been explicit here about what a "structure" is). Sometimes people reserve the word "tautology" for things in propositional logic rather than predicate logic (predicate logic uses universal and existential quantifiers; propositional logic only uses Boolean connectives such as "and", "or", and "not"). Sometimes people express it by saying this means $\varphi$ is "universally valid". $\endgroup$ – Michael Hardy Sep 11 '18 at 17:56
  • $\begingroup$ How would you describe "structure"? Is this the same as "interpretation" or "model"? What does it mean? $\endgroup$ – user525966 Sep 11 '18 at 18:25
  • $\begingroup$ @user525966 In the standard semantics of classical first order logic, sentences are interpreted in structures, i.e. structures are the interpretations. For instance, the first order sentence $\forall x \exists y(x R y)$ can be interpreted in the structure $(\mathbb R, <)$ (where we're interpreting the relation symbol $R$ as $<$) to mean the reals have no maximal element. So it's true in this structure. If a set of first order sentences are all true in a structure, we say the structure is a model of the set of sentences. en.wikipedia.org/wiki/Structure_(mathematical_logic) $\endgroup$ – spaceisdarkgreen Sep 12 '18 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.