Scribd
Upload
25 views14 pages

Partial Orderings and Relations Analysis

The document analyzes various relations on the set {0, 1, 2, 3} to determine which are partial orderings based on reflexivity, antisymmetry, and transitivity. It concludes that relations a) and c) are partial orderings, while relations b), d), and e) fail due to violations of antisymmetry or transitivity. Additionally, it poses questions about the properties of other relations and equivalence relations derived from specific partitions.

Uploaded by

Tester Mail
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
25 views14 pages

Partial Orderings and Relations Analysis

The document analyzes various relations on the set {0, 1, 2, 3} to determine which are partial orderings based on reflexivity, antisymmetry, and transitivity. It concludes that relations a) and c) are partial orderings, while relations b), d), and e) fail due to violations of antisymmetry or transitivity. Additionally, it poses questions about the properties of other relations and equivalence relations derived from specific partitions.

Uploaded by

Tester Mail
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Answer Key:

​
​
Which of these relations on {0, 1, 2, 3} are partial orderings? Determine the properties of a
partial ordering that the others lack.
a) {(0, 0), (1, 1), (2, 2), (3, 3)}
b) {(0, 0), (1, 1), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)}
c) {(0, 0), (1, 1), (1, 2), (2, 2), (3, 3)}
d) {(0, 0), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}
e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 2), (3, 3)}

A partial order on a set is a binary relation that satisfies three properties:

1.​ Reflexivity: For all xxx in the set, (x,x)(x, x)(x,x) must be in the relation.
2.​ Antisymmetry: If (x,y)(x, y)(x,y) and (y,x)(y, x)(y,x) are both in the relation, then x=yx
= yx=y.
3.​ Transitivity: If (x,y)(x, y)(x,y) and (y,z)(y, z)(y,z) are in the relation, then (x,z)(x, z)(x,z)
must also be in the relation.

Now, let's analyze each of the relations you provided and determine which ones are partial
orderings and which properties they may be lacking.

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

●​ Reflexivity: Yes, all elements 0,1,2,30, 1, 2, 30,1,2,3 have their reflexive pairs.
●​ Antisymmetry: Yes, no pairs (x,y)(x, y)(x,y) and (y,x)(y, x)(y,x) exist where x≠yx \neq
yx=y.
●​ Transitivity: Yes, since the only pairs are reflexive, no other pairs break the transitivity
rule.

Conclusion: This is a partial ordering.

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

●​ Reflexivity: Yes, all elements 0,1,2,30, 1, 2, 30,1,2,3 have their reflexive pairs.
●​ Antisymmetry: No. Both (2,3)(2, 3)(2,3) and (3,2)(3, 2)(3,2) are in the relation, but 2≠32
\neq 32=3. This violates antisymmetry.
●​ Transitivity: This condition is harder to check directly, but we can conclude that
antisymmetry is violated, so transitivity is not the primary issue here.

Conclusion: This is not a partial ordering due to the failure of antisymmetry.

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

●​ Reflexivity: Yes, all elements 0,1,2,30, 1, 2, 30,1,2,3 have their reflexive pairs.
●​ Antisymmetry: Yes, there are no pairs (x,y)(x, y)(x,y) and (y,x)(y, x)(y,x) with x≠yx \neq
yx=y.
●​ Transitivity: Yes. If (1,2)(1, 2)(1,2) and (2,2)(2, 2)(2,2) are in the relation, (1,2)(1,
2)(1,2) should be in the relation, which it is.

Conclusion: This is a partial ordering.

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

●​ Reflexivity: Yes, all elements 0,1,2,30, 1, 2, 30,1,2,3 have their reflexive pairs.
●​ Antisymmetry: Yes, there are no pairs (x,y)(x, y)(x,y) and (y,x)(y, x)(y,x) with x≠yx \neq
yx=y.
●​ Transitivity: No. For example, (1,2)(1, 2)(1,2) and (2,3)(2, 3)(2,3) are in the relation, but
(1,3)(1, 3)(1,3) is not. Hence, transitivity is violated.

