0
$\begingroup$

I am relatively new to mathematics, but in the span of a few months, I have knocked out an informal proof/logic book (Solow), an abstract algebra book (Pinter), and am now reading through a real analysis book (Tao). I have developed the mechanical habits of how/when to write a particular styled proof...e.g. getting a sense of when proof by contradiction is easier...a growing familiarity with using contrapositives...etc. However, it occurred to me after posing this question here (When is proving the truth of a biconditional statement "the same" as proving that two propositions are logically equivalent?), that I still have no clue what exactly I am really doing when constructing a formal proof.

I think my major issue is that I am conflating the toolkit (and terminology) used in propositional logic with the toolkit (and terminology) used in predicate logic. The issue that I am having is differentiating between logical equivalency and logical entailment. When I am asked to prove some claim, for example, "If $A\subseteq B$, then $A \cup C \subseteq B \cup C$", then I have proven the statement if/when I show that the truth of the antecedent can be used to produce the truth of the consequent. This, I believe, is the premise of logical entailment.

However, let's say that I was having difficulties finding a direct proof of this. So, noting the logical equivalency between implication and contrapositive, I used a contrapositive-styled proof to demonstrate that I can use the negation of the consequent to produce the negation of the antecedent. ...Basically, it seems as though I am using logical equivalency and carry out a logical entailment.

This issue is exacerbated when I am asked in a predicate logic setting to prove that two statements are logically equivalent. In this context, I believe "logical equivalence" is better described as "reciprocal logical entailment", but I am not positive. Any help would be greatly appreciated!

$\endgroup$
2
$\begingroup$

When I am asked to prove some claim, for example, "If $A\subseteq B$, then $A \cup C \subseteq B \cup C$", then I have proven the statement if/when I show that the truth of the antecedent can be used to produce the truth of the consequent. This, I believe, is the premise of logical entailment.

Correct!

However, let's say that I was having difficulties finding a direct proof of this. So, noting the logical equivalency between implication and contrapositive, I used a contrapositive-styled proof to demonstrate that I can use the negation of the consequent to produce the negation of the antecedent. ...Basically, it seems as though I am using logical equivalency and carry out a logical entailment.

The 'logical equivalence' between implication and contrapositive is this: For any statements $\phi$ and $\psi$: $\phi$ logically implies $\psi$ if and only if $\neg \psi$ logically implies $\neg \phi$

Please note that this 'if and only if' is not your 'typical' logical equivalence, which is usually between two specific statements. Rather, this 'if and only if' is between two logical relationships; between two statements that already express some relationship between two statements. As such, this 'logical equivalence' between a logical implication and its contrapositive is more of a 'meta-logical' equivalence. The point is: you're not using both logical equivalence and logical implication ... but rather use a meta-logical equivalence to show a logical implication.

This issue is exacerbated when I am asked in a predicate logic setting to prove that two statements are logically equivalent. In this context, I believe "logical equivalence" is better described as "reciprocal logical entailment", but I am not positive. Any help would be greatly appreciated!

I am not sure in what sense you feel that the issue is being exacerbated in predicate logic ... could you maybe elaborate on this? Still, I can already say this: Two statements are logically equivalent if and only if they logically entail each other. This is true for any logic, whether propositional, predicate, or what have you. We could call this "reciprocal logical entailment" ... but logical equivalence is the very same idea.

$\endgroup$
1
$\begingroup$

We have to consider possible issues with different terminology...

In logic and mathematics, two statements are said to be logically equivalent, if they are provable from each other under a set of axioms, or have the same truth value in every model.

In propositional logic, there is a simple relation with formulas using the so-called bi-conditional connective:

two formulas $\varphi$ and $\psi$ are logically equivalent if and only if the statement $\varphi \leftrightarrow \psi$ is a tautology.

Using "entailment" to mean Logical consequence, we have two ways to formalize it: through proofs (syntactic consequence) and models (semantic consequence).

In the first case, we said that a set $\Gamma$ of formulas entails formula $\psi$ in a specified formal system $\mathsf F$ (in symbols: $\Gamma \vdash_{\mathsf F} \psi$) when $\psi$ is derivable from $\Gamma$ using the rules of the system.

In the second case, we said that $\Gamma$ entails $\psi$ (in symbols: $\Gamma \vDash \psi$) if and only if there is no interpretation in which all members of $\Gamma$ are true and $\psi$ is false.

For propositional logic as well as predicate logic, the two concepts produce the same results; see Soundness and Completeness.

Logical equivalence between two formulas is reciprocal entailment.


Simple examples with propositional logic and relation with predicate logic.

In propositional logic, where the truth-value of a formula is "checkable" in a mechanical way trough truth table procedure, we have that formula $\varphi \leftrightarrow \psi$ is a tautology (in symbols: $\vDash (\varphi \leftrightarrow \psi)$) when the columns of the two formulas in the t-t have the same truth-values.

Reading the t-t from $\varphi$ to $\psi$, this means that, in every valuation where $\varphi$ is True, also $\psi$ is, i.e. $\varphi \vDash \psi$.

Reading the t-t in reverse, we have also that $\psi \vDash \varphi$.

Thus:

$\vDash (\varphi \leftrightarrow \psi) \text { iff } \varphi \vDash \psi \text { and } \psi \vDash \varphi$.

In predicate logic, we have no mechanical procedure corersponding to t-t.

Formula $p ∨ ¬p$ is a tautology; $\forall x Px \lor \lnot \forall x Px$ is a valid predicate logic formula that is an instance of a tautology.

Formula $∀x(x=x)$ is a valid formula of predicate logic with equality that is not a propositional tautology.

$\endgroup$
3
  • $\begingroup$ I am slightly confused by your definitions. Logically equivalent shows up in your definition of material equivalence. I am not sure I understand the distinction between the logical equivalence that appears in your material equivalence definition versus the logical equivalence that shows up in your definition of logical equivalence. Or are you saying that, depending on the context, logical equivalence means different things. $\endgroup$
    – S.Cramer
    Feb 6 '20 at 14:12
  • $\begingroup$ I think, perhaps, that is why I am confused. As you say, two statements are logically equivalent if the biconditional between the two statement evaluates to a tautology. However, you also say that "Logical equivalence between two formulas is reciprocal entailment". This seems strange to me. Entailment only means that a true statement implies a true statement, right? How is this the same as saying "The two proposition's truth tables are identical" $\endgroup$
    – S.Cramer
    Feb 6 '20 at 14:24
  • $\begingroup$ ohhhhhh. Gotch ya gotch ya. Thank you! $\endgroup$
    – S.Cramer
    Feb 6 '20 at 14:47

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.