Ordering Binary Relations

15 views
Skip to first unread message

William Elliot

unread,
Sep 17, 2008, 5:29:33 AM9/17/08
to
This is a synopsis of a pair of papers by
Victor Porton <por...@narod.ru>

regarding a (partial) order on binary relations f subset XxY
between two sets X and Y, that is an order on P(XxY) coarser than
the subset order.

Definition.
domain f = dom f = { x | some y with (x,y) in f } = p1(f)
image f = img f = { y | some x with (x,y) in f } = p2(f)
restriction f to A = f|A = { (x,y) in f | x in A } = f /\ AxS

(/\ \/, intersection union)

Propositions.
f subset dom f x rng f; dom f subset X; rng f subset Y

f|dom f = f. Proof: f|dom f = f /\ (dom f)xY = f
since f subset dom f x rng f subset dom f x Y

(f|A)|B = f|(A /\ B). Proof: (f|A)|B = f|A /\ BxY = f /\ AxY /\ BxY
= f /\ (A /\ B)xY = f|(A /\ B)

dom f|A = dom f /\ A. Proof
x in dom f|A iff some y with (x,y) in f|A
iff some y with (x,y) in f, x in A iff x in dom f /\ A

Definition
f <= g when f = g|dom f

Propositions
f <= g ==> f subset g, dom f subset dom g

<= is (partial) order (proof follows each property)
f <= f. f = f|dom f
f <= g, g <= f ==> f = g. f subset g; g subset f
f <= g, g <= h ==> f <= h. dom f subset dom g
f = g|dom f = (h|dom g)|dom f = h|(dom g /\ dom f) = h|dom f

Definition
The function induced by f is the function
f*:dom f -> P(Y), x -> { y | (x,y) in f }

Propositions

dom f = dom f*

f = { (x,y) | x in dom f*, y in f*(x) }. Proof.
(x,y) in f iff x in dom f, y in f*(x) iff x in dom f*, y in f*(x)

f = g iff f* = g*

(f|A)* = f* /\ AxP(Y) = f*|A

f <= g iff f* <= g* iff f* subset g*
Proof. f <= g iff f = g|dom f iff f* = (g|dom f)*
iff f* = g*|dom f iff f* subset g*

f <= g iff for all x in dom f, f*(x) = g*(x)

Let R = P(XxY), R* = { F:A -> P(Y) | A subset X }
F,G in R* ==> F /\ G in R

If F in R* then f = { (x,y) | x in dom f, y in F(x) } in R and F = f*

h:(R,<=) -> (R*,subset) is order isomorphism

(R,<=) is a down lattice or meet semi-lattice
f* /\ g* = inf f*, g*; h^-1(f* /\ g*) = inf f,g

-- conditions equivalent to f <= g
f <= g iff some A with f = g|A. Proof left to right.
If f = g|A, then dom f = dom g|A = dom g /\ A
g|dom f = g|(dom g /\ A) = (g|dom g)|A = g|A = f

I fail see the significance for the remaining, final portion of the
author's work.

Notation. f o g = fg = { (x,y) | some t with (x,t) in f, (t,y) in g }

Note. This composition for relations is
the reverse of composition for functions.

f^-1 g|dom f = f^-1 g. Proof: (x,y) in f^-1 g|dom f
iff some t with (t,x) in f, (t,y) in g|dom f
iff some t in dom f with (t,x) in f, (t,y) in g
iff some t with (t,x) in f, (t,y) in g
iff (x,y) in f^-1 g

Thus f <= g ==> f^-1 f = f^-1 g

f^-1 f = f^-1 g iff f^-1 f = g^-1 f. Proof left to right.
f^-1 f = (f^-1 f)^-1 = (f^-1 g)^-1 = g^-1 f

(1) f^-1 f = f^-1 g, f subset g
(2) f^-1 f = g^-1 f, f subset g
(3) f^-1 f = f^-1 g, dom f subset dom g
(4) f^-1 f = g^-1 f, dom f subset dom g

In conclusion
f <= g ==> (1) ==> (2) ==> (3) ==> (4)

The author claims (4) ==> f <= g.

-- This short section notes to be skipped
f^-1 f = f^-1 g ==> img f subset img g. Proof:
if y in img f: some x with (x,y) in f; (y,y) in f^-1 f
some t with (t,x) in f, (t,y) in g; t in img g

function f ==> f^-1 f = { (y,y) | y in img f }
(x,y) in f^-1 f iff some t with (t,x), (t,y) in f
iff some t with (t,x) in f, x = y iff x = y in img f

-- To continue,
the author claims (4) ==> f <= g.

He uses a definition for composition of relations that is the reverse of
the definition I've chosen. He also has reversed f and g. To continue
with his notation, he claims

gg^-1 = gf^-1, dom g subset dom f implies g <= f

He claims when dom g subset dom f, that
gg^-1 = gf^-1
is equivalent to
g* (g*)^-1 = g* (f*)^-1

Actually only implication is needed. How is that substantiated?

He states
g* g*^-1 = l(img g)

