2007 October « Maths for Mortals

Archive for October, 2007

The infimum

October 18, 2007

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$

Posted in Basics, Calculating with booleans | 2 Comments »

We have seen how to use the $\equiv$ operator to calculate with booleans. It is time to investigate another operator, the supremum, written as ` $\sqcup$ ‘ and pronounced `cup’.
$\sqcup$ has a higher binding power than $\equiv$ which means that the expression

$X\sqcup Y\ \equiv\ Z$

is read as

$(X\sqcup Y)\equiv Z$

(Notice the greater space around $\equiv$ in the first expression).

The first two properties of the supremum are familiar:Associativity: $(X\sqcup Y)\sqcup Z\ \equiv\ X\sqcup(Y\sqcup Z)$

Symmetry:

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

The next two are new:

Idempotence:

$X\sqcup X\ \equiv\ X$

Distributivity/Factoring:

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

Armed with these rules, we can now prove our first property concerning the supremum:Distributivity/Factoring:

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

Proof

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

$\equiv\quad\{associativity\}$

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

$\equiv\quad\{symmetry\}$

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

$\equiv\quad\{associativity\}$

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

$\equiv\quad\{idempotence\}$

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

Our next rule isFixed point:

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

Proof

$\quad X\sqcup\top$

$\equiv\quad\{(2)\}$

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

$\equiv\quad\{distributivity\}$

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

$\equiv\quad\{reflexivity\}$

$\quad\top$

Posted in Basics, Calculating with booleans | Leave a Comment »

Equivalence

October 11, 2007

At the heart of our approach to mathematics is the technique of calculation. When we calculate, we rearrange expressions to form new expressions in accordance with certain rules. These expressions may have many different values. One way we cope with this complexity is to identify values which have properties in common and collect them into groups. Such groups are called types. If a value $v$ belongs to a type $T$ , we say that $v$ is of type $T$ .

***

The first type we will explore is a very simple one – so simple it consists of only two values. The type is called boolean and its values are $\top$ , pronounced “top” and $\bot$ , pronounced “bottom”.

Now we can talk about the value of $X = Y$ :

“The value of $X = Y$ is of type boolean.”

or, equivalently,

“The value of $X = Y$ is either $\top$ or $\bot$ .”

***

Equality between booleans is special, and so when we express equality between $X$ and $Y$ , where $X$ and $Y$ are boolean we write

$X\equiv Y$

pronounced “ $X$ equivales $Y$ “.

What is so special about boolean equality – called equivalence - that we have special symbol for it? The answer gives us our first rule for calculating:

Associativity:
$(X \equiv (Y \equiv Z)) \equiv ((X \equiv Y ) \equiv Z)$

We give the rule a name to help us remember what it is. Here is how we would use the rule in calculations:

	$X \equiv (Y \equiv Z)$
$\equiv\quad$	$\{\textrm{associativity}\}$
	$(X \equiv Y ) \equiv Z$

An important consequence of $\eqv$’s associativity is that when we have a series of expressions punctuated by $\eqv$ signs it does not matter where we put the brackets. Indeed, we need not write the brackets at all, as for instance in our next rule:\\

Symmetry: $X\equiv Y\equiv Y\equiv X$

We may parse this rule in several ways:

$ latex (X\equiv Y)\equiv (Y\equiv X)$

$X\equiv (Y\equiv Y\equiv X)$

$(X\equiv Y\equiv Y)\equiv X$

The last two expressions tell us that `equivaling’ $Y\equiv Y$ with any boolean $X$ is $X$ . We say that $Y\equiv Y$ is the identity of $\equiv$ . Our next rule gives a name to the identity:

(2) $X\equiv\top\equiv X$

Up to this point we have simply postulated rules i.e. we have taken it as given that they hold. Our next rule, however, we will prove. How do we prove? When we postulate a rule we are saying that it is an expression which is equivalent to $\top$ . So to show that an expression is a rule, we present a calculation showing that the said expression is also equivalent to $\top$ .

Reflexivity: $X\equiv X$

Proof

$X\equiv X$

$\equiv$ {{(2), parsed as $X\equiv(\top\equiv X)$

$X\equiv\top\equiv X$

$\equiv$ {(2)}

$\top$

Such is the equivalence.

Challenge: Does anyone know how to get the latex \quad and \begin{tabular} commands to work in WordPress?

Posted in Basics, Calculating with booleans | 1 Comment »

Welcome

October 10, 2007

This blog is for people who think they are no good at maths. I say to you: You are better than you think. Read on for proof.

***

Let us start with the simple notion of an expression. As its name suggests, an expression is used to express (or denote) a value. A value may be a sum of money or the weight of an object or the truth of an assertion.

There are two kinds of expressions: constants and variables.

A constant represents a particular value and that value cannot be changed. Examples of constants include $1$ , $2007$ .

A variable can represent any value (though only one value at time). In addition the value of a variable can be replaced by another expression. We’ll see exactly how to do this later on. We use single italic letters for variables e.g. $X$ , $Y$ .

All our expressions will denote at most one value, but a value may be denoted by more than one expression. For example the expressions $1+1$ and $2$ both denote the same value.

Now writing

“the expression $X$ denotes the same value as the expression $Y$ “

over and over would become quite tiresome. So we instead we just write

$X = Y$

pronounced “ $X$ equals $Y$ “.

Moreover, we may view X = Y not just as a statement of fact but as an expression in its own right. But what, then, is its value?

Exercise - Ask any mathematicians you know what they can tell you about the value of $X = Y$ .

Posted in Basics | Leave a Comment »

Maths for Mortals

Archive for October, 2007

The infimum

The supremum

Equivalence

Welcome

Pages

Archives

Categories