Lab: Set Practice

Reading Review

Consider the following relation $R$ over universe $\mathcal{U} = ${$a, b, c, d, e, f $}:

\[R = \{(a, b), (c, e), (d, b), (f, e) \}\]

Compute the equivalence closure of $R$.

Consider the set $\mathcal{U} = ${$ a, b, c, d, e $} and the following relation $R$ over this set:

\[R = \{(a, a), (b, b), (c, c), (d, d), (e, e), \\ (a, b), (a, c), (b, d), (c, d), (d, e), \\ (a, d), (a, e), (b, e), (c, e) \}\]

1. Prove that $R$ is a partial order.
2. Is $R$ a total order? If so, prove it. If not, provide a counterexample demonstrating that some pair of elements in $\mathcal{U}$ is incomparable.

Definitions That may help

• A relation $R$ is reflexive if it relates every element in the universe to itself. \(\forall x \ldotp (x, x) \in R\)
• A relation $R$ is symmetric if any pair of related elements are also related “in the opposite direction.” \(\forall x, y \ldotp (x, y) \in R \rightarrow (y, x) \in R\)
• A relation $R$ is transitive if whenever any pair of elements are related with a common element in the middle, the first and last elements are also related. \(\forall x, y, z \ldotp (x, y) \in R \rightarrow (y, z) \in R \rightarrow (x, z) \in R\)
• A relation an equivalence if it is reflexive, symmetric, and transitive.
• An equivalence class of an equivalence relation $R$ over universe $U$ is a set $S$ of elements drawn from $U$ that are pairwise equivalent according to $R$, i.e., \(\forall x, y \in S \ldotp (x, y) \in R.\)

Lab

Reminder of the Core outcomes from this section on sets:

• Author a rigorous proof of the equality of two sets.
  • Just using the definitions of various set operators
• Author a rigorous proof utilizing classical reasoning (“proof by contradiction”).
• Model real-world phenomena using the fundamental definitions of relations.

Problem 1:

Let S be the set of Positive Integers and T be the set of Positive Even Integers.

• Is $S\subseteq T$?
• Is $T\subseteq S$?
• Is There a Relation $R: S\rightarrow T$ such that R is:
  • (optional) Injective but Not Surjective
  • (optional) Surjective but Not Injective
  • Bijective
  • For any relations R that you find, give the domain and range as well.

Problem 2:

Let S be the set of triples (a,b,c) such that: a, b, c $\in\mathbb{N}$ and $a^2+b^2=c^2$:

• (optional) Which of a, b, c can be even (prove with examples, think triangles)
• Which of a, b, c must be even (prove)

Problem 3:

Prove that for sets S, T, U $(S\cap T)\cap U=S\cap(T\cap U)$

Problem 4:

Prove that for sets S, T, U $S\cap(T\cup U)=(S\cap T)\cup(S\cap U)$ (opposite of Demo 4)

Problem 5:

Given a set of professors, a set of students, and a set of classes

• Define a relation $R_1$ to be the relationship between Professors and the classes they teach
  • What is the range of $R_1$
  • What is the domain of $R_1$
  • Using Set notation, give a formal definition of $R_1$
  • Using Set notation, give a formal definition of $R_1^{-1}$
• Define a relation $R_2$ to be the relationship between students and the classes they are taking
  • Using Set notation, give a formal definition of $R_2$
  • Using Set notation, give a formal definition of $R_2^{-1}$
• For the composition $C=R_1\circ R_2^{-1}$
  • In plain English, describe the relationship C
  • Using Set notation: give a formal definition of C
  • What is the range of C
  • What is the domain of C
• (optional) For each of $R_1$, $R_2$, $C$
  • Is the relation reflexive?
  • Is the relation symmetric?
  • Is the relation transitive?
  • Is the relation anti-symmetric?

Optional Problems

Problem 1 (optional):

Given Integers a and b, is $b^2=4a$

• Always possible (prove it)
• Sometimes possible (give an example, state if there is more than 1)
• Never possible (prove it)

Problem 2 (optional):

Given Integers a and b, is $b^2=a+2$

• Always possible (prove it)
• Sometimes possible (give an example, state if there is more than 1)
• Never possible (prove it)

Problem 3 (optional):

Given Integers a and b, is $b^2=4a+2$ Taken From

• Always possible (prove it)
• Sometimes possible (give an example, state if there is more than 1)
• Never possible (prove it)