# increasing subset of a partial order and characteristic function

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.

• What does $A$ is increasing mean? – André Nicolas Jun 19 '14 at 17:10
• It means that the order in A is increasing – Rud Faden Jun 20 '14 at 5:58
• Or to be more precise: the element in are are ranked in increasing order. – Rud Faden Jun 20 '14 at 19:06
• I really do not know what the problem asks for, language is being used in what is to me a quite non-standard way. – André Nicolas Jun 20 '14 at 19:11
• Maybe I am not conveying it right. I am quite new to set theory. The statement is taken from here: math.uah.edu/stat/foundations/Order.html no. 13 – Rud Faden Jun 20 '14 at 19:13

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!

• Just to be clear. When you write that $y\in A$ and $x\in S$, thus that imply that $x\in S\backslash A$. If for example you take the power set of $S=\{a,b,c\}^2$ and let $A=\{\emptyset , a,b,ab\}\subseteq S$, then $a\le ab \Rightarrow a\in A$, but $ab\ge a \Rightarrow ab\in A$.I find this very confusing. However if $x\in S\backslash A$, then i think it makes more sense. – Rud Faden Jun 27 '14 at 7:45
• @user2702600 On the one hand, when I(we) write $x\in S$, and we really mean $x\in S$, that is, if $A\subseteq S$, $x$ could be in $A$ or not. On the other hand, when trying to prove the property $\forall y\in A~\forall x\in S (x\leq_S y\to x\in A)$ then if we have a $y\in A$ and an $x\in A$ then $(x\leq_S y \to x\in A)$ is automatically verified, so we really need to see that the case when $y\in A$ and $x\in S\setminus A$ and $x\leq_S y$ is impossible. Also, 1. above is equivalent to $\exists y\in A~\exists x \in S\setminus A ~x\leq_S y$. – Yann Pequignot Jun 27 '14 at 8:16