Functional programming languages have an underlying model based on function composition (with one argument functions, etc.). To the extent that they have arguments with multiple functions, etc., it's ultimately just syntactic sugar and optimizing for common cases - While nobody generally writes the low-level "lambda calculus virtual machine language" stuff by hand outside of academic papers or bootstrapping, Scheme's "let" is implemented in terms of lambda at compile-time. (Scheme without set! is representative.)
Imperative languages have a fundamental underlying model of cells in memory and sequential operations that modify them, branch based on them, etc., including an instruction pointer specifying where instructions are currently read. (C is representative.)
Intuitively (and without busting out the Greek letters): compare languages for which functions are a list of expressions, and return the value of the last, versus languages for which functions are a list of statements executed sequentially, the last of which can optionally return a value. A lot of other issues are ultimately due to how that choice directs default behavior. Even when a language has the amenities to borrow the other's tools, the defaults channel common usage.
Likewise: Relational databases are ultimately based on the relational model, even when parts of SQL fill in conceptually irrelevant details for sake of performance; Prolog is based on backtracking and Horn clauses, and well-structured Prolog can be reasoned about in terms of them, even when cuts are used to avoid wandering about needlessly in known dead ends. The ultimate result would (eventually) be the same. Both models are fundamentally different from pure functional or imperative programming, as well, and the languages built on them are as different as Erlang is from Smalltalk.
I'm self-taught and not a mathematician, so I couldn't give a really exhaustive or formal analysis of the distinction -- probably the best way to understand it (and learn quite a bit else, PS) is to work through the exercises in SICP and CTM. The second chapter of SICP includes Church encoding (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html...), among many other things. SICP covers functional programming quite well, but CTM makes the fundamental differences between the different programming models and their strengths and weaknesses clearer.
You can use functional idioms in imperative languages, but they may lack features such as tail call optimization or garbage collection, which mean that you're working at cross-purposes to both the semantics of the language and the cases for which its implementation has been optimized. Whether this means attempting to do so is actually infeasible (e.g. stack overflows in Python) or just slow and/or verbose depends on the language. Likewise, modeling problems in functional languages that are intrinsically better-suited to imperative languages can be messy and confusing.
(OO is a completely different direction, but as people have wildly inconsistent ideas of what it actually refers to, I'm not going there.)
The implementation details, such as the in-memory format of integers, are irrelevant to the language.