Showing a relation is a partial order on a set

In summary, the problem asks for the definition of a relation on a universal set U, where X and Y are subsets of U. The relation is defined as X is less than or equal to Y if X is a subset of Y. The task is to show that this relation is a partial order on U. The solution involves proving that the relation is reflexive, antisymmetric, and transitive. The reflexive property is proved by showing that for any element a in X, (a,a) is in the relation. The solution also involves discussing the potential difficulty of defining this relation on the set of all sets.
  • #1
ironspud
10
0

Homework Statement



Okay, so here's the problem:

(a) Let [itex]U[/itex] be a universal set and suppose that [itex]X,Y\in U[/itex]. Define a relation,[itex]\leq[/itex], on [itex]U[/itex] by [itex]X\leq Y[/itex] iff [itex]X\subseteq Y[/itex]. Show that this relation is a partial order on [itex]U[/itex].

(b) What problem occurs if we try to define this as a relation on the set of all sets?


Homework Equations



A relation [itex]R[/itex] is a partial ordering if [itex]R[/itex] is a reflexive, antisymmetric, and transitive relation.

A relation [itex]R[/itex] on a set A is reflexive if, for all [itex]x\in A[/itex], [itex]x R x[/itex].

A relation [itex]R[/itex] on a set A is antisymmetric if, for all [itex]x,y\in A[/itex], [itex]x R y\wedge y R x\Rightarrow x=y[/itex].

A relation [itex]R[/itex] on a set A is transitive if, for all [itex]x,y,z\in A[/itex], [itex]x R y\wedge y R z\Rightarrow x R z[/itex].


The Attempt at a Solution



I'm really lost here. On part (a), I thought I was doing fine at first, but the more I think about it, the more I feel I'm way off base. Here's what I mean:

Proof that [itex]R[/itex] is reflexive:
Let [itex]a\in X[/itex].
Since [itex]a\in X[/itex], then [itex]a\in X[/itex].
Thus, [itex]X\subseteq X[/itex].
Therefore, [itex](a,a)\in R[/itex].

I think this would make sense if I was trying to prove the relation was a subset of [itex]X\times X[/itex] (right?), but I'm trying to show the relation on [itex]U[/itex] with [itex]X,Y\in U[/itex]. With that, I think, being the case, I really have no idea how to proceed.

Anyway, clearly I'm over my head here. If anyone could help me out, I'd really appreciate it.

Thanks!
 
Physics news on Phys.org
  • #2
Nevermind. I just spoke with my professor. Seems I was just over thinking everything.

Still, if anyone would like to provide some insight to part (b), I'd appreciate it.
 

1. What is a partial order?

A partial order is a mathematical concept that defines a relationship between elements of a set. It is a binary relation that must satisfy three properties: reflexivity, antisymmetry, and transitivity. In simpler terms, it is a way of organizing elements in a set based on their relationship to each other.

2. How do you show that a relation is a partial order?

To show that a relation is a partial order, you must prove that it satisfies the three properties of a partial order: reflexivity, antisymmetry, and transitivity. This can be done through mathematical proofs or by demonstrating specific examples that illustrate the properties.

3. What is the difference between a partial order and a total order?

The main difference between a partial order and a total order is that a total order must satisfy an additional property called comparability. This means that for any two elements in the set, they can be compared to determine which is greater than or less than the other. In a partial order, there may be elements that cannot be compared.

4. Can a relation be both a partial order and an equivalence relation?

No, a relation cannot be both a partial order and an equivalence relation. An equivalence relation must satisfy the properties of reflexivity, symmetry, and transitivity, while a partial order must satisfy reflexivity, antisymmetry, and transitivity. These properties are not compatible with each other.

5. How is partial order related to the concept of a lattice?

A lattice is a partially ordered set in which every pair of elements has both a greatest lower bound and a least upper bound. This means that a lattice must satisfy the properties of a partial order, as well as the additional property of having a greatest lower bound and a least upper bound. In other words, a lattice is a specific type of partial order.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
521
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
693
  • Calculus and Beyond Homework Help
Replies
13
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
813
Replies
1
Views
629
  • Calculus and Beyond Homework Help
Replies
24
Views
2K
Back
Top