hw10.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%free online editor available at%%%%%%%%%%%%%%%%%%%%%%
%%%%%https://www.writelatex.com/%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[10pt,leqno ]{article}
    %The document class defines the master templates, the structure of the document, 
    %and lays out the types of 
    %objects that can be manipulated for this type of document. 
    %the brackets contain basic options that will be applied globally (throughout
    %the document). Here, we specify a 10pt font, and when we number an equation, the 
    %number will be on the left.
    %The document class is a file ***.cls. You will probably never have to edit or create
    % a .cls file. There are many available on the internet for your use.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts}
\usepackage[shortlabels]{enumitem}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{times}
\usepackage{amsthm}
\usepackage{hyperref}
%\usepackage{homework}
    %packages control the ``style'' or look of the document. These come in the form of 
    %files ***.sty. The package ``homework'' above was created by me. The other packages
    %are very common for this type of document. You can google to learn more about what
    %they can do, and what options they give you. For example
\usepackage{textcomp}
\usepackage[margin=1.5in]{geometry}
    %the geometry package lets you customize the margins of your document.
    % and the 

\usepackage{forest}
  % For drawing the tree illustrating the sample space  
\usepackage{setspace}
    %package gives us the ability to set the line spacing.
\usepackage{moreenum}   % for greek letters in enum
\usepackage{xcolor}

\newtheorem{theorem}{Theorem}
\theoremstyle{definition} 
\newtheorem{problem}[theorem]{Problem}
    %these set up environments for listing things. The numbering is automatic.
\usepackage{float}
\restylefloat{table}
\usepackage{mathtools}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}

