edited by
989 views
7 votes
7 votes

Consider a binary function $g :P \times P \to \left \{ true,false \right \}$, where $P$ is a non-empty subset of the natural numbers that contains an even number of distinct elements.

Which of the following statements can be true about $g$ ?

  1.     $g$ is symmetric and antisymmetric
  2.     $g$ defines a total order and an equivalence relation with at least two equivalence classes
  3.     $g$ defines a total order but not a partial order
  4.     $g$ is reflexive and antisymmetric but not a surjection
edited by

1 Answer

Best answer
6 votes
6 votes
  • Option A : g is symmetric and antisymmetric

 A is  possible. For example, let P = {1, 2}, g(1, 1) = g(2, 2) = true, and g(1, 2) = g(2, 1) = false.

Note that for any x and y, if g(x, y) = true, then g(y, x) = true, thus meeting the definition of symmetric.

Note also that for any x and y, if g(x, y) = g(y, x) = true, then x = y, thus meeting the definition of antisymmetric.

  • Option B : g defines a total order and an equivalence relation with at least two equivalence classes 

It is not possible. To prove this by contradiction, select an x and y from different equivalence classes. Since g is a total order, either g(x, y) = true or g(y, x) = true. Since g is an equivalence relation, which is symmetric, it follows that both g(x, y) = true and g(y, x) = true.

Since g is a total order, which is antisymmetric, it follows that x = y. But then x and y would be in the same equivalence class, violating the initial selection criteria.

  • Option C : g defines a total order but not a partial order

It is also not possible, since a total order must be a partial order (meaning reflexive, antisymmetric, and transitive), and also total (either g(x, y) or g(y, x) must be true for all x and y).

  • Option D : g is reflexive and antisymmetric but not a surjection

It is not possible, since set P contains at least two elements.

Because : 
Reflexivity implies that for all x, g(x, x) = true. Antisymmetry implies that for any x and y such that x 6= y, g(x, y) = false or g(y, x) = false. Hence, both true and false are in the range of g, which implies that g must be a surjection, meaning that for any value z in the co-domain {true, false}, there exists some (x, y) in the domain P * P such that g(x, y) = z.

Thats why option A is True only ..

selected by
Answer:

Related questions

4 votes
4 votes
2 answers
2