Bridge to Abstract Mathematics: Mathematical Proof and Structures

6.1 CONCLUSIONS INVOLVING V, FOLLOWED BY 3 191

in Article 4.3. But in junior-senior level mathematics, definitions involving
3 abound. As a consequence, many of the proofs that students at that level
are asked to understand or write are of statements whose conclusion in-
volves the universal quantifier V followed by the existential quantifier 3.
Proofs of this type will be the object of our study in this article. Here are
a few important definitions that involve the quantifier 3.

EXAMPLE 1 (Elementary Algebra) A real number x is said to be rational if
and only if there exist integers p and q (q # 0) such that x = p/q.

EXAMPLE 2 (Elementary Number Theory) Let m and n be integers. We say
that m divides n, denoted mln, if and only if there exists an integer r such
that n = mr (recall Exercise 7, Article 3.4 and Example 7, Article 5.4).

EXAMPLE 3 (Linear Algebra) A square matrix A, ., is said to be invertible if
and only if there exists a matrix B,. , such that AB = BA = I,, where I,
is the n x n identity matrix, that is, I, = (dij),. ,, where dij = {k
;;;I-

EXAMPLE 4 (Elementary Topology) Let S be a subset of the real numbers R.

An element x E S is said to be an interior point of S if and only if there

exists 6 > 0 such that N(x; 6) c S, where N(x; 6) represents the open in-

terval (x - 6, x + 6) and is referred to as the 6 neighborhood of x. Note

that N(x; 6) = {y E RI lx - yl < 6). S is said to be an open subset of R

if and only if each of its points is an interior point.

EXAMPLE 5 (Advanced Calculus) An infinite sequence {x,) of real numbers

is said to converge to the real number x, denoted x, -, x or limn,, x, = x,

if and only if, to every positive real number e, there corresponds a positive

integer N such that Ix, - xl < c whenever n 2 N. In symbols, x, + x o

Before studying some proofs of statements whose conclusion involves

the sequence (V)(3) of quantifiers, let us state some principles governing

the approach to take to such proofs. Especially, let us review some facts

involving dependence between quantified variables. In discussing the

logical relationship between statements of the form (3y)(Vx)p(x, y) and

(Vx)(3y)p(x, y) (the first of these is in general stronger than the second; re-

call Theorem 1, Article 3.4), we saw that the sequence (Vx)(3y) of quantified

variables in the weaker statement signals a possible dependence of y on

x, which, however, does not occur if the corresponding stronger statement

(3y)(Vx)p(x, y) is also true. The student may do well to review Article 3.4,

Exercises 6 and 7, and the remark immediately preceding Theorem 2.

The next example deals with some general situations.