What is this property of relations called?
Frederick Williams
(R(x,y) and R(y,x)) implies x = y
for all x, y?
--
But you see, I can believe a thing without understanding it.
It's all a matter of training.
--Lord Peter Wimsey in Dorothy L Sayers' _Have His Carcase_
Jack Campin - bogus address
>
> (R(x,y) and R(y,x)) implies x = y
>
> for all x, y?
"subrelation of identity"?
==== j a c k at c a m p i n . m e . u k === <http://www.campin.me.uk> ====
Jack Campin, 11 Third St, Newtongrange EH22 4PU, Scotland == mob 07800 739 557
CD-ROMs and free stuff: Scottish music, food intolerance, and Mac logic fonts
Chris Menzel
<frederick...@tesco.net> said:
> What does one call a relation R that is such that
>
> (R(x,y) and R(y,x)) implies x = y
>
> for all x, y?
Antisymmetric
William Elliot
> What does one call a relation R that is such that
>
> (R(x,y) and R(y,x)) implies x = y
>
> for all x, y?
>
Asymmetric.
When R is a transitive relation, the equivalence relation
x ~ y when x R y and y R x,
partitions the set of the relation into
a transitive relation that is asymmetric.
Chris Menzel
<ma...@rdrop.remove.com> said:
> On Sat, 31 Jan 2009, Frederick Williams wrote:
>
>> What does one call a relation R that is such that
>>
>> (R(x,y) and R(y,x)) implies x = y
>>
>> for all x, y?
>>
> Asymmetric.
No, asymmetry is the stronger property Rxy -> ~Ryx.
Frederick Williams
Thanks. I should have known that (maybe I did once). I shall try to
excuse myself by remarking that the jargon is a bit misleading in that a
relation can be both symmetric and antisymmetric. Are there any
interesting examples apart from x = y and its subclasses?
Frederick Williams
Does this have a name:
R(x,y) -> (R(x,x) & R(y,y))
for all x, y?
Can one deduce reflexivity from it, transitivity and antisymmetry? No,
I think.
Chris Menzel
<frederick...@tesco.net> said:
> Chris Menzel wrote:
>>
>> On Sat, 31 Jan 2009 20:16:14 +0000, Frederick Williams
>> <frederick...@tesco.net> said:
>> > What does one call a relation R that is such that
>> >
>> > (R(x,y) and R(y,x)) implies x = y
>> >
>> > for all x, y?
>>
>> Antisymmetric
>
> Thanks. I should have known that (maybe I did once). I shall try to
> excuse myself by remarking that the jargon is a bit misleading in that
> a relation can be both symmetric and antisymmetric.
Only if Rxy -> x=y, no?
> Are there any interesting examples apart from x = y and its
> subclasses?
Less-than-or-equal-to is a standard example here.
Chris Menzel
<frederick...@tesco.net> said:
> Chris Menzel wrote:
>>
>> On Sat, 31 Jan 2009 20:16:14 +0000, Frederick Williams
>> <frederick...@tesco.net> said:
>> > What does one call a relation R that is such that
>> >
>> > (R(x,y) and R(y,x)) implies x = y
>> >
>> > for all x, y?
>>
>> Antisymmetric
>
> Does this have a name:
>
> R(x,y) -> (R(x,x) & R(y,y))
>
> for all x, y?
Not that I know of.
> Can one deduce reflexivity from it, transitivity and antisymmetry? No,
> I think.
Indeed, trivially no, if as usual a (binary) relation R is defined to be
a subset of A x A, for some given set A. For, since transitivity,
antisymmetry, and your property above are all conditional, they are all
satisfied by the empty relation over A, whereas reflexivity requires
that Raa holds for all the members a of A, i.e., all of A must be the
field of the relation. Given that condition (i.e., that A = dom(R) U
rng(R)), reflexivity follows from your property above alone.
Frederick Williams
Thanks. I'm reading Krivine's _Introduction to Axiomatic Set Theory_
and he seems to assume that A = dom(R) U rng(R) though he doesn't spell
it out.
Chris Menzel
<frederick...@tesco.net> said:
> ...
> Thanks. I'm reading Krivine's _Introduction to Axiomatic Set Theory_
> and he seems to assume that A = dom(R) U rng(R) though he doesn't
> spell it out.
That would seem to me to be an odd thing for the author of an intro set
theory text to assume.
William Elliot
> Chris Menzel wrote:
>>> Does this have a name:
>>>
>>> R(x,y) -> (R(x,x) & R(y,y))
>>>
>>> for all x, y?
>>
>> Not that I know of.
>>
Quasi or semi reflexive.
>>> Can one deduce reflexivity from it, transitivity and antisymmetry?
>>> No, I think.
>>
>> Indeed, trivially no, if as usual a (binary) relation R is defined to
>> be a subset of A x A, for some given set A. For, since transitivity,
>> antisymmetry, and your property above are all conditional, they are all
>> satisfied by the empty relation over A, whereas reflexivity requires
>> that Raa holds for all the members a of A, i.e., all of A must be the
>> field of the relation. Given that condition (i.e., that A = dom(R) U
>> rng(R)), reflexivity follows from your property above alone.
>
> Thanks. I'm reading Krivine's _Introduction to Axiomatic Set Theory_
> and he seems to assume that A = dom(R) U rng(R) though he doesn't spell
> it out.
>
It depends how a relation is defined.
A binary relation for a set S is any subset of SxS.
By this definition, quasi reflexive does not imply reflexive.
How does your text defined a binary relation?
Consider the relation integer n divides integer m.
Is this relation about integers, ie a subset of Z^2
or is it a relation between non-zero integers and
integers, ie a subset of Z\0 x Z ? Do we include
0 divides 0?
Consider a (partially) ordered set (S,<=) that's an anti-chain. For
example { a,b }. In this case <= = { (a,a), (b,b) }, is the reflexive
order. There's a bijection between the reflexive orders for a set and
the irreflexive orders.
The equivalent irreflexive order <, of the above order <=, is empty.
However by the requirement introduced above, it could only be the
irreflexive order for the empty set, when in soothe, it's the irreflexive
order for all anti-chains, including the empty and one point anti-chains
(which are also chains).
Riddle of the day.
When is a space both discrete and indiscrete?
When is a particle both particle and an anti-particle?
When is a person both master and slave?
When is a politician both normal and abnormal?
When is a root, two roots?
Give an example of a completely regular abnormal.
Frederick Williams
>
> On Sun, 1 Feb 2009, Frederick Williams wrote:
> > Chris Menzel wrote:
>
> >>> Does this have a name:
> >>>
> >>> R(x,y) -> (R(x,x) & R(y,y))
> >>>
> >>> for all x, y?
> >>
> >> Not that I know of.
> >>
> Quasi or semi reflexive.
>
> >>> Can one deduce reflexivity from it, transitivity and antisymmetry?
> >>> No, I think.
> >>
> >> Indeed, trivially no, if as usual a (binary) relation R is defined to
> >> be a subset of A x A, for some given set A. For, since transitivity,
> >> antisymmetry, and your property above are all conditional, they are all
> >> satisfied by the empty relation over A, whereas reflexivity requires
> >> that Raa holds for all the members a of A, i.e., all of A must be the
> >> field of the relation. Given that condition (i.e., that A = dom(R) U
> >> rng(R)), reflexivity follows from your property above alone.
> >
> > Thanks. I'm reading Krivine's _Introduction to Axiomatic Set Theory_
> > and he seems to assume that A = dom(R) U rng(R) though he doesn't spell
> > it out.
> >
> It depends how a relation is defined.
> A binary relation for a set S is any subset of SxS.
>
> By this definition, quasi reflexive does not imply reflexive.
> How does your text defined a binary relation?
Krivine assumes a universe U and formulae expressed in terms of
variables x, y, z, ...; names a, b, c, ... of sets in U; logical
constants =, \in, \neg, \vee, \exists. A binary relation (on U) is
defined by a formula, R(x,y) say, with two free variables. The *domain*
(I would say field) of R is the class R(x,x). [Generally, a class is
defined by a formula with one free variable.]
Frederick Williams
I fancy the word 'Introduction' is misleading: in fewer than 100 pages
he proves the relative consistency of Choice, not-Choice (using
urelemente) and GCH. That he does all that without a lot of chat is in
many ways a Good Thing, but it's at my intellectual limit.
[Btw, it's translated by the Warwick philosopher David Miller.]
Chris Menzel
I take it you mean the class of objects x such that R(x,x), but that
can't be right. That would mean that the domain of an irreflexive
relation is the empty set. Given the usual definition of a relation
over a universe U -- the "given" set I called "A" above -- as any subset
of U x U, the usual definition of the domain of a relation R is:
dom(R) = {x in U | for some y, <x,y> in R}
(The qualification "in U" here, given the standard definition, is of
course redundant.)
Looks to me like Krivine's definition of "relation over U" is weaker
than the standard one -- according to the above, Krivine seems to
suggest that a relation has to be definable by a formula. That would be
pretty nonstandard, but might be all Krivine needs for his purposes.
(There are also some use/mention issues above -- "R" is being used both
as a metavariable over formulas and as a variable over relations.)
Frederick Williams
'Zackly. My first thought was: domain x \in y = empty set. Daft.
> Given the usual definition of a relation
> over a universe U -- the "given" set I called "A" above -- as any subset
> of U x U, the usual definition of the domain of a relation R is:
>
> dom(R) = {x in U | for some y, <x,y> in R}
For _functional_ relations he defines dom in this way. What I (because
he) have been calling the domain of a relation generally is what I call
its field.
> (The qualification "in U" here, given the standard definition, is of
> course redundant.)
>
> Looks to me like Krivine's definition of "relation over U" is weaker
> than the standard one -- according to the above, Krivine seems to
> suggest that a relation has to be definable by a formula.
He does.
> That would be
> pretty nonstandard, but might be all Krivine needs for his purposes.
I think it is.
> (There are also some use/mention issues above -- "R" is being used both
> as a metavariable over formulas and as a variable over relations.)
Here's a quote: 'The class R(x,x) is the domain of the ordering.' That
is a definition of _domain_ of a weak order R. See page 7 if you have
the book to hand. He also defines equivalence relation R (not in the
usual way) and says: 'The class R(x,x) is called the domain of the
equivalence relation.
Chris Menzel
Oh, well, then that's probably fine, as I suspect weak orderings as he
defines them are reflexive.
> See page 7 if you have the book to hand. He also defines equivalence
> relation R (not in the usual way) and says: 'The class R(x,x) is
> called the domain of the equivalence relation.
Also fine, since equivalence relations are reflexive, by definition.
My worry was that it seemed that you were saying that this is how
Krivine defines the notion of domain for binary relations generally.
Seems like a confusing way to go about it, though. Why not use the
standard definition?
William Elliot
>> Here's a quote: 'The class R(x,x) is the domain of the ordering.' That
>> is a definition of _domain_ of a weak order R.
>
> Oh, well, then that's probably fine, as I suspect weak orderings as he
> defines them are reflexive.
>
Is that what you mean by weak order?
The advantage of reflexive orders over irreflexive orders
is that the reflexive order of itself, shows what the set
is that's being ordered.
>> See page 7 if you have the book to hand. He also defines equivalence
>> relation R (not in the usual way) and says: 'The class R(x,x) is
>> called the domain of the equivalence relation.
> Also fine, since equivalence relations are reflexive, by definition.
> My worry was that it seemed that you were saying that this is how
> Krivine defines the notion of domain for binary relations generally.
> Seems like a confusing way to go about it, though.
Some how I get the notion that to Krivine, all relations are reflexive.
> Why not use the standard definition?
>
What is your standard definition?
Riddle of the day. If there're two standards, is one substandard?
>
Frederick Williams
> > Here's a quote: 'The class R(x,x) is the domain of the ordering.' That
> > is a definition of _domain_ of a weak order R.
>
> Oh, well, then that's probably fine, as I suspect weak orderings as he
> defines them are reflexive.
>
> > See page 7 if you have the book to hand. He also defines equivalence
> > relation R (not in the usual way) and says: 'The class R(x,x) is
> > called the domain of the equivalence relation.
>
> Also fine, since equivalence relations are reflexive, by definition.
Not for Krivine! For both weak order and equivalence, reflexivity is
replaced by
(all x,y)(R(x,y) -> (R(x,x) & R(y,y)).
Hence my question, in news:4985B434...@tesco.net, whether this, in
the presence of other stuff, implies reflexivity.
> My worry was that it seemed that you were saying that this is how
> Krivine defines the notion of domain for binary relations generally.
So it seems to me.
> Seems like a confusing way to go about it, though. Why not use the
> standard definition?
Frederick Williams
>
> What ...
Should anyone be interested, this thread has turned into a discussion of
certain definitions in the first few pages of Jean-Louis Krivine
(translated by David Miller) _Introduction to Axiomatic Set Theory_
Reidel, 1971. It is reviewed by Azriel Levy in JSL, 39(1), 1974, pp
180-181. I don't have access to this.
Frederick Williams
> Some how I get the notion that to Krivine, all relations are reflexive.
And yet he omits reflexivity from both the definition of equivalence
relation and weak order. Bizarre! See my reply to Chris Menzel.
> > Why not use the standard definition?
> >
> What is your standard definition?
(exists y)(xRy) or perhaps any superclass of that.
> Riddle of the day. If there're two standards, is one substandard?
Obviously standards are such good things so the more we have the better.
Alan Smaill
> William Elliot wrote:
>
> > Some how I get the notion that to Krivine, all relations are reflexive.
>
> And yet he omits reflexivity from both the definition of equivalence
> relation and weak order. Bizarre! See my reply to Chris Menzel.
Doesn't his version of equivalence relation turn out to be equivalent
to the usual version, given that Krivine specifies R(x,x) as the domain?
> > > Why not use the standard definition?
> > >
> > What is your standard definition?
>
> (exists y)(xRy) or perhaps any superclass of that.
(exists y) R(x,y) iff R(x,x), in the case of equivalence
relation a la Krivine.
--
Alan Smaill
Frederick Williams
> Doesn't his [Krivine's] version of equivalence relation turn out to be equivalent
> to the usual version, given that Krivine specifies R(x,x) as the domain?
I'll read it again. Do you have the book or are you otherwise familiar
with it?
Alan Smaill
> Alan Smaill wrote:
>
> > Doesn't his [Krivine's] version of equivalence relation turn out to be
> > equivalent to the usual version, given that Krivine specifies
> > R(x,x) as the domain?
>
> I'll read it again. Do you have the book or are you otherwise familiar
> with it?
I do have the book.
--
Alan Smaill
William Elliot
> William Elliot wrote:
>
>> Some how I get the notion that to Krivine, all relations are reflexive.
>
> And yet he omits reflexivity from both the definition of equivalence
> relation and weak order. Bizarre! See my reply to Chris Menzel.
>
>>> Why not use the standard definition?
>>>
>> What is your standard definition?
>
> (exists y)(xRy) or perhaps any superclass of that.
>
That's a definition of a relation?
What is your standard defintion of a binary relation?
Mine like functions is more than just a set.
A function includes a set or ordered pairs,
which determines the domain and a codomain that
may or may not be the range or image of the function.
A relation R includes a set of ordered pairs and a the set S,
the set of elements that R relates.
For example, the relation < over N.
>> Riddle of the day. If there're two standards, is one substandard?
>
> Obviously standards are such good things so the more we have the better.
>
The double standard: are not two better than one?
Riddle of the day. What's a partially ordered pair?
William Elliot
> William Elliot wrote:
>
>> Some how I get the notion that to Krivine, all relations are reflexive.
>
> And yet he omits reflexivity from both the definition of equivalence
> relation and weak order. Bizarre! See my reply to Chris Menzel.
>
>>> Why not use the standard definition?
>>>
>> What is your standard definition?
>
> (exists y)(xRy) or perhaps any superclass of that.
>
What is your standard defintion of a binary relation?
Mine like functions is more than just a set.
A function includes a set or ordered pairs,
which determines the domain and a codomain that
may or may not be the range or image of the function.
A relation R includes a set of ordered pairs and a the set S,
the set of elements that R relates.
For example, the relation < over N.
>> Riddle of the day. If there're two standards, is one substandard?
>
> Obviously standards are such good things so the more we have the better.
>
Frederick Williams
>
> On Tue, 3 Feb 2009, Frederick Williams wrote:
> > (exists y)(xRy) or perhaps any superclass of that.
> >
> That's a definition of a relation?
Sorry, I thought that you were asking for a definition of the domain of
a relation.
Frederick Williams
> I do have the book.
Don't worry I won't pester you with endless technical questions :-)
What do you think of it overall?
Alan Smaill
> Alan Smaill wrote:
>
> > I do have the book.
>
> Don't worry I won't pester you with endless technical questions :-)
>
> What do you think of it overall?
I'm very fond of it, it has a lot of style.
The introduction of model theory right from the start
means that it's not an introduction in the usual sense, though
(it reminds me of Serre's "cours d'arithmétique" for that).
--
Alan Smaill
Frederick Williams
> I'm very fond of it [Krivine's Introduction to Axiomatic Set Theory],
> The introduction of model theory right from the start
> means that it's not an introduction in the usual sense, though
> (it reminds me of Serre's "cours d'arithmétique" for that).
Agreed, it might better be called an introduction to relative
consistency proofs or something.
I do like the way he treats treats set theory like other abstract
theories. The first page of chapter one is about as clear an account of
what set theory is and how it is to be discussed as I have read. I
don't know if anyone now developing a theory of sets (as opposed to
discussing its ontological status) would equate set theory with
mathematics, but if they did it might make a subsequent account of
models of set theory seem a bit, erm, 'dishonest' one might almost say.