Conclusion: This is not a partial ordering due to the failure of transitivity.

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

●​ Reflexivity: Yes, all elements 0,1,2,30, 1, 2, 30,1,2,3 have their reflexive pairs.
●​ Antisymmetry: No. Both (0,1)(0, 1)(0,1) and (1,0)(1, 0)(1,0) are in the relation, but 0≠10
\neq 10=1, which violates antisymmetry.
●​ Transitivity: Since antisymmetry is violated, checking transitivity is unnecessary for this
relation.

Conclusion: This is not a partial ordering due to the failure of antisymmetry.

Summary of Results:

●​ Partial Orderings:
o​ a) {(0, 0), (1, 1), (2, 2), (3, 3)}
o​ c) {(0, 0), (1, 1), (1, 2), (2, 2), (3, 3)}
●​ Not Partial Orderings (due to failure of specific properties):
o​ b) {(0, 0), (1, 1), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3)} (fails antisymmetry)
o​ d) {(0, 0), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)} (fails transitivity)
o​ e) {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 2), (3, 3)} (fails
antisymmetry)
A) Determine whether the relation R on the set of all people is reflexive, symmetric, antisymmetric,
and/or transitive, where (a, b) ∈ R if and only if
​ a) a is taller than b.
​ b) a and b were born on the same day.
​ c) a has the same first name as b.
​ d) a and b have a common grandparent
Let f (x) = ⌊x2∕3⌋. Find f (S) if
a) S = {−2, −1, 0, 1, 2, 3}.
b) S = {0, 1, 2, 3, 4, 5}.
c) S = {1, 5, 7, 11}.
d) S = {2, 6, 10, 14}
Find the relations S2i for i = 1, 2, 3, 4, 5, 6 where
​ S1 = {(a, b) ∈ Z2 ∣ a > b}, the greater than relation,
​ S2 = {(a, b) ∈ Z2 ∣ a ≥ b}, the greater than or equal to relation,
​ S3 = {(a, b) ∈ Z2 ∣ a < b}, the less than relation,
​ S4 = {(a, b) ∈ Z2 ∣ a ≤ b}, the less than or equal to relation,
​ S5 = {(a, b) ∈ Z2 ∣ a = b}, the equal to relation,
​ S6 = {(a, b) ∈ Z2 ∣ a ≠ b}, the unequal to relation.
Let R be the relation consisting of all pairs (x, y) such that x and y are strings of uppercase and
lowercase English letters with the property that for every positive integer n, the nth characters in
x and y are the same letter, either uppercase or lowercase. Show that R is an equivalence relation.
List the ordered pairs in the equivalence relations produced by these partitions of {a, b, c, d, e, f,
g}.
​ a) {a, b}, {c, d}, {e, f, g}
​ b) {a}, {b}, {c, d}, {e, f }, {g}
​ c) {a, b, c, d}, {e, f, g}
​ d) {a, c, e, g}, {b, d}, {f }
List the ordered pairs in the equivalence relations produced by these partitions of {0, 1, 2, 3, 4,
5}.
​ a) {0}, {1, 2}, {3, 4, 5}
​ b) {0, 1}, {2, 3}, {4, 5}
​ c) {0, 1, 2}, {3, 4, 5}
​ d) {0}, {1}, {2}, {3}, {4}, {5}

Common questions

Powered by AI

The order of characters in strings is crucial because the equivalence relation that evaluates strings character by character is dependent on their position. Two strings are equivalent if they have identical characters at corresponding positions for every letter, fulfilling reflexivity, symmetry, and transitivity. This type of relation allows complex string operations like comparative analysis or grouping similar patterns while maintaining strict positional integrity .

