Check each partial order axiom. For every $(a,b)$, $a\le a$ and $b\ge b$, so $S$ is a reflexive relation. If both $(a,b)S(c,d)$ and $(c,d)S(a,b)$, the first coordinates satisfy $a\le c\le a$ and the second coordinates satisfy $b\ge d\ge b$. Therefore $a=c$ and $b=d$, which proves $S$ is an antisymmetric relation.

Finally, if $(a,b)S(c,d)$ and $(c,d)S(e,f)$, then $a\le c\le e$ and $b\ge d\ge f$. Hence $(a,b)S(e,f)$, making $S$ a transitive relation. All three axioms hold, so $S$ is a partial order. It is a product order, with the usual order on the first coordinate and the reversed order on the second.

Take $u=(1,1)$ and $v=(1,2)$. Their first coordinates are equal, so both $uRv$ and $vRu$ hold, although $u\ne v$. Thus $R$ is not an antisymmetric relation, and hence it is not a partial order. The failure arises because its comparisons ignore the second coordinate entirely.

The contrapositive is that an integer perfect square has residue $0$ or $1$ modulo $4$. Let $n=t^2$ for an integer $t$. If $t=2u$ is an even number, then $t^2=4u^2\equiv 0(\mathrm{mod}4)$. If $t=2u+1$ is an odd number, then $t^2=4u(u+1)+1\equiv 1(\mathrm{mod}4)$. These exhaust the possible parities of an integer. Thus a residue of $2$ or $3$ excludes being a perfect square, as required by the contrapositive.

Suppose, for a proof by contradiction, that an integer $n$ is both an even number and an odd number. Then $n=2u$ and $n=2v+1$ for some integers $u,v$. Subtracting yields $u-v=1/2$. The left side is an integer, while $1/2$ is not. This contradiction proves that no integer is both even and odd.

For $n=1$, both sides are $1/3$. Assuming the formula through $n$, adding the next term givesThe last expression is the required formula at $n+1$, completing mathematical induction. The partial fraction decompositionprovides a second explanation: this is a telescoping sum.

For the base case $n=2$, the product is $1-1/4=3/4=(2+1)/(2\cdot 2)$. Assume the identity holds for some $n\ge 2$. Multiplying by the next factor givesThis is the desired expression with $n$ replaced by $n+1$, so mathematical induction proves the identity for every $n\ge 2$. The factorization $1-i^{-2}=(i-1)(i+1)/i^2$ also explains the cancellation as a telescoping product.

Take $(a,b,c,n)=(1,4,2,6)$. These are four distinct positive integers and $n\ge 3$. Their products are $ac=2$ and $bc=8$, whose difference is $6$, so $ac\equiv bc(\mathrm{mod}6)$. Here the correct reduced modulus is $6/\gcd (2,6)=3$, and indeed $1\equiv 4(\mathrm{mod}3)$. The example illustrates why cancelling a noninvertible factor may change the modulus in modular arithmetic.

Let $d=\gcd (c,n)$, $c=d{c}^{\prime }$, and $n=d{n}^{\prime }$. The preceding part gives $\gcd (c^{\prime },n^{\prime })=1$. The integer congruence on the left is equivalent toBy Euclid's lemma, coprimality of $c^{\prime }$ and $n^{\prime }$ makes this equivalent to $n^{\prime }\mid a-b$. The reverse implication is also immediate by multiplying a divisibility relation by $d{c}^{\prime }$. ThereforeThis is cancellation of a common factor in a congruence. The printed equality sign in the right-hand expression is interpreted as equality of residue classes, hence the displayed integer congruence. Ordinary equality of the integers $a,b$ would be false: the following example has $a\ne b$.

Let $d=\gcd (c,n)$, and write $c=d{c}^{\prime }$, $n=d{n}^{\prime }$ with positive integers $c^{\prime },n^{\prime }$. If an integer $e>1$ divided both $c^{\prime }$ and $n^{\prime }$, then $de$ would divide both $c$ and $n$, contradicting the maximality of their greatest common divisor $d$. Thus $\gcd (c^{\prime },n^{\prime })=1$. Equivalently, Bézout's identity for $c,n$ can be divided by $d$ to express $1$ as an integer combination of $c^{\prime },n^{\prime }$.

Divide the divisibility relation $91\mid 26x-39$ by $13$ to obtain $7\mid 2x-3$. Since $2\cdot 4\equiv 1(\mathrm{mod}7)$, multiplication by the modular multiplicative inverse gives $x\equiv 12\equiv 5(\mathrm{mod}7)$. Therefore all integer solutions are $x=5+7q$, $q\in \mathbb{Z}$.

