The infimum « Maths for Mortals

The infimum

By eeoam

The infimum is defined for boolean $X$ and $Y$ by the Golden Rule:

$X\sqcap Y\ \equiv\ X\ \equiv\ Y\ \equiv\ X\sqcup Y$

By studying this rule we can observe several facts about the infimum. First, since it is defined in terms of $\equiv$ and $\sqcup$ we have

$X\sqcap Y$

$\equiv$ {Golden Rule}

$X\ \equiv\ Y\ \equiv\ X\sqcup Y$

$\equiv$ {Symmetry of $\equiv$ and $\sqcup$ }

$Y\ \equiv\ X\ \equiv\ Y\sqcup X$

$\equiv$ {Golden Rule}

$Y\sqcap X$

i.e. $\sqcap$ is symmetric.

Exercise: Show that $\sqcap$ is associative.

Furthermore, $\sqcap$ is idempotent:

$X\sqcap X$

$\equiv$ {Golden Rule}

$X\ \equiv X\ \equiv\ X\sqcup X$

$\equiv$ {identity of $\equiv$ ; idempotence of $\sqcup$ }

$X$

With regard to last three properties, $\sqcap$ is just like $\sqcup$ . We might very well ask, is $\top$ a fixed point of $\sqcap$ as it is of $\sqcup$ ? Let’s calculate:

$X\sqcap\top$

$\equiv$ {Golden Rule}

$X\ \equiv\ \top\ \equiv\ X\sqcup\top$

$\equiv$ {fixed point of $\sqcup$ }

$X\ \equiv\ \top\ \equiv\ \top$

$\equiv$ {identity of $\equiv$ }

$X$

So $\top$ is the identity of $\sqcap$ .

Next we have two very useful laws of absorption/introduction:

$X\sqcap(X\sqcup Y)$

$X\sqcup(X\sqcap Y)$

We shall prove the first, the second follows by interchanging $\sqcap$ and $\sqcup$ .

$X\sqcap(X\sqcup Y)$

$\equiv$ {Golden rule}

$X\ \equiv\ X\sqcup Y\ \equiv\ X\sqcup X\sqcup Y$

$\equiv$ {idempotence}

$X\ \equiv\ X\sqcup Y\ \equiv\ X\sqcup Y$

$\equiv$ {identity of $\equiv$ }

$X$

What about distributivity properties?

$X\sqcup(Y\sqcap Z)\ \equiv\ (X\sqcup Y)\sqcap(X\sqcup Z)$

$X\sqcup(Y\sqcap Z)$

$\equiv$ {Golden rule}

$X\sqcup(Y\ \equiv\ Z\ \equiv\ Y\sqcup Z)$

$\equiv$ {distributivity}

$X\sqcup Y\ \equiv\ X\sqcup Z\ \equiv\ X\sqcup Y\sqcup Z$

$\equiv$ {idempotence, preparing for the Golden Rule}

$X\sqcup Y\ \equiv\ X\sqcup Z\ \equiv\ X\sqcup Y\sqcup X\sqcup Z$

$\equiv$ {Golden Rule}

$(X\sqcup Y)\sqcap(\sqcup Z)$

$(X\sqcap Y)\sqcup(X\sqcap Z)$

$\equiv$ { $\sqcup$ distributes over $\sqcap$ }

$((X\sqcap Y)\sqcup X)\sqcap((X\sqcap Y)\sqcup Z)$

$\equiv$ {absorption}

$X\sqcap((X\sqcap Y)\sqcup Z)$

$\equiv$ { $\sqcup$ distributes over $\sqcap$ }

$X\sqcap((X\sqcup Z)\sqcap(Y\sqcup Z))$

$\equiv$ {associativity; symmetry}

$X\sqcap(((X\sqcup Z)\sqcap Z)\sqcup Y)$

$\equiv$ {absorption}

$X\sqcap(Y\sqcup Z)$

So $\sqcap$ distributes over $\sqcup$ . What about $\equiv$ ? The best we can do is

$X\sqcap(Y\equiv Z)$

$\equiv$ {Golden rule}

$X\ \equiv\ Y\ \equiv\ Z\ \equiv\ X\sqcup(Y\equiv Z)$

$\equiv$ {distributivity}

$X\ \equiv\ Y\ \equiv\ Z\ \equiv\ X\sqcup Y\ \equiv\ X\sqcup Z$

$\equiv$ {symmetry, preparing for Golden rule}

$X\ \equiv\ Y\ X\sqcup Y\ \equiv\ Z\ \equiv\ X\sqcup Z$

$\equiv$ {Golden rule, twice}

$X\sqcap Y\ \equiv\ X\sqcap Z\ \equiv X$

As a consolation we do have

$W\sqcap(X\equiv Y\equiv Z)\ \equiv\ W\sqcap X\ \equiv\ W\sqcap Y\ \equiv\ W\sqcap Z$ .

Finally we have

$X\sqcap(X\equiv Y)$

$\equiv$ {pseudo-distributivity}

$X\sqcap X\ \equiv\ X\sqcap Y\ \equiv X$

$\equiv$ {idempotence; identity of $\equiv$ }

$X\sqcap Y$

This entry was posted on October 18, 2007 at 11:11 am and is filed under Basics, Calculating with booleans. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “The infimum”

vlorbik Says:
November 9, 2007 at 3:45 pm | Reply
when i first saw this, i thought
it was probably incoherent.
in particular, the “golden rule”
$X\sqcap Y\ \equiv\ X\ \equiv\ Y \equiv X\sqcup Y$
sure looks like it would benefit from some parentheses:
$((X\sqcap Y) \equiv\ X) :\equiv (Y \equiv (X\sqcup Y))$ –
i.e., we’re defining $\sqcap$ in terms of $\sqcup$ .

but i looked a little more carefully and am now
willing to admit that, for example,
$(X\sqcap Y) \equiv\ ((X \equiv Y) \equiv X\sqcup Y)$
“equivales to Top” (“evaluates to True”
in my preferred dialect)
for any assignment of boolean values to X and Y
–as you’ve observed, $\equiv$ is associative.
now: why bother? “maths for mortals”?
do you actually think this presentation
will be *easier* for a beginner
to follow than the more-or-less standard
“truth tables and venn diagrams” approach?
– if so, don’t get me wrong,
you might very well be right.
i was wrong about the golden rule
and i might very well be wrong about
thinking that nobody who isn’t
pretty doggone sure of themselves already
would ever think of trying to jump in
and wade through this depth of code
without considerable amounts of coaching.
i suppose my question for you
is: who are you trying to reach here?
eeoam Says:
November 13, 2007 at 9:39 am | Reply
That’s something I’ve been thinking myself. I think I’ve been going too far too fast. I’d like to reach people who are familiar with basic mathematics but want to move to the next level. My next post will take a gentler approach.

Leave a Reply