The reason why velocity behaves like a mathematical vector is theoretical, experimental or purely logical? 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?
 A: Surely not by pure logic. We can't figure out how the world works with logic alone. I think we just guess that these quantities can be modeled using vectors. Then we work out the predictions of our model and see if the predictions agree with our measurements. If the agreement is good, then the model is effective.
Terence Tao once wrote a comment about how physical models work on an online forum:

The way mathematical or physical models work, one assumes the
existence of a variety of mathematical quantities (e.g. forces,
masses, and accelerations associated to each physical object) that
obey a number of mathematical equations (such as $F=ma$), and one also
assumes that the result of various physical measurements can be
computed in terms of these quantities. For instance, two physical
objects $A_1, A_2$ will be in the same location if and only if their
displacements $x_1, x_2$ are equal.
Initially, the numerical quantities in these models (such as $F, m, a$)
are unknown. However, because of their relationships to each other and
to physical observables, one can in many cases derive their values
from physical measurement, followed by mathematical computation. Using
rulers, one can compute displacements; using clocks, one can compute
times; using displacements and times, one can compute velocities and
accelerations; by measuring the amount of acceleration caused by the
application of a standard amount of force, one can compute masses; and
so forth. Note that in many cases one needs to use the equations of
the model (such as $F=ma$) to derive these mathematical quantities. (The
use of such equations to compute these quantities however does not
necessarily render such equations tautological. If, for instance, one
defines a Newton to be the amount of force required to accelerate one
kilogram by one meter per second squared, it is a non-tautological
fact that the same Newton of force will also accelerate a two-kilogram
mass by only one half of a meter per second squared.)
If one has found a standard procedure to compute one of these
quantities via a physical measurement, then one can, if one wishes,
take this to be the definition of that quantity, but there are
multiple definitions available for any given quantity, and which one
one chooses is a matter of convention. (For instance, the definition
of a metre has changed over time, to make it less susceptible to
artefacts.)
In some cases, it is not possible to measure a parameter in the model
through physical observation, in which case the parameter is called
"unphysical". For instance, in classical mechanics the potential
energy of a system is only determined up to an unspecified constant,
and is thus unphysical; only the difference in potential energies
between two different states of the system is physical. However,
unphysical quantities are still useful mathematical conveniences to
have in a model, as they can assist in deriving conclusions about
other, more physical, parameters in the model. As such, it is not
necessary that every quantity in a model come with a physical
definition in order for the model to have useful physical predictive
power.

A: 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.
A: That's a long story, that started with accepting the concept of "length" of a rope, then by representing a field (piece of land) by a sum of triangles individuated by the length of the rope between the corner pickets: it worked and nobody (or marginally few) could contest the "validity" of the principle (... till recognizing that the earth is spherical).
Then the volume, ... the Law of inclined plane and so on.
A: The mathematical classification of a vector is an object which switches sign when the coordinates are inverted.
Consider motion in the plane. In time $\Delta t$, the test object moves $\left( \Delta x, \Delta y \right)$. The velocity is
$$
 v = \left(
\frac{\Delta x} {\Delta t}, \frac{\Delta y} {\Delta t}
\right)
$$
Apply the vector test. Invert the coordinates: 
$$
\tilde{x} = -x, \qquad \tilde{y} = -y
$$
The velocity transforms as
$$
 \color{blue}{\tilde{v}} = 
\left(
\frac{\Delta \tilde{x}} {\Delta t}, \frac{\Delta \tilde{y}} {\Delta t}
\right)
=
\left(
-\frac{\Delta x} {\Delta t}, -\frac{\Delta y} {\Delta t}
\right)
=
\color{blue}{-v}
$$
This property is a categorization. Other nomenclature includes proper vector or polar vector.
If the quantity of interest is invariant under coordinate inversion, it is labelled pseudovector or axial vector.
Read more at Mathworld: Pseudovector; Wikipedia: Pseudovector