Modulo $91=13\cdot 7$, the choices $q=0,\dots ,12$ giveThey are distinct residue classes: equality of two such classes would imply $91\mid 7(q-q^{\prime })$, hence $13\mid q-q^{\prime }$. Every integer $q$ is congruent to one of those thirteen choices, so the list is exhaustive.

The Euclidean algorithm givesso $\gcd (754,91)=\gcd (26,91)=13$. Since $13\mid 39$, the criterion for a linear congruence guarantees a solution. One can also exhibit it directly: $26\cdot 5+91(-1)=39$, or in the original coefficients,Thus $x=5$ is a solution, with an explicit Bézout coefficient certificate.

Let $u$ be fresh, not free in any of the three universal premises. Universal quantifier elimination rule gives $\neg P(u)\vee R(c,u)$, $Q(u)\to R(c,u)$ and $P(u)\vee Q(u)$. Apply disjunction elimination rule to the last formula.

In the $P(u)$ branch, apply disjunction elimination rule to $\neg P(u)\vee R(c,u)$. Its $\neg P(u)$ case contradicts $P(u)$ by negation elimination rule, and logical falsity elimination rule then gives $R(c,u)$. Its $R(c,u)$ case already gives that conclusion. Discharge those two inner case assumptions to obtain $R(c,u)$ under the outer $P(u)$ assumption. In the outer $Q(u)$ branch, the modus ponens rule applied to $Q(u)\to R(c,u)$ gives $R(c,u)$ directly.

Discharge the two outer case assumptions by disjunction elimination rule. The conclusion $R(c,u)$ now depends only on the universal premises, in which $u$ is not free. Universal quantifier introduction rule therefore gives $\forall xR(c,x)$. All case assumptions have been discharged, and the argument requires no classical reductio ad absurdum.

Choose arbitrary fresh variables $y,x,z$ and assume $H=((x=y\vee y=z)\wedge P(y))$ under label $a$. The conjunction elimination rule gives $x=y\vee y=z$ and $P(y)$. Apply the disjunction elimination rule to the equality disjunction.

In the case $x=y$, the supplied symmetry rule gives $y=x$, and the equality elimination rule applied to $P(y)$ gives $P(x)$. Disjunction introduction rule gives $P(x)\vee P(z)$. In the case $y=z$, equality elimination rule applied directly to $P(y)$ gives $P(z)$; the other disjunction introduction rule gives the same conclusion $P(x)\vee P(z)$. Discharge the two equality case assumptions by disjunction elimination rule.

Discharge $a$ with the implication introduction rule. There are now no undischarged assumptions. Use the universal quantifier introduction rule successively for $z$, then $x$, then $y$, yieldingFreshness holds at every generalization because the sole temporary assumption has already been discharged; the arbitrary variables are not tied to any premise.

Temporarily assume $Q(c)$ under label $a$. The implication premise and the modus ponens rule yield $\forall x(P(x)\leftrightarrow P(c))$. Instantiate it at $c^{\prime }$ using the universal quantifier elimination rule, obtaining $P(c^{\prime })\leftrightarrow P(c)$. Its right biconditional elimination rule gives $P(c)\to P(c^{\prime })$.

Apply the modus ponens rule with the premise $P(c)$ to obtain $P(c^{\prime })$. Together with $\neg P(c^{\prime })$, negation elimination rule gives $\perp$. Discharge $a$ using the negation introduction rule to conclude $\neg Q(c)$. Nothing assumes that the two constant symbols denote different objects; if they denoted the same object, the stated premises would themselves already be inconsistent.

Apply the universal quantifier elimination rule to the universal premise with term $c$, obtaining $P(c)\leftrightarrow Q(c)$. The left biconditional elimination rule gives $P(c)\to Q(c)$. Use the premise $P(c)$ and the modus ponens rule to derive $Q(c)$. The existential quantifier introduction rule with witness $c$ yields $\exists xQ(x)$. Substitution of a constant is capture-free here, so both quantifier side conditions hold.

Write $D(\varphi ,\psi )=\neg (\neg \varphi \wedge \neg \psi )$. We derive the two disjunction introduction rules and the disjunction elimination rule without using any disjunction rule inside the derivations.