To verify if a relation fails to be a partial ordering due to antisymmetry, check if there exist elements x and y such that the pairs (x, y) and (y, x) are in the relation, while x ≠ y. If such pairs are found, antisymmetry is violated. For transitivity, ensure that whenever (x, y) and (y, z) are in the relation, (x, z) is also present. If any such condition fails, transitivity is violated. In the document, relation (b) fails antisymmetry because it includes (2, 3) and (3, 2) where 2 ≠ 3, and relation (d) fails transitivity as it has (1, 2) and (2, 3) but not (1, 3).

The 'equal to' relation is reflexive because every element is equal to itself, symmetric as if a = b then b = a, and transitive because if a = b and b = c, then a = c. 'Unequal to,' however, is not reflexive since no element is non-equal to itself, it is symmetric as if a ≠ b then b ≠ a, but not transitive because a ≠ b and b ≠ c does not imply a ≠ c. Applications hinge on needing different operations: equality checks ensure identity and similar groups, while inequality can handle distinctions and exceptions in sets .

The relation R on strings based on identical characters at corresponding positions across strings is an equivalence relation due to satisfying reflexivity, symmetry, and transitivity. Reflexivity is met because any string has itself as an identical string pair. Symmetry holds as if string x is equivalent to y, then y is comprised of the same characters as x at each position. Transitivity is satisfied since if x relates to y and y to z, x and z must share identical characters at matching positions. Therefore, R forms valid equivalence classes .

A binary relation is considered a partial ordering if it satisfies three properties: reflexivity, antisymmetry, and transitivity. A relation is reflexive if every element is related to itself. Antisymmetry requires that if an element x is related to y and y is related to x, then x must equal y. Transitivity means that if x is related to y and y is related to z, then x must be related to z. In the provided document, relations (a) {(0, 0), (1, 1), (2, 2), (3, 3)} and (c) {(0, 0), (1, 1), (1, 2), (2, 2), (3, 3)} fulfill these conditions and are partial orderings .

Partitions of a set create equivalence relations by grouping elements into subsets where each element relates to others within the same subset. For instance, partitioning {a, b, c, d, e, f, g} into subsets like {a, b}, {c, d}, {e, f, g} results in equivalence relations that contain ordered pairs (a, a), (b, b), (c, c), (d, d), (e, e), (f, f), (g, g), and pairs within each subset like (a, b), (b, a), etc. These relations demonstrate reflexivity within subsets and symmetry between each member of respective subsets .

The function f(x) = ⌊x^2/3⌋ represents the floor of x squared divided by 3, outputting the greatest integer less than or equal to the expression. When applied to S = {-2, -1, 0, 1, 2, 3}, it evaluates to {0, 0, 0, 0, 1, 3} respectively due to each term being floored after division. This approach can be generalized to other sets by computing the expression for each element and flooring the result .

Partial orders and equivalence relations share reflexivity and transitivity properties, but they fundamentally differ with antisymmetry and symmetry. In partial orders, antisymmetry is required, which means for any two elements x and y, if x is related to y and y is related to x, then x must equal y. In contrast, equivalence relations require symmetry, which allows both x related to y and y related to x without requiring x and y to be the same. This differentiation ensures that equivalence classes contain elements indistinguishably related in all aspects covered by the relation type, while partial orders establish a hierarchy with distinct, non-equal relationships .

The relation where two people have a common grandparent is reflexive, as every person shares a grandparent with themselves. It is symmetric because if a shares a grandparent with b, then b shares that grandparent with a. Notwithstanding, the relationship is not antisymmetric, as a shared grandparent does not imply identity. However, it is not transitive in many instances because sharing grandparents with different pairs doesn't guarantee that all share the same grandparent across pairs .

The relation 'a is taller than b' cannot be reflexive because no person can be taller than themselves, violating reflexivity. It is not symmetric because if a is taller than b, b cannot be taller than a, thereby failing symmetry. However, it is antisymmetric because if a is taller than b, both (a, b) and (b, a) cannot happen unless a = b, which does not occur. For transitivity, if a is taller than b and b is taller than c, then a is taller than c, satisfying transitivity .

You might also like