I know you have to keep dividing by 2 and prove that it is still negative but I don't know how to prove it as a full proof
You basically have it already in your update. You just have to write it down a little more formally.
Assume that there is a greatest negative rational number r.
The number is of the form r = -p/q, where p and q are positive integers.
Divide that number by 2 to get -p/2q.
That new number is rational and negative since 2q is a positive integer and that doesn't affect the sign or the rationality.
But let's compare -p/q and -p/2q.
Take the absolute value of each:
|-p/q| = p/q
|-p/2q| = p/2q
If we compare these we see:
1(p/q) > ½(p/q)
1 > ½
The absolute value is another way of describing the distance from the number to zero. Since -p/q is further from zero and they are both negative, that means -p/2q is closer to zero and thus greater.
But this contradicts our initial statement that r = -p/q is the largest negative rational number.
QED: There is no negative rational number greater than all other negative rational numbers.
Easy. Let X be that greatest negative rational number. But then (1/2)x is greater, and is also rational. Contradicting the assumption.