What's the chance that a number randomly drawn from a set of numbers is bigger than one drawn before it? It has been a long time since last I opened a book on probability/statistics, so this might actually be a very basic question.
Let's say I have a set $S = \{1, 2, \cdots, 5000\}$. Clearly, $S$ has 5000 elements.
Now, I select a number randomly from $S$ and remove it (I reassign $S = S\backslash\{a^0\}$), where I'm calling the number $a^0$. Now, $S$ has 4999 elements.
If I select and then remove a second number at random, called $a^*$, what is the probability that $a^* > a^0$?

So, after removing $a^0$, we have 4999 elements in the set. The chance that a number in the set is greater than $a^0$ will be 
$$
P(a^*>a^0)= \dfrac{\mbox{number of elements greater than $a^0$}}{\mbox{number of elements remaining}} = \dfrac{\mbox{number of elements greater than $a^0$}}{4999}
$$
Let's try a simpler example, $T = \{1,2,3,4\}$.
I pick | P(a^*>a^0)
     1 | 1
     2 | 2/3
     3 | 1/3
     4 | 0


I thought about looking at the expected value as well.
$$
E(X) = \sum xP(x) = x_0 P(x_0) + x_1 P(x_1) + \cdots + x_n P(x_n)
$$
Applying this to the diminished set, we have
$$
E(S) = \sum aP(a) = a_0P(a_0) + \cdots + a_{5000}P(a_{5000})
$$
Now, $P(a_i) = 1/4999$ for all $i = 1,\cdots,5000$ except for when $i=i^0 \implies a_{i^{0}} = a^0 \implies P(a_{i^{0}}) = 0$.
So a rough estimate of the expectation is $E(S) = \frac{1}{4999}\sum_{k=1}^{5000} k = 5001 \times 2500 \div 4999 \approx 2501.00020004$. Obviously, this is quite far off. For example, $a^0 = 5000$ means that we will have an error in our expectation greater than $1$!

I'm editing because there were a lot of comments and I think I was unclear.
When selecting the first number $a^0$, each number has probability $1/5000$ of being drawn. Hence, the expected value drawn is $(1+2+\cdots+5000)/5000 = 2500\times5001\div5000 = 5001/2$ (using the definition of the expectation). This was mentioned by André Nicolas below.
But remember: I remove $a^0$ after drawing it, so the size of the set decreases by 1.
So now I'll draw for the second time, from the set with $a^0$ removed.
Each number still in the set has probability $1/4999$ of being drawn. But our sum in the numerator is missing $a^0$.
So the expected value is $(1+2+\cdots+5000 - a^0)/4999$. Is there a way of making this value more explicit?

Sorry if you think I'm being obtuse; I just really don't get it! 

The probability is $\frac12$ by symmetry. Since all numbers are by assumption equiprobable, for each pair you have the same probability of drawing first the one number and then the other or vice versa.