For left introduction, start with $\varphi$ and temporarily assume $\neg \varphi \wedge \neg \psi$. The conjunction elimination rule gives $\neg \varphi$, and the negation elimination rule gives $\perp$. Discharge the temporary conjunction by the negation introduction rule, concluding $D(\varphi ,\psi )$. For right introduction, start with $\psi$ and use the right conjunction elimination rule to obtain $\neg \psi$ instead. Thus either input derives the required encoded disjunction.

For elimination, suppose $D(\varphi ,\psi )$ is available, together with a derivation of $\kappa$ from an additional assumption $\varphi$ and a derivation of $\kappa$ from an additional assumption $\psi$. Keep their common external context fixed. Temporarily assume $\neg \kappa$ under label $a$. Temporarily assume $\varphi$ under label $b$ and insert the supplied first branch derivation to obtain $\kappa$. Negation elimination rule gives $\perp$, so negation introduction rule discharges $b$ and gives $\neg \varphi$. Repeat with a temporary assumption $\psi$ under label $c$ and the supplied second branch derivation, discharging $c$ to obtain $\neg \psi$.

Conjunction introduction rule now gives $\neg \varphi \wedge \neg \psi$. Its negation $D(\varphi ,\psi )$ gives $\perp$ by negation elimination rule. The supplied reductio ad absurdum rule discharges $a$ and yields $\kappa$. This discharges the two branch assumptions as required and proves the encoded elimination rule. Its last step uses classical propositional logic; the same encoded elimination principle is not generally available in Intuitionistic propositional logic.

Let $N(\varphi ,\psi )$ abbreviate $\neg \varphi \wedge \neg \psi$. Suitable rules areTheir derivations require no new axiom. For introduction, apply the conjunction introduction rule to the two premises, obtaining $\neg \varphi \wedge \neg \psi$, which is exactly the abbreviation. For left and right elimination, unfold the abbreviation and apply the corresponding conjunction elimination rule. These are therefore derived rules for the NOR connective.

An equivalent subproof presentation of introduction permits one subproof from assumption $\varphi$ to $\perp$ and another from assumption $\psi$ to $\perp$: use the negation introduction rule to discharge each assumption, then apply the conjunction introduction rule. If elimination is desired in contradiction form, combine the left projection with $\varphi$, or the right projection with $\psi$, using the negation elimination rule. All these presentations reduce directly to the permitted rules.

Assume $E\to G$ under label $a$, $F\to G$ under label $b$, and $E\vee F$ under label $c$. A temporary case assumption $E$ gives $G$ by the modus ponens rule using $a$. A temporary case assumption $F$ gives $G$ by the modus ponens rule using $b$. The disjunction elimination rule discharges these case assumptions and concludes $G$ under $a,b,c$.

Apply the implication introduction rule three times, discharging $c$, then $b$, then $a$. The resulting theorem isThe displayed parentheses make explicit the right association of the source formula.

Use the disjunction elimination rule on the outer disjunction. In its left branch, assume $P\vee Q$ and apply the disjunction elimination rule again: from a case assumption $P$, the disjunction introduction rule gives $P\vee R$; from a case assumption $Q$, the premise $Q\to R$ and the modus ponens rule give $R$, then the disjunction introduction rule gives $P\vee R$. Discharging those two inner case assumptions yields $P\vee R$ under the left outer branch.

In the right outer branch, assume $R\vee S$. A case assumption $R$ gives $P\vee R$ by the disjunction introduction rule. A case assumption $S$, together with the premise $\neg S$, gives $\perp$ by the negation elimination rule, and then $P\vee R$ by logical falsity elimination rule. Discharge these inner case assumptions with the disjunction elimination rule.

Both outer branches now have the same conclusion. Discharge the two outer case assumptions with the disjunction elimination rule to obtain $P\vee R$ under exactly the stated premises.

Keep the four given premises in context and assume $P$ under label $a$. The modus ponens rule applied to the first two premises gives $Q\vee R$ and $\neg S$. Apply the disjunction elimination rule to $Q\vee R$ as follows.

Under a case assumption $Q$, the premise $Q\to S$ gives $S$ by the modus ponens rule. Together with $\neg S$, the negation elimination rule gives $\perp$, and the supplied logical falsity elimination rule gives $R$. Under the other case assumption $R$, the required conclusion $R$ is already available. Discharge both case assumptions with the disjunction elimination rule to conclude $R$.

Finally discharge $a$ with the implication introduction rule, giving $P\to R$. The premise $S\to Q$ is not needed: a derivation is permitted to leave a premise unused.