The Forum for Discussion about The Third Manifesto and Related Matters

You need to log in to create posts and topics.

Relational Theory and the Russell Paradox

Quote from AntC on December 18, 2019, 9:57 am
Quote from Erwin on December 15, 2019, 8:43 pm
Quote from Dave Voorhis on December 12, 2019, 1:49 pm

Here's my Tutorial D equivalent:

I remain puzzled why it takes so much code to tackle such a small problem, but may I suggest a slightly different approach.

From Wikipedia, the problem is this:

You can define the barber as "one who shaves all those, and those only, who do not shave themselves". The question is, does the barber shave himself?

So there is no occupation attribute by which a barber is known, this is the part of the question to be answered. I read this as

  1. A  relation of men
  2. A relation between men of is-shaved-by
  3. A barber query that can determine the set of men who are barbers by the rules given
  4. A shaves-self query on any barber determined by (2).

There are no constraints other than valid keys. The code to implement this is left as an exercise (I could write it in Andl, but it wouldn't really help).

We can add whatever we like to these relations to reflect our little population. Regardless, we shall always find that:

  1. The barber query returns an empty relation. There is no X such that the set of 'X shaves Y' is equal to the set of 'Y is not shaved by Y'.
  2. The question of a self-shaving barber is never resolved.

That's what this paradox looks like in the RM/RA: the set of barbers remains stubbornly empty and queries about them remain unanswered. But perhaps you were looking for something more 'interesting'?

Andl - A New Database Language - andl.org
Quote from dandl on December 19, 2019, 12:27 am
Quote from AntC on December 18, 2019, 9:57 am
Quote from Erwin on December 15, 2019, 8:43 pm
Quote from Dave Voorhis on December 12, 2019, 1:49 pm

Here's my Tutorial D equivalent:

I remain puzzled why it takes so much code to tackle such a small problem, but may I suggest a slightly different approach.

From Wikipedia, the problem is this:

You can define the barber as "one who shaves all those, and those only, who do not shave themselves". The question is, does the barber shave himself?

So there is no occupation attribute by which a barber is known, this is the part of the question to be answered. I read this as

  1. A  relation of men
  2. A relation between men of is-shaved-by
  3. A barber query that can determine the set of men who are barbers by the rules given
  4. A shaves-self query on any barber determined by (2).

There are no constraints other than valid keys. The code to implement this is left as an exercise (I could write it in Andl, but it wouldn't really help).

We can add whatever we like to these relations to reflect our little population. Regardless, we shall always find that:

  1. The barber query returns an empty relation. There is no X such that the set of 'X shaves Y' is equal to the set of 'Y is not shaved by Y'.
  2. The question of a self-shaving barber is never resolved.

That's what this paradox looks like in the RM/RA: the set of barbers remains stubbornly empty and queries about them remain unanswered. But perhaps you were looking for something more 'interesting'?

No constraints (apart from keys)?  So Fred can shave Joe and so can Emile, and Fred can shave himself too, to boot.  I don't see how this represents the scenario in question.  Added moments later: Oh, I suppose keys can look after that.  Sorry!  But it still allows somebody other than both the barber and Fred to shave Fred, doesn't it?

Btw, I once a long time came up with a logical conundrum myself and my friend Adrian Larner told me he thought it was yet another manifestation of the Russell (or Epimenides) paradox:

There are certain people that I regard as my all-time great heroes.  E.g. Shakespeare, Mozart, Beethoven, Jane Austen, Lewis Carrol, JRR Tolkien, Ted Codd, and me.  People suggest that it's rather immodest to include myself on that list of admirable people and on reflection I have to agree that modesty is an admirable quality.  So I resolve to become modest and exclude myself.  But here's the rub: if modesty, in my own eyes, is an admirable quality, don't I, by acquiring it, become in my own eyes an even more admirable person than before?  And in that case, surely I have to stay on that list?

Hugh

Coauthor of The Third Manifesto and related books.
Quote from AntC on December 18, 2019, 4:21 am

Note the 'certain people' with the POOD have never managed to give a coherent account of it, let alone apply it to a reasonably meaty example like the Barber paradox. And IIRC McGoveran explicitly excludes inter-relational constraints from being subject to POOD (at least in one of his pronouncements).

Yes, but that exclusion is extremely superficial and handwavy.  He does not explain the slightest bit about the sense in which the "ignoring" and the "except" should be interpreted :

"The semantic orthogonality property holds in a database design (a particular schema) if and only if, ignoring multi-relation constraints, there is no "overlap" or redundancy between the intended membership of any two relations in the schema. If this is true, then we can add (or remove) tuples to (from) one without that operation in and of itself implying tuples need to be added (or removed) to the other for database consistency, except as required by some multi-relation constraint (e.g., a foreign key)."

To me, that just says that any design that includes all the (logically) needed constraints, is POOD-compliant.  Which in turn means to me that POOD as a principle means just nothing, all the designer needs to do is capture any possible semantic inconsistency and declare the constraints needed to prevent them.  It might be pragmatically beneficial to strive for the number of declared constraints to be minimal, but no such thing is actually stated anywhere.

Quote from Hugh on December 19, 2019, 12:18 pm

don't I, by acquiring it, become in my own eyes an even more admirable person than before?  And in that case, surely I have to stay on that list?

Hugh

No, because the newly acquired modesty helps you value those other admirable qualities as less (e.g. as "not sufficient to be considered admirable") than you did when you were still immodest.

:-)

Quote from Erwin on December 19, 2019, 6:23 pm
Quote from Hugh on December 19, 2019, 12:18 pm

don't I, by acquiring it, become in my own eyes an even more admirable person than before?  And in that case, surely I have to stay on that list?

Hugh

No, because the newly acquired modesty helps you value those other admirable qualities as less (e.g. as "not sufficient to be considered admirable") than you did when you were still immodest.

:-)

