discrete-mathematics-assignment-7

• Determine whether the following relation R is reflexive, symmetric, antisymmetric, or transitive if (remember to prove your answer)

  • a);

    The following relation R is reflexive, symmetric, anti-symmetric, and transitive
    R is reflexive: False, since there are no ordered pairs in R.
    R is symmetric: True, vacuously. There are no ordered pairs in R to violate symmetry.
    R is antisymmetric: True, vacuously. There are no ordered pairs in R to violate antisymmetry.
    R is transitive: True, vacuously. There are no ordered pairs in R to violate transitivity.
    is reflexive, symmetric, antisymmetric, and transitive.

  • b) is on $ \mathbb{Z}$;

    The following relation R is symmetric.

    x may not larger than -x
    is not reflexive.
    if larger than then y must larger than -x
    is symmetric.
    is not antisymmetric.
    
    may not larger than
    may not in R
    is not transitive.

  • c) is on ;

    The following relation R is reflexive, symmetric and transitive

    
    then and
    then there must have
    R is reflexive.
    then there must have
    R is Symmetric. R can't be antisymmetric.
    then there must have
    R is transitive.

  • d) is on

    The following relation R is reflexive, symmetric and transitive

    x=w and y=z then
    R is reflexive
    And
    R is symmetric and transitive but not antisymmetric.

  • e)

    The following relation R is reflexive and symmetric

    A is reflexive
    A is symmetric but not antisymmetric.
    $ A\cap B \ne \emptyset$
    $ A\cap C$ may equal to A is not transitive.

• Let be two arbitrary relations on an arbitrary set A. Prove or disprove

  a) if and are reflexive, then is reflexive.
  are reflexive.
  A relation 𝑅 on a set 𝐴 is called reflexive if (𝑎, 𝑎) ∈ 𝑅 for every element 𝑎 ∈ 𝐴.
  contains for every element
  contains for every element
  at least contains for every element
  is reflexive.

  b) if and are symmetric, then is symmetric.
  are symmetric.
  A relation 𝑅 on a set 𝐴 is called symmetric if (𝑏, 𝑎) ∈ 𝑅 whenever (𝑎, 𝑏) ∈ 𝑅.
  Suppose = then there must also has .
  Otherwise, or only has it can't be symmetric respectively.
  is symmetric.

  c) if and are antisymmetric, then is antisymmetric.
  are antisymmetric.
  A relation 𝑅 on a set 𝐴 is called anti-symmetric if whenever (𝑎, 𝑏) ∈ 𝑅 and (𝑏, 𝑎) ∈ 𝑅, then 𝑎 = 𝑏
  Suppose = then there can not has .
  Otherwise, and both have and it can't be antisymmetric respectively.
  is antisymmetric.

d) if and are transitive, then is transitive
are transitive.
A relation 𝑅 on a set 𝐴 is called transitive if whenever (𝑎, 𝑏) ∈ 𝑅 and (𝑏, 𝑐) ∈ 𝑅, then (𝑎, 𝑐) ∈ 𝑅.
:

= Obviously, it can't be transitive.
is not transitive.

• Determine whether the following relations are equivalence relation. You need to prove your answer. If yes, list all distinct equivalent classes (each subset of the partition defined by the equivalence relation).

  • a) on ;

  if (x mod 5=x） R is reflexive
  if (x mod 5=y) y mod 5 may not be x
  is not symmetric is not equivalence relation

  • b){(x,y)| x and y are two UIC students and from the same faculty/school.} on the set of all UIC students;

  For reflexive, the same student must be in the same faculty/school as himself/herself, so R satisfies reflexivity

  For symmetric, if student a and student b are from the same faculty/school, then student b and student a are from the same faculty/school, then (a, b) ∈ R, (b, a) ∈ R, so R satisfies symmetric.

  For transitive, if (a, b) ∈ R, (b, c) ∈ R, then will have (a, c) ∈ R, so R satisfies transitive.

  ∴ this relation is equivalence relation.

  • c){| there is a bijection } on is the powerset of . So, A and B are subsets of .

  For reflexive, let A = B, that will have a bijection : A → B, so R satisfies reflexivity
  For symmetric, if : A → B is a bijection, then : B → A is a bijection, it means that if
  (A, B) ∈ R, that will also have (B, A) ∈ R, so R satisfies symmetric
  For transitive, if : A → B is a bijection, : B → C is a bijection, then it will always have
  ℎ: A → C is a bijection, so R satisfies transitive.
  ∴ this relation is equivalence relation. equivalent classes are all that can have bijection relation to every