\newenvironment{solution}[1][Solution]{\begin{doublespace}\textbf{#1.}\quad }{\ \rule{0.5em}{0.5em}\end{doublespace}}
    %this is the environment for writing solutions. Doble spaced, with an end of proof
    %box at the end
    
\title{Discrete Math\\
CSCI 150, Fall 2020\\
Homework 1}
\author{Guy Matz \\
Hunter College}
    %above is the information that goes in the title. Notice the { and }. 
    %the double slashes \\ mean start a new line.


\begin{document} %this means end the preamble (stuff controling the styles above and
%start the content of the document. We can make adjustments as we go. For example,
%\maketitle
\textbf{Exercises}\\
For each of the following relations, determine if it is reflexive, symmetric, anti-symmetric, and transitive.  We have seen the reflexive, symmetric, and transitive properties in class.  The antisymmetric property states that if $a \neq b$ then $(a, b) \in \mathbb{R} \implies (b, a) \notin \mathbb{R}$.

\begin{center}
Reflexive: $(a,a) \in R$\\
Symmetric: $(a,b) \in R  \implies (b, a) \in R$\\
Transitive: $((a, b) \in R \wedge (b, c) \in R) \implies (a,c) \in R$\\
Antisymmetric: $(a,b) \in R \implies (b, a) \notin R$ (if $a\neq b$)\\
\end{center}
\begin{problem} The subset relation on the power set of some set $S$
\Large
\begin{itemize}
\item \underline{Reflexive}: $\forall x \in S, x S x$\\
False, since $a \not\subset a$
\item \underline{Symmetric}: $\forall x, y \in S, (x, y) \in S \implies (y, x) \in S$\\
False, since $a \subset b \implies b \subset a$ is false
\item \underline{Anti-symmetric}: $\forall x \neq y \in S, (x, y) \in S \implies (y, x) \notin S$\\
True, since $a \subset b \implies b \not\subset a$
\item \underline{Transitive}: $\forall x,y,z \in S, (x, y) \in S$ and $(y, z) \in S \implies (x, z) \in S$ \\
True, since $a \subset b \wedge b \subset c \implies a \subset c$
\\\\
So the relation is a strict partial ordering
\end{itemize}

\end{problem}
\newpage

\begin{problem} The relation $\leq$ on $\mathbb{R}$
\\\\
\Large
\item \underline{Reflexive}: $\forall x \in \mathbb{R}, x \leq x$.  \\
This is true since any number is less than or equal to itself.\\
\item \underline{Symmetric}: $\forall x,y \in \mathbb{R}, x \leq y \implies y \leq x$.  \\
This is false.  As a counter-example, take $(4, 5)$.  $4 \leq 5$, but $5 \not\leq 4$. \\
\item \underline{Anti-symmetric}: $\forall x \neq y \in \mathbb{R}, (x, y) \in \mathbb{R} \implies (y, x) \notin \mathbb{R}$\\
This is true.  It is only the case for any two $x, y$ where $x \neq y$, that $x < y$, or $x > y.$  Then, if $x < y$ it cannot be that $x > y$, so we have anti-symmetry.
\\
\item \underline{Transitive}: $\forall x,y,z \in \mathbb{R}, x \leq y$ and $y \leq z \implies x \leq z$\\
This is true due to transitivity of real numbers
\\\\
So  $\leq$ is a partial ordering
\end{problem}
\newpage

\begin{problem}  The relation $<$ on $\mathbb{Z}$
\\\\
\Large
\item \underline{Reflexive}: $\forall x \in \mathbb{Z}, x < x$.  \\
This is false since no a number cannot be less than itself.\\
\item \underline{Symmetric}: $\forall x,y \in \mathbb{Z}, x < y \implies y < x$.  \\
This is false.  As a counter-example, take $(4, 5)$.  $4 < 5$, but $5 \nless 4$. \\
\item \underline{Anti-symmetric}: $\forall x,y \in \mathbb{Z}, (x, y) \in \mathbb{Z} \implies (y, x) \notin \mathbb{Z}$ if $a \neq b$\\
This is true.  It is only the case for any two $x, y$ where $x \neq y$, that $x < y$, or $x > y.$  Then, if $x < y$ it cannot be that $x > y$, so we have anti-symmetry.
\\
\item \underline{Transitive}: $\forall x,y,z \in \mathbb{Z}, x < y$ and $y < z \implies x < z$
\\
True due to the transitivity of real numbers.
\\\\
So $<$ is a strict partial ordering
\end{problem}
\newpage

\begin{problem} The relation “shares a class with” where two people share a class if there is a class they are both enrolled in this semester.
\\\\
\Large
\item \underline{Reflexive}: $\forall x \in S, x S x$\\
True, for surely every student "shares a class with" them self!\\
\item \underline{Symmetric}: $\forall x,y \in S, (x, y) \in S \implies (y, x) \in S$\\
True, for if student A shares a class with student B, then student B shares that same class with student A.\\
\item \underline{Anti-symmetric}: $\forall x,y \in S, (x, y) \in S \implies (y, x) \notin S$ if $x \neq y$\\
False since it must be that if $x$ and $y$ are in the same class then certainly $y$ and $x$ and in the same class..\\
\item \underline{Transitive}: $\forall x,y,z \in S, (x, y) \in S$ and $(y, z) \in S \implies (x, z) \in S$\\
False.   Students A and B may share a class, and students B and C may share a different class, meaning that A and C do not share a class.
\\\\
The relation is an Equivalence.
\end{problem}
\newpage

\begin{problem} The relation given by $\{(a, c),(a, f),(a, h),(b, h),(c, f),(c, h),(d, h),(e, h),(f, h),(g, h)\}$
\\\\
\Large
\item \underline{Reflexive}: $\forall x \in S, x S x$\\
False.  There is no $(a, a)$. \\
\item \underline{Symmetric}: $\forall x,y \in S, (x, y) \in S \implies (y, x) \in S$\\
False.  $(a, c) \in S$ but $(c, a) \notin S$\\
\item \underline{Anti-symmetric}: $\forall x,y \in S, (x, y) \in S \implies (y, x) \notin S$ if $a \neq b$\\
True. There is no element which is symmetric.\\
\item \underline{Transitive}: $\forall x,y,z \in S, (x, y) \in S$ and $(y, z) \in S \implies (x, z) \in S$\\
True.  There are three pairs of elements - $(a, c) \& (c, f), (a, c) \& (c, h), (a, f) \& (f, h)$, and the relation contains a corresponding "$(x, z)$" element for each, $(a, f), (a, h) \& (a, h)$
\end{problem}
\newpage

\begin{problem} The relation on the set of ordered pairs of integers, where $((a, b),(c, d))  \in R$ means $ab=cd$
\\\\
\Large
\item \underline{Reflexive}: $\forall x \in S, x S x$\\
True.  $ab = ab$\\
\item \underline{Symmetric}: $\forall x,y \in S, (x, y) \in S \implies (y, x) \in S$\\
True.  For $((a, b), (c, d)) \in R$, $ab = cd$ is the same as $cd = ab$.\\
\item \underline{Anti-symmetric}: $\forall x,y \in S, (x, y) \in S \implies (y, x) \notin S$ if $a \neq b$\\
False.  As an example, $((3, 4), (2, 6))$  is  $3 * 4 = 2 * 6$, and $((2, 6), (3, 4))$ is $2 * 6 = 3 * 4$, which is in $R$.\\
\item \underline{Transitive}: $\forall x,y,z \in S, (x, y) \in S$ and $(y, z) \in S \implies (x, z) \in S$\\
True.  If $((a, b),(c, d))  \in R$ and $((c, d), (e, f))  \in R$, then $ab = cd$ and $cd = ef$, so $ac = ef$.
\end{problem}
\newpage

\begin{problem} The relation $R$ on $\mathbb{N}$ where $(x, y) \in R$ means $x < y+ 2$.
\\\\
\Large
\item \underline{Reflexive}: $\forall x \in S, x S x$\\
True for $(x, x)$ since $ x < x + 2$.\\
\item \underline{Symmetric}: $\forall x,y \in S, (x, y) \in S \implies (y, x) \in S$\\
False for $(x, y)$.  If $x < y + 2$ then it can be shown that $y + 2 \nleq x$.  For example, $(4, 5)$, $ 4 < 5 + 2$, but it is not true that $5 + 2 < 4$.\\  
\item \underline{Anti-symmetric}: $\forall x,y \in S, (x, y) \in S \implies (y, x) \notin S$ if $a \neq b$\\
True for $(x, y)$.  If $x < y + 2$ then it can be shown that $y + 2 \nleq x$.  For example, $(4, 3)$, $ 4 < 3 + 2$, but it is also true that $5 + 2 < 4$.\\
\item \underline{Transitive}: $\forall x,y,z \in S, (x, y) \in S$ and $(y, z) \in S \implies (x, z) \in S$\\
False. Let $x = 2, y = 1$, and $z = 0.$  Then it is the case that $x < y + 2$ and $y < z + 2$, but it not the case that $x < z + 2$.
\end{problem}
\newpage

\begin{problem} The relation $R$ on $\mathbb{N}$ where $(a, b) \in R$ means $a|b$.
\\\\
\Large
\item \underline{Reflexive}: $\forall x \in R, x R x$\\
True, since any number divides itself.\\
\item \underline{Symmetric}: $\forall x,y \in R, (x, y) \in S \implies (y, x) \in R$\\
False.  As a counter-example, $(4, 8) \in R$ means $4|8$ which is true, but $(8, 4) \notin R$, since $8 \not| 4$.\\
\item \underline{Anti-symmetric}: $\forall x,y \in S, (x, y) \in S \implies (y, x) \notin R$ if $a \neq b$\\
True. If $x | y$ and $x \neq y$, then $x < y$, and $y \not| x$.\\
\item \underline{Transitive}: $\forall x,y,z \in S, (x, y) \in R$ and $(y, z) \in R \implies (x, z) \in R$\\
True since any number $x$ that divides a number $y$ also divides a multiple of $y$, that is $z$.
\end{problem}
\newpage

\begin{problem} Consider the relation $\prec$ on $\mathbb{Z}$ defined as:
$$ x \prec y  \Leftrightarrow (|x| < |y|) \vee (|x| = |y| \wedge x < y)$$
Show that $\prec$ is not reflexive, antisymmetric, and transitive.
\\\\
\Large
\item \underline{Reflexive}: $\forall x \in \mathbb{Z}, x \prec x$\\
False since it is not the case that either $(|x| < |x|)$ or $x < x$\\

\item \underline{Anti-symmetric}: $\forall x,y \in \mathbb{Z}, x \prec y \implies y \prec x $ if $x \neq y$\\
True.  For two elements $x, y$, if it is the case that $(|x| < |y|) \vee (|x| = |y| \wedge x < y)$ then $x$ is "closer" to $0$ than $y$.  Since the two cannot be equal it must be the case that $y$ is "farther" from 0 than $x$, in which case $\prec$ is both not symmetric and anti-symmetric.
\\
\item \underline{Transitive}: $\forall x,y,z \in \mathbb{Z}, x \prec y$ and $y \prec z \implies x \prec z$\\
If $x \prec y$ then $x$ is "closer" to $0$ than $y$.  And if $y \prec z$, then $y$ is "closer" to 0 than $z$.  Certainly, if $x$ is "closer" to 0 than $y$, and $y$ is "closer" to 0 than $z$, then surely $x$ is "closer" to 0 than $z$ and the relation is transitive. 
\end{problem}
\newpage

\begin{problem} Consider a symmetric relation $\not\equiv$ that satisfies
$$\forall x,y,z. (x \not\equiv y \implies (x \not\equiv z \vee z \not\equiv y))$$
If $\not\equiv$ is non-reflexive for every $x$, what can you say about the relation $\equiv$? (the complement of $\not\equiv$)
\\\\
\Large
The complement of a relation includes all elements for which the relation does not hold.  We can then say that the complement of $\not\equiv$ is reflexive.
\\\\
We also know that the complement of a symmetric relation is also symmetric.  Additionally, looking at the contrapositive we see that $(x \equiv z \wedge z \equiv y) \implies x \equiv y$, so we have transitivity.
\end{problem}
\newpage

\begin{problem} Consider the relation $\sim$ that satisfies for every $x$ and $y$:
$$(\forall z. (x \sim z \Leftrightarrow y \sim z)) \Leftrightarrow x \sim y$$
Is $\sim$ reflexive?  Symmetric?  Transitive?\\\\
Note: Answering these questions requires a careful understanding of the above logical statement.
\\\\
\Large
\item \underline{Reflexive}: $\forall x \in R, x \sim x$\\
True, since the left-hand side is a tautology.\\
\item \underline{Symmetric}: $\forall x,y \in R, x \sim y \implies y \sim x $ if $x \neq y$\\
True, since the left-hand side is equivalent when the right-hand side is either $x \sim y$ or $y \sim x$\\
\item \underline{Transitive}: $\forall x,y,z \in R, x \sim y$ and $y \sim z \implies x \sim z$\\
True.  Let's rewrite the logical expression as:
$$(\forall \alpha. (x \sim \alpha \Leftrightarrow y \sim \alpha)) \Leftrightarrow x \sim y$$\\
Then we have:
$$(\forall \alpha. (x \sim \alpha \Leftrightarrow y \sim \alpha)) \Leftrightarrow x \sim y$$
$$(\forall \alpha. (y \sim \alpha \Leftrightarrow z \sim \alpha)) \Leftrightarrow y \sim z$$
$$(\forall \alpha. (x \sim \alpha \Leftrightarrow z \sim \alpha)) \Leftrightarrow x \sim z$$
So we're assuming that $x \sim \alpha$, $y \sim \alpha$ and $z \sim \alpha$ which means that $x \sim y$ and $y \sim z$ so $x \sim z$.
\end{problem}
\newpage
\end{document}