0

My professor showed me Russell's paradox as a proof that the set of all sets doesn't exist. He later proved Cantor's theorem using a similar method.

Question: Are there other theorems that have been proven using the same type of trick?

I have seen some discussion of the relationship between the barber paradox and Russell's paradox, although they appear to be equivalent. I am wondering if there have been other important theorems that were proven using this kind of clever argument.

David Raveh
  • 1,795
  • the zfc set theory is 95% of theorems proved using methods similar to that of russell's paradox and cantor's theorem... infact 90% of theoretical computer science uses the same method..... –  Nov 05 '23 at 08:40
  • @AdityaMishra I didn't know that. Could you elaborate as an answer? – David Raveh Nov 05 '23 at 08:42
  • nothing really to elaborate, its just an observation... most of the theorems you will learn in set theory and theoretical computer science - are proved using similar arguments, basically diagonalizing. There are some snobbish hypocrites who for some reason like to say that godel's first incompleteness isn't diaonalization , instead its a 'diagonal lemma' - claiming they are different - but that's just to look knowledeable - you can basically prove it rigorously that both are exactly the same thing... so ... yeah .. diagonalization is the OG of set theory and computer science –  Nov 05 '23 at 10:32

3 Answers3

1

The halting problem is another example. And of course, the mother of all the self-referencing theorems, The Gödel First incompleteness theorem.

jjagmath
  • 18,214
0

There is a generalization to Cantor's Theorem that you might find interesting.

Theorem ( Cantor's Diagonal Argument )

Let f be a function with domain A

Then D = { x∈A| x∉f(x) }∉Rang(f)

Proof:

Assume otherwise ( RAA)

Then D = f(a) for some a∈A ( as it is in the range of f )

Notice:

a∈D → a∉f(a)=D so a∉D

and

a∉D → a∈f(a)=D so a∈D

thus, a∈D ⟺ a∉D Contradiction

So D is not in the range of f

You can prove all kinds of things with this theorem.

A cute example: In ZF - Foundation, we can prove that if ∀y∈x(y∉y) then x∉x

Proof:

Assume ∀y∈x(y∉y)

Consider the identity function ( maps every element to itself): Id:x → x

Let D = {y∈x| y∉I(y)} = {y∈x| y∉y} by assumption D = x

By Cantor's Diagonal Argument x∉rang(Id) = x

Thus, x∉x.

In some sense, we just proved that sets can "inherit" properties from their elements. If every element in a set is not an element of itself, then the set is not an element of itself either.

Note: This leads us to Russell's Paradox.

As, if R = {y| y∉y)} were a Set, by the above Results

R∉R, but this is a contradiction ( famously) as then R∈R.

Michael Carey
  • 680
0

The principle underlying both proofs is the method of reductio ad absurdum aka negation introduction, which follows the basic structure:

  1. Declare that we want to prove the negation of a statement, $\lnot P$.

  2. Assume instead that the original statement $P$ is true.

  3. Demonstrate that under this assumption we can prove two contradictory statements $Q$ and $\lnot Q$.

  4. Infer that $P$ cannot be true, and hence $\lnot P$ is true.

This might also be called "proof by contradiction", although in some logic systems there's a distinction between the two.

More specifically, they both employ a form of diagonal argument, which just means that the use the structure:

  1. Declare that we want to prove a statement of the form "The set $X$ does not exist."

  2. Assume that the set $X$ does exist.

  3. Produce an object $x$ that simultaneously satisfies and does not satisfy the condition for being in $X$, i.e. show that $x \in X$ and $x \notin X$.

  4. Infer that $X$ cannot exist.

These kind of arguments are common in demonstrating that certain sets are uncountable (as in Cantor's argument), or that certain kinds of systems cannot be self-referential (as in Russel's paradox, or Godel's incompleteness theorems). There are some more examples given in this math.SE post.

ConMan
  • 24,300