More generally, an address space is just the set of valid (and distinct) addresses in an addressing scheme, together with special rules governing the application of these addresses
For example, in IP (Internet Protocol, or, more strictly IPv4), it is the set of IP addresses 0.0.0.0 -> 255.255.255.255 together with the special rules governing the use of some of these addresses (eg. some special addresses, like 127.0.0.0 -> 127.255.255.255, the RFC 1918 private addresses, 192.168.0.0 -> 192.168.255.255 and so on, are guaranteed non-routable on the public Internet).
Another example would be the MAC addresses which are used for the unique identification of ethernet network interfaces (i.e. network cards) which consist of six pairs of hexadecimal digits each. For example my MAC adddress is 00:20:AF:0E:3B:C2, from which it is possible to deduce that I have a 3com network card, since the first 3 pairs of hex digits, "00:20:AF", are assigned exclusively for the use of 3com - they have their own address space, consisting of 00:20:AF:00:00:00 -> 00:20:AF:FF:FF:FF within the overall MAC address space. (Although, strictly speaking, some cards and machines have programmable MAC addresses, so you couldn't be absolutely certain.)
A more complex example would be the set of valid hostnames which are able to be registered and made active in the global DNS (Domain Naming Service) system. The rules here are complex and difficult to define because, though the limits imposed by the DNS technology itself (i.e., in practice, what will run correctly when entered into the BIND configuration files) are clear, political and social factors influence what you can actually register at the different national naming registries around the globe and the effective 'address space' changes constantly.
Often, it's useful to be able to introduce a mapping from one address space to another. "Address Resolution Protocol" or ARP, does this for mapping between IP and Ethernet addresses, and of course the DNS service maps between hostnames and IP.
Where the addresses are in (more or less) alphanumeric form, as in hostnames (or E2 node titles, for that matter), it's common to call the address space a namespace.