What does it mean when a codec is "lossless"?
Imagine you want to encode something like y = 2 * sin(2 * x) + .1 * sin(10 * x) to save space.
http://www.wolframalpha.com/input/?i=sin%28x%29+%2B+.1*sin%2...
That is composed of two different sine waves added together - one low frequency, large amplitude and one high frequency low amplitude. That can be encoded two different ways - lossy or lossless.
A lossy encoder gets rid of unimportant data and keeps a "close enough" representation of the original. In this example, .1 * sin(10 * t) is a minor component of the overall signal (plot them separately if you need to compare the difference) so the encoder chooses to delete it and only save 2 * sin(2 * t). In a real world sound, this would be like throwing away noise that is so high pitched we can't hear it, or is so quiet we can't detect it. A real encoder has to decide what the "small enough it can be deleted" threshold is, and it's rarely black and white.
A lossless encoder looks at that signal and thinks "there has got to be a more efficient way to store that data". They are both sine functions, so that doesn't need to be repeated twice. "x" is completely unnecessary, because it knows the sine functions are dependent on some variable. So, it could write out something like "sin (2,2) (.1,10)". All of the original data is still there, if whoever receives the data (the decoder) knows how to interpret it.
Also, even if you don't go that far, many lossless algorithms operate by first providing an approximation and then including the (usually small) deltas between the approximation and the actual bitstream.
Beyond that, discrete Fourier and cosine transforms as usually implemented are not fully reversible because of loss in precision. A colleague of mine blogged about the issue in the context of Haar transforms a few years ago: http://cbloomrants.blogspot.com/2008/09/09-08-08-1.html. By decomposing an orthogonal transform into shears as explained by Charles, you can design reversible fixed-precision variants of the DCT like binDCT: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.8...
The original point the OP made was a bad example. Unfortunately I made a poor attempt at explaining that.
Audio codecs don't try to find functions that describe waves, they sample the waves.
What you get from a microphone or an electric guitar is a changing voltage, a wave of some sort. To digitize that wave (i.e. to save it using numbers and not vinyl discs or magnetic tape) you take samples (i.e. measure the voltage) at regular intervals. You typically might do that 48k times or 96k times per second (i.e. have a sampling frequency of 48kHz or 96kHz).
What you do then with those samples is quantize them, i.e. they get an integer depinding on how high or low the voltage is, for example a 16 Bit number.
That's how an analog-digital converter works on a basic level (you also need an filter to get rid of all the frequencies you don't want to digitize). This process is of course lossy. It's not possible to recontruct the wave that was digitized perfectly, it's only an approximation. All analog-digital converters are lossy (in some sense of the word). If you sample at 48kHz all frequencies higher than half of that (24kHz) are irrevocably lost (look up the Nyquist-Shannon Sampling Theorem if you want to know more). Quantization also means that you have to round the voltage you are measuring up or down, the audible effect this has on the sound is that it adds noise.
The parameters are, however, usually chosen in such a way that a human ear can't tell the difference. A healthy and young ear can hear frequencies up to about 20kHz, that's why the music on CDs is sampled at 44.1kHz (40kHz with some safety margin).
But that's only the conversion and it has not much to do with lossy codecs.
A lossless codec takes the result of this digitization (let's say 48k 16Bit numbers for a one second sound) and encodes them in such a way that those exact same 48k 16Bit numbers can be reconstructed after decoding.
Re-encoding a sound file with a lossless codec can consequently still be lossy: If you change the parameters (e.g. you half the sampling rate) you are still losing imformation - but it's at least possible to preserve the result of the original digitization perfectly.
A lossy codec doesn't aim for perfect reconstruction of all the numbers. It uses quirks in human hearing to be more or less precise about how those numbers are reconstructed. For example: A really loud sound masks quieter sounds. It's not possible for humans to hear that quieter sound, so why bother with all that precision for that quiet sound? That's where, for example, MP3 can dynamically decrease the quality. It's quite ingenious, really.
It is of course inevitable that during that process information is lost. It's not possible to get those original 48k numbers back, but at least something that sounds to an human ear more or less like them.
A nice explanation of the 44.1kHz is here: http://www.cs.columbia.edu/~hgs/audio/44.1.html
Initially digital video tracks were used and as such they were constrained by the video formats commonly recorded on them and the playback devices coming with that.
In the image space, PNGs are likewise lossless, whereas JPEG causes a loss of fidelity.
Unlike MP3 which uses a number of lossy compression techniques, including psychoacoustics, that are specifically designed to reduce the bitrate of an audio stream with minimal artifacts.
Lossy: jpeg.
Lossless: PNG
Lossy: JPEG