Math Problem Statement

Which of these relations on {0*,* 1*,* 2*,* 3} are partial order-

ings? Determine the properties of a partial ordering that

the others lack.

a) {(0*,* 0), (2*,* 2), (3*,* 3)}

b) {(0*,* 0), (1*,* 1), (2*,* 0), (2*,* 2), (2*,* 3), (3*,* 3)}

c) {(0*,* 0), (1*,* 1), (1*,* 2), (2*,* 2), (3*,* 1), (3*,* 3)}

d) {(0*,* 0), (1*,* 1), (1*,* 2), (1*,* 3), (2*,* 0), (2*,* 2), (2*,* 3),

(3*,* 0), (3*,* 3)}

e) {(0*,* 0), (0*,* 1), (0*,* 2), (0*,* 3), (1*,* 0), (1*,* 1), (1*,* 2),

(1*,* 3), (2*,* 0), (2*,* 2), (3*,* 3)}

Solution

To determine whether each relation is a partial ordering, we need to check if the relation is:

  1. Reflexive: Every element is related to itself, i.e., (x,x)(x, x) is in the relation for every xx in the set.
  2. Antisymmetric: If (x,y)(x, y) and (y,x)(y, x) are in the relation, then x=yx = y.
  3. Transitive: If (x,y)(x, y) and (y,z)(y, z) are in the relation, then (x,z)(x, z) must also be in the relation.

The set in question is {0,1,2,3}\{0, 1, 2, 3\}. Let's evaluate each relation.

a) {(0,0),(2,2),(3,3)}\{(0, 0), (2, 2), (3, 3)\}

  • Reflexive: Not reflexive because (1,1)(1, 1) is missing.
  • Antisymmetric: Yes, all pairs are of the form (x,x)(x, x), so antisymmetry holds trivially.
  • Transitive: Yes, since there are no pairs like (x,y)(x, y) and (y,z)(y, z) for xyx \neq y, transitivity holds trivially.

Conclusion: This is not a partial ordering because it is not reflexive.


b) {(0,0),(1,1),(2,0),(2,2),(2,3),(3,3)}\{(0, 0), (1, 1), (2, 0), (2, 2), (2, 3), (3, 3)\}

  • Reflexive: Not reflexive because (3,3)(3, 3) is present but (1,1)(1, 1) is missing.
  • Antisymmetric: Yes, antisymmetry holds trivially_ans_parser

Ask a new question for Free

By Image

Drop file here or Click Here to upload

Math Problem Analysis

Mathematical Concepts

Set Theory
Relations
Partial Orders

Formulas

-

Theorems

Properties of Partial Orders: Reflexive, Antisymmetric, Transitive

Suitable Grade Level

Undergraduate Level (Discrete Mathematics)