I stumbled upon this question by trying to prove that the rationals $\Bbb Q$ are not uncountable, but not by using the knowledge that they are already provably countable. I think I forbid myself using a proof by contradiction. But then, can I even show that the reals are uncountable in a construcive way. In the end, any kind of diagonal argument is using proof by contradiction, right? So in more general terms:
Can I show the existence of an infinite set with no bijection to $\Bbb N$ without using proof by contradiction?
I found this, and read from it that this seems to be a hard and still studied question for the reals. But I ask this in more general terms.