Hi All. There is a problem in Halmos's Naive Set Theory on page 49. It states that(adsbygoogle = window.adsbygoogle || []).push({});

"if n[itex]\neq[/itex]0 and if n is a natural number, prove that n=S(m) for some natural number m." Here, S(m) denotes the successor of the number m and is given by S(m)=m[itex]\bigcup[/itex]{m}.

My attempted solution to this was to use induction. Let P be a set which has "0" in it. Also, let P contain all the natural numbers such that if n[itex]\in[/itex]P, then n=S(m) for some natural number m. Now 1=S(0). So 1[itex]\in[/itex]P. 2=S(1). Hence 2[itex]\in[/itex]P. Now let this be true for some n. Now as the successor of n, namely S(n) is, by definition, successor of n, we have that S(n) has a number (equal to n) such that S(n)=S(n). Therefore S(n)[itex]\in[/itex]P. Hence by induction, it must be true for all n.

Since every natural number is in P, which posesses the property that all its elements have a predecessor, it must be true that all natural numbers have a predecessor.

I have two questions.

1. Is my proof right?

2. If it is wrong, kindly point out the mistake

3. If it is right, then I feel that "S(n)[itex]\in[/itex]P whenever n[itex]\in[/itex]P" is a funny statement. S(n)[itex]\in[/itex]P even if n[itex]\notin[/itex]P because it has a number n which is its predecessor. Why do weneedn to be in P to prove it? In other words,

can this be proved without using induction? Please let me know.

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Problem on successor/predecessor set

Loading...

Similar Threads - Problem successor predecessor | Date |
---|---|

B Problem in Counting - Number of Passwords | Feb 23, 2018 |

I A specific combination problem | Feb 6, 2018 |

I A seemingly simple problem about probability | Jan 29, 2018 |

I Extension of Turing computable | Nov 14, 2017 |

I Axiom of Infinity & Garling, Th. 1.7.4 & the successor set | Nov 4, 2016 |

**Physics Forums - The Fusion of Science and Community**