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 Dave Voorhis on December 12, 2019, 1:49 pm

Here's my Tutorial D equivalent:

// All people in a Russell world...
VAR Person REAL RELATION {ID CHARACTER} KEY {ID};

// ...either shave themselves...
VAR ShavesSelf REAL RELATION {ID CHARACTER} KEY {ID};

// ...or do not shave themselves.
VAR ShavesSelfNot REAL RELATION {ID CHARACTER} KEY {ID};

// The barber
VAR Barber REAL RELATION {ID CHARACTER} KEY {};

// Who shaves who?
VAR Shaves VIRTUAL
   UNION {
     ((EXTEND ShavesSelf: {Shaver := ID, Shavee := ID}) {ALL BUT ID}),
     IF IS_EMPTY(Barber) THEN
       REL {Shaver CHAR, Shavee CHAR} {}
     ELSE
       ((EXTEND ShavesSelfNot: {Shaver := ID FROM TUPLE FROM Barber, Shavee := ID}) {ALL BUT ID})
     END IF
   };

CONSTRAINT C1_All_Persons_Shave_Or_Not
   Person = ShavesSelf UNION ShavesSelfNot;

CONSTRAINT C2_Nobody_Both_Does_And_Does_Not_Shave
   IS_EMPTY(ShavesSelf INTERSECT ShavesSelfNot);

CONSTRAINT C3_Barber_Is_A_Person
   IS_EMPTY(Barber MINUS Person);

CONSTRAINT C4_All_Who_Dont_Shave_Themselves_Are_Shaved_By_Barber
   (Barber JOIN ShavesSelfNot) = (Barber JOIN ((Shaves RENAME {Shaver AS ID})) {ID});

CONSTRAINT C5_All_Who_Shave_Themselves_Are_Shaving_Themselves
   ShavesSelf = ((Shaves WHERE Shaver = Shavee) {Shavee}) RENAME {Shavee AS ID};

// Start with two people, one who shaves and one who does not.
INSERT Person REL {TUP {ID 'Dave'}}, INSERT ShavesSelf REL {TUP {ID 'Dave'}};
INSERT Person REL {TUP {ID 'Nikki'}}, INSERT ShavesSelfNot REL {TUP {ID 'Nikki'}};

Attempting to define a barber fails thusly:

INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelf REL {TUP {ID 'BobTheBarber'}};INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelf REL {TUP {ID 'BobTheBarber'}};

ERROR: RS0285: Update will cause CONSTRAINT C4_All_Who_Dont_Shave_Themselves_Are_Shaved_By_Barber to fail.

INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelfNot REL {TUP {ID 'BobTheBarber'}};INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelfNot REL {TUP {ID 'BobTheBarber'}};

ERROR: RS0285: Update will cause CONSTRAINT C5_All_Who_Shave_Themselves_Are_Shaving_Themselves to fail.

How come inserting Nikki is even possible ?  We got C4 wrong.  Or incomplete.  It's due to the join with empty barber.  Seems it must be rephrased as an equality, same style as C5 : ShaveSelfNot = ...

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:

// All people in a Russell world...
VAR Person REAL RELATION {ID CHARACTER} KEY {ID};

// ...either shave themselves...
VAR ShavesSelf REAL RELATION {ID CHARACTER} KEY {ID};

// ...or do not shave themselves.
VAR ShavesSelfNot REAL RELATION {ID CHARACTER} KEY {ID};

// The barber
VAR Barber REAL RELATION {ID CHARACTER} KEY {};

// Who shaves who?
VAR Shaves VIRTUAL
   UNION {
     ((EXTEND ShavesSelf: {Shaver := ID, Shavee := ID}) {ALL BUT ID}),
     IF IS_EMPTY(Barber) THEN
       REL {Shaver CHAR, Shavee CHAR} {}
     ELSE
       ((EXTEND ShavesSelfNot: {Shaver := ID FROM TUPLE FROM Barber, Shavee := ID}) {ALL BUT ID})
     END IF
   };

CONSTRAINT C1_All_Persons_Shave_Or_Not
   Person = ShavesSelf UNION ShavesSelfNot;

