Special Binary Relations

Prove that if the relations $R_{1}$ and $R_{2}$ are reflexive, then the relations $R_{1} \cup R_{2}$, $R_{1} \cap R_{2}$, $R_{1}^{-1}$, $R_{1} \cdot R_{2}$ are reflexive.

Prove that if the relations $R_{1}$ and $R_{2}$ are irreflexive, then the relations $R_{1} \cup R_{2}$, $R_{1} \cap R_{2}$, $R_{1}^{-1}$ are irreflexive. Show that the product $R_{1} \cdot R_{2}$ of irreflexive relations need not be irreflexive.

Prove that if the relations $R_{1}$ and $R_{2}$ are symmetric, then the relations $R_{1} \cup R_{2}$, $R_{1} \cap R_{2}$, $R_{1}^{-1}$, $R_{1} \cdot R_{2}^{-1}$ are symmetric.

Prove that the product $R_{1} \cdot R_{2}$ of symmetric relations $R_{1}$ and $R_{2}$ is symmetric if and only if $R_{1} \cdot R_{2} = R_{2} \cdot R_{1}$.

Prove that:

Construct a binary relation that is:

Prove that any relation $R$ that is both symmetric and antisymmetric is transitive.

Prove that a relation $R$ on a set $A$ is simultaneously an equivalence and a partial order if and only if $R = i_{A}$.

On the sets $\mathbb {N}$ and $\mathbb {N} \times \mathbb {N}$ define $R_{m}$, $Q$, $S$ as follows:

Let $A$ be the set of all lines in the plane. Are the following relations equivalences:

On the set $\mathbb {R}$ of real numbers define a relation $R$ as follows:

Prove that $R$ is an equivalence.

Prove that if $R$ is an equivalence, then:

Prove that if $R$ is an equivalence, then $R^{-1}$ is also an equivalence.

Let $R \subseteq A^{2}$. Prove that

Prove that if $R_{1}$ and $R_{2}$ are equivalences on $A$, then:

Prove that there exists a one-to-one correspondence between the class of all partitions of a set $A$ into disjoint nonempty subsets and the family of all equivalence relations on $A$. (A family $\left\{ A_{i}\right\}_{i \in I}$ is called a partition of $A$ if $\bigcup_{i \in I} A_{i} = A$ and the sets $A_{i}$ are pairwise disjoint.)

Prove that $R$ is an equivalence relation on a set $A$ if and only if there exists a system $P$ of pairwise disjoint sets such that

Let $f: A \rightarrow B$ be an arbitrary function. Put

Prove that $Q$ is an equivalence on $A$ and that the map $f$ admits a factorization

where $\varepsilon$ is the natural map of $A$ onto $A/Q = \left\{ [x]_{Q} \mid x \in A\right\}$, i.e., $\varepsilon (x) = [x]_{Q}$, and $f_{1}$ is a one-to-one correspondence between $A/Q$ and $f(A)$.

Prove that the intersection of any system of equivalences on a set $A$ is an equivalence on $A$.

Prove that the union $R_{1} \cup R_{2}$ of equivalences $R_{1}$ and $R_{2}$ is an equivalence if and only if $R_{1} \cup R_{2} = R_{1} \cdot R_{2}$.

Prove that the product $R_{1} \cdot R_{2}$ of two equivalences $R_{1}$ and $R_{2}$ is an equivalence if and only if $R_{1} \cdot R_{2} = R_{2} \cdot R_{1}$.

Prove that if $R_{1}$ and $R_{2}$ are equivalences and $R_{1} \cdot R_{2} = R_{2} \cdot R_{1}$, then $R_{1} + R_{2} = R_{1} \cdot R_{2}$, where $R_{1} + R_{2}$ is the smallest equivalence relation containing $R_{1} \cup R_{2}$.

Prove that for every family of equivalences $\left\{ R_{i}\right\}_{i \in I}$ there exists an equivalence $Q$ such that $\bigcup_{i \in I} R_{i} \subseteq Q$ and, for every equivalence relation $R$, if $\bigcup_{i \in I} R_{i} \subseteq R$, then $Q \subseteq R$.

Prove that

where $p_{n}$ is the number of equivalences on a set of $n$ elements.

Prove that the set of all subsets of a given set is partially ordered by the inclusion relation $\subseteq$.

Let $\leq$ and $<$ on the set $\mathbb {N} = \left\{ 0, 1, 2, \ldots \right\}$ be defined in the usual way. Prove that $< \cdot < \; \neq \; <$; $\leq \cdot < \; = \; <$; $\leq \cdot \geq \; = \; \mathbb {N}^{2}$.

Prove that $i_{A}$ is a partial order on $A$.

Let $a \leq b \Leftrightarrow a, b \in \mathbb {N}$ and $a$ divides $b$. We take $0$ to divide $0$. Prove that $\leq$ is a partial order on $\mathbb {N}$.

Prove that if $R$ is a partial order, then $R^{-1}$ is a partial order.

Show that if $\left\{ R_{i}\right\}_{i \in I}$ is a system of partial orders on a set $A$, then $\bigcap_{i \in I} R_{i}$ is a partial order on the set $A$.

