Prove that the binary relation "is a subset of" is a partial order (POSET)?
Should I try to prove this in reference to the power set of a general set?
When is this relation a total order?
[Math] Prove that the binary relation “is a subset of” is a…
order-theoryrelations
Related Solutions
Orders are a special kind of binary relation.
A binary relation $R$ on a set $A$ is just a collection of ordered pairs $R\subseteq A\times A$, with absolutely no conditions on $R$. So long as it is a subset, it is a binary relation.
A (partial) order on $A$, by contrast, is a subset $P\subseteq A\times A$ which satisfies three conditions:
- The relation is reflexive: For every $a\in A$, $(a,a)\in P$.
- The relation is anti-symmetric: for every $a,b\in A$, if $(a,b)\in P$ and $(b,a)\in P$, then $a=b$.
- The relation is transitive: for every $a,b,c\in A$, if $(a,b)\in P$ and $(b,c)\in P$, then $(a,c)\in P$.
The partial order is a total or linear order if, in addition, for every $a,b\in A$, either $(a,b)\in P$ or $(b,a)\in P$.
So an order on $A$ is a special kind of binary relation, because it must satisfy the three properties above, whereas a "general binary relation" doesn't have to satisfy anything other than being a collection of ordered pairs of elements of the set.
Okay, addressing your additions.
The most basic notion is "partial order". Every other kind of order is a "partial order with extra conditions".
The one exception is a pre-order, because, as the name indicates, a pre-order is something which is not yet an order (again, "order" is just a short way of saying "partial order"), but may become one (when it grows up, so to speak).
Pre-orders
A pre-order is a binary relation which is reflexive and transitive, but is not necessarily anti-symmetric. An example of this is the relation "divides" in the integers: define $a\preceq b$, with $a$ and $b$ integers, if and only if $a$ divides $b$. This is reflexive (every integer divides itself), and transitive (if $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$), but it is not anti-symmetric, because if $a$ divides $b$ and $b$ divides $a$, the best you can conclude is that $|a|=|b|$; for instance, $2$ and $-2$ are different, but $2\preceq -2$ and $-2\preceq 2$. So this relation is not a partial order because it lacks anti-symmetry.
One way to solve this lack is to use the relation to define something which is a partial order on a closely related set. We define an equivalence relation on the integers by saying $a\sim b$ if and only if $a\preceq b$ and $b\preceq a$ (in this case, if and only if $|a|=|b|$). Then we can consider the quotient set, and define the relation $\leq$ on the quotient set by $[a]\leq [b]$ if and only if $a\preceq b$ (here, $[a]$ is the equivalence class of $a$ under $\sim$, etc). Then one can show that this is a partial order on the quotient set; it is patently closely related to the original pre-order $\preceq$.
That's why relations that are reflexive and transitive are called pre-orders: you only need one further step to get to a partial order, though not usually on the set you started with.
Other kinds of orders
The basic notion, as I said above, is "partial order". There are lots of extra conditions one can put on a partially ordered set to make it a "nicer" kind of ordered set. These extra conditions define special kinds of orders. A random sampling off the top of my head (I'm using $\leq$ to denote whatever the partial order relation in question is; $a\leq b$ means $(a,b)$ is in the relation that defines the order):
Total or linear orders. In a partial order, it is possible for two elements to not be comparable at all, that is, you have neither $a\leq b$ nor $b\leq a$. For example, if you take a set $X$, you can define a partial order on $\mathcal{P}(X)$, the power set of $X$ (the set of all subsets of $X$) by saying that $A\leq B$ if and only if $A\subseteq B$ (in fact, this is in a sense the most basic kind of "partial order"). If $X$ has more than one element, though, then you have elements of $\mathcal{P}(X)$ that cannot be compared: take $x,y\in X$, $x\neq y$; then $\{x\}\not\leq \{y\}$ and $\{y\}\not\leq\{x\}$. This in contrast to the order relations we are used to in the natural numbers, real numbers, etc., where any two elements can be compared: one is bigger than the other. So we add a condition: the partially ordered set $A$ is totally ordered or linearly ordered if the partial order also satisfies the condition that for every $a,b\in A$, either $a\leq b$ or $b\leq a$.
Well order. This is a very strong generalization of total orders. In a total order, any subset with finitely many elements has a smallest element. A partially ordered set $A$ is said to be well-ordered if any nonempty subset $B$ of $A$ has a smallest element. For instance, the natural numbers with their usual order is well-ordered, but the real numbers with their usual order are not (the positive reals have no least element). A well-order must be a total order, but the converse is not true in general.
Lattice order. A lattice order is a partial order where, even though it is not true that any two elements are comparable, it is nevertheless the case that any two elements have a least upper bound (given $a,b\in A$, there exists a $c\in A$ such that $a\leq c$, $b\leq c$, and for every $d\in A$, if $a\leq d$ and $b\leq d$, then $c\leq d$), and a greatest lower bound (the dual concept; just reverse all the inequalities in the definition above). The typical example is going back to the partially ordered set of subsets of a given $X$ under inclusion; the least upper bound of $A$ and $B$ is $A\cup B$, and the greatest lower bound is $A\cap B$. You can weaken the definition to require only least upper bounds (upper semi-lattice) or just greatest upper bounds (lower semi-lattices). Or you can strengthen it to require least upper bound and/or greatest lower bounds for any nonempty subset (complete lattices); you can also require the existence of a smallest element and/or a greatest elements, or the existence of "complements" (if $0$ is the smallest element and $1$ is the greatest element, then a complement of $a\in A$ is an element $b\in A$ such that the least upper bound of $\{a,b\}$ is $1$ and the greatest lower bound of $\{a,b\}$ is $0$; in the case of $\mathcal{P}(X)$, the complement is the usual set-complement relative to $X$).
Directed sets. This is a kind of compromise between partially ordered sets and linear sets, in one direction: a partially ordered set $A$ is directed if and only if for every $a,b\in A$ there exists a $c\in A$ such that $a\leq c$ and $b\leq c$ (any two elements have a common upper bound). the dual notion, where any two elements have a common lower bound, is called an inversely directed sets. They play an important role in many areas of mathematics to construct special kinds of limits; when the index set is a directed system, you get something called a directed limit; when the index set is an inversely directed set, you get something called an "inverse limit". The $p$-adic integers are an example of an inverse limit.
Note: These are just a few of the ones I know, and they are likely a very limited sample of the ones that people who actually work with orders know. I don't do research anywhere near these topics, I just use orders all the time, like most mathematicians.
Strict orders
In addition, there is a "sister" notion to partial orders, called "strict orders". A binary relation $\prec$ is a strict order if and only if it is:
- Anti-reflexive: for every $a\in A$, $a\not\prec a$.
- Asymmetric: for all $a,b\in A$, if $a\prec b$, then $b\not\prec a$.
- Transitive: for every $a,b,c\in A$, if $a\prec b$ and $b\prec c$, then $a\prec c$.
However, strict and partial orders are actually closely connected. If you have a partial order $\preceq$, then you can define a strict order $\prec$ by $$a\prec b \Longleftrightarrow a\preceq b\text{ and }a\neq b.$$
Conversely, if you have a strict order $\prec$, then you can use it to define a partial order $\preceq$ by $$a\preceq b \Longleftrightarrow a\prec b\text{ or } a=b.$$
So you can take either notion as your "original" notion, and define the other one in terms of it. These days, it is more common to take "partial order" as the original, and define strict order in terms of it.
Here's an example.
Suppose we get our partial order by considering divisibility; let's say we've got the poset of all divisors of $12$, with $mRn$ if $m$ divides $n$. Then we can "restrict" this order to consider only divisors of, say, $6$ (or any other divisor of $12$, really). Or we could just pick our favorite handful of divisors of $12$, and keep the same strategy for ordering them; say we throw away $3$ and $12$. You can just draw the Hasse diagrams to "see" what's happening.
Anyway, you're right, the result is obvious, and its proof is trivial. But this brings about its own difficulties: How do you even prove something when it's trivial?
By resorting to the definitions and doing some bookkeeping! Specifically, you need to show that
$T$ is reflexive: for all $x \in P$, we have $(x, x) \in T$.
$T$ is transitive: whenever $(x, y) \in T$ and $(y, z) \in T$, we have $(x, z) \in T$, and
$T$ is antisymmetric: whenever $x \neq y$ and $(x, y) \in T$, we have $(y, x) \not\in T$.
But since you're focusing only on $x, y \in P \subseteq S$ then $T$ "inherits" these properties from $R$, truly!
Let's look at the transitive one.
We'd like to show that $T$ is transitive: whenever $(x, y) \in T$ and $(y, z) \in T$, we have $(x, z) \in T$. To do that, we just assume we have some arbitrary $(x, y)$ and $(y, z)$ in $T$, and we'll be done once we've shown that $(x, z)$ is necessarily in $T$ as well.
Suppose $x, y, z \in P$, and $(x, y), (y, z) \in T$. By the definition of $$T = \{(a,b) \mid a \in P, b \in P, (a, b) \in R\},$$ we have that $(x, y)$ and $(y, z)$ are in $R$ as well, hence $(x, z) \in R$ since $R$ is transitive. But since $x, z \in P$ and $(x, z) \in R$, then again by the definition of $T$, we have $(x, z) \in T$, as desired.
Blech. But, it's completely mundane and is just a matter of crossing i's and dotting t's.
(By the way, $T$ is usually called an induced (sub)poset; you pick elements to include from a given poset, and are forced to included any relations that exist between them. I can't seem to find a Wikipedia-like reference for this, but I'm fairly sure it's at least somewhat standard.)
Best Answer
To prove that $R \subseteq \mathcal{P}(X) \times \mathcal{P}(X)$ defined by $(A,B) \in R \Leftrightarrow A\subseteq B$ is a partial order you need to show:
It's very easy to prove these three items just using the definition of $\subseteq$.
Moreover, $\mathcal{P}(X)$ is totally ordered if and only if $X$ has at most 1 element.