Constructive proof for existence of uncountable sets? 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.

Your question "Can I show the existence of an infinite set with no bijection to N N without using proof by contradiction?" is ill-posed because it does not clarify the nature of "existence" you have in mind.  This is the gist of constructivist objections to classical mathematics as formulated for instance by Errett Bishop.  What you can retain from Cantor's diagonal argument is the following: if you have a map from the natural numbers to the reals then it won't be surjective. This is proved without using the law of excluded middle and in fact this is proved in Bishop's book.