CONSTRAINT C2_Nobody_Both_Does_And_Does_Not_Shave
   IS_EMPTY(ShavesSelf INTERSECT ShavesSelfNot);

CONSTRAINT C3_Barber_Is_A_Person
   IS_EMPTY(Barber MINUS Person);

CONSTRAINT C4_All_Who_Dont_Shave_Themselves_Are_Shaved_By_Barber
   (Barber JOIN ShavesSelfNot) = (Barber JOIN ((Shaves RENAME {Shaver AS ID})) {ID});

CONSTRAINT C5_All_Who_Shave_Themselves_Are_Shaving_Themselves
   ShavesSelf = ((Shaves WHERE Shaver = Shavee) {Shavee}) RENAME {Shavee AS ID};

// Start with two people, one who shaves and one who does not.
INSERT Person REL {TUP {ID 'Dave'}}, INSERT ShavesSelf REL {TUP {ID 'Dave'}};
INSERT Person REL {TUP {ID 'Nikki'}}, INSERT ShavesSelfNot REL {TUP {ID 'Nikki'}};

Attempting to define a barber fails thusly:

INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelf REL {TUP {ID 'BobTheBarber'}};INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelf REL {TUP {ID 'BobTheBarber'}};INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelf REL {TUP {ID 'BobTheBarber'}};

ERROR: RS0285: Update will cause CONSTRAINT C4_All_Who_Dont_Shave_Themselves_Are_Shaved_By_Barber to fail.

INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelfNot REL {TUP {ID 'BobTheBarber'}};INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelfNot REL {TUP {ID 'BobTheBarber'}};INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelfNot REL {TUP {ID 'BobTheBarber'}};

ERROR: RS0285: Update will cause CONSTRAINT C5_All_Who_Shave_Themselves_Are_Shaving_Themselves to fail.

How come inserting Nikki is even possible ?  We got C4 wrong.  Or incomplete.  It's due to the join with empty barber.  Seems it must be rephrased as an equality, same style as C5 : ShaveSelfNot = ...

Line 17 is the escape clause, otherwise you couldn't insert anyone who's shaved by the barber and couldn't insert a barber. And, yes, I think C4 is questionable. I've been thinking  about ways to recast the problem, but they'll have to wait until I have some time.

I'm the forum administrator and lead developer of Rel. Email me at dave@armchair.mb.ca with the Subject 'TTM Forum'. Download Rel from https://reldb.org
Quote from Dave Voorhis on December 15, 2019, 9:49 pm

Line 17 is the escape clause, otherwise you couldn't insert anyone who's shaved by the barber and couldn't insert a barber. And, yes, I think C4 is questionable. I've been thinking  about ways to recast the problem, but they'll have to wait until I have some time.

I'm curious how you judge the correctness of your solution.

It's easy enough to test whether it behaves correctly: the database is not allowed to contain any "barbers who shave only those men who do not shave themselves". You can obtain that result by analysing the problem and coding it directly: disallow inserting any person who is a barber and for whom 'will shave self-shavers' is false.

How will you judge the correctness of your solution where the goals seems to be qualitative, in terms of faithfulness to the original statement of the paradox or other unstated goals? How will you judge the OP goal of a "Russell Paradox smell"?

Andl - A New Database Language - andl.org
Quote from dandl on December 15, 2019, 11:41 pm
Quote from Dave Voorhis on December 15, 2019, 9:49 pm

Line 17 is the escape clause, otherwise you couldn't insert anyone who's shaved by the barber and couldn't insert a barber. And, yes, I think C4 is questionable. I've been thinking  about ways to recast the problem, but they'll have to wait until I have some time.

[...]

How will you judge the correctness of your solution where the goals seems to be qualitative, in terms of faithfulness to the original statement of the paradox or other unstated goals? How will you judge the OP goal of a "Russell Paradox smell"?

The same way we judge the correctness of any solution that can't be automatically evaluated: Rational analysis and logical thinking.

I'm the forum administrator and lead developer of Rel. Email me at dave@armchair.mb.ca with the Subject 'TTM Forum'. Download Rel from https://reldb.org
Quote from Dave Voorhis on December 16, 2019, 10:17 am
Quote from dandl on December 15, 2019, 11:41 pm
Quote from Dave Voorhis on December 15, 2019, 9:49 pm

