Problem Set 9

Due Date: Thurs, April 17, 2003

Problems

  1. a) Give a finite model of a semigroup that is not commutative.

    b) Give a finite model of a commutative semigroup that is not a monoid.

  2. Consider the boolean ring $\langle$I B, =, \(\,\Leftrightarrow\,\), \(\,\scriptstyle\vee\,\), T, F$\rangle$. Define the operations \(\sim\), \(\,\scriptstyle\wedge\,\), and \(\supset\) in terms of the ring operations and prove the followng laws solely on the basis of the ring axioms.

    (1) p\(\supset\)(p \(\,\scriptstyle\vee\,\)q),
    (2) (p \(\,\scriptstyle\wedge\,\)q)\(\supset\)p,
    (3) (p \(\,\scriptstyle\wedge\,\)q)\(\supset\)q,
    (4) p\(\supset\)(q\(\supset\)p),
    (5) \(\sim\)q\(\supset\)(q\(\supset\)p),
    (6) p\(\supset\)q\(\supset\)(\(\sim\)q\(\supset\)\(\sim\)p), and
    (7) p \(\,\scriptstyle\vee\,\)p \(\,\Leftrightarrow\,\)p.

  3. Is $\langle$\(\mathbb{Z}\), =$_5$, +, *$\rangle$ a field?
    If so, give brief proofs of the axioms. If not, show which axiom is not satisfied.

  4. Define x<y \(\,\equiv\,\) (\({\exists}\)z)(x+z+1 =y) and prove the seven axioms of discrete linear orders for < from the Peano axioms.

    lt-asym: (\({\forall}\)x,y) (x<y \(\supset\) \(\sim\)(y<x))
    lt-trans: (\({\forall}\)x,y,z) ((x<y \(\,\scriptstyle\wedge\,\) y<z) \(\supset\) x<z)
    lt-linear: (\({\forall}\)x,y) (x<y \(\,\scriptstyle\vee\,\) y<x \(\,\scriptstyle\vee\,\) x=y)
    lt-discrete:(\({\forall}\)x,y) \(\sim\)(x<y \(\,\scriptstyle\wedge\,\) y<x+1)
    lt-0-1: 0<1
    lt-mono-+: (\({\forall}\)x,y,z)(x<y \(\supset\) x+z < y+z)
    lt-mono-*: (\({\forall}\)x,y,z)((0<z \(\,\scriptstyle\wedge\,\) x<y) \(\supset\) x*z < y*z)


Juanita Heyerman 2003-04-10