15
$\begingroup$

On a recent assignment, I had a question where I had to prove a certain statement to be true for all $n\in\mathbb{Z}$. The format of my proof looked like this:

  • Statement is true when $n=0$
  • "Assume statement is true for some $k\in\mathbb{Z}$"
  • Statement must be true for $k+1$
  • Statement must be true for $k-1$

My professor said the logic is flawed because of my second bullet point above. She says that since mathematical induction relies on the well-ordering principle and since $\mathbb{Z}$ has no least or greatest element, that using induction is invalid.

Instead, she says my argument should be structured like this:

  • Statement is true when $n=0$
  • "Assume statement is true for some integer $k\geq0$"
  • Statement must be true for $k+1$
  • "Assume statement is true for some integer $k\leq0$"
  • Statement must be true for $k-1$

I am failing to understand where my logic fails and why I need to split the assumptions like she is suggesting. Could someone explain why relying on the well-ordering principle makes the structure of my proof logically unsound?

$\endgroup$
13
  • 3
    $\begingroup$ Was your proof logically sound? I.e., did you in fact prove that "Statement is true for 3" implies "Statement is true for 4 AND Statement is true for 2" (S(3) => S(4) AND S(2))? I'm asking because, for a lot of statements S, proving that sounds a lot harder than proving "S(3) => S(4)" and "S(-3) => S(-4)" (as suggested by your teacher). $\endgroup$
    – Heinzi
    Feb 22 at 12:46
  • $\begingroup$ @Heinzi Sounds pretty unlikely to be the case here. Can you give a plausible example for S? $\endgroup$ Feb 22 at 13:32
  • 5
    $\begingroup$ The subtle trap you need to avoid is accidentally proving, e.g., that it's true for k==3 because it's true for k==2, while simultaneously arguing that it's true for k==2 because it's true for k==3. Your professor's argument avoids that. $\endgroup$
    – chepner
    Feb 22 at 17:30
  • 2
    $\begingroup$ In fact, your induction principle matches the typical definition of $\mathbb Z$ better than the teacher's does. Typical definition is to consider the quotient of $\mathbb N\times\mathbb N$ under a certain equivalence relation that more or less corresponds to subtracting the second value from the first, and one natural induction principle for $\mathbb N\times\mathbb N$ requires an inductive step of "if the property is true for $(m,n)$, then it is true for $(m+1,n)$ and $(m,n+1)$", which when viewed as an element of $\mathbb Z$ is exactly adding one and subtracting one. $\endgroup$ Feb 23 at 20:07
  • 1
    $\begingroup$ I think the main point of @chepner 's argument is to be careful of circular reasoning in the proof of OP's original method. As Filip suggests, one could argue that upon closer inspection, all that the argument proves is a biconditional. Nevertheless, it is probably worth warning of such fallacy for more novice readers. $\endgroup$
    – Cynicrom
    Feb 25 at 5:51

10 Answers 10

24
$\begingroup$

You are correct. You don't even need to start with $n=0$, you can start at any integer.

To prove that your approach is correct, see that if you have proven your version of the induction step, you have automatically proven your teacher's version of the induction step. This in turn then lets you reach your teacher's conclusion step, which is also your conclusion step.

Your teacher is saying that you need to induct on the positive integers and the negative integers separately. While this is closer to standard (natural number) induction, and also a correct method of proof, it is not necessary.

