@Lewis It is indeed the same Euler! His work seems to pervade much of modern mathematics.
This is a really fascinating topic to read and think about. You're completely right about our systems of logic never being able to encompass all of mathematics; this was actually proven by Kurt Gödel in his famous incompleteness theorems. In short, the incompleteness theorems tell us that "no consistent system of axioms whose theorems can be listed by an effective procedure (i.e. an algorithm) is capable of proving all truths about the arithmetic of the natural numbers. For any such formal system, there will always be statements about the natural numbers that are true, but that are unprovable within the system."
(quoted from https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems)
As a maths undergraduate I also enjoy thinking about questions like these! I agree for the most part, I think most (if not all) of mathematics is inherent in the universe and is discovered rather than invented, but I think it's less clear in some areas.
With pure/abstract maths (as opposed to maths that can easily be found and applied in the real world) in particular there is room for debate, because there is no physical evidence to verify things, and it's all in our minds. Some branches of maths began with the question of 'what if X was true?' and people just started working under the assumption X and seeing where that would logically take them. There are whole areas of mathematics based on statements that can't be proven to be true or false in our universe, so essentially the entire field is speculation based on an assumption that can't even be confirmed.
My impression is that most people (or most mathematicians at least) think that maths is discovered, but there are a lot of different (and sometimes really bizarre) opinions out there. If anyone wants to read a little about different theories about the nature of mathematics: https://en.wikipedia.org/wiki/Philosophy_of_mathematics#Contemporary_schools_of_thought
Recently a professor of mine used an interesting choice of words during a class; he said something like "...this result was known to Euler in 1765...", and in doing so he avoided entirely the question of whether Euler discovered or 'invented' it (though I suspect he too agrees that it was discovered).