where l is the identity function. I can make no sense of that.
What I can show is
g* g*^-1 = { (y,y) | y in img g }

Thus if x in dom g*, f*(x) = g* g*^-1 f*(x)
(since img g* subset img f* as hinted at in short section)
= g* (f*)^-1 f*(x) = g*(x). This shows g <= f as show above.

----
Theorem about limiting binary relations

Theorem. Let f and g are binary relations. Then the following
statements are equivalent:
1. g = f|[dom g].
2. Exists a set K such that g = f|[K].
3. gg-1 = fg-1 and g is a subset of f.
4. gg-1 = gf^-1 and g is a subset of f.
5. gg-1 = fg-1 and dom g is a subset of dom f.
6. gg-1 = gf^-1 and dom g is a subset of dom f.


An other, a little less convenient for usage but much easier to
remember (mnemonic), equivalent form of this theorem is:

Theorem (mnemonic form). Given that f and g are binary relations and
dom g is a subset of dom f, right "multiplying" (composing) both sides
of the equation g = f|[dom g] with g-1 produces a formula equivalent
to this equation.

I have [9]stated this theorem as a conjecture in this weblog post. Now
I have proved it. (The proof is below.)

Note that qp denotes the composition of binary relations p and q.

Lemma

First we will prove the following lemma:

Lemma. If gg-1 = fg-1 and dom g is a subset of dom f then f|[dom g] =
g for any binary relations f and g.

Proof. Let gg-1 = fg-1.

For any relation p I will denote p* the corresponding function mapping
an X to a set of Y. That is p*(x) = {y : (x, y) in p}. Note that dom
p* = dom p.

I will denote L the multivalued function (relation) which maps a set
to its elements (that is the reverse of set membership relation).
Obviously p = Lp* and p = q <=> p* = q* for any relations p and q.

Our equation can be equivalently rewritten as

Lg* (Lg*)-1 = Lf* (Lg*)-1; Lg* g*-1 L-1 = Lf* g*-1 L-1;

what accordingly noted above is equivalent to
g*g*-1 = f*g*-1.

By well known properties of monovalued functions, we have

g* g*-1 = I[im g*]

g* g*^-1 = { (y,y) | y in img g* }

(I[im g*] denotes the identity relation on the set im g*); so

f*g*-1 = I[im g*],

that is for any y in im g* we have f*g*-1y = y.

So for any x in dom g* we have f*g*-1g*x = g*x. Because g*-1g*x
contains x and x in dom f* (dom f* is a superset of dom g*), we have
f*x = g*x.

So f*|[dom g*] = g* what is the same as f|[dom g] = g. End of proof.

Proof of the main theorem

Now we can easily prove the main theorem. First we will prove its
mnemonic form (repeated below):

Theorem (mnemonic form). Given that f and g are binary relations and
dom g is a subset of dom f, right multiplying both sides of the
equation g = f|[dom g] with g-1 produces a formula equivalent to this
equation.

Proof of the main theorem (mnemonic form).

Multiplying both sides of the equation g = f|[dom g] with g-1 produces
the formula gg-1 = fg-1. We need to prove that this formula is
equivalent to g = f|[dom g] (under the condition that dom g is a
subset of dom f).

Direct implication is obvious. Reverse implication is already proved
in the lemma (that dom g is a subset of dom f is taken into account).
End of proof.

Now let reprise the full form of the main theorem again and prove it:

Theorem. Let f and g are binary relations. Then the following
statements are equivalent:
1. g = f|[dom g].
2. Exists a set K such that g = f|[K].
3. gg-1 = fg-1 and g is a subset of f.
4. gg-1 = gf^-1 and g is a subset of f.
5. gg-1 = fg-1 and dom g is a subset of dom f.
6. gg-1 = gf^-1 and dom g is a subset of dom f.

Proof of the main theorem (full form).

Equivalences (3)<=>(4) and (5)<=>(6) can be proved by inverting the
formulas taking in account that (qp)-1 = p-1q-1 for any binary
relations p and q.

Implications (3)=>(5) and (4)=>(6) are obvious.

(5)=>(1) is exactly the lemma proved above.

(1)=>(3) is obvious (right multiply both sides of the equality (1)
with g-1).

(1)=>(2) is obvious. (Take K = dom g.)

To prove (2)=>(1) let assume that g = f|[K]. Then dom g is
intersection of dom f and the set K; from this follows g = f|[dom g].

From proved implications follows that all six statements are
equivalent. End of proof.

----

Victor Porton

unread,
Sep 17, 2008, 7:03:54 AM9/17/08
to
On Sep 17, 12:29 pm, William Elliot <ma...@hevanet.remove.com> wrote:
> This is a synopsis of a pair of papers by
> Victor Porton <por...@narod.ru>
>
> regarding a (partial) order on binary relations f subset XxY
> between two sets X and Y, that is an order on P(XxY) coarser than
> the subset order.

http://www.mathematics21.org/misc-math.html
^^^

William Elliot, I don't understand your purpose of re-publishing (with
a little additional info) info from my site it the newsgroup.
(However thanks for your attention to my work.)

