Suppose that we have a set of positive integers S. Suppose we known the followin

Question

Suppose that we have a set of positive integers S. Suppose we known the following two facts about S. 1 E S Whenever k E S then K + l E S Then we can conclude from this every positive integer is in S. (Using the Well -ordering property. Assume that we have a set that satisfies (1) and (2). Let T be the set of all positive integer that are not in S. In order to conclude that every positive integer is in S, we would like to show that T is the empty set Suppose that it is not the empty set. Then, by the well-Ordering property, T must have a least element, n. By the exercise below, n-1 is a positive integer. Since n was the least element of T n-1E T so n - l E S. Let k = n- 1. Then, by (2), we can conclude that n = k + l E S. This contradicts our assumption that n was an elements of T. // Complete the proof above by proving that, for the n chosen in the proof, n -1 is a positive integer.

Explanation / Answer

Alternate proof:

Assume that we have a set that satisfies

a) 1 is in S

b) If k is in S, then k+1 is in S

Let T be the set of all positive integers that are not in S

If we prove that T is empty set that is equivalent to our required proof

Let if possible T be non empty

Then T by well ordering property have a least element say (n-1)

This implies that n-1-1 is not in T but n-2 is in S

Let k = n-2

Then since 1 is in S, 1+n-2 i.e. n-1 is in S

This leads to a contradiction of our assumption

Hence T is an empty set

Hence proved

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.