Prerequisites: Prime numbers, proof by contradiction
Here’s an awesome, easy, super clever, and really beautiful theorem/proof combination (which I cannot take credit for (Euclid can, though)). Once you’ve learned what a prime number is and how to use proof by contradiction, you’ll be good to go (seriously, that’s it).
The beginning of the list of primes goes as follows: 
Now, there is no reason that there has to be an infinite amount of primes. As numbers get bigger they become more and more divisible (i.e., there are more numbers that are smaller than them, and therefore more candidates for things that could divide them), so it might be plausible for there to be a cut-off point above which every number can be divided and is therefore not prime.
How might we go about proving a statement regarding infinity? If the enemy listed a whole bunch of consecutive non-prime numbers, it might provide evidence for the fact that there is a “largest prime”, but that is in no way a proof. For I could just take the largest number that the enemy gave me and multiply it by itself a hundred billion billion trillion times and tell him to prove that we didn’t “miss” any primes. What do we do?
Proof by contradiction
We will suppose that there is a largest prime, and arrive at a contradiction. This contradiction will force us to draw the opposite conclusion, thus proving our claim. Here we go.
Theorem: There are infinitely many prime numbers.
Proof: Suppose there aren’t. Then there is a “largest prime”. We don’t know what this prime is, but we know it’s out there (because we just supposed it exists), so let’s call it P. Then the entire list of primes looks something like 
Now we can ask whether or not N is prime. Remember, it is one or the other, but not both and not neither.
Well, clearly it can’t be prime, because it’s larger than P and we supposed that P was the largest prime. Thus if N were larger than P and prime, P wouldn’t be the largest prime, which is a contradiction! So then P must be not prime. Now if N is not prime, then N must be divisible by a prime number. This is because N is divisible by something (because it’s not prime), and this something is then either prime or not prime. If this something is prime, then we’ve shown that N is divisible by a prime. If this something is not prime, then this something is in turn divisible by something else. We now just apply the same logic to this “something else”, and eventually we’ll hit a prime. Thus, since we know N is not prime, it must be divisible by a prime.
Recall though that all of the primes are in our list 
QED (which means “you just finished the proof and you’re a boss!” in Latin).
The True Beauty of Math 
There’s something really interesting about Euclid’s proof. It’s always used as an example of proof by contradiction, and it fills this role admirably– it’s clear and concise. However, it doesn’t need to use contradiction!
We can simply show that no finite set of primes contains all primes. The construction is the same: Take any finite set of primes {p_1,p_2…,p_n}. Let’s call it P. Let’s call k the number (p_1*p_2*….*p_n)+1. If this number is prime, then P is not the set of all primes, because k is a prime bigger than any prime in P. If not, there must be some prime not in P which divides k.
Since no finite set of primes is the set of all primes, the set of all primes is must be infinite. (QED)
This proof is really interesting, because it has essentially “the same structure” as the proof you showed, but doesn’t use contradiction. So it raises the question “when can you eliminate contradiction from a proof?” Sometimes (like this example), removing contradiction doesn’t change the proof in a “fundamental way”, but sometimes a proof which doesn’t use contradiction looks very different from the one which does, and *sometimes* you can’t prove something at all without using contradiction!
This same idea works for the proofs you give in lessons 13 and 14! Instead of supposing we have a bijection, we simply take any old function (with the right domain and codomain), and show that it can’t be a bijection for exactly the same reason: we can always find an element in the codomain which isn’t hit by the function.
This is a very good point you bring up, so thanks for doing so! Of course you’re right, we can prove this statement without using proof by contradiction, and there are tons of people who would view this as an objectively “better” way of arriving at the result. (Much of this you’ll already know, but it’s primarily for anyone else who might be taking a gander at our discussion). There is a huge school of thought that believes, in short, that proof by contradiction is not really proof. The main motivation for this is (again, to put it simply) that the lack of something being true does not imply its falseness. The technical term for this school of thought, or really for this model of logic, is intuitionistic logic. Now there is a huge can of worms amongst all of this, and while I’m not an intuitionist myself, I do think there is a lot of cool stuff within it all.
As you pointed out, deviating from contradiction in this case did not cost much: primarily just a re-wording. But as you also mentioned, this is not always the case, and sometimes it’s hard or even impossible to let go of the crutch of contradiction. This is a very cool, subtle, and extremely philosophical question: what does it mean to not be able to prove the truth of a statement, but only the lack of its falseness? (or conversely replacing truth with falseness and falseness with truth). On a social level, it would mean that intuitionists don’t view it as true, whereas others would. But truth with a capital “T” should not depend on our social circles, right? Well therein lies another can of worms that likes to be opened by epistomologists, and one which I simply refuse to open here. Namely, what is truth with a capital “T”?
Sorry for the philosophical ramblings. In short, thanks for bringing up this point. I’ll try to write some more about it in some other posts in a less cheesy and philosophical way than I did just now. I use contradiction here because even though it’s not necessary, I do think it’s easier to digest on the first go at things. But ease is subjective, so maybe some people like your way better. It’s always good to know a few different ways to prove things! (Although I actually think that a lack of contradiction in lessons 13 and 14 might even be better).
(Mostly for the benefit of anyone else reading this)
The philosophical questions that intuitionistic logic raises are really interesting! But besides that, one of the cool things about intuitionistic logic is that it shows up in a lot of applications of logic. The idea is that a proof in intuitionistic logic somehow corresponds to a “construction”– To prove that something is true, you have to construct a “witness” of this fact; you can’t just say “if it’s false, then we get a contradiction.” Computer programs are essentially the same sort of construction, so intuitionistic logic expresses the logic of computer programs. This makes intuitionistic logic a powerful tool for reasoning about whether a program “does what we want”.
Beyond this (and this is probably going beyond the scope of this website), there is a type of structure which allows you to do both geometry and logic in an “abstract way”– the idea is that this type of structure somehow captures the “important” parts of both geometry and logic. But it turns out that the “natural” way to do logic in such a structure precisely lines up with intuitionistic logic! This means that at some fundamental level, there’s something very, very similar about geometry and computation, which is absolutely crazy!