In the first episode, when Kirito was showing Klein the ropes of combat, the conversation goes

Kirito: However, there is no magic.

Klein: An RPG without magic? That is a bold decision.

However later on in the show, Kirito visits Lizbeth's shop in Temperature of the Heart.. Kirito is in shop for another sword, and shows Lizbeth his Elucidator.

Lizbeth responds with:

An Elucidator! This is the gnarliest magic sword a person can get from a monster drop.

If magic did not exist, how would there be a magic sword?