Line 17 is the escape clause, otherwise you couldn't insert anyone who's shaved by the barber and couldn't insert a barber. And, yes, I think C4 is questionable. I've been thinking  about ways to recast the problem, but they'll have to wait until I have some time.

[...]

How will you judge the correctness of your solution where the goals seems to be qualitative, in terms of faithfulness to the original statement of the paradox or other unstated goals? How will you judge the OP goal of a "Russell Paradox smell"?

The same way we judge the correctness of any solution that can't be automatically evaluated: Rational analysis and logical thinking.

In the case of this particular paradox, we have plenty of materials criss-crossing the ground. I'll quote from wikipedia whilst also noting it's supported by plenty of heavy-duty References and External links. The "smell" is to find a set R:

{\text{Let }}R=\{x\mid x\not \in x\}{\text{, then }}R\in R\iff R\not \in R

In case of the Barber, we have plenty of sets to consider: people; those who shave themselves; those who don't shave themselves; those who are shaved by barber(s); barber(s) even if there's only one of them; ...

For each of those sets, the elements are people. But to get a smell of Russell's Paradox we need a set whose elements (or at least some of them) are sets. That's what the x ∉ x is doing in the formula. I see no set-of-sets in the way the Barber's paradox is formulated.

So I'm agreeing with Russell himself: the Barber paradox is expressible within FOL (and therefore within a relational model); and does not exhibit Russell's Paradox.

Rational analysis/logical thinking/case closed.

Quote from Dave Voorhis on December 16, 2019, 10:17 am
Quote from dandl on December 15, 2019, 11:41 pm
Quote from Dave Voorhis on December 15, 2019, 9:49 pm

Line 17 is the escape clause, otherwise you couldn't insert anyone who's shaved by the barber and couldn't insert a barber. And, yes, I think C4 is questionable. I've been thinking  about ways to recast the problem, but they'll have to wait until I have some time.

[...]

How will you judge the correctness of your solution where the goals seems to be qualitative, in terms of faithfulness to the original statement of the paradox or other unstated goals? How will you judge the OP goal of a "Russell Paradox smell"?

The same way we judge the correctness of any solution that can't be automatically evaluated: Rational analysis and logical thinking.

That's a straight cop-out. It says: I have no idea what I'm looking for but if I look rationally and logically I'll know it when I see it.

Have you thought this through? Do you actually know what you're looking for?

Andl - A New Database Language - andl.org
Quote from dandl on December 16, 2019, 10:05 pm
Quote from Dave Voorhis on December 16, 2019, 10:17 am
Quote from dandl on December 15, 2019, 11:41 pm
Quote from Dave Voorhis on December 15, 2019, 9:49 pm

Line 17 is the escape clause, otherwise you couldn't insert anyone who's shaved by the barber and couldn't insert a barber. And, yes, I think C4 is questionable. I've been thinking  about ways to recast the problem, but they'll have to wait until I have some time.

[...]

How will you judge the correctness of your solution where the goals seems to be qualitative, in terms of faithfulness to the original statement of the paradox or other unstated goals? How will you judge the OP goal of a "Russell Paradox smell"?

The same way we judge the correctness of any solution that can't be automatically evaluated: Rational analysis and logical thinking.

That's a straight cop-out. It says: I have no idea what I'm looking for but if I look rationally and logically I'll know it when I see it.

Have you thought this through? Do you actually know what you're looking for?

Your question is no more or less than, "if you've solved a math problem, how do you know the answer is right?"

It is a math problem, and because it is, my answer is correct.

But to be more specific, I expect problems with a "Russell Paradox smell" -- whether genuinely Russellesque or pseudo paradoxes like the Barber's Paradox -- to be inexpressible, or expressible but result in unavoidable violation of necessary constraints, or expressible but result in infinite recursion.

