Crime wouldn't increase in a libertarian society because there would be fewer laws on the books and a free system of civil rights and civil liberties would ensue. People would be responsible for their own protection and the government would step in less to help its poorest citizens in a libertarian world. Fewer laws means fewer crimes because things such as illegal drugs wouldn't exist--drugs would be legal and punishments for having those substances would no longer exist.
In a libertarian society, everyone pretty much does whatever they want with limited government. There would be less crime because anyone who tries to perpetrate a crime would get a gun pointed at their face. Plus, there would be less crime because there are fewer laws to enforce. Fewer laws mean fewer lawbreakers.