I was reading Landau's Foundations of Analysis. He starts his construction of number systems by stating five axioms. My question is related to the fifth, the axiom of induction:

Let there be given a set $\mathscr{N}$, of natural numbers with the following properties:

I) 1 belongs to $\mathscr{N}$

II) If $x$ belongs to $\mathscr{N}$ then so does $x'$

Then $\mathscr{N}$ contains all the natural numbers

(Here $x'$ is the successor of $x$ )

Now consider the following proposition:

Let $(A,≤)$ be an ordered set. If $S$ is a finite subset of $A$ then $S$ contained a maximum and a minimum.

This can be proved by induction on the cardinal of $S$. Now my (first) question is, for the induction to "work" is it necessary to first prove that each $S$ has an unique cardinal? That is, that there is an unique $n\in \Bbb{N}$ such that there exists a bijection between $S$ and $\left \{ 1, \cdots ,n \right \}$.

In accordance with the axiom of induction we would be forming the set: $$\mathscr{N}=\left \{ n \in \Bbb{N} : S\subset A \ \wedge \ \#(S)=n \Rightarrow S \ \text{contains a maximum and a minimum} \right \}$$

Is this correct?

Now, for my second (third) question, consider Bernoulli's inequality:

$$\prod_{i=1}^{n}(1+a_i)≥1+\sum_{i=1}^{n}a_i \, \quad \text{if $a_i≥-1$, $i=1,...n$}$$

If I wanted to construct the set $\mathscr{N}$ cited in the axiom, how would I do it? Furthermore, should any care be taken when defining the set, analogous to proving that the cardinal is unique in the previous question?

  • $\begingroup$ Was that an error when you wrote ", of natural numbers" ? It seems to beg the question. $\endgroup$ – DanielV Feb 26 '15 at 0:20
  • $\begingroup$ @DanielV I copied it exactly as it is from the text. Landau refrains from using set symbols such as $\in$, $\subset$ or $\cap$ throughout the whole book, and states everything in plain english. So "of natural numbers" means $\mathscr{N} \subset \Bbb{N}$ $\endgroup$ – Reveillark Feb 26 '15 at 0:54
  • $\begingroup$ Not having Landau's book, could you fill in how he defines "finite set"? Also is the "ordered set" assumed to be well-ordered by $\le$, or maybe at least totally ordered, etc.? $\endgroup$ – coffeemath Feb 26 '15 at 1:34
  • $\begingroup$ @coffeemath He doesn't, that proposition is not from Landau's book, which is entirely devoted to constructing number systems (rationals, integers, reals, complex). I just mentioned the book as a reference for the axiom of induction. As I was reading the book this question came to my mind. By $(A,≤)$ being an ordered set I mean that $≤$ is an order relation: it is reflexive, anti-symetric and transitive. $\endgroup$ – Reveillark Feb 26 '15 at 2:39
  • $\begingroup$ Reveillark: Just having a partial order doesn't guarantee existence of maxima/minima in a finite subset. For example consider the set $A=\{\ \{1\},\ \{2\}, \{1,2\}\ \}$ as a (finite)subset of the power set of naturals ordered by taking $\le$ as inclusion. Then $A$ does not have a minimal element. $\endgroup$ – coffeemath Feb 26 '15 at 3:07

No, for this purpose you don't need to prove that a finite set has a unique cardinality. It is enough to define a finite set as one that is equinumerous with $\{1,2,3,\ldots,n\}$ for some $n$. If we ever find a set that is equinumerous with both $\{1,2,3,\ldots,42\}$ and $\{1,2,3,\ldots,108\}$, then that set will just be finite in two different ways. (In reality, that's an impossible situation, of course. But knowing that it's impossible is not necessary for the definition to work here).

Your definition of $\mathscr N$ is problematic, because you have forgotten a quantifier for $S$, so it looks like $\mathscr N$ is something that depends on the value of $S$. What you want is something like $$ \mathscr N = \{ n\in\mathbb N \mid \forall S\subseteq A. S\cong\{1,2,3,\ldots,n\} \Rightarrow S \text{ has maximum and minimum} \} $$ were $\cong$ denotes the existence of a bijection between the two sets. Note that the notation $S\cong\{1,2,3,\ldots n\}$ instead of $\#S=n$ allows us to remain ignorant whether some sets might have more than one cardinality.

Once we know that $\mathscr N=\mathbb N$, then it's not a problem if we were to find a freak $S$ that's equinumerous with both $\{1,2,\ldots,42\}$ and $\{1,2,\ldots,108\}$. All that would mean is that we'd have two different ways to know that $S$ has a maximum and a minimum, namely either to appeal to $42\in\mathscr N$ or to appeal to $108\in\mathscr N$.

Note that in actual proofs by induction we don't actually write down a definition of a named set $\mathscr N$. Instead we just say something like "we will now prove $$ \forall S\subseteq A. S\cong\{1,2,3,\ldots,n\} \Rightarrow S \text{ has maximum and minimum} $$ for all $n$ by induction on $n$", and then give the proofs that $1$ has the property and that the successor of any $n$ with the property itself has it.

  • $\begingroup$ Thank you very much for your reply. I know that we never write down the set when doing a proof by induction, but I wanted to see how it would look (and any technicalities that might appear) if we wanted to write down a definition for the set for some reason. For my second question, would something like: $\mathscr{N}=\left \{ n \in \Bbb{N} : \forall(a_1,...a_n) \in \Bbb{R}^n, (a_1,...a_n) \in [-1,+\infty)^n \Rightarrow \prod_{i=1}^{n}(1+a_i) ≥ 1 + \sum_{i=1}^{n} a_i \right \}$ work? $\endgroup$ – Reveillark Feb 26 '15 at 2:49
  • $\begingroup$ @Reveillark: Yes, something like that. $\endgroup$ – hmakholm left over Monica Feb 26 '15 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.