Also note that you have violated the implied copyright of my work re-
publishing its large portions. (However I'm glad, not irritated, and
am not going to sue you.)
For the future I explicitly allow you to quote me (in reasonable
limits).

Also: there are no l[...] but I[...] in my texts. You messed the
letters L and i.

Note that my main works are not "Misc math" but Algebraic General
Topology:
http://www.mathematics21.org/algebraic-general-topology.html

> Notation. f o g = fg = { (x,y) | some t with (x,t) in f, (t,y) in g }
>
> Note. This composition for relations is
> the reverse of composition for functions.

You have messed the order (should be first g then f):
f o g = fg = { (x,y) | some t with (x,t) in g, (t,y) in f }

Glad to hear you further, William Elliot.

Victor Porton

unread,
Sep 17, 2008, 7:14:05 AM9/17/08
to
On Sep 17, 2:03 pm, Victor Porton <por...@narod.ru> wrote:
> On Sep 17, 12:29 pm, William Elliot <ma...@hevanet.remove.com> wrote:
>
> > This is a synopsis of a pair of papers by
> > Victor Porton <por...@narod.ru>
>
> > regarding a (partial) order on binary relations f subset XxY
> > between two sets X and Y, that is an order on P(XxY) coarser than
> > the subset order.
>
> http://www.mathematics21.org/misc-math.html
> ^^^

Does it make sense to attempt to publish "Theorem about limiting
binary relations" (http://www.mathematics21.org/misc/limiting-binary-
relations-theorem.html) in a referated journal?

It seems being too simple theorem for publishing but indeed I suspect
that it may be a new result. To publish it officially or just to leave
as it (having an unofficial Web page about this theorem)?

Anyway I expect to use this theorem as a special case for proving
certain conjectures in my research on Algebraic General Topology
(http://www.mathematics21.org/algebraic-general-topology.html). So it
could anyway be published by me in a (future) book.

Ask me about System Design

unread,
Sep 18, 2008, 3:36:27 AM9/18/08
to

Most of this appears to me to be similar to exercises in relation
algebras
and cylindric algebras. Before submitting your work for publication,
you
might look at some basic texts in universal algebra that deal with
relation
algebras. I recall only advanced work that Alfred Tarski did with
cylindric
algebras, but he might have written (or referred to) a more basic text
that
covers some of the same material.

Gerhard Paseman, 2008.09.18

William Elliot

unread,
Sep 18, 2008, 4:58:59 AM9/18/08
to
On Wed, 17 Sep 2008, Victor Porton wrote:
> > On Sep 17, 12:29 pm, William Elliot <ma...@hevanet.remove.com> wrote:
> >
> > > This is a synopsis of a pair of papers by
> > > Victor Porton <por...@narod.ru>
> >
> > > regarding a (partial) order on binary relations f subset XxY
> > > between two sets X and Y, that is an order on P(XxY) coarser than
> > > the subset order.
> >
> > http://www.mathematics21.org/misc-math.html
>
> Does it make sense to attempt to publish "Theorem about limiting
> binary relations" (http://www.mathematics21.org/misc/limiting-binary-
> relations-theorem.html) in a referated journal?
>
I have found an astonishingly simple and direct way of proving the major
lemma of that paper.

First I show for all f,g
x in dom f /\ dom g ==> f*(x) x g*(x) subset gf^-1

Hence immediately
x in dom f /\ dom g ==> f*(x) x g*(x) /\ gf^-1 = f*(x) x g*(x)

Consequently
ff^-1 = gf^-1 ==> for all x in dom f /\ dom g, f*(x) = g*(x)

which shows
ff^-1 = gf^-1, dom f subset dom g ==> for all x in dom f, f*(x) = g*(x)
and finally
ff^-1 = gf^-1, dom f subset dom g ==> f <= g

William Elliot

unread,
Sep 19, 2008, 3:04:59 AM9/19/08
to
On Thu, 18 Sep 2008, William Elliot wrote:
> On Wed, 17 Sep 2008, Victor Porton wrote:
> > > On Sep 17, 12:29 pm, William Elliot <ma...@hevanet.remove.com> wrote:
> > >
> > > > This is a synopsis of a pair of papers by
> > > > Victor Porton <por...@narod.ru>
> > >
> > > > regarding a (partial) order on binary relations f subset XxY
> > > > between two sets X and Y, that is an order on P(XxY) coarser than
> > > > the subset order.
> > >
> > > http://www.mathematics21.org/misc-math.html
> >
> > Does it make sense to attempt to publish "Theorem about limiting
> > binary relations" (http://www.mathematics21.org/misc/limiting-binary-
> > relations-theorem.html) in a referated journal?
> >
> I have found an astonishingly simple and direct way of proving the major
> lemma of that paper.
>
> First I show for all f,g
> x in dom f /\ dom g ==> f*(x) x g*(x) subset gf^-1
>
> Hence immediately
> x in dom f /\ dom g ==> f*(x) x g*(x) /\ gf^-1 = f*(x) x g*(x)
>
These two are correct.

