\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{ytableau}
\usepackage{skak}
\usepackage{rotating}
\usepackage[framemethod=tikz]{mdframed}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Friday, October 08, 2021 14:18:03}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\ihead{Math 220-002 Fall 2021 (Darij Grinberg): homework set 1}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 220-002 Fall 2021 (Darij Grinberg): homework set 1}

due date: Friday 2021-10-08 at noon on gradescope (
\url{https://www.gradescope.com/courses/313263} ).

Please solve only \textbf{4 of the 6 exercises}.
\end{center}

\begin{exercise}
Define the logical connective $\operatorname*{UNLESS}$ as follows: For any two
propositions $P$ and $Q$, we define \textquotedblleft%
$P\ \operatorname*{UNLESS}\ Q$\textquotedblright\ to mean $\left(
\operatorname*{NOT}\ Q\right)  \Longrightarrow P$. (This is more or less the
common-sense understanding of \textquotedblleft unless\textquotedblright.)

Prove (by comparing truth tables) that $P\ \operatorname*{UNLESS}\ Q$ is
actually equivalent to $P\ \operatorname*{OR}\ Q$.
\end{exercise}

\begin{exercise}
\label{exe.hw1.2}Let $P$, $Q$ and $R$ be three propositions. Prove the
following equivalences by comparing truth tables: \medskip

\textbf{(a)} \ \ \ \ $\left(  P\ \operatorname*{OR}\ \left(
Q\ \operatorname*{AND}\ R\right)  \right)  \ \Longleftrightarrow\ \left(
\left(  P\ \operatorname*{OR}\ Q\right)  \ \operatorname*{AND}\ \left(
P\ \operatorname*{OR}\ R\right)  \right)  $. \medskip

\textbf{(b)} \ \ \ \ $\left(  P\ \operatorname*{AND}\ \left(
Q\ \operatorname*{OR}\ R\right)  \right)  \ \Longleftrightarrow\ \left(
\left(  P\ \operatorname*{AND}\ Q\right)  \ \operatorname*{OR}\ \left(
P\ \operatorname*{AND}\ R\right)  \right)  $. \medskip

\textbf{(c)} \ \ \ \ $\left(  P\ \operatorname*{XOR}\ \left(
Q\ \operatorname*{XOR}\ R\right)  \right)  \ \Longleftrightarrow\ \left(
\left(  P\ \operatorname*{XOR}\ Q\right)  \ \operatorname*{XOR}\ R\right)  $.
\medskip

\textbf{(d)}\ \ \ \ $\left(  \left(  P\ \operatorname*{OR}\ Q\right)
\Longrightarrow R\right)  \ \Longleftrightarrow\ \left(  \left(
P\Longrightarrow R\right)  \ \operatorname*{AND}\ \left(  Q\Longrightarrow
R\right)  \right)  $. \medskip

[\textbf{Hint:} You can save yourself some writing by making a common truth
table with 8 rows and 11 columns for all 4 parts of the exercise.]
\end{exercise}

\begin{exercise}
Which of the following statements are true? \medskip

\textbf{(a)}\ \ \ \ $\forall x\in\mathbb{Z}:\ \left(  2x\in\mathbb{Z}\right)
$. \medskip

\textbf{(b)}\ \ \ \ $\forall x\in\mathbb{Z}:\ \left(  \dfrac{x}{2}%
\in\mathbb{Z}\right)  $. \medskip

\textbf{(c)}\ \ \ \ $\forall x\in\mathbb{Z}:\ \left(  x^{3}\geq0\right)  $.
\medskip

\textbf{(d)}\ \ \ \ $\forall x\in\mathbb{Z}:\ \left(  x^{4}\geq0\right)  $.
\medskip

\textbf{(e)}\ \ \ \ $\forall x\in\mathbb{Z}:\ \left(  \left(  x\leq3\right)
\ \operatorname*{OR}\ \left(  x\geq4\right)  \right)  $. \medskip

\textbf{(f)}\ \ \ \ $\forall x\in\mathbb{Q}:\ \left(  \left(  x\leq3\right)
\ \operatorname*{OR}\ \left(  x\geq4\right)  \right)  $. \medskip

\textbf{(g)}\ \ \ \ $\forall x\in\mathbb{Q}:\ \left(  \exists y\in
\mathbb{Z}:\ y>x\right)  $. \medskip

\textbf{(h)}\ \ \ \ $\forall x\in\mathbb{N}:\ \left(  \exists y\in
\mathbb{N}:\ \left(  y>x\ \operatorname*{AND}\ y\text{ is prime}\right)
\right)  $. \medskip

In the cases of \textbf{(g)} and \textbf{(h)}, give a counterexample or a
short intuitive justification (not a rigorous proof) in a sentence or two.
\end{exercise}

\begin{exercise}
\textbf{(a)} Find (and describe) a set $S$ satisfying $\mathbb{Z}\subseteq
S\subseteq\mathbb{Q}$ and $S\neq\mathbb{Z}$ and $S\neq\mathbb{Q}$. \medskip

\textbf{(b)} Let $S=\left\{  \ldots,-4,-2,0,2,4,\ldots\right\}  $ be the set
of all even integers, and let $T=\left\{  \ldots,-6,-3,0,3,6,\ldots\right\}  $
be the set of all integers that are multiples of $3$. Let $R$ denote the set
$\left\{  s+t\ \mid\ s\in S\text{ and }t\in T\right\}  $; this means the set
of all sums of an element of $S$ with an element of $T$. This set $R$ is a
subset of $\mathbb{Z}$. Is $R$ the whole set $\mathbb{Z}$ or a proper subset
of $\mathbb{Z}$ ? (Justify your answer in a few sentences.)
\end{exercise}

\begin{exercise}
Let $A$, $B$ and $C$ be three sets. Prove the following equalities: \medskip

\textbf{(a)} \ \ \ $A\cup\left(  B\cap C\right)  =\left(  A\cup B\right)
\cap\left(  A\cup C\right)  $. \medskip

\textbf{(b)}\ \ \ \ $A\cap\left(  B\cup C\right)  =\left(  A\cap B\right)
\cup\left(  A\cap C\right)  $. \medskip

\textbf{(c)}\ \ \ \ $A\bigtriangleup\left(  B\bigtriangleup C\right)  =\left(
A\bigtriangleup B\right)  \bigtriangleup C$. \medskip

[\textbf{Hint:} You can use the results of previous exercises.]
\end{exercise}

\begin{exercise}
Let $S$ be a set, and let $P\left(  x\right)  $ and $Q\left(  x\right)  $ be
two statements for each $x\in S$. \medskip

\textbf{(a)} Is it necessarily true that $\left(  \exists x\in S:\ \left(
P\left(  x\right)  \ \operatorname*{OR}\ Q\left(  x\right)  \right)  \right)
$ is equivalent to $\left(  \exists x\in S:\ P\left(  x\right)  \right)
\ \operatorname*{OR}\ \left(  \exists x\in S:\ Q\left(  x\right)  \right)  $ ?
\medskip

\textbf{(b)} Is it necessarily true that $\left(  \exists x\in S:\ \left(
P\left(  x\right)  \ \operatorname*{AND}\ Q\left(  x\right)  \right)  \right)
$ is equivalent to $\left(  \exists x\in S:\ P\left(  x\right)  \right)
\ \operatorname*{AND}\ \left(  \exists x\in S:\ Q\left(  x\right)  \right)  $
? \medskip

\textbf{(c)} Is it necessarily true that $\left(  \exists x\in S:\ \left(
P\left(  x\right)  \Longrightarrow Q\left(  x\right)  \right)  \right)  $ is
equivalent to $\left(  \exists x\in S:\ P\left(  x\right)  \right)
\Longrightarrow\left(  \exists x\in S:\ Q\left(  x\right)  \right)  $ ?
\medskip

\textbf{(d)} Is it necessarily true that $\left(  \forall x\in S:\ \left(
P\left(  x\right)  \ \operatorname*{OR}\ Q\left(  x\right)  \right)  \right)
$ is equivalent to $\left(  \forall x\in S:\ P\left(  x\right)  \right)
\ \operatorname*{OR}\ \left(  \forall x\in S:\ Q\left(  x\right)  \right)  $ ?
\medskip

\textbf{(e)} Is it necessarily true that $\left(  \forall x\in S:\ \left(
P\left(  x\right)  \ \operatorname*{AND}\ Q\left(  x\right)  \right)  \right)
$ is equivalent to $\left(  \forall x\in S:\ P\left(  x\right)  \right)
\ \operatorname*{AND}\ \left(  \forall x\in S:\ Q\left(  x\right)  \right)  $
? \medskip

\textbf{(f)} Is it necessarily true that $\left(  \forall x\in S:\ \left(
P\left(  x\right)  \Longrightarrow Q\left(  x\right)  \right)  \right)  $ is
equivalent to $\left(  \forall x\in S:\ P\left(  x\right)  \right)
\Longrightarrow\left(  \forall x\in S:\ Q\left(  x\right)  \right)  $ ?
\medskip

(By \textquotedblleft necessarily true\textquotedblright, we mean
\textquotedblleft true no matter what $S$, $P\left(  x\right)  $ and $Q\left(
x\right)  $ are\textquotedblright. Almost everything becomes true in a
sufficiently trivial example; we are wondering whether things are true in
general. In each case, \textbf{give reasons or counterexamples}.)
\end{exercise}


\end{document}