Most definitions of fantasy involve the supernatural or the impossible. A typical example can be found in Manlove’s Modern Fantasy. He there defines fantasy as
…a fiction evoking wonder and containing a substantial and irreducible element of supernatural or impossible worlds, beings or objects with which the mortal characters or the readers of the story become on at least partly familiar terms.
I think that this is a good definition as far as it goes. It dwells on material elements, but then, the definition of any art-form necessarily does. For instance, a painting is an arrangement of pigments on a plane surface. It’s our idea of what sort of beauty painting aims at that allows us to argue whether a particular piece is or isn't good. Still, when I come to consider what sort of beauty fantasy aims at, I wonder if Manlove's definition doesn’t miss the point after all. A painting without ground or pigments can't very well be conceived. But can we conceive of a fantasy without "supernatural or impossible worlds," etc.? Perhaps so, in a way. Certainly some existing fantasies come very close, e.g., Titus Groan, as Manlove concedes. And it is easy to think of books that involve the elements Manlove lists but that are almost universally recognized as being something other than fantasy.
What is crucial, I think, is not the possibility or impossibility of the world, but the way the world is presented. It’s just that "impossible" worlds lend themselves to this sort of holistic presentation. The crumbling castle-world of Gormenghast is a well-considered, closed system, and its denizens are woven into its very fabric. The same is true of Middle-Earth, Perelandra, Narnia, Tormance, Earthsea, and Arrakis. Perhaps this interdependence of inhabitants and environment is what makes fantasy fantasy.
Gary Wolfe, in "The Encounter with Fantasy," argues that it is a mistake to regard fantasy merely as the fictional presentation of the supernatural or the impossible, or even as fiction that "evokes wonder"—the latter being a subjective criterion that allows for no bad fantasies. Wolfe suggests that the overall affective structure is what makes fantasy fantasy. For fantasy has both a cognitive and an affective aspect. The latter may be a little difficult to get our hands on, but it is nevertheless an objective element.
Wolfe goes on to note that the most successful fantasies overlie an objective set of beliefs held by the author. One has the Christian Platonism of Lewis, for instance, or the Catholicism of Tolkien, or the Taoism of Le Guin, or the anti-Aestheticism of Lindsay, or the quasi-Nietzschean paganism of Eddison. However, these beliefs are subordinate to the final form of the work as a work of fantasy, and one need not share them to enjoy the work in question.
Fantasy indeed tries to set us free by making us captive to belief, but since the kind of belief that is peculiar to fantasy arises as much from affect as from cognition, it is not necessary for us to share an author's philosophies or beliefs that are external to the work for us to accept and "believe in" their embodiment in the narrative… Fantasy authors who are most successful at creating his kind of belief attempt neither to allegorize their own systems of belief nor to subordinate those systems to sensation. Instead, they achieve a balanced tension—perhaps more properly a dialectic—between cognition and affect, between moralism and passion, between the impossible and the inevitable. They do not merely construct metaphors for a preconceived reality, or if they do, the power of the metaphors is apt to transform the nature of those preconceptions into something new.
The focus on material elements such as elves and imaginary countries is what leads to all the delightful hair-splitting one finds in wikipedia articles on the subject, arguments about which category such-and-such a book really fits into based on the presence of this or that element. It is all quite beside the point apart from the purely commercial point of view. Books like Dune or The Time Machine should be classed with books like The Lord of the Rings or A Voyage to Arcturus or the Earthsea trilogy. If they aren’t, then the lines need to be redrawn.