Skip to main content
Contents Index
Search Book
Search Results:
No results.
Readability settings Prev Up Next \(\require{cancel}
\newcommand{\nth}[1][n]{{#1}^{\mathrm{th}}}
\newcommand{\bbrac}[1]{\bigl(#1\bigr)}
\newcommand{\Bbrac}[1]{\Bigl(#1\Bigr)}
\newcommand{\correct}{\boldsymbol{\checkmark}}
\newcommand{\incorrect}{\boldsymbol{\times}}
\newcommand{\inv}[2][1]{{#2}^{-{#1}}}
\newcommand{\leftsub}[3][1]{\mathord{{}_{#2\mkern-#1mu}#3}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\sqrtop}{sqrt}
\newcommand{\lgcnot}{\neg}
\newcommand{\lgcand}{\wedge}
\newcommand{\lgcor}{\vee}
\newcommand{\lgccond}{\rightarrow}
\newcommand{\lgcbicond}{\leftrightarrow}
\newcommand{\lgcimplies}{\Rightarrow}
\newcommand{\lgcequiv}{\Leftrightarrow}
\newcommand{\lgctrue}{\mathrm{T}}
\newcommand{\lgcfalse}{\mathrm{F}}
\newcommand{\boolnot}[1]{{#1}'}
\newcommand{\boolzero}{\mathbf{0}}
\newcommand{\boolone}{\mathbf{1}}
\newcommand{\setdef}[2]{\left\{\mathrel{}#1\mathrel{}\middle|\mathrel{}#2\mathrel{}\right\}}
\newcommand{\inlinesetdef}[2]{\{\mathrel{}#1\mathrel{}\mid\mathrel{}#2\mathrel{}\}}
\let\emptyword\emptyset
\renewcommand{\emptyset}{\varnothing}
\newcommand{\relcmplmnt}{\smallsetminus}
\newcommand{\union}{\cup}
\newcommand{\intersection}{\cap}
\newcommand{\cmplmnt}[1]{{#1}^{\mathrm{c}}}
\newcommand{\disjunion}{\sqcup}
\newcommand{\cartprod}{\times}
\newcommand{\words}[1]{{#1}^\ast}
\newcommand{\length}[1]{\abs{#1}}
\newcommand{\powsetbare}{\mathcal{P}}
\newcommand{\powset}[1]{\powsetbare(#1)}
\newcommand{\funcdef}[4][\to]{#2\colon #3 #1 #4}
\newcommand{\ifuncto}{\hookrightarrow}
\newcommand{\ifuncdef}[3]{\funcdef[\ifuncto]{#1}{#2}{#3}}
\newcommand{\sfuncto}{\twoheadrightarrow}
\newcommand{\sfuncdef}[3]{\funcdef[\sfuncto]{#1}{#2}{#3}}
\newcommand{\funcgraphbare}{\Delta}
\newcommand{\funcgraph}[1]{\funcgraphbare(#1)}
\newcommand{\nmathrel}[1]{\mathrel{\not #1}}
\newcommand{\relset}[3]{#1_{{} #2 #3}}
\newcommand{\gtset}[2]{\relset{#1}{\gt}{#2}}
\newcommand{\posset}[1]{\gtset{#1}{0}}
\newcommand{\geset}[2]{\relset{#1}{\ge}{#2}}
\newcommand{\nnegset}[1]{\geset{#1}{0}}
\newcommand{\neqset}[2]{\relset{#1}{\neq}{#2}}
\newcommand{\nzeroset}[1]{\neqset{#1}{0}}
\newcommand{\ltset}[2]{\relset{#1}{\lt}{#2}}
\newcommand{\leset}[2]{\relset{#1}{\le}{#2}}
\newcommand{\natnumlt}[1]{\ltset{\N}{#1}}
\DeclareMathOperator{\id}{id}
\newcommand{\inclfunc}[2]{\iota_{#1}^{#2}}
\newcommand{\projfunc}[1]{\rho_{#1}}
\DeclareMathOperator{\proj}{proj}
\newcommand{\funcres}[2]{\left.{#1}\right\rvert_{#2}}
\newcommand{\altfuncres}[2]{\left.{#1}\right\rvert{#2}}
\DeclareMathOperator{\res}{res}
\DeclareMathOperator{\flr}{flr}
\newcommand{\floor}[1]{\lfloor {#1} \rfloor}
\newcommand{\funccomp}{\circ}
\newcommand{\funcinvimg}[2]{\inv{#1}\left({#2}\right)}
\newcommand{\card}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\cardop}{card}
\DeclareMathOperator{\ncardop}{\#}
\newcommand{\EngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \mathrm{c}, \, \dotsc, \, \mathrm{y}, \, \mathrm{z} \}}
\newcommand{\ShortEngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \dotsc, \, \mathrm{z} \}}
\newcommand{\eqclass}[1]{\left[#1\right]}
\newcommand{\partorder}{\preceq}
\newcommand{\partorderstrict}{\prec}
\newcommand{\npartorder}{\npreceq}
\newcommand{\subgraph}{\preceq}
\newcommand{\subgraphset}[1]{\mathcal{S}(#1)}
\newcommand{\connectedsubgraphset}[1]{\mathcal{C}(#1)}
\newcommand{\permcomb}[3]{{#1}(#2,#3)}
\newcommand{\permcombalt}[3]{{#1}^{#2}_{#3}}
\newcommand{\permcombaltalt}[3]{{\leftsub{#2}{#1}}_{#3}}
\newcommand{\permutation}[2]{\permcomb{P}{#1}{#2}}
\newcommand{\permutationalt}[2]{\permcombalt{P}{#1}{#2}}
\newcommand{\permutationaltalt}[2]{{\permcombaltalt{P}{#1}{#2}}}
\newcommand{\combination}[2]{\permcomb{C}{#1}{#2}}
\newcommand{\combinationalt}[2]{\permcombalt{C}{#1}{#2}}
\newcommand{\combinationaltalt}[2]{{\permcombaltalt{C}{#1}{#2}}}
\newcommand{\choosefuncformula}[3]{\frac{#1 !}{#2 ! \, #3 !}}
\DeclareMathOperator{\matrixring}{M}
\newcommand{\uvec}[1]{\mathbf{#1}}
\newcommand{\zerovec}{\uvec{0}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Exercises 18.7 Exercises
1.
Let
\(\mathord{\equiv} \) represent the relation on
\(\R\times\R \) where
\((x_1,y_1) \equiv (x_2,y_2) \) means
\(y_1 - x_1^2 = y_2 - x_2^2 \text{.}\)
(a) Verify that
\(\mathord{\equiv} \) is an equivalence relation.
(b) Describe the equivalence classes
\([(0,0)] \text{,}\) \([(0,1)] \text{,}\) and
\([(1,0)] \) geometrically as sets of points in the plane.
2.
Given a connected (undirected) graph
\(G \text{,}\) we can define a relation on the set
\(V \) of vertices in
\(G \) as follows: let
\(v_1 R v_2 \) mean that there exists a trail within
\(G \) beginning at vertex
\(v_1 \) and ending at vertex
\(v_2 \) that traverses an even number of edges.
(a) Prove that
\(R \) is an equivalence relation on
\(V \text{.}\)
(b) Determine the equivalence classes for this relation when
\(G \) is the graph below.
Equivalence relations and classes.
In each of
Exercises 3–12 , you are given a set
\(A \) and a relation
\(R \) on
\(A \text{.}\) Determine whether
\(R \) is an equivalence relation, and, if it is, describe its equivalence classes. Try to be more descriptive than just “
\(\eqclass{a} \) is the set of all elements that are equivalent to
\(a \text{.}\) ”
3.
\(A = \{a, b, c\} \text{;}\) \(R = \{(a,a),(b,b),(c,c),(a,b),(b,a)\} \text{.}\)
4.
\(A = \{-1, 0, 1\} \text{;}\) \(R = \{(x,y) | x^2 = y^2\} \text{.}\)
5.
\(A \) is the power set of some set;
\(R \) is the subset relation.
6.
\(A = \R \text{;}\) \(x_1 \mathrel{R} x_2 \) means
\(f(x_1) = f(x_2) \text{,}\) where
\(\funcdef{f}{\R}{\R} \) is the function
\(f(x) = x^2 \text{.}\)
7.
\(A \) is some abstract set;
\(a_1 \mathrel{R} a_2 \) means
\(f(a_1) = f(a_2) \text{,}\) where
\(\funcdef{f}{A}{B} \) is an arbitrary function with domain
\(A \text{.}\)
8.
\(A \) is the set of all “formal” expressions
\(a/b \text{,}\) where
\(a,b \) are integers and
\(b \) is nonzero;
\((a/b) \mathrel{R} (c/d) \) means
\(ad = bc \text{.}\)
Note. Do not think of
\(a / b \) as a fraction in the usual way; instead think of it as a collection of symbols consisting of two integers in a specific order with a forward slash between them.
9.
\(A \) is the power set of some finite set;
\(X \mathrel{R} Y \) means
\(\card{X} = \card{Y} \text{.}\)
10.
\(A \) is the set of all straight lines in the plane;
\(L_1 \mathrel{R} L_2 \) means
\(L_1 \) is parallel to
\(L_2 \text{.}\)
11.
\(A \) is the set of all straight lines in the plane;
\(L_1 \mathrel{R} L_2 \) means
\(L_1 \) is perpendicular to
\(L_2 \text{.}\)
12.
\(A = \R \cartprod \R \text{;}\) \((x_1,y_1) \mathrel{R} (x_2,y_2) \) means
\(x_1^2 + y_1^2 = x_2^2 + y_2^2 \text{.}\)
Hint .
Does the expression
\(x^2 + y^2 \) remind you of anything from geometry?
