In senior high school math, teacher taught us that many physical quantity ARE vectors, such like velocity, force, momentum, etc. And since they are vectors, you can decompose them to the horizontal and vertical components.
But I don't know why they are vectors. By experiment? By theory? Or by definition? Or by purely logical reason? For example, the reason that displacement or velocity are vectors seems somewhat reasonable: we define position function $\mathbf{r}(t)$, which specifies a position in the Cartesian plane(or space) in terms of an ordered pair or tuple, and then we naturally define $\mathbf{r}'(t)$ to be its velocity function. Everything here seems purely logical, and they are all happen in our brain, we neither need to make a experiment nor to refer to the real world.
So, my questions are, how to understand these things? And how do we know that we always can safely decompose them to the horizontal and vertical components if we need, and can always get the correct result?
It's not really that mathematical objects are physical quantities like velocity, but rather that they represent or model the physical quantities in a useful way.
In other words, a vector is just an ordered collection of real numbers, and numbers themselves are an abstract concept. So, velocity is not the same thing as this abstract concept. However, if we want to understand velocity, it helps to represent it in some way that provides useful and meaningful results. It turns out that an effective way to do this is to use vectors. That doesn't mean it is necessarily the only way to represent velocity, but it has proven sufficiently useful to us that it sticks around and gets taught to students.
Regarding your question about why we can safely decompose them into horizontal and vertical components, this just follows from the mathematics of vectors. Once we have chosen to represent velocity as a vector, there is no harm in applying the normal rules of vectors, except that perhaps the operations don't have meaningful physical equivalents because, after all, we are just modeling the physical world with mathematics.