> Consequently
> ff^-1 = gf^-1 ==> for all x in dom f /\ dom g, f*(x) = g*(x)
>

I have overstated my hand and retract this claim.

Victor Porton

unread,
Sep 19, 2008, 5:40:53 AM9/19/08
to
On Sep 18, 11:58 am, William Elliot <ma...@hevanet.remove.com> wrote:
> I have found an astonishingly simple and direct way of proving the major
> lemma of that paper.
>
> First I show for all f,g
> x in dom f /\ dom g ==> f*(x) x g*(x) subset gf^-1
>
> Hence immediately
> x in dom f /\ dom g ==> f*(x) x g*(x) /\ gf^-1 = f*(x) x g*(x)
>
> Consequently
> ff^-1 = gf^-1 ==> for all x in dom f /\ dom g, f*(x) = g*(x)
>
> which shows
> ff^-1 = gf^-1, dom f subset dom g ==> for all x in dom f, f*(x) = g*(x)
> and finally
> ff^-1 = gf^-1, dom f subset dom g ==> f <= g

"f*(x) x g*(x) subset gf^-1"

What you mean by "x"?

William Elliot

unread,
Sep 19, 2008, 6:43:12 AM9/19/08
to

The cross product
. . AxB = { (x,y) | x in A, y in B }

However, if you read my other recent post, you will see that I retracked
that proof. Is this a counter example to the lemma? N is positive
integers.

f = { (n,m) in NxN | n <= m }
g = NxN; f subset g; dom f = dom g

ff^-1 = NxN = gf^-1

Victor Porton

unread,
Sep 19, 2008, 7:36:19 AM9/19/08
to

First, you have messed f and g. I use f where you use g and vice
versa.

ff^-1 = {(x,y) | exists t in N such that (t,x) in f and (t,y) in f} =
{(x,y) | exists t in N such that t<=x and t<=y} =
{(x,y) | x, y in N} = NxN.

gf^-1 = {(x,y) | exists t in N such (t,x) in f and (t,y) in g} =
{(x,y) | exists t in N such t<=x, y in N} =
{(x,y) | x, y in N} = NxN

Hmm... yes, this seems to be a counterexample to my lemma... ~-)
Where is the error then? I will look at this when will have a free
time.
Now, you may discuss where is the error in this newsgroup.

http://www.mathematics21.org/misc/limiting-binary-relations-theorem.html

Victor Porton

unread,
Sep 19, 2008, 1:48:34 PM9/19/08
to

It seems that mistakeous statement at
http://www.mathematics21.org/misc/limiting-binary-relations-theorem.html
is claiming


"what accordingly noted above is equivalent to g*g*-1 = f*g*-1."

So counterexample by William Elliot wins. My mistake.

Now the mistake is noted at
http://www.mathematics21.org/misc/limiting-binary-relations-theorem.html

This does not undetermines my other articles however.

--
Victor Porton - http://www.mathematics21.org

William Elliot

unread,
Sep 20, 2008, 3:13:00 AM9/20/08
to
On Fri, 19 Sep 2008, Victor Porton wrote:
> On Sep 19, 2:36 pm, Victor Porton <por...@narod.ru> wrote:
> > On Sep 19, 1:43 pm, William Elliot <ma...@hevanet.remove.com> wrote:
> > > However, if you read my other recent post, you will see that I retracked
> > > that proof. Is this a counter example to the lemma? N is positive
> > > integers.
> >
> > > f = { (n,m) in NxN | n <= m }
> > > g = NxN; f subset g; dom f = dom g
> >
> > > ff^-1 = NxN = gf^-1
> >
> > First, you have messed f and g. I use f where you use g and vice
> > versa.
> >
> > ff^-1 = {(x,y) | exists t in N such that (t,x) in f and (t,y) in f} =
> > {(x,y) | exists t in N such that t<=x and t<=y} =
> > {(x,y) | x, y in N} = NxN.
> >
> > gf^-1 = {(x,y) | exists t in N such (t,x) in f and (t,y) in g} =
> > {(x,y) | exists t in N such t<=x, y in N} =
> > {(x,y) | x, y in N} = NxN
> >
> > Hmm... yes, this seems to be a counterexample to my lemma... ~-)

> It seems that mistakeous statement at


> http://www.mathematics21.org/misc/limiting-binary-relations-theorem.html
> is claiming "what accordingly noted above is equivalent to g*g*-1 =
> f*g*-1."
>

Correct.

> So counterexample by William Elliot wins. My mistake.
>
> Now the mistake is noted at
> http://www.mathematics21.org/misc/limiting-binary-relations-theorem.html
>

Here's another simpler counter example.

{ (0,0), (0,1), (1,1) }
and
{ (0,0), (0,1), (1,1), (1,0) }
or
{ (0,0), (0,1), (1,1), (1,0), (2,2) }

The latter with (2,2) is to have counter example
where one domain is proper subset of the other.

> This does not undetermines my other articles however.
>

Would you like me to proof read, review another of your papers?
Let's start with Set Theoretic Filters, the lattice of filters.

