What framework or tool solves the Barber Paradox?

Question

The Barber Paradox is usually phrased as follows:

I know a barber whose policy is to shave everyone who doesn't shave himself.

If a person shaves himself, the barber does not shave that person.

If the person does not shave himself, then the barber shaves him.

Does the barber shave himself?

First order logic says that this arrives at a contradiction, and yet it is a legal expression and an apparently valid policy in the English language, and perhaps any natural language.

Under what framework can the Barber paradox be solved, (meaning that all of the propositions are valid and true, but result in no contradiction)?

Answer 1

It is worth noting that although the Barber paradox is often compared with Russell's paradox, it does not require any set theory. It can be formulated in elementary logic as follows:

(∃x)(∀y)(Person(x) ∧ (Person(y) → (Shaves(x, y) ↔ ¬Shaves(y, y))))

Where → is the material conditional and ↔ is the material biconditional. From this by instantiation we get

Person(a) ∧ (Person(a) → (Shaves(a, a) ↔ ¬Shaves(a, a)))

and hence:

Shaves(a, a) ↔ ¬Shaves(a, a)

which is a contradiction.

It is not really a paradox. It is just a contradiction. There can be no such barber. It seems paradoxical only because at first glance there does not seem anything odd in the expression, "person who shaves all and only those persons who do not shave themselves". It is only after a little reflection that the contradiction becomes apparent.

There is no plausible way around this paradox. However we must be precise with the wording. Your wording did not specify that the barber is a person, so it leaves open the possibility that it is a robot barber.

Russell's paradox is different, because it arises in the context of naive set theory, in which it is assumed that every property determines a set. There are several ways of responding to this:

1. We can retain classical logic, reject naive set theory and reject the paradoxical sentence as false. This is the most common approach. Rejecting naive set theory usually involves adopting an axiom system such as ZFC or NBG or NF.

2. We can reject classical logic, accept naive set theory and accept the paradoxical sentence as true. This is the approach favoured by dialetheists such as Graham Priest. It allows that we can make non-trivial statements about inconsistent objects. It requires a logic that does not feature explosion.

3. We can reject classical logic, accept naive set theory and avoid the derivation of the paradox. This usually involves using a substructural logic, particularly one that does not include the rule of contraction. Grishin showed that Russell's paradox can be avoided in this way.

Answer 2

We must take care to track the differences between qualified quantifiers like "all other" and "all and only," or then "all and only other," for that matter. If this barber shaves all and only others who don't shave themselves, then he doesn't shave himself. If he shaves all others who don't shave themselves, he yet might shave himself. If he shaves all people whatsoever, he will shave himself. He can't shave all and only those who don't shave themselves (this would give the paradox).

So, a formal system that carefully tracks the different kinds of quantification, here, is one that would "resolve"^E the paradox. Theories about quantification are quite many and varied (see here also for more about generalized quantifiers and here for more about plural quantification).

ADDENDUM: the set-theoretic analogy