(Of course, there is the theoretical possibility that there are statements which can only be proven in the direction $k\implies k+1$ for positive $k$ and $k\implies k-1$ for negative $k$, and in those very special cases, your teacher's version of induction will actually lead to a proof, while your induction will fail to reach a conclusion, since you can't get a proof for your induction step. I am not fluent enough in this area of logic to know whether such cases can ever exist, but if they do, then that's a point to your teacher. But if your proof in this particular instance is indeed correct, then I would have no issues calling it a proof by induction.)

$\endgroup$
4
  • 2
    $\begingroup$ About the added strength of splitting: the weaker version that requires the implication in both direction for all $k \in \mathbb{Z}$ is sufficient, since the implications are always true if the property to prove is true. However, there may be cases where the only way to prove that involves doing another induction (for example on $|k|$, which is one way to deduce the $\mathbb{Z}$ induction principle from the one on $\mathbb{N}$). $\endgroup$ Feb 22 at 13:23
  • $\begingroup$ @Gilles'SO-stopbeingevil' See, that's the kind of thing I'm talking about: arguing about the relative theoretical strengths of different forms of induction is not something I'm used to. I can write induction proofs pretty well, and usually determine accurately whether a proof is complete. Those I'm good at. But proof theory, even on such a low level, just isn't something I'm at all familiar with. I didn't want to sound conclusive, because I am afraid to miss some subtlety somewhere. $\endgroup$
    – Arthur
    Feb 22 at 13:43
  • 3
    $\begingroup$ Re your parenthetical: By the completeness theorem, if a statement must necessarily be true, then there exists a proof of that statement. If you can prove $\forall k \in \mathbb{Z} \: \phi(k)$, then you can prove $\forall k \in \mathbb{Z} \: [\phi(k) \implies \phi(k\pm1)]$, because the former implies the latter. However, the proof may be easier if you assume that k has a given sign in a given case. $\endgroup$
    – Kevin
    Feb 22 at 19:55
  • $\begingroup$ You don’t even need the completeness theorem. The parenthetical case is impossible by the very same argument stated earlier in the post. $\endgroup$ Feb 24 at 12:03
18
$\begingroup$

You are in fact doing two separate inductions - one upwards and one downwards. Each relies on a well-ordered set with a minimum element and a maximum element respectively.

The union of the two sets is $\mathbb Z$, which has no maximum or minimum element. But you are not doing induction on $\mathbb Z$, rather you are covering $\mathbb Z$ with two sets on which induction is possible.

$\endgroup$
10
$\begingroup$

If your professor says that induction on the integers is invalid, your professor is wrong.

Induction arguments can be used on any ordered set where the ordering is well-founded. Although it's true that the usual $<$ relation is not well-founded on the integers, we can consider the relation $$a\prec b$$ that means $$|a| < |b|.$$ This relation is well-founded on the integers.

Your induction argument can be put in terms of this well-founded $\prec$ relation: you've shown that if the statement fails for some integer $n$, it must also fail for some integer $m\prec n$. Or, in terms of the usual $<$, if it fails for $n$ it must fail for some $m$ with $|m|<|n|$. Since this process can't repeat forever, it must end at $0$, and since you proved that the statement doesn't fail at $0$, it can't fail anywhere.

$\endgroup$
4
  • $\begingroup$ I think perhaps the teacher's point was to clarify the implications between the 4 bullet points the OP states. It is true that bullet points 2 and 3 and bullet points 4 and 5 do not need to impose the condition that $k\leq 0$ and $k \geq 0$, but on the other hand, given the assumption that the statement is true for $n=0$, they give weaker assumptions that still imply the required conclusion. $\endgroup$
    – krm2233
    Feb 22 at 0:22
  • 1
    $\begingroup$ My professor wasn't concerned about clarity as much as she believes the logic itself is flawed. She says I can not use the assumption "Assume $P(n)$ is true for some integer $n$". $\endgroup$ Feb 22 at 5:11
  • 1
    $\begingroup$ @JuneRichardson If you make the assumption, then you can use it. $\endgroup$ Feb 23 at 23:48
  • 1
    $\begingroup$ @JuneRichardson: Your teacher is wrong, full-stop. For any property Q on ℤ, we can prove ( Q(0) ∧ ∀k∈ℤ ( Q(k) ⇒ Q(k+1) ∧ Q(k−1) ) ⇒ ∀k∈ℤ ( Q(k) ) ). This is a trivial exercise for first-year undergraduate mathematics majors. And this implies that your proof approach is logically sound. If she cannot understand this, then she is not qualified to teach about induction at all. $\endgroup$
    – user21820
    Mar 8 at 5:02
8
$\begingroup$

I think perhaps what your teacher was concerned about how you have phrased your logic: If we write $P(m)$ for the statement for an integer $m\in \mathbb Z$, and you wish to show that $P(m)$ is true for all $m \in \mathbb Z$, then you can show this by establishing the following three statements:

  1. P(k) is true for some $k \in\mathbb Z$,
  2. if $P(m)$ is true, then $P(m-1)$ is true,
  3. if $P(m)$ is true, then $P(m+1)$ is true.

In your final two bullet points, I think your teacher's concern was that you need to make clear that the statement is "$P(k)$ true implies $P(k+1)$ is true", and similarly that "$P(k)$ true implies $P(k-1)$ true".

Given 1,2, and 3 above, then it follows by ordinary induction using $1$ and $3$ that $P(m)$ is true for all $m \geq k$. Similarly using $1$ and $2$, it follows that $P(m)$ is true for all $m \leq k$.

$\endgroup$
7
$\begingroup$

I'd say carry on thinking for yourself and ignore the professor.

Your construction is a very trivial and perfectly valid corollary of the one she needs to use twice (once as normally stated and the second time as also a very trivial and perfectly valid corollary of the first).

The remarks concerning the well ordering principle are more misleading than useful.

$\endgroup$
1
  • $\begingroup$ The last sentence is spot-on. So many 'mathematics teachers' think they know better just because they can say the words "well-ordering principle". In fact, as any logician knows, the true philosophical justification that PA is meaningful is (meta-)induction, not well-ordering. Equivalence over PA⁻ doesn't imply that they are on equal footing, just like induction and strong induction are equivalent but one is more fundamental than the other. $\endgroup$
    – user21820
    Mar 8 at 5:03
4
$\begingroup$

If a poset $P$ is order-isomorphic to $\Bbb N$, then one can perform induction on $P$. Let $\phi: \Bbb N \to P$ be such an isomorphism, then we use $\phi(0)$ as the base case and $\phi(n)\implies\phi(n+1)$ as the inductive step.

It's easy to construct the isomorphisms for both $\Bbb Z_{\geq k}$ and $\Bbb Z_{\leq k}$ so that your version of induction is perfectly valid; just take $n\mapsto n-k$ and $n\mapsto k-n$. Since $\Bbb Z_{\geq k}\cup\Bbb Z_{\leq k} = \Bbb Z$, the result holds for all integers.

$\endgroup$
3
$\begingroup$

Any nonempty set $A$ of integers which contains $k+1$ and $k-1$ whenever it contains $k$ is the entire set of integers. So yes, you can do induction over all the integers.

But it's not often done that way. It seems more frequent to:

  • Prove the the statement for all nonnegative integers, possibly by induction
  • Reduce the negative case to the nonnegative case

For example, I'm teaching discrete mathematics from a textbook that proves the theorem “every integer is either even or odd” this way:


Lemma 1: For all integers $n$, if $n$ is even or odd, then $n+1$ is even or odd.

Lemma 2: For all integers $n$, $n$ is even if and only if $|n|$ is even, and $n$ is odd if and only if $|n|$ is odd.

The proofs are left to the reader.

Proposition: All natural numbers are either even or odd.

Proof: By induction on $n$. The base case $n=0$ is apparent by the definition of even. For the inductive case, suppose $k$ is either even or odd. By Lemma 1, $k+1$ is either even or odd. So by induction all natural numbers are either even or odd. QED.

Theorem: All integers are either even or odd.

Proof: Consider an integer $x$. If $x \geq 0$, the proposition already shows that $x$ is either even or odd. If $x < 0$, the proposition shows that $|x|$ is either even or odd. By Lemma 2, $x$ is either even or odd. QED


To me, this is more readable than going forwards and backwards at the same time. When people read a lot of induction proofs, they expect them to follow an idiomatic pattern, and this follows that pattern. Also, reducing the negative case to a nonnegative one is a pretty standard trick.

$\endgroup$
2
$\begingroup$

Your method is valid because

  • your bullet points 1, 2, and 3 are a standard induction proof of "$P(n)$ holds for all non-negative integers"
  • your bullet points 1, 2, and 4 are a standard induction proof of "$P(-n)$ holds for all non-negative integers"
$\endgroup$
1
$\begingroup$

Let's look at induction on the natural numbers. You can prove $P(k)$ for any $k \in \mathbb{N}$ if you can prove:

  1. $P(0)$ is true
  2. For all $n \ge 0$, $P(n) \rightarrow $P(n+1)$.

This works works, intuitively, because a proof of $P(k)$ either follows directly from (1) if $k = 0$, or indirectly from (2) if $k > 0$. (That is, the proof of $P(k)$ follows from the proof of $P(k-1)$ which follows from the proof of $P(k-2)$, ..., which follows from the proof of $P(1)$, which follows from the proof of $P(0)$, which is already established.

For integers, though, you have stated that you can prove $P(k)$ for any $k \in \mathbb{Z}$ if you can prove

  1. $P(0)$ is true
  2. There exists $n \in \mathbb{Z}$ for which $P(k)$ is true
  3. For all $k \in \mathbb{Z}$, $P(k) \rightarrow P(k+1)$
  4. For all $k \in \mathbb{Z}$, $P(k) \rightarrow P(k-1)$

Now, how do we prove $P(57)$? Do we prove $P(56)$ is true, or do we prove $P(58)$ is true? Either one seems sufficient, but one either leads to a circular argument or spirals off towards infinity. The problem is that nothing forces you to reduce your proof of $P(k)$ to the established proof that $P(0)$ is true. That's because you haven't explicitly tied your argument that induction works for integers to a well-ordering of the integers. That's easy to fix, though. It turns out that (2) is insufficient; not just any assumption will work. It also turns out that (3) and (4) are overly broad. You don't need to assume (3) holds for all integers, only the positive integers. Likewise, (4) need only hold for the negative integers.

So we can reformulate our inductive principle over the integers to

  1. $P(0)$ is true
  2. For all $k \ge 0 \in \mathbb{Z}$, $P(k) \rightarrow P(k+1)$
  3. For all $k \le 0 \in \mathbb{Z}$, $P(k) \rightarrow P(k-1)$

(Note that in the case of positive integers, this reduces exactly to induction over natural numbers.)

Now, our proof that $P(57)$ is true necessarily follows from a proof that $P(56)$ is true and (2), while a proof that $P(-57)$ is true follows from $P(-55)$ and (3). For any $k \ne 0$, exactly one of (2) or (3) can be used to connect the truth of $P(k)$ to the truth of $P(0)$. We won't, for example, use $P(-58)$ to prove $P(-57)$, because even if we could, it doesn't help us get close to $P(0)$, and it prevents us from immediately turning around and using $P(-57)$ to prove the truth of $P(-58)$.

$\endgroup$
1
$\begingroup$

Here is a (quotient-)inductive definition of the integers whose natural induction principle is the exact induction principle you used. Inlining:

data ℤ : Type where
  zero : ℤ
  suc pre : ℤ -> ℤ
  s-p : ∀ i → suc (pre i) ≡ i
  p-s : ∀ i → pre (suc i) ≡ i
  squash : isSet ℤ

It is the type simultaneously generated by the first three 'constructors' ($\mathsf{zero}$, $\mathsf{suc}$ and $\mathsf{pre}$) and quotiented by the other three rules. So, $ℤ$ is given by the rules:

  • $ℤ$ contains a value $\mathsf{zero}$, representing $0$
  • If $i$ is a value of $ℤ$, then so is $\mathsf{suc}\ i$, representing $i+1$
  • If $i$ is a value of $ℤ$, then so is $\mathsf{pre}\ i$, representing $i-1$
  • $\mathsf{suc}\ (\mathsf{pre}\ i) = i$
  • $\mathsf{pre}\ (\mathsf{suc}\ i) = i$
  • Don't worry about $\mathsf{squash}$

Then, the natural induction principle says that for a predicate $P : ℤ → \mathsf{Prop}$, to prove $∀i. P(i)$ we need to show:

  • $P(0)$
  • $∀ i. P(i) → P(\mathsf{suc}\ i)$
  • $∀ i. P(i) → P(\mathsf{pre}\ i)$

Conditions induced by the equations are automatically satisfied by $P$ being valued in propositions.

In the computation based system I'm using in the linked file, these conditions are not really redundant. The actual members of the type might be represented as $\mathsf{pre}\ (\mathsf{suc}\ \mathsf{zero})$. Even though this value is formally equal to $\mathsf{zero}$, the recursive process witnessing the induction will actually produce $Pp\ (Ps\ Pz)$ as the witness of $P(\mathsf{pre}\ (\mathsf{suc}\ \mathsf{zero}))$, although this is equivalent to $Pz : P(\mathsf{zero})$.

Quotient-inductive definitions like these are a relatively new idea in type theory (the system I'm using, where inductive definitions are bread and butter). But actually, the usual way you'd define $ℤ$ there without quotients would admit almost the same induction. It'd actually be easier because they are more normalized, and you'd only need to show that $P(i) → P(\mathsf{pre}\ i)$ for non-positive $i$, and that $P(i) → P(\mathsf{suc}\ i)$ for non-negative $i$. So I doubt any type theorist in recent memory would quibble about your induction.

Unfortunately, based on questions/answers that crop up here, it seems like the general conception of induction is pretty antiquated in educational environments (at least in my opinion).

Also, I'd take umbrage in the idea that induction is based on the well-ordering principle, because I don't believe in the latter, even for all inductively defined types. It is easy enough to well-order the integers, though.

$\endgroup$
1
  • 2
    $\begingroup$ I don't understand some terms e.g. "(quotient-)inductive", "constructors" (except in terms of certain computer languages), "witness", "squash", nor the formalism in your inlined definition. Would you expect OP to understand these given the wording of his question? $\endgroup$ Feb 24 at 12:24

You must log in to answer this question.

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