Wrong Definitions - Existence and Definitions

Mathematical Writing - Vivaldi Franco 2014

Wrong Definitions
Existence and Definitions

As we did in Sect. 7.7 for logical arguments, we consider here some common mistakes made in definitions. A faulty definition may imply that the object being defined does not exist at all, or that it is not the one we had in mind, or that there is more than one object that fits the description.

We begin with an incorrect function definition which can be put right in several ways.

WRONG DEFINITION Let $$f$$ be given by:

$$ f{:}\,\mathbb {Q} \rightarrow \mathbb {Q}\qquad \qquad f(x) = x^2y+1. $$

The mistake is plain but fatal: the expression $$f(x)$$ involves the unspecified quantity $$y$$. As defined, $$f$$ is not a function. There are many legitimate interpretations of what this formula could mean, each resulting in a different function.

1.

2.

3.

In the second example, the existence of a function requires more conditions than those given. The definition relies on a hidden assumption, so that using it adds extra information (we say that the definition is creative).

WRONG DEFINITION Let $$A$$ and $$B$$ be sets, and let $$f,g: A\rightarrow B$$ be functions. We define the function $$h=f+g$$ as follows:

$$ h{:}\,A\rightarrow B\qquad x\mapsto f(x)+g(x). $$

The hidden assumption is that the elements of the co-domain can be added together. However, $$B$$ may be a set where addition is not defined (e.g., $$f$$ and $$g$$ are predicates) or which is not closed under addition (e.g., $$B$$ is an interval). We give a more restrictive definition without hidden assumptions.

DEFINITION Let $$A$$ be a set, let $$B$$ be a set closed under addition, and let $$f,g{:}A\rightarrow B$$ be functions. ...

In the next example we attempt to extend to modular arithmetic the concept of the reciprocal of an element, but our definition has a hidden assumption.

WRONG DEFINITION Let $$m$$ be a natural number, and let $$a$$ be an integer. If $$[a]_m\not =[0]_m$$, then we define the multiplicative inverse $$[a]_m^{-1}$$ as follows:

$$ [a]_m^{-1} \mathop {=}\limits ^\mathrm{def} [b]_m \quad \text {where} \quad [a]_m [b]_m=[1]_m. $$

Take $$m=6$$ and $$a=3$$. We have $$[3]_6 \not =[0]_6$$, but the equation $$[3]_6[x]_6=[1]_6$$ has no solution. What went wrong? We have assumed that the implication

$$ {\mathrm{if\,}}\quad a\ne 0 \quad {\mathrm{and\,}}\quad ab=ac, \quad {\mathrm{then\,}}\quad b=c, $$

which is valid for real or complex numbers, is also valid for congruence classes. Requiring that $$[a]_m\not =[0]_m$$, namely that $$a$$ is not divisible by the modulus is not enough; for this implication to hold, we must assume that $$a$$ is co-prime to the modulus.

DEFINITION Let $$m$$ be a natural number and let $$a$$ be an integer co-prime to $$m$$. We define the multiplicative inverse $$[a]_m^{-1}$$ of $$[a]_m$$ as follows...

In the following definition both existence and uniqueness are problematic.

WRONG DEFINITION Let $$p\in \mathbb {Z}[x]$$, and let $$z_p$$ be the root of $$p$$ having smallest modulus.

If $$p$$ has degree zero, then $$z_p$$ does not exist, so this definition relies on the hidden assumption that $$p$$ has positive degree. If $$z_p$$ exists, then it may still not be unique (e.g., $$p=x^2+1$$), but the use of the definite article (’the root’) implies that it is. Requiring that $$p$$ be non-constant solves the existence problem. The way we address uniqueness depends on the context. If we merely require that no root of $$p$$ has smaller modulus than $$z_p$$, then we don’t need uniqueness.

DEFINITION Let $$p\in \mathbb {Z}[x]$$ with $${\mathrm{deg}}(p)>0$$, and let $$z_p$$ be a root of $$p$$ with smallest modulus.

This definition does not identify $$z_p$$; it tells us that $$z_p$$ is a member of a well-defined non-empty set, but this set may have more than one element. If, on the other hand, we require a specific complex number, then we must supply additional information. In the following definition we impose a condition on the argument of $$z_p$$, which removes any ambiguity.

DEFINITION Let $$p$$ be a non-constant polynomial with integer coefficients, and let $$z_p$$ be the root of $$p$$ with smallest modulus. If there is more than one root with this property, we let $$z_p$$ be the root with smallest non-negative argument.

In our final example, the definition hides a subtle lack of uniqueness.

WRONG DEFINITION Let $$x\in [0,1]$$, and let $$f$$ be the function that associates to $$x$$ its binary digits sequence

$$ f{:}\,[0,1]\rightarrow \{0,1\}^\mathbb {N}\qquad x\mapsto (c_1,c_2,\ldots ), $$

where

$$\begin{aligned} x=\sum _{k=1}^\infty \frac{c_k}{2^k}\qquad c_k\in \{0,1\}. \end{aligned}$$

(9.10)

(The co-domain of $$f$$ is the set of all infinite binary sequences, see Sect. 3.5.1.) What’s wrong with this definition? Consider the rational numbers

$$ x_n=\frac{1}{2^n}=\sum _{k=1}^\infty \frac{1}{2^{k+n}}\qquad n\geqslant 1. $$

If we write $$x_n$$ in the form (9.10), then the above identity shows that there are two binary representations, namely

$$\begin{aligned} (\underbrace{0,\ldots ,0}_{n-1},1,0,0,0,\ldots ) \qquad {\mathrm{and}}\qquad (\underbrace{0,\ldots ,0}_{n-1},0,1,1,1,\ldots ). \end{aligned}$$

(9.11)

So the function $$f$$ is not uniquely defined at these rationals and, more generally, at all rationals of the form

$$ \sum _{k=1}^{n-1} \frac{c_k}{2^k} \,+\,x_n $$

where $$c_1,\ldots ,c_{n-1}$$ are arbitrary binary digits.

We resolve this ambiguity by choosing consistently the first of the two digit sequences in (9.11).

DEFINITION Let $$x\in [0,1)$$ be given by

$$ x=\sum _{k=1}^\infty \frac{c_k}{2^k}\qquad c_k\in \{0,1\}. $$

Without loss of generality, we assume that all sequences $$(c_k)$$ contain infinitely many zeros. Let now f be the function that associates to $$x$$ its binary digit sequence

$$ f{:}\,[0,1)\rightarrow \{0,1\}^\mathbb {N}\qquad x\mapsto (c_1,c_2,\ldots ). $$

Exercise 9.1

Use Dirichlet’s box principle to prove the following existence statements.

1.

2.

3.

Exercise 9.2

Each function definition contains an error. Explain what it is and how it should be corrected.

1.

2.

3.

4.

5.

6.

Exercise 9.3

The following definitions have several flaws. Explain what they are, hence write a correct, clearer definition.

1.

2.

3.

Exercise 9.4

Exploit each conjecture to define a function whose existence cannot be decided at present.

1.

2.

3.

Footnotes

1

There was no guess here: first I chose $$x_+$$, and then I derived the equation of which $$x_+$$ is a solution.

2

Some authors use ’effective’ to mean ’constructive’.

3

For $$n>1$$, the integer $$1+n!$$ is followed by $$n-1$$ composite integers. (Why?)

4

Conjectured by Joseph Bertrand (French: 1822—1900) in 1845. Proved by Pafnuty Chebyshev (Russian: 1821—1894) in 1850.

5

Leonardo Pisano, known as Fibonacci (Italian: 1170—ca.1240).