The infimum

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

Advertisements

2 Responses to “The infimum”

  1. vlorbik Says:

    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?

  2. eeoam Says:

    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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: