Prove $\forall n \in N$, every set of natural numbers of size n has a maximum element. May assume that sets do not repeat numbers. Prove using induction. 
So i'm a bit confused about how to do this question. My attempt at it seems like i'm missing a lot and it looked to easy.
Base cases:
P(1) = {1} = 1
P(2) = {1,2} = 2 is the largest 
P(3) = {1,2,3} = 3 is the largest
P(4) = {1,2,3,4} = 4 is the largest.

Assume that n $\ge$ 1, and the set of size n has a maximum element. (induction hypothesis) 
P(n+1) = {{P(n)}, n+1} since the set of size n is included just before n+1 in the set of size n+1, we know that n is the largest element in the set of size n by the induction hypothesis, and n+1 > n. So n+1 is the largest element in the set. So this is true.
Is there anything wrong with what i did? 
 A: You should induct on the size, $n$. 
First prove that all size-$1$ subsets of $\mathbb{N}$ have a maximal element. This is straightforward, since their maximal element is simply their only element. That was the base case of your induction proof. 
Now, for the inductive step. Suppose that all subsets of $\mathbb{N}$ that have $n$ elements have maximal elements. Consider a general subset of size $n+1$. Call it $A$. Pick an arbitrary element of $A$, call it $a$. 
Note that $A$ is the union of some $n$-element subset of $\mathbb{N}$ and $\{a\}$. Call this $n$-element subset $B$. Note that $a \not\in B$ (otherwise $A$ would only have $n$ elements). By your assumption, $B$ must have a maximal element. Call that $b$. 
By trichotomy (which is probably one of the axioms you're allowed to assume for this, in some equivalent form), exactly one of the following is true:


*

*$a < b$

*$a > b$

*$a = b$


The third statement can't be true, because we know $a \not\in B$. If the first statement is true, then $b$ is the maximal element of $A$. If the second statement is true, then $a$ is the maximal element of $A$. Either way, $A$ has a maximal element, so this completes your inductive step.
