Conjunctions - Loops of Implications - Forms of Argument

Mathematical Writing - Vivaldi Franco 2014

Conjunctions - Loops of Implications
Forms of Argument

A conjunction is a statement of the type

$$P$$ and $$Q$$.

The statements $$P$$ and $$Q$$ are called the conjuncts. As with implications, conjunctions are not necessary presented explicitly.

A direct proof of a conjunction consists of the separate proofs of the two conjuncts, which must be differentiated clearly. It’s common practice to put the conjuncts in an ordered list, say (i) and (ii). (If there are more than two conjuncts, the list may be extended using lower-case Roman numerals: (iii), (iv), etc.) Then the proof itself should use the matching labels (i) and (ii), and in each case we should begin by stating what we intend to prove.

PROOF.

(i)

(ii)

Equality of sets is the canonical hidden conjunction:

$$A=B.$$

What are the conjuncts? Two sets are equal if they have the same elements, namely every element of $$A$$ is an element of $$B$$, and vice-versa.

$$ (A=B)\,\,\Leftrightarrow \,\,(A\subset B)\,\wedge \,(B\subset A). $$

The structure of the proof is now determined by the definition (4.19) of a subset.

PROOF.

(i)

(ii)

Another basic conjunction is the equivalence of two statements:

$$P$$ if and only if $$Q$$.

The equivalence operator $$\Leftrightarrow $$ is the conjunct of an implication and its converse—see (4.12).

PROOF.

(i)

(ii)

We could replace either part by a proof of the contrapositive implication.

The following theorem is of this type: it provides an alternative characterisation of primality.

Theorem. 3 A natural number $$n>1$$ is prime if and only if $$n$$ divides $$(n-1)! + 1$$.

This theorem says $$P\wedge Q$$, where

$$P\,=\, \forall n > 1, \,\,$$ ($$n$$ is prime) $$\,\,\Rightarrow \,\,(n\mid (n-1)!+1)$$

$$Q\,=\, \forall n > 1,\,\,(n\mid (n-1)!+1) \,\,\Rightarrow \,\,$$ ($$n$$ is prime).

The outline of the proof is now clear.

PROOF.

(i)

(ii)

The adverb ’precisely’ may be used to turn a one-sided implication into an equivalence, hence a conjunction. Thus the proof of the statement

The set $$\mathbb {Z}/n\mathbb {Z}$$ is a field precisely if $$n$$ is prime.

will have to be carried out in two stages.

PROOF. Let $$n\in \mathbb {N}$$ be given.

(i)

(ii)

7.4.1 Loops of Implications

The equivalence of several statements is sometimes expressed by a chain of implications in which the last statement in the chain coincides with the first one, thus forming a loop. This type of argument combines conjunctions with implications.

The equivalence of two statements $$P_1$$ and $$P_2$$, may be viewed as a loop:

$$ P_1\Rightarrow P_2\Rightarrow P_1. $$

More generally, we consider loops of $$n$$ implications:

$$ P_1\Rightarrow P_2\Rightarrow \cdots \Rightarrow P_{n-1}\Rightarrow P_n\Rightarrow P_1. $$

Proving all implications in the loops amounts to proving that all statements are equivalent, namely that $$P_i\Leftrightarrow P_j$$, for all $$i,j=1\ldots ,n$$. This follows from the transitivity of the implication operator.

For example, let $$G$$ be a group and $$H$$ a subgroup of $$G$$. A left coset of $$H$$ in $$G$$ is a set $$gH = \{gh: h \in H\}$$ where $$g$$ is an element of $$G$$. [This is a variant of the algebraic product of sets (2.21)]. A result in group theory states that if $$x,y$$ are elements of $$G$$, then the following statements are equivalent:

·  ($$a$$) $$xH = yH$$

·  ($$b$$) $$xH \subseteq yH$$

·  ($$c$$) $$xH \cap yH \ne \emptyset $$

·  ($$d$$) $$y^{-1}x \in H$$.

These are usually proved in a circle, for example ($$a$$) $$\Rightarrow $$ ($$b$$) $$\Rightarrow $$ ($$c$$) $$\Rightarrow $$ ($$d$$) $$\Rightarrow $$ ($$a$$), but other arrangements are possible, e.g., ($$a$$) $$\Leftrightarrow $$ ($$b$$) $$\Rightarrow $$ ($$c$$) $$\Rightarrow $$ ($$d$$) $$\Rightarrow $$ ($$b$$).

In Chap. 8 we will use a loop of implications to show the equivalence of four formulations of the principle of induction.