It is known that the set of filters for a set S is a complete down
lattice, that is a meet complete semi-lattice. Does this paper go
beyond that?

Victor Porton

unread,
Sep 20, 2008, 5:07:48 AM9/20/08
to

Certainly I would like you to proof read these.

> It is known that the set of filters for a set S is a complete down
> lattice, that is a meet complete semi-lattice. Does this paper go
> beyond that?

The set of filters for a set S is a complete lattice, distributive
lattice, atomistic lattice.

The paper goes far beyond that.

Now in the free time I'm writing the book "Filters on Posets" but it
will probably take yet long time.

Victor Porton

unread,
Sep 20, 2008, 5:17:08 AM9/20/08
to
On Sep 20, 12:07 pm, Victor Porton <por...@narod.ru> wrote:
> On Sep 20, 10:13 am, William Elliot <ma...@hevanet.remove.com> wrote:
>
> > On Fri, 19 Sep 2008, Victor Porton wrote:
> > > This does not undetermines my other articles however.
>
> > Would you like me to proof read, review another of your papers?
> > Let's start with Set Theoretic Filters, the lattice of filters.
>
> Certainly I would like you to proof read these.
>
> > It is known that the set of filters for a set S is a complete down
> > lattice, that is a meet complete semi-lattice. Does this paper go
> > beyond that?
>
> The set of filters for a set S is a complete lattice, distributive
> lattice, atomistic lattice.

A correction: Atomistic is the reverse lattice to the lattice of
filters on a set S. I'm not sure about the direct (non-reverse)
lattice whether it is atomistic.

William Elliot

unread,
Sep 20, 2008, 6:26:29 AM9/20/08
to
On Sat, 20 Sep 2008, Victor Porton wrote:
> On Sep 20, 12:07 pm, Victor Porton <por...@narod.ru> wrote:
> > On Sep 20, 10:13 am, William Elliot <ma...@hevanet.remove.com> wrote:
> > > On Fri, 19 Sep 2008, Victor Porton wrote:
> >
> > > Would you like me to proof read, review another of your papers?
> > > Let's start with Set Theoretic Filters, the lattice of filters.
> >
> > Certainly I would like you to proof read these.
> >
> > > It is known that the set of filters for a set S is a complete down
> > > lattice, that is a meet complete semi-lattice. Does this paper go
> > > beyond that?
> >
> > The set of filters for a set S is a complete lattice, distributive
> > lattice, atomistic lattice.
>
It is not complete because it has no top element.
Being complete down lattice, it's a bounded complete lattice
ie, every nonnul bounded set has a sup. It's also chain complete.

What do you mean it's distrubuitive? Consider N and the
principal filters F_A generated by the set A = {0}, {1}, {0,1}

(F_0,1 inf F_0) sup (F_0,1 inf F_1) = F_0,1 sup F_0,1 = F_0,1
/=
F_0,1 inf (F_0 sup F_1) because F_0 sup F_1 doesn't exist.

What are the atoms? They are not the princpals filters because
for b not in A, F_(A \/ {b}) proper subset F_{b}.

> A correction: Atomistic is the reverse lattice to the lattice of
> filters on a set S. I'm not sure about the direct (non-reverse)
> lattice whether it is atomistic.
>

The subset order ideals of S?

Anyway, what formats have you for that paper?
TeX and some other, what did you call it, that's easier
to read in raw file form than TeX? Can you convert them
into the web reable formate used for your two papers on
relations? Anyway as I can't do the pdf, post, email or
put on web a version that I can read and I'll consider what
I can for it.

Victor Porton

unread,
Sep 20, 2008, 6:47:09 AM9/20/08
to
On Sep 20, 1:26 pm, William Elliot <ma...@hevanet.remove.com> wrote:
> On Sat, 20 Sep 2008, Victor Porton wrote:
> > On Sep 20, 12:07 pm, Victor Porton <por...@narod.ru> wrote:
> > > On Sep 20, 10:13 am, William Elliot <ma...@hevanet.remove.com> wrote:
> > > > On Fri, 19 Sep 2008, Victor Porton wrote:
>
> > > > Would you like me to proof read, review another of your papers?
> > > > Let's start with Set Theoretic Filters, the lattice of filters.
>
> > > Certainly I would like you to proof read these.
>
> > > > It is known that the set of filters for a set S is a complete down
> > > > lattice, that is a meet complete semi-lattice. Does this paper go
> > > > beyond that?
>
> > > The set of filters for a set S is a complete lattice, distributive
> > > lattice, atomistic lattice.
>
> It is not complete because it has no top element.
> Being complete down lattice, it's a bounded complete lattice
> ie, every nonnul bounded set has a sup. It's also chain complete.

Oh, well, I forgot to say that my definition of filter is different
than the definition of filters in some other's works.
See
http://www.mathematics21.org/binaries/set-filters.pdf
for the exact definition.

In my terminology it has top and bottom elements.

