According to the Sorites, all men have beards, they just vary in length, density and coarseness. In a loose sense, a beard must have some appreciable length to be considered a beard. Yet, how much is 'appreciable'? Based on the vagueness of the predicate 'has a beard', I'm not lying when I say such and such, has a beard despite being clean shaven, because what I'm saying is true. Even those people who use the loose sense of the meaning 'beard' would come up with different explanations of what they think a beard is amongst themselves. So, why would someone argue that I lied, if suppose I saw a man rob a store and I tell the police he had a beard despite being clean shaven?
Do you define a lie as "a deliberate attempt to deceive" or as "a statement counter to the facts"? We can presume your statement to the police was a deliberate attempt to deceive, even if it was technically not a statement counter to the facts.
This type of situation is the reason behind the fact that people in a court of law are required to swear to tell the "truth, the whole truth and nothing but the truth." --the phrase the whole truth recognizes the existence of half truths intended to deceive.
As far as the seeming paradox: In natural language, there are many ambiguities, and two exploited by this dilemma are the fuzziness of the definition of "lie" and the fuzziness of the definition of "beard." In a formalized language, on the other hand, ambiguities are eliminated and statements are given exact truth values. Since your statement was not in a formalized language, it is not unusual that it has an ambiguous truth value (see logician Tarksi for more on the subject).
Philosophers call what you're doing "equivocation" - in this case you are equivocating on the definition of a beard.
Given a fixed definition, either the man had a beard or not. Thus, you either told the truth or lied, respectively. There is no logical problem.
You're using two standards here.
When you claim that you lied to the police, you're using that a beard which is very small actually isn't a beard. However, when you claim that you spoke truthfully, you're using that a beard, even though very small, still is a beard.
Of course, when you use two different definitions, the conclusions implied by premises using these definitions don't have to be consistent with each other.
You could rewrite your two statements as:
- It is not true that the man I saw had a beard which was sufficiently long to be noticed.
- It is true that the man I saw had a beard of some length, albeit a very small one.
And these two statements are consistent.
You are trying to argue that "he had a beard" is a true statement, when you actually know that the person was clean shaven. In the normal interpretation of "he had a beard", a clean shaven person does not have a beard. Tomorrow morning, when I haven't shaved for 24 hours, even though you can see beard hair, I do not have a beard. If I then don't shave for the rest of the day, you could say "he is badly shaved", but I still don't have a beard. So in this case, you are telling a lie and you are not saying the truth. If your statement interfered with catching the robber and the police could prove it, and if it was important to them, you could be prosecuted. All this means you picked a bad example.
Now you may say things that are the truth, but you know that they will misinterpreted (in your example, you didn't say the truth). For example, you might say "Joe was arrested for murdering his wife" while fully knowing that the true murderer was found and Joe was fully exonerated. You are telling the truth, you are not telling a lie, but you are intentionally misleading. (That's a situation where saying the truth doesn't protect you in a libel case). So in this case, the truth is not a lie.
But saying a lie means saying something that you believe to be not the truth. You may be wrong. If I tell you truthfully "Jim is in this bar", you mishear it and believe that Joe is in the bar, and then you tell people that Joe isn't in the bar, then your statement is the truth but at the same time a lie.
It's simple my friend, you just didn't tell a lie at all. First, let's try to define what a lie consists of. I define it as any truth-value of a function f(A,p) whose form is "A tells p and p is false" (i.e, "A tells p and ~p"). Note that the first variable term is necessary, since for a proposition to be a lie at all it needs to be told by someone. Now, breaking it down, for the function be true for any of its values is necessary that "A tells p" is true, and "~p" is also true. Supposing the first one evident, we have "Michael Lee 'he had a beard'" is true. Now, for the second part, we have a falsity, since "~'he had a beard'" is false. I.e, is false that he did not have a beard. So, f(A,p) is false for the term Michael Lee and the proposition 'he had a beard'. Which is the same as to say your lie was false, which is the same as to say you didn't lie.
The problem here is that we got into a case of utility. You provided a true information, but it just wasn't useful. If someone comes to me and ask "where's my car keys" and I answer "somewhere", I'm not lying, just not giving him a useful information. The question of usefulness is very important in philosophy and mathematics. For example, in the theory of progressions, which the finite cardinals are part of, why don't we choose as our first element 100? Why choose 0? Because we need to count! There wouldn't be a single paradox if we create mathematics starting from 100, is just not useful..