0

I'm having some trouble answering a question and any help would be appreciated. The question is:

"Let $\mathbb Z$ be the set of integers and consider the set $X = \mathbb Z\times \mathbb Z$. Consider the relation $R$ on $X$ defined by $(x,y)R(z,w)$ if:

  1. $x < z$ or
  2. $x = z$ and $y \leq w$

Show that $R$ is a partial order on $X$."

The whole set of integers is really throwing me off, how would you go about tackling this question?

drhab
  • 151,093
Cormac
  • 3

3 Answers3

1

To show that R is a partial order you need to show reflexivity, antisymmetry, and transitivity.

$\mathbf{Reflexivity}$: Given any $(x,y) \in \mathbb{Z} \times \mathbb{Z}$, is $(x,y)R(x,y)$? Certainly yes, since condition 2 of the relation is satisfied.

$\mathbf{Antisymmetry}$: Suppose $(x,y)R(z,w)$ and $(z,w)R(x,y)$. We must show that in fact $(x,y) = (z,w)$.

Now, look at $(x,y)R(z,w)$. This means one of the 2 conditions is satisfied. It cannot be the first, that $x<z$, since then $(z,w)R(x,y)$ could not be true.

Thus we must have condition 2 satisfied: $x=z$ and $y\leq w$.

Now looking at $(z,w)R(x,y)$, we know this cannot satisfy condition 1 ($x< z$) since $x=z$, thus it satisfies condition 2: $w\leq y$. Therefore we have $y \leq w$ and $w \leq y$, therefore $w = y$. And since $x=z$, the two pairs are equal.

$\mathbf{Transitivity}$: Suppose $(x,y)R(z,w)$ and $(z,w)R(a,b)$. We want to show that $(x,y)R(a,b)$.

You're going to have to break this into cases based on which of the 2 conditions are satisfied in each case, but it should be pretty straightforward.

pwerth
  • 3,880
0

1) Show that $(x,y)R(x,y)$ is true for each $(x,y)\in X$ (reflexive)

2) Show that $(x,y)R(z,w)\wedge(z,w)R(p,q)$ implies that $(x,y)R(p,q)$ (transitive)

3) Show that $(x,y)R(z,w)\wedge(z,w)R(x,y)$ implies that $(x,y)=(z,w)$ (antisymmetric)

These conditions are enough (and necessary) for $R$ to be a partial order.

drhab
  • 151,093
0

You need $3$ things to be a partial order relation. That is:

  1. Antisymmetric property:
    $(x,y)R(w,z)\text{ and }(w,z)R(x,y)\implies (w,z)=(x,y)$
  2. Reflexive property:
    $(x,y)R(x,y)$ for all $(x,y)$
  3. Transitive property:
    $(x,y)R(w,z)\text{ and }(w,z)R(s, t)\implies (x,y)R(s,t)$

Antisymmetric Property

To show this, we pick two points in $\mathbb{Z}^2$. We call these points $(a, b)$ and $(c, d)$. If those two points have (what I'll call) a two-way relationship, then we have two options: $a<b$ and $b<a$ (impossible), or $a=b$ and ($c\le d$ and $d\le c$). Clearly, the only possible result is that $a=b$ and $c=d$.

See if that helps you do the other two options. (Pick arbitrary points, and show that they satisfy the requirements.) Comment if you need further assistance.

apnorton
  • 17,706