increasing subset of a partial order and characteristic function

Question

Can someone help me understand this?

Suppose that $\preceq$ is a partial order on a set $S$ and that $A\subseteq S$. If $\mathbf{1}_A$ is the indicator function then

1. $A$ is increasing if and only if $\mathbf{1}_A$ is increasing.

2. $A$ is decreasing if and only if $\mathbf{1}_A$ is decreasing.

Answer 1

Based on your reference a decreasing subset of a partial order $(S,\leq)$ is a subset $A$ of $S$ such that $\forall y\in A ~\forall x\in S ~(x\leq y \to x\in A)$. A decreasing subset is also called (in fact more usually called) a downset or an initial segment.

Now if $(P,\leq_P)$ and $(Q,\leq_Q)$ are partial ordered sets, a partial map $f:P\to Q$ is said to be decreasing if $\forall x,y\in P ~(x\leq_P y \to f(y)\leq_Q f(x))$.

Remember that the characteristic function of a subset $A$ of a set $S$ is the function $1_A:S\to 2$ where $2=\{0,1\}$ defined by $1_A(s)=1 \leftrightarrow s\in A$ for all $s\in S$.

Now the proposition in question states the following:

Let $\mathbf{2}$ be the set $\{0,1\}$ partially ordered by $0\leq 0$, $0\leq 1$ and $1\leq 1$. Let $(S,\leq_S)$ be a partial order and $A$ be a subset of $S$. Then $A$ is decreasing (or a downset, or an initial segment) if and only if $1_A:S\to 2$ is a decreasing map from $(S,\leq_S)$ to $\mathbf{2}$.

And the proof goes by observing that the following statement are equivalent:

1. $A$ is not a downset
2. $\exists y\in A ~\exists x\in S ~(x\leq_S y \land x\not\in A)$
3. $\exists x,y\in S ~(x\leq_S y \land x\not\in A \land y\in A)$
4. $\exists x,y\in S~(x\leq_S y \land 1_A(x)=0 \land 1_A(1)=1)$
5. $\exists x,y\in S ~(x\leq_S y \land 1_A(x)\not \geq 1_A(y))$
6. $1_A$ is not decreasing.

The equivalence 4.$\leftrightarrow$5. comes from the fact that in $\mathbf{2}$ for every $a,b\in 2$ we have $a\not\geq b$ if and only if $a=0$ and $b=1$.

The part on increasing sets is dual, meaning it is just the statement on decreasing sets about the upside-down poset $S^\text{op}$ where $x\leq_{S^\text{op}} y$ iff $y\leq_S x$. So there is no need to prove it, it follows from what we have done. But if you are not familiar with partial orders, you might find it a useful exercise!

I hope it helps!