- #1
solakis1
- 422
- 0
Can we prove in the predicate calculus,that there does not exist someone who can shave all those that do not shave themselfs?? (Russell's Paradox)
Evgeny.Makarov said:Let $S(x,y)$ mean that $x$ shaves $y$. Then the statement that no barber with the desired property exists is
\[
\neg\exists b\,\forall x.\,S(b,x)\leftrightarrow\neg S(x,x).
\]
I believe this is a tautology, so it is provable.
First, Russell's paradox is usually stated about sets. Second, it's difficult to say whether a formula is an exact translation of a claim in the natural language. Sometimes we change the claim into an equivalent one during translation into a formula, but there are infinitely many formulas equivalent to any given formula, so there are many translation variants to choose from. Also, I started the formula with negation, so it is a tautology. If the negation is omitted, it becomes a contradiction, which is more like a paradox. Wikipedia has the following version.solakis said:1)Is the above formula an exact translation of the RASSELL'S papadoxe.
Decidability is not important here. In fact, the word "decidable" has two meanings with respect to logical theories. The modern meaning is that there exists an algorithm that says whether a given formula is in the theory (or is a corollary of the theory) or not. The older meaning, which Gödel used in the title of his article "On Formally Undecidable Propositions"), says that the theory is complete, i.e., derives $A$ or $\neg A$ for every formula $A$. But every first-order theory is complete with respect to the set of all of its models (this is Gödel's completeness theorem). This means that if $T$ is a theory, $A$ is a formula and $I\models A$ for all interpretations $I$ such that $I\models T$, then $T\vdash A$. The problem with arithmetic is that we consider not all models, but the natural model $\mathbb{N}$, and arithmetic is incomplete w.r.t. this model: there exists a formula $A$ such that $\mathbb{N}\models A$, but $\text{PA}\not\vdash A$ where PA stands for Peano Arithmetic.solakis said:2) Is it provable??,since predicate calculus is not a decidable theory
Evgeny.Makarov said:Also, I started the formula with negation, so it is a tautology.
.
Of course not. I am saying that my formula asserts that no barber exists (which is true), while the Wikipedia formula asserts that he exists (which is false).solakis said:So whenever we start a formula in predicate calculus with a negation ,automatically we have created a tautology?
A tautology (rather, a valid formula in the context of first-order logic) is a formula that is true in every interpretation. By completeness theorem, every valid formula is derivable.solakis said:By a tautology ,you mean a valid argument and thus provable, I suppose
How do we formally prove that in set theoryEvgeny.Makarov said:Of course not. I am saying that my formula asserts that no barber exists (which is true), while the Wikipedia formula asserts that he exists (which is false)..
In set theory we can prove $\neg\exists y\,\forall x\,(x\in y\leftrightarrow \neg x\in x)$. We don't even need to use any axioms of set theory, just first-order logic.solakis said:How do we formally prove that in set theory
Russell's Paradox in Predicate Calculus is a logical contradiction that arises when trying to define a set that contains all sets that do not contain themselves. This paradox challenges the notion of sets and their membership criteria in the context of predicate calculus.
Russell's Paradox can be proven in Predicate Calculus by assuming the existence of a set, let's call it R, that contains all sets that do not contain themselves. Using this assumption, a formula can be constructed that leads to a contradiction, thus proving the paradox.
Russell's Paradox is important because it highlights the limitations of set theory and the need for a more rigorous foundation for mathematics. It also has implications for the foundations of logic and the philosophy of mathematics.
While not directly applicable to real-world situations, Russell's Paradox has sparked ongoing discussions and debates in the fields of mathematics, logic, and philosophy. It has also influenced the development of alternative set theories, such as type theory, which aim to avoid such paradoxes.
There is ongoing research and debate on how to resolve or avoid Russell's Paradox. One approach is to modify the standard axioms of set theory to avoid the construction of such paradoxical sets. Another approach is to use alternative set theories, as mentioned above. However, it is important to note that these solutions also have their own limitations and implications.