Discrete structure and theory of logic

 Partially ordered sets (posets) and lattices are fundamental concepts in order theory, a branch of mathematics dealing with the arrangement of elements under a certain relation.

Partially Ordered Sets (Posets)

A poset is a set $P$ equipped with a partial order $\leq$, which satisfies the following properties for all $a, b, c \in P$:

1. Reflexivity: $a \leq a$
2. Antisymmetry: If $a \leq b$ and $b \leq a$, then $a = b$
3. Transitivity: If $a \leq b$ and $b \leq c$, then $a \leq c$

A partial order means that not every pair of elements must be comparable (i.e., it is not necessarily a total order).

Examples of Posets

1. The set of natural numbers $\mathbb{N}$ with the usual $\leq$.
2. The power set of a set $S$, ordered by set inclusion $\subseteq$.
3. The divisibility relation on $\mathbb{Z}^+$, where $a \leq b$ if $a$ divides $b$.

Lattices

A lattice is a poset in which every pair of elements $a, b$ has:

1. A greatest lower bound (GLB) or meet $a \wedge b$.
2. A least upper bound (LUB) or join $a \vee b$.

This means that in a lattice, any two elements must have a well-defined meet and join.

Types of Lattices

1. Bounded Lattice: A lattice with a least element (0) and a greatest element (1).
2. Distributive Lattice: A lattice where the meet and join operations distribute over each other: $$a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$$ $$a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$$
3. Modular Lattice: Weaker than distributive, it satisfies: $$a \leq c \Rightarrow a \vee (b \wedge c) = (a \vee b) \wedge c$$
4. Complete Lattice: A lattice where every subset has a meet and join.

Examples of Lattices

1. The power set of a set $S$ with union (join) and intersection (meet).
2. The divisibility lattice of integers, where join is LCM and meet is GCD.
3. Boolean algebras, which are distributive lattices with complements.