2
$\begingroup$

The definition of an equivalence relation is that of a binary relation between distinct elements of a set. Partial orders have a similar definition.

Seeing as this could include things like the set of all people, as well as standard sets of numbers, could an equivalence relation, and by extension, a partial order, be constructed over the set of Boolean statements (such as 'It will rain tomorrow') which have true or false values?

I have conjectured and attempted to prove that biconditional implication $\leftrightarrow$ is an equivalence relation.

Proof: Let $p, q, r$ be propositions with value true or false.

Claim 1: $\leftrightarrow$ is reflexive. If $p$ is a proposition with value true or false, $\neg p \lor p$ is a tautology, but by the law of material implication $\neg p \lor p \equiv p \to p$. So $p \to p$ together with itself gives $p \leftrightarrow p$ and $\leftrightarrow$ is reflexive.

Claim 2: $\leftrightarrow$ is symmetric. Suppose $p \leftrightarrow q$. Then by definition, $p \to q \land q \to p$. The commutative law gives $q \to p \land p \to q \equiv q \leftrightarrow p$ and hence $\leftrightarrow$ is symmetric.

Claim 3: $\leftrightarrow$ is transitive. Suppose $p \leftrightarrow q \land q \leftrightarrow r$. Using definitions, the associative & commutative laws and transitivity of $\to$ we have $$(p \to q \land q \to p) \land (q \to r \land r \to q)$$ $$\equiv (p \to q \land q \to r) \land (r \to q \land q \to p)$$ $$\equiv (p \to r) \land (r \to p)$$ $$\equiv p \leftrightarrow r$$

and so $\leftrightarrow$ is transitive.

By proof of claims 1, 2 and 3, $\leftrightarrow$ is an equivalence relation.

$\endgroup$
2
  • $\begingroup$ Note that partial orders are usually required to be antisymmetric. Relations that are reflexive and transitive but possibly not antisymmetric are often called preorders. $\endgroup$
    – hmakholm left over Monica
    Commented Dec 22, 2017 at 13:34
  • $\begingroup$ In your proof of claim 3, you should be careful that $(p \to q) \land (q \to r)$ does imply $p \to r$ but is not actually equivalent to $p \to r$ (check it with $p$ false, $q$ true and $r$ false). $\endgroup$
    – Luca Bressan
    Commented Dec 22, 2017 at 18:06

1 Answer 1

Reset to default
3
$\begingroup$

To be sure, biconditional implication is an equivalence relation.

How to prove that most directly depends on your official definition of the biconditional. So there's no "right" answer here. You give one line of argument which works given enough background apparatus.

But of course, if you define biconditional implication semantically by the standard truth-table, then reflexivity and symmetry can be trivially read off the truth-table, and the most direct proof of transitivity is by an eight-line brute force calculation. If you define the biconditional proof-theoretically by its natural deduction rules, then the most direct proof that it is an equivalence relation is by three trivial natural deduction proofs.

$\endgroup$

You must log in to answer this question.

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