I deleted my Macintosh HD

Try using the Internet Recovery option listed here: OS X: About OS X Recovery - Apple Support

You may only boot the computer from the Recovery HD. You cannot install anything on it. Since you have posted this in the wrong forum, you need to tell us what your exact Mac model is, what version of OS X was installed on it, what were you doing when you think you deleted the Macintosh HD volume?

If you reformatted the Mac HD it won't show up on the start up menu until you reinstall OS X on it... use that article I posted to boot to recovery or internet recovery in order to reinstall OS X.

Install or Reinstall OS X from Scratch

Boot to the Recovery HD:

Restart the computer and after the chime press and hold down the COMMAND and R keys until the menu screen appears.

Erase the hard drive:

1. Select Disk Utility from the main menu and click on the Continue button.

2. After DU loads select your startup volume (usually Macintosh HD) from the

left side list. Click on the Erase tab in the DU main window.

3. Set the format type to Mac OS Extended (Journaled.) Optionally, click on

the Security button and set the Zero Data option to one-pass. Click on

the Erase button and wait until the process has completed.

4. Quit DU and return to the main menu.

Reinstall OS X: Select Reinstall OS X and click on the Install button.

Note: You will need an active Internet connection. I suggest using Ethernet if possible

because it is three times faster than wireless.

This should install the version of OS X that you had installed.

Boot the MBA with the OPTION + COMMAND + R keys. The result should be a display with a revolving globe. By following the directions, you will be connected to the Apple servers and should be able to install the original OSX that came with the MBA.

A solid Internet connection will be required.

Ciao.