This information is meant to complement Jo Wehler's answer. Now, you can generate the Russell set either directly, via naive comprehension, or indirectly, by starting with a universal set and using what we might call "naive separation" on it. This would mean separating out elements from the universal set using the formula "all and only x ∉ x," which would give the paradox again. So, the lesson to be learned is either that naive separation has to go, or some things have but are not elements (we call them "proper classes" and have them be the conceptual reciprocals of ur-elements, which are but don't have elements; but we could just as well call them "sets that aren't contained by other sets," not even singletons say); then the universe either has at least some inseparable elements (some of its elements can't be "factored out" into separate subsets, which means waiving the powerset axiom on the universe, incidentally) or is not a set like other sets.

---

^EI put "resolve" in scare quotes to obliquely indicate that it might be more fitting to say "dissolve" instead. Conifold addressed the dissolution/resolution distinction some time ago here, in a comment on this question.

Answer 3

CAVEAT: Both Bumble and Mauro's answers supercede this argument by making a very informed claim that the Barber paradox is an informal version of Russell's paradox, and therefore do not require set theory and only FOL.

---

Historically, type theory was invented to resolve paradoxes resulting from set theoretic contradictions. The gist of this strategy is that under naive set theory, there are no restrictions on sets as a general rule. Sets contain elements which themselves can be sets. In type theory, we simply say that sets also have types and those types impose constraints on membership employed to avoid contradictions. In pseudo-prolog:

barber
person
person(barber)
selfshaver(person)
not_selfshaver(person)
shaves(person,barber)

Here we can see that '? shaves(_,barber)' returns us:

selfshaver(barber), not_selfshaver(barber)

which isn't problematic, except for that it is true:

selfshaver(person) NOT not_selfshaver(person)

So, to eliminate the contradiction that arises from the construction of our system, we can simply implement a constraint on the set and the rules that process it. Our person must not be a barber:

barber
non-barber_person
non-barber_person NOT barber
selfshaver(non-barber_person)
not_selfshaver(non-barber_person)
selfshaver(non-barber person) NOT not_selfshaver(non-barber person)
shaves(non-barber_person,barber)

Now, no contradiction can be produced by the system. Of course, you can use set theoretical formal semantics to restricts sets in an isomorphic way, but type theory just makes it easier. The notion of type systems are fundamental to preventing contradictions in program logic because they lead to non-deterministic outcomes.

Answer 4

The barber paradox has been formalized as Russell's antinomy of naive set theory: Denote by R the set of all sets S with S not-element of S

R := { S: S not-element of S }

Question: Is R element of R?

• Alternative 1: If R element of R, then R not-element of R by definition of R, a contradiction
• Alternative 2: If R not-element of R then R element of R by definition of R, a contradiction.

Hence the above definition of R leads in both cases to a contradiction. Hence the set R does not exist.

There are several solutions of the paradox. One solution restricts the possibility of constructing sets. It is not allowed to state arbitrary properties which the elements have to satisfy. This solution introduces the new concept of a proper class which by definition cannot be used in the role of an element. For an introduction see Set theory.

Answer 5

Long comment

See Barber paradox: "The barber paradox is a puzzle derived from Russell's paradox. It was used by Bertrand Russell as an illustration of the paradox, though he attributes it to an unnamed person who suggested it to him [B.Russell, "The Philosophy of Logical Atomism" (1919).] The puzzle shows that an apparently plausible scenario is logically impossible. Specifically, it describes a barber who is defined such that he both shaves himself and does not shave himself, which implies that no such barber exists."

In conclusion, the "framework" is formal logic as well as predicate logic (aka first-order logic): the assumption that such a barber exists leads to a contradiction; thus, the assumption is inadmissible. [Nitpicking issue: the first premise must be "There is a barber whose policy is to shave everyone who doesn't shave himself."]

Please, note that - contrary to most answers - no set theory is involved in the paradox.

Also Russell's paradox can be formulated in "pure" logical terms: see this post.

What is the difference between "the Barber" and Russell's paradox? The context of the second one, that we may call the "Logical Theory of Classes".

The theory assumes the so-called Naïve Comprehension principle (in symbols: ∃A ∀x [x∈A ↔ ϕ]) asserting that “There is a class A containing all and only those elements for which the condition expressed by formula ϕ holds."

Using the definition of the "Russell's class" R as ϕ we derive a contradiction, and thus we conclude that R does not exist, and this is inconsistent with the NC principle asserting that every meaningful condition must define a class.

What is the difference with the Barber's case? In this case we have no "Logical Theory of Barbers", and more specifically we have no "axiom" asserting that "Every conceivable barber must exist."

Answer 6

Add a time dimension.

In the real world, the execution of any policy requires time. This is a deficiency of expression in first-order logic, and it is trivially overcome by introducing a concept of sequential processing as is available in any computing language. The barber cannot check whether someone is shaving himself and simultaneously execute a policy in consequence of that observation, since that would violate causality. This is true regardless of the subject and action. No matter how quickly the state is observed, any action taken in consequence of that observation, including a decision, cannot be arrived at in the same moment as the state is observed.

Since the time at which the observation occurs and any consequent action are taken are necessarily different, the resultant state ("shaving" versus "not shaving") on himself will be that of a time-varying periodic function, similar to a ring oscillator:

The instantaneous value at any given point in time will not be in contradiction to the most recently observed state, and hence no logical inconsistency arises. The statement that the barber shaves everyone who does not shave himself is equivalent in the case of the barber's self-reference to a feedback loop into the simple inverter ("NOT") logic gate. The period of the signal will depend on the sampling frequency of the observation and the time taken to perform the shaves. All real-world inversion circuits are causal and therefore must have a propagation delay, pictured as follows for an example physical circuit:

This acknowledgement of causality and introduction of time completely avoids any problem of contradiction due to self-reference.

All statements of the form "If A does B, A does not do B. If A does B, A does B" reduce to the above circuit. This is true without needing any reference to set theory, since the only part of the quantification or set containment that results in a contradiction is the self-reference, hence we simplify the statement to eliminate such extraneous reference. Since the output evolves according to the policy, this statement of necessity expresses a dynamical system, not a static or flat logical statement. The existence of a dynamic consequent requires causality and hence, time. No logical language can deal in dynamical systems or non-static consequents without respecting causality and time.

Simultaneity is already known to be an ill-posed concept according to numerous theories of physics is and this is also the phenomenon behind race conditions in parallel processing. The same solution applies to any problem of self-reference that invokes simultaneity. It may be that there is no contradiction by the simple introduction of time to the logical system being examined.

It is appears to be true that in the absence of time, first order logic cannot adequately express the problem, since "shaving" and "observing that someone does or does not shave himself" are time-constrained, causal activities, incapable of being reduced to timeless, static and invariant propositions irrespective of their structure and dependencies. The lack of a model for causal state or time-dependent (dynamical) relationships in such logic systems makes the conflation of causation and simultaneity into such a "flat" system incapable of representing the problem itself accurately. Turing machines or more generally, computing models that include time as a variable eliminate the contradiction.

Answer 7

It's not really possible to solve, but it is potentially possible to disregard it as an issue. Natural language is messy, so I'll speak of it in terms of the set theoretic version (Does a set that contains all sets that do not contain themselves include itself?). If you view logic and mathematics as constructed, or even imperfectly discovered, you could take a bottom-up approach; statements are generated from the axioms rather than any statement being evaluable by the axioms, so unless the statements can be built up from the axioms and notation, which wouldn't be possible if the axioms don't allow for it, the statements would just be disregarded and not considered to be a statement from within the system. This is what type theory and Zermelo–Fraenkel set theory were made for. If we simply disallow problematic self-reference, then the problem won't apply.

Zermelo–Fraenkel set theory does this by making the creation of sets harder. One can't just add in any set, it has to be carved out from the set's previous form. This gets rid of Russell's paradox because the set of sets that do not contain themselves just can't really be constructed and so it's not considered.

Answer 8

There is no paradox, only an ambiguity.

If I were given the task of writing a program to simulate this, I'd request a specification clarification because, as stated, we can't tell whether he shaves any of his customers, due to time ambiguities in the definitions of "shaves someone" and "shaves themself" preventing them from being evaluated as true or false.

If someone has ever shaved themselves, are they forever in the self-shaving category, for a single shaving incident?

Contrariwise, if they are not at the current moment holding a razor to their throat, are they considered to be in the non-self-shaving category?

If it's time-bounded as "shaved themselves today", then does the barber shave everyone instantaneously at midnight?

So, clearly, the specifications of the problem need to identify:

1. Over what period do you test whether someone has shaved themselves?
2. Over what period does he shave them?

And as soon as you put in a time constraint onto these definitions, then the supposed paradox entirely disappears.

If "shaves a citizen" is defined as something like:

1. "shaves a citizen on entry to his store"
2. "shaves a citizen on request"
3. "shaves a citizen by the end of each day"
4. "shaves a citizen on Tuesday"
5. "shaves a citizen at one or more undefined points in his life"
6. "shaves a citizen when he sees them"

...and if "shaves themself" is defined as something like:

1. "shaved themselves yesterday"
2. "shaved themselves so far today"
3. "shaved themselves ever in the past"
4. "shaved themselves this year"
5. "shaved themselves within some undefined period"
6. "identifies as a self-shaver"

...then we end up with rules like:

1. "The barber shaves shaves each citizen on entry to his store, if they have not shaved themselves yesterday." --> the barber shaves himself only on alternate days.

2. "The barber shaves shaves each citizen on request, if they have not shaved themselves so far today." --> the barber shaves himself whenever he likes, but no more than once a day.

3. "The barber shaves each citizen by the end of each day, if they have never shaved themselves in the past." --> the barber shaves himself only once in his lifetime.

4. "The barber will shave each citizen every Tuesday, if they haven't shaved themselves yet this year" --> the barber will shave himself on the first Tuesday of each year.

5. "The barber will shave each citizen at one or more points in his life, if they haven't shaved themselves in some set time range from those points" --> the barber will shave himself at least once in his life, at the first point he can.

6. "The barber will shave each citizen when he sees them, if they don't identify as a self-shaver" --> the barber will shave himself any time he sees himself and doesn't at that time identify as a self-shaver: if he identifies as self-shaving before actually ever shaving himself, then he'll potentially never shave himself unless he changes his identification.

Whatever time rules you apply to the self-shaving test, and to the shaving action, the problem goes away, because you can then clearly define not just whether but also when the barber shaves himself.

In short: this is not a paradox, even in any natural language; it's just a case of incomplete requirement specifications, which prevent the initial statements from being evaluated as true or false, not just for the barber, but for any of his customers.

Note that it remained a non-paradox, with a clear outcome, even in case 5, where we didn't provide precise specifications. The result was simply true: in every case the barber does shave himself, at least once. So, that's the overall answer to this paradox.

It also remained non-paradoxical in case 6, but with a specification-dependent outcome, as we left undefined what caused the self-shaver flag to become set, but as soon as that's well-defined, the outcome becomes well-defined too.

We could try to make a paradox by having the self-shaving state be continuously tested, rather than being tested only once at the start of shaving. Even then, the answer is non-paradoxical and well-defined once we define whether the state is changed a the start or end of shaving: either "the barber touches the razor to his skin once, then stops," or "the barber shaves himself fully once, then stops."

It gets a bit more paradoxical if shaving is both instantaneous and simultaneous with the state change. Even then, I'd argue that in that case he switches from (shaved=0, self-shaver=0) to (shaved=1, self-shaver=1), so again there's no ambiguity: yes, he shaved himself.

So long as we can evaluate whether any arbitrary customer has the self-shaving state, and know when the barber will evaluate that state and shave them, I can't find any way to make this paradoxical even in natural language.

Answer 9

In natural language that wouldn't even come to the point of the paradox because way before that, just after stating the first sentence:

I know a barber whose policy is to shave everyone who doesn't shave himself.

People would respond with: "Wait a second, what do you mean by 'everyone'? Like there are 8 billion people, even if only include facial hair and exclude those who don't grow it in significant quantities, there's still billions left and the day has only 86400 seconds. So before you're done with that, you'd need to start anew. So no such a barber cannot exist. Period. Case closed.

So in order to proceed to the next sentence you'd already need to limit the scope of "everyone". So either you have to for the sake of the argument, limit the number of people in the vicinity of the barber for whom that claim applies or people are likely to reinterpret the semantic value of that sentence to something like "is shaving customers without discrimination, so no limits to who can be a customer aka everyone". Another option that is also probably directly excluded by non-pedantic people is the idea of a criminally invasive light speed barber who is so addicted to clean shaven skin that he shaves everyone not already shaven regardless of whether people want that or not.

So as natural language and it's speakers usually default to the most likely meaning of a word given a specific context, you'd already need to provide more context to make the one leading to the paradox the most likely, which to be frank it is not.

But fine assume it's a small village with just one barber. So about the next line:

If a person shaves himself, the barber does not shave that person.

That is likely read as a no-information sentence. Like "Duh, why would you visit a barber for their service when you've just done it yourself. Or if you've botched that, you've technically not done the actual thing hence why you go to a professional". It would already require that you've taken the first sentence literally to even see the information in that sentence. Also it requires the personal union of Barber and idk let's call him Frank. While you could also think of "barber" as a job that frank performs 9to5 so that it's not the barber who shaves Frank, but Frank.

Not to mention that authorities evaluating the legal implication of such a claim would likely simply don't care who shaves the barber as long as the barber provides the services they advertise for.

Similarly "shaving" (by a barber) is not just the act of shaving it consists of a service being request, paid for, and finally performed. So if the barber shaves himself would that constitute being shaven by a barber given that he skipped a lot of steps that are otherwise essential to the thing for everyone else. Like if you someone has a stroke and asks for a doctor and a Ph.D in philosophy responds to the request, that is technically being treated by a doctor, but does that count?

So the reason why that is a contradiction in first order logic but not in natural language is that they are operating in a different context and thus use different semantic meanings for the same terminology.