\problemdata
{relations}
{S00 ps3}
{false proofs}

\begin{problem}
Find the flaws in the following fallacious proofs of
putative theorems.  For each, if the theorem is false, give a
counterexample; if it is correct, give a correct proof.

\begin{problemparts}

\problempart
% topic: false proof, Cartesian products, relations
% source: Velleman 4.1.5


\emph{Theorem?} For any sets $A$, $B$, $C$, and $D$, $(A \union C)
\times (B \union D) \subseteq (A \times B) \union (C \times D)$?

\begin{proof}
  Suppose $(x, y) \in (A \union C) \times (B \union D)$.  Then $x \in A \union 
  C$ and $y \in B \union D$, so either $x \in A$ or $x \in C$, and either 
  $y \in B$ or $y \in D$.  We consider these cases separately.

  \emph{Case 1}. $x \in A$ and $y \in B$.  Then $(x, y) \in A \times B$.
  \newline
  \emph{Case 2}. $x \in C$ and $y \in D$.  Then $(x, y) \in C \times D$.

  Thus, either $(x, y) \in A \times B$ or $(x, y) \in C \times D$, so 
  $(x, y) \in (A \times B) \union (C \times D)$.
\end{proof}

\solution{
\newline
\textbf{The theorem does not hold.}
The cases do not exhaust all of the
possibilities.
The correct way to write the proof would be to include first the possibilities
that $A$, $B$, $C$, and $D$ are null and then trying out all \emph{four} 
cases, $x \in A \land y \in B$, $x \in A \land y \in D$, $x \in C \land y \in 
B$, and $x \in C \land y \in D$.
\newline
Consider the case where $A = \emptyset$, $C = \{1\}$, $B = \{2\}$, and $D = 
\{4\}$.  Then, the LHS (left-hand-side) gives $\{(1, 2), (1, 4)\}$, while the
RHS gives $\{(1, 4)\}$.  The statement of the theorem clearly does not hold in
this case.
}

\problempart
% topic: ???
% source: Velleman 4.3.10

\emph{Theorem?}  Suppose $R$ is a relation on $A$.  If $R$ is symmetric and 
transitive, then $R$ is reflexive.

\begin{proof}
Let $x$ be an arbitrary element of $A$.  Let $y$ be any element of $A$ such 
that $xRy$.  Since $R$ is symmetric, it follows that $yRx$.  Then by 
transitivity, since $xRy$ and $yRx$.  We conclude that $xRx$.  Since $x$ was
arbitrary, we have shown that $\forall x \in A (xRx)$, so $R$ is reflexive.
\end{proof}

\solution{
\newline
\textbf{The theorem does not hold.}
Suppose $A = \{a, b, c, d\}$ and we are given the relation 
$R = \{(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), 
(c, c)\}$.  Then R is symmetric [``$\forall x \in A \forall y \in A (xRy 
\implies yRx$''] and transitive [``$\forall x \in A \forall y \in A 
\forall z \in A ((xRy \land yRz) \implies xRz)$''].  However, it is not
reflexive, as it is not the case that ``$\forall x \in A (xRx)$'', as 
$(d, d) \notin R$.
}


\problempart
% topic: relations, building posets out of transitive closure of a reflexive, 
%        antisymmetric relation
% source: Velleman 4.5.12

\emph{Theorem?}  Suppose $R$ is a reflexive, antisymmetric relation on $A$.  
Let $S$ be the transitive closure of $R$.  Then $S$ is a partial order on $A$.
\begin{proof}
$R$ is already reflexive and antisymmetric.  To form the relation $S$ we add 
more ordered pairs to make it transitive as well.  Thus, $S$ is reflexive, 
antisymmetric, and transitive, so it is a partial order.
\end{proof}

\solution{
\newline
\textbf{The theorem does not hold.}
Suppose we have the relation $R = \{(a, a), (b, b), (c, c), (a, b), 
(b, c), (c, a)\}$.  This relation is both reflexive and antisymmetric
on $A = \{a, b, c\}$.  However, taking its transitive closure would break
the antisymmetry.  For example, the transitive closure $T$ of $R$ includes 
$(a, c)$, since there is a walk from $a$ to $c$ in $R$.  Since $T$ also 
contains $(c, a)$, it is not antisymmetric.
}

\end{problemparts}
\end{problem}