Prove that a relation $R$ on a set $A$ is a preorder if and only if $R = (R \cdot R) \cup i_{A}$.

Let $R$ be a preorder relation on $A$. Put

Prove that:

Prove that if $R$ is a partial (linear, complete) order on $X$ and $A \subseteq X$, then $R \cap A^{2}$ is a partial (linear, complete) order on $A$.

Let $\leq$ be a partial order on $A$. Prove that $<$ is irreflexive and transitive.

Prove that if some relation $<$ on $A$ is irreflexive and transitive, then the relation

is a partial order on $A$.

Show that if $A$ and $A_{1}$ are partially ordered sets and $f: A \rightarrow A_{1}$ is a monotone function establishing a one-to-one correspondence between $A$ and $A_{1}$, then $f^{-1}$ need not be monotone.

Consider the case where $A$ is a linearly ordered set.

Prove that any partially ordered set $A$ is isomorphic to some system of subsets of $A$, ordered by inclusion $\subseteq$.

Let $R_{1}$ and $R_{2}$ be linear orders on a set $A$. When is $R_{1} \cdot R_{2}$ a linear order?

Construct a linear order on the set:

Prove that any finite set can be linearly ordered.

Prove that any partial order $R$ on a finite set $A$ can be extended to a linear order $R \subseteq Q$ on the set $A$ (see also problem I.5.69).

Let $A$ be a partially ordered set in which every chain has at most $m$ elements, and every subset of pairwise incomparable elements consists of at most $n$ elements. Show that $A$ has at most $m \cdot n$ elements.

Let $\leq_{A}$ be a partial order on a set $A$, and $\leq_{B}$ a partial order on a set $B$. Call the direct product of the partially ordered sets $A$ and $B$ the set $A \times B$ with the relation $\leq$ defined on it:

Prove that $\leq$ is a partial order on $A \times B$.

Let $A$ be a partially ordered set, $a, b \in A$, and $a \leq b$. Call the set $[a, b] = \left\{ x \mid a \leq x \leq b\right\}$ a segment. Show that the set of all segments of $A$, partially ordered by inclusion, is isomorphic to some subset of the direct product of $A$ and its dual partially ordered set.

Call a partially ordered set $A$ self-dual if it is isomorphic to its dual partially ordered set. Prove that:

We say that a partially ordered set $A$ satisfies:

1. the minimality condition, if every nonempty subset $M$ of the set $A$ has at least one minimal element;

2. the descending chain condition, if every strictly decreasing chain in $A$ is finite;

3. the induction condition, if for every property $T$ the following holds:

   suppose that for every element $a \in A$, the validity of the property $T$ for all elements strictly less than $a$ implies the validity of $T$ for $a$; then all elements of the set $A$ have the property $T$. Prove that all these conditions are equivalent.

Prove that a partially ordered set satisfies the minimality condition if and only if all its chains are well-ordered.

Describe all linearly ordered sets $A$ having the property that for any $a \leq b$ there exist only finitely many $c$ such that $a \leq c \leq b$.

Find all sets $M$ such that there exists a complete order $R$ such that $R^{-1}$ is also a complete order on $M$.

Let $\varphi : A \times A \rightarrow A$ and, for all $x, y, z \in A$,

Define $x \leq y \Leftrightarrow \varphi (x, y) = x$. Prove that:

Prove that any subset of the set $P(A)$, partially ordered by inclusion, has a least upper bound and a greatest lower bound.

Prove that:

Prove that in a lattice any maximal element is the greatest element, and any minimal element is the least element.

Prove that any finite lattice has a greatest and a least element.

Give examples of lattices:

Prove that in any lattice the identities

hold.

Suppose two-place functions $\cup$ and $\cap$ are defined on a set $M$, satisfying the identities $(l_{1})$--$(l_{6})$ of the previous problem.

Prove that in every Boolean algebra $M$:

Prove that an algebra of subsets, ordered by inclusion, is a Boolean algebra.

Prove that $1 \in D$ and $0 \notin D$ for any filter $D$.

Let $M$ be a Boolean algebra, $A \subseteq M$. Prove that if $a_{1} \cap \ldots \cap a_{n} \neq 0$ for every $n > 0$ and any elements $a_{1}, \ldots , a_{n} \in A$, then the set

is a filter on $M$.

Let $D$ be a filter on a Boolean algebra $M$ and $(x \cup y) \in D$. Prove that there exists a filter $D_{1} \supseteq D$ such that $x \in D_{1}$ or $y \in D_{1}$.

Prove that for any filter $D$ the following conditions are equivalent:

Prove that any filter on a Boolean algebra $M$ is contained in some maximal filter on $M$.

Prove that for any elements $a, b$ of a Boolean algebra $M$, if it is not the case that $a \leq b$, then there exists a prime filter $D$ such that $a \in D$ and $b \notin D$.

Let $M$ be a Boolean algebra, $P$ the set of all prime filters on $M$. Put, for $a \in M$,

Prove that the set

is an algebra of subsets of the set $P$.

Prove that any Boolean algebra is isomorphic to some algebra of subsets of a suitable set (Stone’s theorem).

Prove that any filter on a finite Boolean algebra has a least element.

Prove that any finite Boolean algebra is isomorphic to the algebra of all subsets of some set.