Question

Let \(S\) be a binary predicate symbol. Show \(\models \neg \exists y \forall x(S(y, x) \leftrightarrow \neg S(x, x))\). (Think of " \(y\) shaves \(x\) " and recall Russell's barber's paradox).

Short answer

The proposition holds because assuming such \(y\) leads to a contradiction, illustrating a similar scenario to Russell's paradox.

Step-by-step solution

Understand the Predicate

We are given a binary predicate symbol \(S(y, x)\). Think of \(S(y, x)\) as "\(y\) shaves \(x\)." The expression \(S(y, x) \leftrightarrow eg S(x, x)\) means the following: \(y\) shaves \(x\) if and only if \(x\) does not shave himself.

Analyze the Given Logical Expression

The expression to consider is \(eg \exists y \forall x (S(y, x) \leftrightarrow eg S(x, x))\), which translates to 'it is not the case that there exists a person \(y\) such that for every person \(x\), \(y\) shaves \(x\) if and only if \(x\) does not shave himself.'

Familiarize with Russell's Paradox

Recall Russell's barber paradox, which implies the logical inconsistency where a barber (\(y\)) is supposed to shave all those who do not shave themselves (\(x\)), leading to a paradox if one tries to determine whether the barber shaves himself.

Prove the Non-Existence

Suppose such a \(y\) exists. Then, \(y\) shaves a person \(x\) if and only if \(x\) does not shave himself. Examine \(y\): does \(y\) shave \(y\) or not? If \(y\) shaves \(y\), then by definition, \(y\) should not shave \(y\), leading to inconsistency. If \(y\) does not shave \(y\), then \(y\) should shave \(y\), again leading to inconsistency. Thus, no such \(y\) can exist.

Conclusion

Conclusion is drawn based on the contradiction: there cannot exist such \(y\), with no possible consistent assignment for who shaves whom without inconsistency. Thus, \(eg \exists y \forall x (S(y, x) \leftrightarrow eg S(x, x))\) is valid.

Key concepts

Russell's Paradox

Russell's paradox is a famous problem in the realm of set theory and logic. Put forth by the British philosopher Bertrand Russell in the early 20th century, the paradox highlights a contradiction in naive set theory through the concept of a "set of all sets that do not contain themselves." When translated into everyday terms, it turns into a paradoxical situation, commonly explained using the barber's paradox.
This scenario describes a barber who shaves everyone who does not shave themselves. The paradox arises when we ask: does the barber shave himself?
If he does, according to the rule, he should not; if he does not, then he should shave himself.
This contradiction showcases the complications that can arise when self-reference and set membership collide, revealing logical inconsistencies in how we define certain sets or predicates.

Quantifiers

In predicate logic, quantifiers are symbols that express the quantity of specimens in the domain of discourse that satisfy an open formula. There are two primary quantifiers we use: ∀ (universal quantifier) and ∃ (existential quantifier).

• The universal quantifier ∀ translates to "for all" and implies that the expression it qualifies is true for every possible instance in the domain.
• The existential quantifier ∃ translates to "there exists" and means that there is at least one instance in the domain where the expression it qualifies is true.

Understanding these quantifiers is crucial for interpreting and constructing logical formulas in predicate logic.
They help determine whether scenarios like Russell’s paradox can consistently occur within given constraints.
For example, in the expression given in the original exercise, \( \exists \, y \forall \, x ( S(y, x) \leftrightarrow eg S(x, x) ) \,\), we are examining whether there exists a person \(y\) for whom a condition holds for all individuals \(x\).

Logical Inconsistency

Logical inconsistency arises when a set of statements or propositions cannot all be true at the same time. It occurs quite visibly in foundational paradoxes like Russell's.
Inconsistent logic usually results from contradictory premises, much like in the barber's paradox.
When trying to define whether such a barber can exist, the definition itself defeats its possibility—shaving conditions generate a logical inconsistency.
In predicate logic, logical inconsistence makes it impossible to make a true, consistent assignment across the predicates involved.
For the exercise, the logical inconsistency is inherent in the condition \( S(y, x) \leftrightarrow eg S(x, x) \), meaning the barber \( y \) cannot exist without leading to contradictions.
This demonstrates how reliance on flawed premises can lead to overall failure in defining logical truth.

Binary Predicates

Binary predicates are logical expressions that involve a relation between two entities or variables. In predicate logic, a binary predicate is usually denoted as \( S(y, x) \), implying a certain relationship between \( y \) and \( x \).
In the context of the original exercise, the binary predicate involves the concept of shaving, where \(S(y, x)\) denotes "\(y\) shaves \(x\)."
Understanding binary predicates is essential for modeling complex relationships or hierarchies within logical systems.

• They allow us to build statements that better represent and dissect real-world scenarios by detailing pairwise interactions or conditions.
• They underpin the expression of many common relational concepts, such as "greater than," "likes," or "is a parent of."

In the exercise, the binary predicate leads to paradox when trying to resolve how one entity relates to itself or another entity within given logical constraints.