> What do you mean it's distrubuitive? Consider N and the
> principal filters F_A generated by the set A = {0}, {1}, {0,1}
>
> (F_0,1 inf F_0) sup (F_0,1 inf F_1) = F_0,1 sup F_0,1 = F_0,1
> /=
> F_0,1 inf (F_0 sup F_1) because F_0 sup F_1 doesn't exist.

The same note about different definition.

I skip about atoms of the lattice of filters. It is probably the same
problem with different definition.

> Anyway, what formats have you for that paper?
> TeX and some other, what did you call it, that's easier
> to read in raw file form than TeX? Can you convert them
> into the web reable formate used for your two papers on
> relations? Anyway as I can't do the pdf, post, email or
> put on web a version that I can read and I'll consider what
> I can for it.

I have sent you by email LaTeX file set-filters.tex. I can't offer you
something better.

William Elliot

unread,
Sep 20, 2008, 7:28:33 AM9/20/08
to
On Sat, 20 Sep 2008, Victor Porton wrote:
> > > > On Sep 20, 10:13 am, William Elliot <ma...@hevanet.remove.com> wrote:
> > > > > On Fri, 19 Sep 2008, Victor Porton wrote:
> >
> > > > > Would you like me to proof read, review another of your papers?
> > > > > Let's start with Set Theoretic Filters, the lattice of filters.
> >
> > > > Certainly I would like you to proof read these.
> >
> > > > > It is known that the set of filters for a set S is a complete down
> > > > > lattice, that is a meet complete semi-lattice. Does this paper go
> > > > > beyond that?
> >
> > > > The set of filters for a set S is a complete lattice, distributive
> > > > lattice, atomistic lattice.
> >
> > It is not complete because it has no top element.
> > Being complete down lattice, it's a bounded complete lattice
> > ie, every nonnul bounded set has a sup. It's also chain complete.
>
> Oh, well, I forgot to say that my definition of filter is different
> than the definition of filters in some other's works.

Then it needs a different name.

> See
> http://www.mathematics21.org/binaries/set-filters.pdf
> for the exact definition.
>
> In my terminology it has top and bottom elements.
>

> I skip about atoms of the lattice of filters. It is probably the same
> problem with different definition.
>

Atoms for filters of a set S are the filters A_x = {S, S\x}, x in S.
The atoms for the filter F_B are A_x, x not in B.
The atoms for the Flechet filter are A_x, x in S.

William Elliot

unread,
Sep 20, 2008, 7:57:08 AM9/20/08
to
On Sat, 20 Sep 2008, William Elliot wrote:

> Atoms for filters of a set S are the filters A_x = {S, S\x}, x in S.
> The atoms for the filter F_B are A_x, x not in B.
> The atoms for the Flechet filter are A_x, x in S.
>

sup{ A_x | x in S } = Flechet filter
Thus the set of filters isn't atomistic.
It's bounded complete, chain complete, with bottom.
The non-negative reals are bounded complete, with bottom
but not chain complete.

On the other hand doesn't F_B = sup { A_x | x not in B } ?

> > I have sent you by email LaTeX file set-filters.tex. I can't offer you
> > something better.
> >

It has not arrived. Did you forget to remove "remove" from my email
address before sending?

----

Victor Porton

unread,
Sep 20, 2008, 9:57:03 AM9/20/08
to
On Sep 20, 2:28 pm, William Elliot <ma...@hevanet.remove.com> wrote:
> On Sat, 20 Sep 2008, Victor Porton wrote:
> > > > > On Sep 20, 10:13 am, William Elliot <ma...@hevanet.remove.com> wrote:
> > > > > > On Fri, 19 Sep 2008, Victor Porton wrote:
>
> > > > > > Would you like me to proof read, review another of your papers?
> > > > > > Let's start with Set Theoretic Filters, the lattice of filters.
>
> > > > > Certainly I would like you to proof read these.
>
> > > > > > It is known that the set of filters for a set S is a complete down
> > > > > > lattice, that is a meet complete semi-lattice. Does this paper go
> > > > > > beyond that?
>
> > > > > The set of filters for a set S is a complete lattice, distributive
> > > > > lattice, atomistic lattice.
>
> > > It is not complete because it has no top element.
> > > Being complete down lattice, it's a bounded complete lattice
> > > ie, every nonnul bounded set has a sup. It's also chain complete.
>
> > Oh, well, I forgot to say that my definition of filter is different
> > than the definition of filters in some other's works.
>
> Then it needs a different name.

