Can we do a thought experiment to prove that the horizontal and vertical motion of a projectile are independent of each other? It seems really hard for me to grasp the idea that horizontal and vertical motion of a projectile are independent of each other. Intuitively I feel that they should affect each other. How can it be that  a bullet fired horizontally from the gun and a ball dropped from the same height reach the ground at exactly the same time? Can anyone show me logically why this is true?
 A: We're working in the flat earth no atmosphere model, right?
Then if you're moving along with the bullet, it just falls straight down, and it is the ball on a ballistic trajectory "backwards". Now your intuition may be bothered by the Earth and it's little downward $\vec g$ arrows rushing backwards in this frame, but, it is only the Earth moving backwards. The little $\vec g$ arrows are stationary w.r.t to the bullet's horizontal motion, so the bullet just drops.
A: Gravity only operates along the vertical direction. No matter the object or how it's moving, gravity will only affect its vertical velocity, because gravity cannot impart a horizontal force. Furthermore, gravity affects all objects the same way, whether or not they are moving horizontally. From this, we can see that motion and acceleration in the vertical direction aren't related to motion and acceleration in the horizontal direction. We can have forces that operate in one or both directions, but they can be totally independent of one another. Forces can operate in both directions, like those involved in launching a cannonball at 45 degrees, but those can be decomposed into their horizontal and vertical components. Those components can be related - as we lower the angle of the cannon, we get more horizontal force and less vertical.
It's perhaps worth pointing out that you can decompose any 2-dimensional vector into an infinite number of orthogonal pairs of dimensions. We normally use the vertical/horizontal decomposition  precisely because we have a common force (gravity) that only operates along one axis. If we were to use any other decomposition, the force of gravity would contribute along both axes, which complicates matters. We can instead choose our axes of analysis to fit the problem, knowing that the appropriate choice will allow us to ignore the effects of gravity in the horizontal direction.
A: Following thought experiment is a very simple one to imagine and provides the results you want.
Imagine two identical spherical masses.
Ignore the air resistance.
Let's pick both of them in our hand and drop one ball into free fall while giving some purely horizontal velocity to the second one, such that the second ball has a starting horizontal velocity but zero vertical velocity.
If you keep the height of both balls same while starting their motion you will see no matter what the horizontal velocity second ball has the ball falls on earth in same time as that the vertical one takes to reach earth.
You check the math out on any online calculator or even perform it yourself.
(Condition- the second ball doesn't have velocity which is equal to orbital velocity at that height and you are standing near earth)

The principle behind the separation of horizontal and vertical velocities is very intuitive.
You can just imagine that a river is flowing and you have to swim across it.
No matter how fast river flows it cannot disrupt your swimming speed and no matter how hard you swim (in horizontal direction) you cannot change the drift that the river's flow is causing.
Hence when a projectile is flying the gravitational acceleration acts like a river no matter how much it is the horizontal velocity remains unaffected.
And no matter how fast your ball is thrown gravity will always pull it down with same force. 
(Condition? The projectile does not have the orbital velocity at that height)
A: Imagine an ant crawling directly across a stationary conveyor belt.  Now imagine the same ant crawling along the same path of the same belt with the belt moving.  Did turning on the belt motor have any effect on the ant's velocity across the belt. Thinking of the two motions (ant's and belt's) in terms of momentum per Newtons first law the ant's forward motion is constant while the ant's sideways motion is variable depending on the belt speed.  With two reference frames you get two independent motion vectors. (SR)
In your minds eye you see the projectile and its historical path (past and future) as a smooth parabolic curve.  But if you could zoom into a small portion of the curve on the smallest scale you would actually see a staircase of alternating horizontal and vertical increments representing the momentum given by gravity and the momentum given to the projectile by some previous force. In the freely falling projectile case there are no horizontal increments so all you see are the vertical ones. In the second case the same vertical increments are carried over and the horizontal increments are alternately inserted getting smaller and smaller.  Thus while the vertical increments remain constant (they both accelerate at the same rate), the horizontal increments are variable and independent.  Do not confuse momentum with a purely geometric parabolic construction.  The projectile is not actually tracing out the smooth parabolic curve.  The curve is just your perception of what is the case just as a million sided polygon would appear to be a circle. (GR)
