How to justify the existence of a function, in general? Maybe I'm too naive in asking this question, but I think it's important and I'd like to know your answer. So, for example I always see that people just write something like "let $f:R\times R\longrightarrow R$ such that $f(x,y)=x^2y+1$", or for example "Let $g:A\longrightarrow A\times \mathbb{N}$ such that for every function $f:\mathbb{N}\longrightarrow A$ we have $g(f(n))=(f(n),n)$)". They never justify the existence, but rather they assume the function to exist. So my question is why? How do you justify the existence? 
 A: This is a good question. To properly address it one needs to be very precise about what a function is and what it means to have defined/constructed one. So, in the modern era we define a function to be a triple $(A,f,B)$ where $A,B$ are sets and $f\subseteq A\times B$ is a relation from $A$ to $B$. We write $f(x)=y$ as shorthand for $(x,y)\in f$. The condition the relation needs to satisfy in order to be called a function is for all $x,y,z$: $f(x)=y$ together with $f(x)=z$ implies $y=z$.
So now things are reduced to sets. So, when do we say that we defined or constructed a valid set? Well, to answer that we need to be very precise about what sets are. That is tricky. There are different axiomatization and quite a lot of intricate results regarding the foundations of set theory. So, here is just a little bit without getting technical. Defining what sets are is quite hopeless, since what on earth will you define sets in terms of? What is more primitive than a set? (if you have a good answer, please do write a paper about it). Instead, we abandon the idea of defining what sets are, and instead we adopt the axiomatic approach. We don't say what sets are, we say what we can do with sets. 
Well, that's good enough, since we want to know that certain sets exist, so if we know what we can do with sets, perhaps we can show them to exist by following the rules that tell us how to build sets. This turns out to work quite fine, after a bit of work of introducing all that is needed. 
Now, there is a rule of constructing sets that tells you that if you have a formula, like $x^2y+1$, then you can construct a set out of it that consists of all pairs $(x,y)$ of real numbers that satisfy this formula. So, we have a candidate for the function $(\mathbb R,f,\mathbb R)$, we just need to check that this set $f$ indeed satisfies the condition of being a function (which it does for the formula you mention). There are also rules for building sets that allow you to give recursive definitions of functions. 
So, the 'standard' ways of constructing functions are justified by axiomatic set theory. It should be noted though that no model of set theory is known, and that if one is ever found it will immediately imply that the theory is inconsistent. So, the foundations are tricky. We did not rule out that mathematics is free of contradictions, and we never will. But, it seems ok. 
A: For your first example, such a function exists because you've explicitly told us what $f(x,y)$ should be for each $x$ and $y$. On the other hand, $g$ may or may not exist. It isn't immediately clear what to make $g(x)$ for a given $x$.
A: Your first example is the just the composition of several real-valued functions. For simplicity, lets recast it as $f(x)=xxy+1$. It is just the composition of known functions: the multiplication and addition of real numbers. Multiplication maps every pair of real numbers to a real number. Likewise for addition. (Things get more complicated with division and exponentiation.) So, it is easy to verify that for every pair of reals numbers $x$ and $y$, $xxy+1$ gives you a real number, and that $f$ is indeed a function.
Not all functions are defined in terms of simple compositions of known functions, however. If you are starting from, say, Peano's Axioms, and want to prove the existence of an add function on the natural numbers, you would have to construct a suitable subset $A$ of the set of ordered triples of natural numbers (tricky!) and prove that:
$\forall a,b\in N (\exists c\in N((a,b,c)\in A))$
$\forall a,b,c_1, c_2\in N((a,b,c_1)\in A\land(a,b,c_2)\in A \rightarrow c_1=c_2)$ 
Then you would be entitled to use the function notation $A: N^2 \rightarrow N$, or (my preference) $\forall a,b\in N (A(a,b)\in N)$. Then, of course, you would have to prove that the function $A$ has all the required properties of an add function: associativity, commutativity, etc.
BTW, that subset $A$ is such that:
$\forall a,b,c ((a,b,c)\in A \leftrightarrow (a,b,c)\in N^3$ 
$\land \forall d\in P(N^3) (\forall e\in N ((e,1,s(e)\in d))$ 
$\land \forall e,f,g\in N ((e,f,g)\in d \rightarrow (e,s(f),s(g))\in d)$ 
$ \rightarrow (a,b,c)\in d)))$
where $1$ is the first natural number and $s$ is the usual successor function.
From this construction, you can derive:
$\forall a\in N (A(a,1)=s(a)$
$\forall a,b\in N (A(a,s(b))=s(A(a,b)))$
A: In general it suffices to prove that for your function, each $x$ in the domain maps to exactly one $f(x)$ in the codomain. Assuming the existence of a function is therefore equivalent to assuming this property, which is rather trivial to prove in most cases (but not all; Cantor-Bernstein is one notable example where the existence of a function with certain properties is non-obvious).