Some authors (I can't remember who) also like me allow empty sets as
member of filters.

> > See
> >http://www.mathematics21.org/binaries/set-filters.pdf
> > for the exact definition.
>
> > In my terminology it has top and bottom elements.
>
> > I skip about atoms of the lattice of filters. It is probably the same
> > problem with different definition.
>
> Atoms for filters of a set S are the filters A_x = {S, S\x}, x in S.
> The atoms for the filter F_B are A_x, x not in B.
> The atoms for the Flechet filter are A_x, x in S.

The order of filters in my article is reversed. So what I call atomic
filters correspond to ultrafilters in the traditional terminology.

http://www.mathematics21.org/binaries/set-filters.pdf

Victor Porton

unread,
Sep 20, 2008, 10:03:48 AM9/20/08
to
On Sep 20, 2:57 pm, William Elliot <ma...@hevanet.remove.com> wrote:
> On Sat, 20 Sep 2008, William Elliot wrote:
> > Atoms for filters of a set S are the filters A_x = {S, S\x}, x in S.
> > The atoms for the filter F_B are A_x, x not in B.
> > The atoms for the Flechet filter are A_x, x in S.

I've forgot to say that I use non-standard terminology.
This annuls these problems.

See my other message in this thread for some more info about the
terminology I use.

Or better see
http://www.mathematics21.org/binaries/set-filters.pdf

> sup{ A_x | x in S } = Flechet filter
> Thus the set of filters isn't atomistic.
> It's bounded complete, chain complete, with bottom.
> The non-negative reals are bounded complete, with bottom
> but not chain complete.
>
> On the other hand doesn't F_B = sup { A_x | x not in B } ?
>
> > > I have sent you by email LaTeX file set-filters.tex. I can't offer you
> > > something better.
>
> It has not arrived. Did you forget to remove "remove" from my email
> address before sending?

I've not forgot to remove .remove. Now I sent it once more.

William Elliot

unread,
Sep 21, 2008, 2:44:38 AM9/21/08
to
On Sat, 20 Sep 2008, Victor Porton wrote:
> On Sep 20, 2:57 pm, William Elliot <ma...@hevanet.remove.com> wrote:
> > On Sat, 20 Sep 2008, William Elliot wrote:
> > > Atoms for filters of a set S are the filters A_x = {S, S\x}, x in S.
> > > The atoms for the filter F_B are A_x, x not in B.
> > > The atoms for the Flechet filter are A_x, x in S.
>
> I've forgot to say that I use non-standard terminology.
> This annuls these problems.
>
> See my other message in this thread for some more info about the
> terminology I use.
>
> Or better see
> http://www.mathematics21.org/binaries/set-filters.pdf

I cannot read that. I asked adobe@pdf2txt to convert that
file to text. It did not work because all the spaces between words had
been removed. That is quite unusual for a conversion. Are you using some
special software that use strange character for space?

> > sup{ A_x | x in S } = Flechet filter
> > Thus the set of filters isn't atomistic.
> > It's bounded complete, chain complete, with bottom.
> > The non-negative reals are bounded complete, with bottom
> > but not chain complete.
> >
> > On the other hand doesn't F_B = sup { A_x | x not in B } ?
> >
> > > > I have sent you by email LaTeX file set-filters.tex. I can't offer
> > > > you something better.
> >
> > It has not arrived. Did you forget to remove "remove" from my email
> > address before sending?
>
> I've not forgot to remove .remove. Now I sent it once more.
>

It still has not arrived. Perhaps it got caught in the spam trap.
I'll check on that. On the other hand, a possible work around would be
the address ma...@rdrop.com .

----

William Elliot

unread,
Sep 21, 2008, 2:53:02 AM9/21/08
to
On Sat, 20 Sep 2008, Victor Porton wrote:
> >
> > > > It is not complete because it has no top element.
> > > > Being complete down lattice, it's a bounded complete lattice
> > > > ie, every nonnul bounded set has a sup. It's also chain complete.
> >
> > > Oh, well, I forgot to say that my definition of filter is different
> > > than the definition of filters in some other's works.
> >
> > Then it needs a different name.
>
> Some authors (I can't remember who) also like me allow empty sets as
> member of filters.
>
> > > See
> > >http://www.mathematics21.org/binaries/set-filters.pdf
> > > for the exact definition.
> >
That doesn't work as explained in other post.

> > > In my terminology it has top and bottom elements.
>

> The order of filters in my article is reversed. So what I call atomic
> filters correspond to ultrafilters in the traditional terminology.
>
> http://www.mathematics21.org/binaries/set-filters.pdf
>

From what you tell me, here's a synopsis of what I expect the paper
to cover. Have I missed any points?

--
We shall consider the set of filters F on a set S and the extended set F*
of filters which is F with the addition of the 'filter' generated by the
empty set.

The following three theorems are familiar to those who use filters.
The intersection of any set of filters is a filter.
The union of a chain of filters is a filter.
The intersection of the ultrafilters containing a filter,
is that filter.

Expressing these facts as order theory, F is a
complete down lattice, ie a meet complete semi-lattice
a bounded complete lattice
chain complete
and F* is
a complete anti-atomic lattice
for which the ultrafilters are anti-atoms.
In other words, if the subset order of F* is reversed, it is atomic.

If f,g in F, then f inf g = f /\ g = intersection f,g.
f sup g = { A /\ B | A in f, B in G }
provided that that set does not contain the empty set.
If it does, then f sup g doesn't exist in F, that is { f,g } is
unbounded. However f sup g will exist in F* as top element.

Let F_A be the principal filter generated by A. Then
F_A inf F_B = F_(A \/ B)
and
F_A sup F_B = F_(A /\ B)
(provided A /\ B /= nulset when within F).

It can easily be shown that F* is finitely distributive from
which one discerns that F is finitely bounded distributive.

The question if F* is infinitely or completely distributive
has been left unaddressed.

--
Anyway, what does the sequel paper that generalizes those
results to (partially) ordered sets concern itself about?

----

Victor Porton

unread,
Sep 21, 2008, 5:32:00 AM9/21/08
to
On Sep 21, 9:44 am, William Elliot <ma...@hevanet.remove.com> wrote:
> It still has not arrived. Perhaps it got caught in the spam trap.
> I'll check on that. On the other hand, a possible work around would be
> the address [ANTISPAM] .

I've tried to send attached research.zip to this email.
Say me whether this arrives.

If not download it from http://www.mathematics21.org/research.zip

Victor Porton

unread,
Sep 21, 2008, 5:42:01 AM9/21/08
to
On Sep 21, 9:53 am, William Elliot <ma...@hevanet.remove.com> wrote:
> From what you tell me, here's a synopsis of what I expect the paper
> to cover. Have I missed any points?

I quickly (having busy time) viewed and answered what you've write in
your review. Not sure that I have not missed anything. Don't look on
my below replies as authoritative. I suggest better to look inside the
paper itself:
http://www.mathematics21.org/binaries/set-filters.pdf

> We shall consider the set of filters F on a set S and the extended set F*
> of filters which is F with the addition of the 'filter' generated by the
> empty set.

Yes. I call a filter also the "extended" 'filter' generated by the
empty set.

> The following three theorems are familiar to those who use filters.
> The intersection of any set of filters is a filter.
> The union of a chain of filters is a filter.
> The intersection of the ultrafilters containing a filter,
> is that filter.

In my reversed order intersection of any set of filters is a filter
AND union of any set of filters is a filter.

> Expressing these facts as order theory, F is a
> complete down lattice, ie a meet complete semi-lattice
> a bounded complete lattice
> chain complete
> and F* is
> a complete anti-atomic lattice
> for which the ultrafilters are anti-atoms.
> In other words, if the subset order of F* is reversed, it is atomic.

Like this.

> If f,g in F, then f inf g = f /\ g = intersection f,g.
> f sup g = { A /\ B | A in f, B in G }
> provided that that set does not contain the empty set.
> If it does, then f sup g doesn't exist in F, that is { f,g } is
> unbounded. However f sup g will exist in F* as top element.

> The question if F* is infinitely or completely distributive
> has been left unaddressed.

No, it was addressed. F* is infinitely distribuitive for \/ over
infinite /\.
It is not infinitely distribuitive for /\ over infinite \/ (not said
in the article but easy to find a counterexample). Consequently F* is
not completely distributive.

There are yet several things/theorems which my paper "Set Theoretic
Filters" consider.

> Anyway, what does the sequel paper that generalizes those
> results to (partially) ordered sets concern itself about?

This will be not a paper but a book, a complete reference about
filters on posets and some info about more general lattices.

William Elliot

unread,
Sep 21, 2008, 7:42:46 AM9/21/08
to
On Sun, 21 Sep 2008, Victor Porton wrote:

> On Sep 21, 9:53 am, William Elliot <ma...@hevanet.remove.com> wrote:

> > We shall consider the set of filters F on a set S and the extended set F*
> > of filters which is F with the addition of the 'filter' generated by the
> > empty set.
>
> Yes. I call a filter also the "extended" 'filter' generated by the
> empty set.
>
> > The following three theorems are familiar to those who use filters.
> > The intersection of any set of filters is a filter.
> > The union of a chain of filters is a filter.
> > The intersection of the ultrafilters containing a filter,
> > is that filter.
>
> In my reversed order intersection of any set of filters is a filter
> AND union of any set of filters is a filter.

No. What's being reversed? Anything other than for filters f,g,

f <= g when f subset g is being reversed to f <= g when g subset f?

Then f \/ g <= f,g <= f /\ g and sup and inf of sets of filters
is reversed. No. F_{0} \/ F_{1} is not an (extended) filter because
{0} /\ {1} = nulset and it lacks nulset.

Victor Porton

unread,
Sep 21, 2008, 12:53:11 PM9/21/08
to
On Sep 21, 2:42 pm, William Elliot <ma...@hevanet.remove.com> wrote:
> On Sun, 21 Sep 2008, Victor Porton wrote:
> > On Sep 21, 9:53 am, William Elliot <ma...@hevanet.remove.com> wrote:
> > In my reversed order intersection of any set of filters is a filter
> > AND union of any set of filters is a filter.
>
> No. What's being reversed? Anything other than for filters f,g,
>
> f <= g when f subset g is being reversed to f <= g when g subset f?

Yes.

> Then f \/ g <= f,g <= f /\ g and sup and inf of sets of filters
> is reversed. No. F_{0} \/ F_{1} is not an (extended) filter because
> {0} /\ {1} = nulset and it lacks nulset.

sup and inf of sets of filters is reversed as well as <=.

Reply all
Reply to author
Forward
0 new messages