Really we should have a more seasonal theme to this paradox:

Santa puts a present in the sock of only those children whose parents don't en-sock a present. Do Santa's children get presents? Who puts their presents in their socks?

Quote from Hugh on December 19, 2019, 12:18 pm
Quote from dandl on December 19, 2019, 12:27 am
Quote from AntC on December 18, 2019, 9:57 am
Quote from Erwin on December 15, 2019, 8:43 pm
Quote from Dave Voorhis on December 12, 2019, 1:49 pm

Here's my Tutorial D equivalent:

I remain puzzled why it takes so much code to tackle such a small problem, but may I suggest a slightly different approach.

From Wikipedia, the problem is this:

You can define the barber as "one who shaves all those, and those only, who do not shave themselves". The question is, does the barber shave himself?

So there is no occupation attribute by which a barber is known, this is the part of the question to be answered. I read this as

  1. A  relation of men
  2. A relation between men of is-shaved-by
  3. A barber query that can determine the set of men who are barbers by the rules given
  4. A shaves-self query on any barber determined by (2).

There are no constraints other than valid keys. The code to implement this is left as an exercise (I could write it in Andl, but it wouldn't really help).

We can add whatever we like to these relations to reflect our little population. Regardless, we shall always find that:

  1. The barber query returns an empty relation. There is no X such that the set of 'X shaves Y' is equal to the set of 'Y is not shaved by Y'.
  2. The question of a self-shaving barber is never resolved.

That's what this paradox looks like in the RM/RA: the set of barbers remains stubbornly empty and queries about them remain unanswered. But perhaps you were looking for something more 'interesting'?

No constraints (apart from keys)?  So Fred can shave Joe and so can Emile, and Fred can shave himself too, to boot.  I don't see how this represents the scenario in question.  Added moments later: Oh, I suppose keys can look after that.  Sorry!  But it still allows somebody other than both the barber and Fred to shave Fred, doesn't it?

Use of definite article "the barber" is in effect a null key for the BARBER relvar: there can be at most one barber. The specification "... those only, who do not shave themselves" is in effect a key for the SHAVES relvar, being the shavee, not the shaver.

But yes to make the possible scenarios more interesting it would be nice to start by allowing all the cases you suggest; then impose tighter constraints; then impose the 'clincher' constraint to see what cases get ruled out at each step.

I realise a couple of things about my attempt to express it in a theorem prover (which is not Datalog):

  • I'm not giving 'contents' of any relvars.
  • I'm not encoding the Closed World Assumption.

Ref Erwin's q: yes the tool shows its proof steps. More informative/useful is asking it to concoct counter-examples. But it wants the counter-examples to be populated by at least 2 (and preferably more) individuals. If we're trying concoct a scenario with exactly one barber, that seems to be giving it indigestion.

 

 

Quote from Hugh on December 19, 2019, 12:18 pm
Quote from dandl on December 19, 2019, 12:27 am
Quote from AntC on December 18, 2019, 9:57 am
Quote from Erwin on December 15, 2019, 8:43 pm
Quote from Dave Voorhis on December 12, 2019, 1:49 pm

Here's my Tutorial D equivalent:

I remain puzzled why it takes so much code to tackle such a small problem, but may I suggest a slightly different approach.

From Wikipedia, the problem is this:

You can define the barber as "one who shaves all those, and those only, who do not shave themselves". The question is, does the barber shave himself?

So there is no occupation attribute by which a barber is known, this is the part of the question to be answered. I read this as

  1. A  relation of men
  2. A relation between men of is-shaved-by
  3. A barber query that can determine the set of men who are barbers by the rules given
  4. A shaves-self query on any barber determined by (2).

There are no constraints other than valid keys. The code to implement this is left as an exercise (I could write it in Andl, but it wouldn't really help).

We can add whatever we like to these relations to reflect our little population. Regardless, we shall always find that:

  1. The barber query returns an empty relation. There is no X such that the set of 'X shaves Y' is equal to the set of 'Y is not shaved by Y'.
  2. The question of a self-shaving barber is never resolved.

That's what this paradox looks like in the RM/RA: the set of barbers remains stubbornly empty and queries about them remain unanswered. But perhaps you were looking for something more 'interesting'?

No constraints (apart from keys)?  So Fred can shave Joe and so can Emile, and Fred can shave himself too, to boot.  I don't see how this represents the scenario in question.  Added moments later: Oh, I suppose keys can look after that.  Sorry!  But it still allows somebody other than both the barber and Fred to shave Fred, doesn't it?

I could always have written more, but it seemed blindingly obvious to me that is-shaved-by would have a key attribute (say shavee) which would be unique, as well as having the obvious FK constraints. So every shavee can only be shaved by a single shaver, which could be the shavee (self-shaver). A missing shavee will presumably grow a beard. . The point is how easy it is to express this in the RM, and how obvious it then is there can be no barber, under those rules. The whole paradox is what we call a furphy.

Btw, I once a long time came up with a logical conundrum myself and my friend Adrian Larner told me he thought it was yet another manifestation of the Russell (or Epimenides) paradox:

There are certain people that I regard as my all-time great heroes.  E.g. Shakespeare, Mozart, Beethoven, Jane Austen, Lewis Carrol, JRR Tolkien, Ted Codd, and me.  People suggest that it's rather immodest to include myself on that list of admirable people and on reflection I have to agree that modesty is an admirable quality.  So I resolve to become modest and exclude myself.  But here's the rub: if modesty, in my own eyes, is an admirable quality, don't I, by acquiring it, become in my own eyes an even more admirable person than before?  And in that case, surely I have to stay on that list?

IMO if you reduce that to a concise problem statement you would come up with something more in the Epimenides than barber vein. It should be easy enough to set up in RM form and populate with suitable candidate heroes. It would be resolved by discovering that there is at least one admirable person who is not modest and/or a modest person who is not admirable. It might be you.

 

Andl - A New Database Language - andl.org
Quote from Hugh on December 19, 2019, 12:18 pm

No constraints (apart from keys)?  So Fred can shave Joe and so can Emile, and Fred can shave himself too, to boot.  I don't see how this represents the scenario in question.  Added moments later: Oh, I suppose keys can look after that.  Sorry!  But it still allows somebody other than both the barber and Fred to shave Fred, doesn't it?

I missed the edit. I think you missed the point.

No-one is defined to be a barber except by satisfying the given condition. Yes, there may be many people who shave others, and are not barbers. Indeed, there is not and can never be a barber. That's the point.

A different problem statement might be: "There is a barber who shaves men; all men shave themselves or are shaved by the barber; who shaves the barber?" Obviously the barber is not a man and the answer is no-one.

Andl - A New Database Language - andl.org
Quote from dandl on December 20, 2019, 12:36 am
Quote from Hugh on December 19, 2019, 12:18 pm
Quote from dandl on December 19, 2019, 12:27 am
Quote from AntC on December 18, 2019, 9:57 am
Quote from Erwin on December 15, 2019, 8:43 pm
Quote from Dave Voorhis on December 12, 2019, 1:49 pm

Here's my Tutorial D equivalent:

I remain puzzled why it takes so much code to tackle such a small problem, but may I suggest a slightly different approach.

There's many possible formulations (and it seems Russell himself airily dismissed the whole thing, so never gave any precise formulation). There's no need to follow wikipedia -- and indeed their formulation adds unnecessary assumptions IMO. But I agree with your implication that Erwin's OP formulation adds rather more assumptions, along with relvars to hold their content.

From Wikipedia, the problem is this:

You can define the barber as "one who shaves all those, and those only, who do not shave themselves". The question is, does the barber shave himself?

"the barber" [definite singular] is going to be problematic, because it carries a presupposition of existence. I'll start in the plural at "barbers shave all and only those who do not shave themselves". That is "barbers if any ...".

There are no constraints other than valid keys.

Let's not assume we need keys. Let's not assume anybody shaves atall; nor if they do shave they always shave themselves or always go to the same barber.

So I won't have a relation PERSON. There might be in the domain of discourse women and/or men who grow beards. I'll have a relation SHAVES that talks only about those who do shave. Presumably the purpose of a BARBER relation is to identify those qualified to shave others -- we don't want random strangers waving sharp implements about near people's faces. I'll merely require anybody who does shave others to themselves be shaven. (This'll provide mutual quality control amongst barbers; and avoid wriggling out via women barbers.)

I want to allow scenarios:

  • Nobody shaves/gets shaved. The empty database, as allowed by OP.
  • All who get shaved, shave themselves. As allowed by OP.
  • People might both shave themselves sometimes and get shaved other times. (So a given shavee might have several entries in the SHAVES relation.)
  • The same person might go to a variety of barbers. (So ditto.)
  • Two barbers who shave each other. (At least, up to a guild of barbers mutually maintaining quality control.)
  • Some barbers might have no customers.

And then later impose a constraint there is at most one barber. That is, of the last two barbers, one quits business.

Code to follow.

Quote from AntC on December 21, 2019, 11:22 am

I remain puzzled why it takes so much code to tackle such a small problem, but may I suggest a slightly different approach.

There's many possible formulations (and it seems Russell himself airily dismissed the whole thing, so never gave any precise formulation). There's no need to follow wikipedia -- and indeed their formulation adds unnecessary assumptions IMO. But I agree with your implication that Erwin's OP formulation adds rather more assumptions, along with relvars to hold their content.

I took the wording in Wikipedia as a quote. I have now confirmed that it is so: ref.

From Wikipedia, the problem is this:

You can define the barber as "one who shaves all those, and those only, who do not shave themselves". The question is, does the barber shave himself?

"the barber" [definite singular] is going to be problematic, because it carries a presupposition of existence. I'll start in the plural at "barbers shave all and only those who do not shave themselves". That is "barbers if any ...".

In my use of English, the form is one of definition, not of existence. It reads that anyone who '...' is by definition 'a barber'. But by all means pose and hopefully solve a different problem.

There are no constraints other than valid keys.

Let's not assume we need keys. Let's not assume anybody shaves atall; nor if they do shave they always shave themselves or always go to the same barber.

So I won't have a relation PERSON. There might be in the domain of discourse women and/or men who grow beards. I'll have a relation SHAVES that talks only about those who do shave. Presumably the purpose of a BARBER relation is to identify those qualified to shave others -- we don't want random strangers waving sharp implements about near people's faces. I'll merely require anybody who does shave others to themselves be shaven. (This'll provide mutual quality control amongst barbers; and avoid wriggling out via women barbers.)

Your first point: the PERSON (or MEN) relation serves only to validate keys. It did nothing beyond allow a query for those who neither shave nor are shaved. Losing it is no loss, unless...

Your second point is a different problem, and I don't see it adds anything. Having a MEN relation seems simpler and safer.

I want to allow scenarios:

  • Nobody shaves/gets shaved. The empty database, as allowed by OP.
  • All who get shaved, shave themselves. As allowed by OP.
  • People might both shave themselves sometimes and get shaved other times. (So a given shavee might have several entries in the SHAVES relation.)
  • The same person might go to a variety of barbers. (So ditto.)

Like I said: this really changes the problem. How do you now define a barber?

  • Two barbers who shave each other. (At least, up to a guild of barbers mutually maintaining quality control.)
  • Some barbers might have no customers.

And then later impose a constraint there is at most one barber. That is, of the last two barbers, one quits business.

Code to follow.

Under the definition we have there are still no barbers, so no guild and none to quit. Or do you have a new problem statement?

Andl - A New Database Language - andl.org