I had this kind of question myself for a long time because before studying Physics I've studied Math and in Mathematics we do things quite differently. In Mathematics, a general procedure is to give some definitions, probably by specifying some axioms, then we derive and prove theorems from this.
On Physics there is a similar procedure, but it goes a little bit different. The idea is that based on observations we assume certain things. The justification for those things is that our observation sugested it, so there is not any logical reasoning behind that allows one to obtain those things from previously defined ones. Those things we assume, are like the axioms in Math. From those axioms, we derive results.
The results we derive will be true as long as what we assumed is true. So this provides a nice way to test those axioms. We go there and see if we observe our predictions. Provided they are observed this doesn't prove the axioms are in fact true, but gives us more confidence about it. Perhaps some times something will be observed which was not predicted and we revise those axioms.
Newton's laws are the "axioms" for Mechanics. Newton observed mechanical phenomena and based on observation assumed his three laws. In particular, the second law can be thought of as what force really is. Also, in Physics not always is possible to define everything in a precise way like in Math. So Force, for example, is defined as something which changes the state of motion of a particle. This is the best initial intuition on force and is what the second law tries to capture.
So, in summary, Newton defined force exactly as the change in the quantity of motion. Also, he did not prove that, he argued that should be assumed based on observation.