Inductive Sets

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Inductive Sets

Based on the first part of section 4.1 of the textbook and this discussion of inductive sets.

Definition

Definition: an inductive set is any set that is

1. A subset of the integers, and
2. For all integers n, if n is in the set, then n+1 is in the set.

One consequence of this definition is that every non-empty inductive set extends to infinity. But is the empty set inductive?

(From the discussion) which of the following statements are true and which are false, and why?

1. The set of integers greater than or equal to 0 is inductive. This is true, since it’s certainly a subset of the integers, and if n ≥ 0, the n+1 ≥ 0 too.
2. The set of integers less than or equal to 0 is inductive. This is false, because 0 is in the set but 0+1 = 1 isn’t.
3. If A is an inductive set, then 1 ∈ A. False, an inductive set can start anywhere.
4. If A is an inductive set, and 1 ∈ A, then 100 ∈ A. True, since if 1 is in A then 1+1 = 2 is in A, and then 2+1 = 3 is, and so forth for all integers ≥ 1.
5. The set of positive integer multiples of 1/2 (i.e., {1/2, 1, 3/2, 2, 5/2, ...}) is inductive. False. Even though n being in the set implies that n+1 is, it’s not a subset of the integers.
6. The set of numbers computed by multiplying 1/2 by an odd positive integer, i.e., {1/2, 3/2, 5/2, ...}, is inductive. False, for the same reason (5) is.
7. If A is an inductive set, and A ⊆ B, then B is inductive (i.e., anything with an inductive subset is inductive).  False. As a counterexample, {1,2,3,4,....} is inductive but { 1/2, 1, 2, 3, 4, ...} isn’t.
8. If A is an inductive set, and B ⊆ A, then B is inductive, i.e., (any subset of an inductive set is inductive). This is also false, for example {1,2,3,4,....} is inductive but {1,2,3} is not. 
9. No inductive set has a largest member. True, inductive sets go to infinity, as mentioned above (unless maybe the empty set is inductive, but the empty set doesn’t have a largest member either).

Can you give some other examples of inductive sets?

Infinite sets of consecutive integers starting at negative values, e.g., {-5, -4, -3, -2, .... }.

Proofs

4n + 3 Is Odd

(Also from the discussion)

Can you prove that the set of natural numbers n for which 4n + 3 is odd is inductive?

We came up with two proofs for this.

Proof 1: 4n + 3 = 4n + 2 + 1 = 2(2n+1) + 1 which is odd by closure of integers under addition and multiplication, and the definition of odd number. This holds for all integers, and therefore for all natural numbers.

Since 4n + 3 is odd for all natural numbers, and the natural numbers are a subset of the integers, the set of natural numbers n for which 4n + 3 is odd is a subset of the integers.

Furthermore, whenever n is a natural number so is n+1, so the set of natural numbers, and therefore the set of natural numbers for which 4n + 3 is odd, is inductive.

Proof 2: First, note that any subset of the naturals is a subset of the integers.

Then show that if n is a natural number such that 4n+3 is odd, so is n+1

Assume 4n + 3 is odd, then 4(n+1) + 3 = 4n + 4 + 3 = (4n+3) + 4 is also odd. (For this conversation, I’m willing to accept that (4n+3) + 4 is odd because 4n + 3 is an an odd number and an odd number plus an even one is odd. If you’re unhappy with this because we haven’t previously proven it, you can work out the proof here in more detail: since 4n+3 is odd, write it as 2k + 1 for some integer k, and then (4n+3) + 4 = (2k+1) + 4 = (2k+4) + 1 = 2(k+2) + 1 which is an odd number.)

What we did in proof 2, namely assuming that n has some property and showing that n+1 does too, is much more typical of proofs about inductive sets than proof 1 is.

Rapidly Growing Functions

How about the set of natural numbers n such that n! > 2ⁿ? Can you prove that it’s inductive?

It wasn’t completely clear at first that this set isn’t empty, but by checking some natural numbers we eventually found that 4! > 2⁴ and 5! > 2⁵ as examples.

To show that this set is inductive, first observe that it is a subset of the integers.

Then suppose k is a natural number such that k! > 2^k, and try to show that (k+1)! > 2^k+1:

(k+1)! = (k+1) k! > (k+1) 2^k > 2 2^k as long as k+1 > 2, i.e., k > 1.

Finally, 2 2^k =2¹ 2^k = 2^k+1, so (k+1)! is indeed greater than 2^k+1.

Next

Extending some of these proofs that sets are inductive into proofs about more generally interesting statements.

Please read the rest of section 4.1 in the text, i.e., from “The Principle of Mathematical Induction” to the end of section 4.1.

Please also use this discussion of induction proofs to start practicing such proofs.

Next Lecture