Results 1 to 5 of 5

Math Help - self-contradictory recursive problem

  1. #1
    Newbie
    Joined
    Mar 2008
    Posts
    1

    self-contradictory recursive problem

    "Let the barber of Seville shave every man of Seville who does not shave himself.
    Who shall shave the barber?"

    So my book says that this is self-contradictory. but how?

    From my reading of it, it's just that the barber of Seville shaves every man in Seville who doesn't shave themselves. Well the barber doesn't have to shave himself (or he could shave himself). So then someone else can shave the barber along with every man of Seville (and those who do not shave themselves can be shaved twice...)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Who shaves him? If he shaves himself that is impossible for he shaves everyone who does not shave himself. If he does not shave himself then he has to shave himself because he shaves everyone who does not shave himself.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by inquilinekea View Post
    "Let the barber of Seville shave every man of Seville who does not shave himself.
    Who shall shave the barber?"

    So my book says that this is self-contradictory. but how?

    From my reading of it, it's just that the barber of Seville shaves every man in Seville who doesn't shave themselves. Well the barber doesn't have to shave himself (or he could shave himself). So then someone else can shave the barber along with every man of Seville (and those who do not shave themselves can be shaved twice...)
    Another possibility is that nobody shaves the barber because she doesn't grow a beard.

    This question ilustrates the difference between mathematics and real life. A mathematical model of a real-life problem often contains many unstated assumptions. In this case, it is assumed that the men of Seville form a precisely identified set which contains the barber and on which the relation "shaves" is a function. That is to say, each man in the set is shaved by exactly one man in the set.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2008
    Posts
    148
    Self-referential statements can lead to all kinds of fun paradoxes. Whether or not a statement is actually paradoxical and how one can resolve the paradox is a topic of much discussion in philosophy and mathematics. Your problem is an example of Russel's Paradox: Does the set of all those sets that do not contain themselves contain itself?

    One of my favorites is: "The smallest integer not definable in fewer than twelve English words." This takes a bit of thought to see why it is a paradox.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by iknowone View Post
    Your problem is an example of Russel's Paradox: Does the set of all those sets that do not contain themselves contain itself?
    But it is not really a paradox in math. The point of this paradox is to show that the set of all sets cannot exist. Suppose that \mathcal{S} is the set of all sets then by the Axiom Schema of Compresension that set \{ x \in \mathcal{S} | x\not \in x \} will exist. But this set will lead to a contradiction. Thus, the set of all sets cannot exist.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: April 27th 2010, 07:57 AM
  2. Don't know what to do here, recursive problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 12th 2009, 07:28 PM
  3. A Recursive Function Problem in Mathematica
    Posted in the Math Software Forum
    Replies: 2
    Last Post: July 1st 2009, 02:20 PM
  4. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 29th 2009, 07:32 AM
  5. Recursive Deinition of order pairs problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 5th 2008, 12:45 PM

Search Tags


/mathhelpforum @mathhelpforum