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
up vote 0 down vote accepted

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.