Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the set of natural numbers $\mathbb N$. On this set we define an operation '+', as follows: for all $n,m \in \mathbb N$ we put $n+m$ to be the unique natural number $t \in \mathbb N$ such that there are $X,Y$ such that

$$ X \cap Y = \emptyset, \quad X \cup Y = t, \quad X \sim n, \quad Y \sim m.$$

This is called, for obvious reasons, the "cardinal definition" of addition on the natural numbers.

(You can assume that we already know (i.e. we've already proved) that there is such a natural number $t$, and moreover that this number is unique.)

Here '$X \sim n$' means that there is a bijection between $X$ and $n$.

I'm having a lot of trouble proving the following (quite elementary it seems) result:

Theorem. For all $m,n,k \in \mathbb N$ we have $$ n < m \quad \Leftrightarrow \quad n + k < m + k.$$

(Here for any natural numbers $n,m$ we use the abbreviation $n<m$ for $n \in m$.)

Of course one would think that a good first approach would be to go by induction; I've tried it on $k$ but it didn't work out. Well..., it is clear that induction on $k$ 'works' assuming the fact that we already know that $n+(k+1) = (n+k) + 1$ for all natural numbers $n,k$. So it is sufficient to show the latter statement. I've found a proof for it, but ironically in the proof I (have to) use the above (unproved) theorem, namely the implication from left to right. So I'm basically stuck in a circularity.

I also tried several other things, without success.

Comment. You are not allowed to use any 'theorems' about the natural numbers, except for the most basic ones. For example, you may use that they form a linear order, but not much more. Also, at this point there is no such thing as an 'ordinal definition' of the '+' on the natural numbers.

share|improve this question
    
What is your definition of the natural numbers? –  Baby Dragon Mar 29 '13 at 2:15
    
The 'usual one', I guess: take any inductive set, which exists by the axiom of infinity. Then define $\mathbb N$ as the intersection of all inductive subsets of this set. (We can prove that this is well-defined etc. etc.) –  Elisheva Mar 29 '13 at 2:27
    
it appears $$ 0=\emptyset \\ 1=\{0\} \\ 2=\{0,1\} \\ \cdots $$ –  suissidle Mar 29 '13 at 2:31

2 Answers 2

up vote 1 down vote accepted

First note that the natural numbers in your definition are transitive sets. So if $m\in m$ then $m\subseteq n$, and furthermore $m\neq n$, otherwise you would have $n\in n$ in contradiction to the axiom of regularity.

Use this fact to deduce that $m<n$ if and only if whenever $M,N$ are sets of cardinality $m,n$ respectively, there is an injection from $M$ into $N$, but there is no injection from $N$ into $M$. The latter may be easier to prove by using the pigeonhole principle (which you can prove independently by induction, see [1]).

First note that if $m=0$ then this follows from the above directly regardless to the value of $k$. So we may assume that $m\neq 0$.

We next prove by induction on $k$. For $k=0$ this is obvious. Assume that for $k-1$ it is true that $m+(k-1)<n+(k-1)$ whenever $m<n$.

Now suppose that $M\subsetneqq N$, and $K$ are sets of cardinality $m,n,k$ respectively, and $K$ is disjoint from $N$ (and so from $M$ as well). By the above it suffices to show that that there is no injection from $N\cup K$ into $M\cup K$ in order to show that $m+k<n+k$.

Suppose that there was an injection $g\colon N\cup K\to M\cup K$, restrict $g$ to $N$, since $M$ is a proper subset there has to be some $x\in N$ such that $g(x)\in K$, otherwise $g\upharpoonright N$ is an injection from $N$ into $M$. It follows that there exists some $u\in K$ such that $g(u)\in M$, otherwise $g\upharpoonright K$ would be an injection into $K\setminus\{g(x)\}$, which is impossible.

Define $f$ to be $(g\setminus\{\langle x,g(x)\rangle,\langle y,g(y)\rangle\})\cup\{\langle x,g(y)\rangle\}$. This is an injection from $N\cup K\setminus\{y\}$ into $M\cup K\setminus\{g(x)\}$. That is, an injection from a set of cardinality $n+(k-1)$ into a set of cardinality $m+(k-1)$. But the induction hypothesis tells us that this is a contradiction.


More:

  1. Subset of a finite set is finite
share|improve this answer

Let us define addition in a slightly different way. Let $n$ and $m$ be two natural numbers. Then we will define $n+m$ to be the unique element of $\mathbb{N}$ such that there exists sets $X_n, X_m$ such that if $X_n\sim n$ and $X_m\sim m$ and $X_n\cap X_m=\emptyset$, then $n+m\sim X_n\cup X_m$. We may also define $m\leq n$ if their is an injection of sets, $Y_n\hookrightarrow Y_m$ and $Y_n\sim n$ and $Y_m\sim m$. One may readily show that this is well defined given the following proposition.

Proposition: Let $X$ be any set such that $X\sim n$ and $X\sim m$. Then $n=m$.

Now to show your Theorem. If $m\leq n$, then their are is an injection ,$Y_m\hookrightarrow Y_n$. Now pick a set $X_k\sim k$ such that $X_k\cap Y_m=\emptyset$ and $X_k\cap Y_n=\emptyset$. Then we have $Y_m\cup X_k\hookrightarrow Y_n\cup X_k$ which proves the theorem.

Edit In the comments, the OP notes that we must show that the two definitions of $<$ is the same (the new one was implicitly defined in terns of $\leq$). To this end let us first assume that $<$ is transitive that is if $n\in m\in k$, then $n\in k$. This means that $m=\{l:l<m\}$ and $k=\{l:l<k\}$. Then we get a map $m\hookrightarrow k$ which sends $l\mapsto l$.

Proof of Transitivity Let us consider the set, $P=\{k\in\mathbb{N}:l\in n\in k\implies l\in k\}$. Certainly the empty set is in $P$ vacuously. Now suppose that $p\in P$ let us now show that $p\cup\{p\}\in P$, making $P$ an inductive set sitting inside if $\mathbb{N}$, amd therefore equal to $\mathbb{N}$. We must show that if we have a chain, $n\in k \in p\cup\{p\}$, then $k\in p\cup\{p\}$. If $n\in k\in p$ we are done since $p\in P$. On the other hand if $k\notin p$, then $k\in\{p\}$ which means that $k=p$. But then $n\in k=p\subset p\cup\{p\}$. Thus $P\subset\mathbb{N}$ is inductive and so $P=\mathbb{N}$, and so $,$ is transitive

share|improve this answer
    
Probably you mean that $n+m$ is the unique element in $\mathbb N$ such that there are $X_n$ and $X_m$ such that $X_n \sim n$, $X_m \sim m$, $X_n \cap X_m = \emptyset$ and $n + m \sim X_n \cup X_m$? Also, in your definition of $m \leq n$ I think you should say, $m \leq n$ if there are $Y_n, Y_m$ such that $Y_n \sim n$ and $Y_m \sim m$. I'm still looking at it, but for the rest it seems good, thanks. Also, I've already showed this proposition earlier, so it's no problem that it is left unproven here. –  Elisheva Mar 29 '13 at 3:18
    
Using your 'new' definition of $\leq$, I think we should prove that it is well-defined. Namely, let us define $m < n$ iff ($m \leq n$ and $m \neq n$). We should prove that "our" $<$ is the same as the "old" $<$, which is $\in$. So we have to show that $$ ( m \neq n \mbox{ and } \exists Y_m \sim m, \; \exists Y_n \sim n \mbox{ and an injection } Y_m \hookrightarrow Y_n ) \quad \mbox{ iff } \quad m \in n. $$ –  Elisheva Mar 29 '13 at 3:33
    
Note that the proof of transitivity translates to other sets, $P$ which proves induction. –  Baby Dragon Mar 29 '13 at 5:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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