For example, in playing around with this I managed a moment ago to create a horrible little pseudo paradox (at least, I think it's a pseudo paradox) that runs for a while before it blows the stack and returns null. In Rel, null isn't a thing, so returning null is... something.. .. . that is not... uh... something.

I guess...

I'm the forum administrator and lead developer of Rel. Email me at dave@armchair.mb.ca with the Subject 'TTM Forum'. Download Rel from https://reldb.org
Quote from AntC on December 16, 2019, 9:33 pm
Quote from Dave Voorhis on December 16, 2019, 10:17 am
Quote from dandl on December 15, 2019, 11:41 pm
Quote from Dave Voorhis on December 15, 2019, 9:49 pm

Line 17 is the escape clause, otherwise you couldn't insert anyone who's shaved by the barber and couldn't insert a barber. And, yes, I think C4 is questionable. I've been thinking  about ways to recast the problem, but they'll have to wait until I have some time.

[...]

How will you judge the correctness of your solution where the goals seems to be qualitative, in terms of faithfulness to the original statement of the paradox or other unstated goals? How will you judge the OP goal of a "Russell Paradox smell"?

The same way we judge the correctness of any solution that can't be automatically evaluated: Rational analysis and logical thinking.

In the case of this particular paradox, we have plenty of materials criss-crossing the ground. I'll quote from wikipedia whilst also noting it's supported by plenty of heavy-duty References and External links. The "smell" is to find a set R:

{\text{Let }}R=\{x\mid x\not \in x\}{\text{, then }}R\in R\iff R\not \in R

In case of the Barber, we have plenty of sets to consider: people; those who shave themselves; those who don't shave themselves; those who are shaved by barber(s); barber(s) even if there's only one of them; ...

For each of those sets, the elements are people. But to get a smell of Russell's Paradox we need a set whose elements (or at least some of them) are sets. That's what the x ∉ x is doing in the formula. I see no set-of-sets in the way the Barber's paradox is formulated.

So I'm agreeing with Russell himself: the Barber paradox is expressible within FOL (and therefore within a relational model); and does not exhibit Russell's Paradox.

Agreed. But the OP was referring to the 'ersatz-Russell' paradox of the barber, not the 'kosher-Russell' paradox itself. So if we stick to the barber we should expect to be able to replicate the contradiction of someone who both shaves himself and does not shave himself, and we can resolve that by rejecting the update that would add this person to our database. Or we could allow the update and arrange for the 'shaves himself' attribute to hold the value 'undecidable'. Not all that smelly.

Or we can observe that the RM can express some kinds of sets of sets via self-join. In a family tree, the descendants attribute of any member is a set of sets, which does not include itself, and family is a set of sets including itself, but I don't think we can go up a level to consider a set of sets of sets. So no kosher-Russell that I can see.

 

Andl - A New Database Language - andl.org
Quote from dandl on December 16, 2019, 10:36 pm
Quote from AntC on December 16, 2019, 9:33 pm
Quote from Dave Voorhis on December 16, 2019, 10:17 am
Quote from dandl on December 15, 2019, 11:41 pm
Quote from Dave Voorhis on December 15, 2019, 9:49 pm

Line 17 is the escape clause, otherwise you couldn't insert anyone who's shaved by the barber and couldn't insert a barber. And, yes, I think C4 is questionable. I've been thinking  about ways to recast the problem, but they'll have to wait until I have some time.

[...]

How will you judge the correctness of your solution where the goals seems to be qualitative, in terms of faithfulness to the original statement of the paradox or other unstated goals? How will you judge the OP goal of a "Russell Paradox smell"?

The same way we judge the correctness of any solution that can't be automatically evaluated: Rational analysis and logical thinking.

In the case of this particular paradox, we have plenty of materials criss-crossing the ground. I'll quote from wikipedia whilst also noting it's supported by plenty of heavy-duty References and External links. The "smell" is to find a set R:

{\text{Let }}R=\{x\mid x\not \in x\}{\text{, then }}R\in R\iff R\not \in R

In case of the Barber, we have plenty of sets to consider: people; those who shave themselves; those who don't shave themselves; those who are shaved by barber(s); barber(s) even if there's only one of them; ...

For each of those sets, the elements are people. But to get a smell of Russell's Paradox we need a set whose elements (or at least some of them) are sets. That's what the x ∉ x is doing in the formula. I see no set-of-sets in the way the Barber's paradox is formulated.

So I'm agreeing with Russell himself: the Barber paradox is expressible within FOL (and therefore within a relational model); and does not exhibit Russell's Paradox.

Agreed. But the OP was referring to the 'ersatz-Russell' paradox of the barber, not the 'kosher-Russell' paradox itself.

We'll have to get the OP to explain what counts as a "database design that had a Russell Paradox smell to it". If it means merely some design in which some relvars must be always-empty, that's hardly interesting.

So if we stick to the barber we should expect to be able to replicate the contradiction of someone who both shaves himself and does not shave himself, and we can resolve that by rejecting the update that would add this person to our database. Or we could allow the update and arrange for the 'shaves himself' attribute to hold the value 'undecidable'. Not all that smelly.

Or we can observe that the RM can express some kinds of sets of sets via self-join. In a family tree, the descendants attribute of any member is a set of sets, which does not include itself, and family is a set of sets including itself, but I don't think we can go up a level to consider a set of sets of sets. So no kosher-Russell that I can see.

 

Self-join would need Transitive Closure. And that's amongst the things these alleged 'certain people' object to on grounds it's beyond first-order. OTOH:

  • TCLOSE wasn't included in Codd's 1972 'Relational Completeness' paper; given the omissions and difficulties with what that paper was trying to express, that's not really evidence either way for whether it scare-quotes 'should' be included in an expressively complete Data Manipulation Language.
  • Codd in later work [1979, 1985] seemed entirely comfortable with Transitive Closure -- at least of the non-generalised form for 'Parts explosion'.
  • He didn't express an opinion AFAICT whether non-generalised TCLOSE is within first-order.
  • IIRC luminaries on the forum think non-generalised TCLOSE is within first-order (generalised isn't).

Hmm hmm thinking about a family tree: consider the people who are related by marriage as opposed to blood-descendant. Are those mutually exclusive? No, somebody might marry their 2nd cousin (or whatever it allows in the Bible/Southern States). Then I hear occasional tittle-tattle of 'only in America' where two people are both cousins and uncle-nephew, or some such. Can we construct some paradox there? A nephew can marry an aunt, provided she's not blood-related. What's the set of family members a person can marry?

Quote from Dave Voorhis on December 16, 2019, 10:26 pm
Quote from dandl on December 16, 2019, 10:05 pm
Quote from Dave Voorhis on December 16, 2019, 10:17 am
Quote from dandl on December 15, 2019, 11:41 pm
Quote from Dave Voorhis on December 15, 2019, 9:49 pm

Line 17 is the escape clause, otherwise you couldn't insert anyone who's shaved by the barber and couldn't insert a barber. And, yes, I think C4 is questionable. I've been thinking  about ways to recast the problem, but they'll have to wait until I have some time.

[...]

How will you judge the correctness of your solution where the goals seems to be qualitative, in terms of faithfulness to the original statement of the paradox or other unstated goals? How will you judge the OP goal of a "Russell Paradox smell"?

The same way we judge the correctness of any solution that can't be automatically evaluated: Rational analysis and logical thinking.

That's a straight cop-out. It says: I have no idea what I'm looking for but if I look rationally and logically I'll know it when I see it.

Have you thought this through? Do you actually know what you're looking for?

Your question is no more or less than, "if you've solved a math problem, how do you know the answer is right?"

'Create something with a Russell smell' is hardly a maths problem. It sounds more like an exploration in the hope of finding something interesting (for some definition of interesting).

But to be more specific, I expect problems with a "Russell Paradox smell" -- whether genuinely Russellesque or pseudo paradoxes like the Barber's Paradox -- to be inexpressible, or expressible but result in unavoidable violation of necessary constraints, or expressible but result in infinite recursion.

You wrote dozens of lines of code on the Barber and then worried about a problem with one of them. I can do the whole thing in a line or two of pseudo-code. I'm trying to understand what it is you see in the problem that takes so much code to solve, and what you expect it to do if you manage it.

And why should it blow up? Either you admit a barber with an undecidable 'shaves self' attribute, or you do not.

For example, in playing around with this I managed a moment ago to create a horrible little pseudo paradox (at least, I think it's a pseudo paradox) that runs for a while before it blows the stack and returns null. In Rel, null isn't a thing, so returning null is... something.. .. . that is not... uh... something.

That's undefined behaviour: rainbows and unicorns.

Andl - A New Database Language - andl.org