0

If $B$ is a set ordered (partially or fully) under $S$ then $S=S^2$?

Intuitively this seems right.

We know according to the definition of ordered sets that $S$ is reflexive, antisymmetric and transitive.

Let $S=I_B\cup R$ where $I_B$ is the identity relation over $B$ and $R=S-I_B$. Then $R$ is of form $\{(a,b), (b,c), (a,c)\}$ and $R\cdot I_B = R$ so $R\subseteq S$ and therefore $S=S^2$.

I know something lacks in my proof but I can't think of another way to prove this.

Kenny Lau
  • 25,049
Yos
  • 611
  • 2
    You mean $S$ is a relation that is a (partial or total) order of $B$. Whchmakes $B$ an ordered set. For a general set, $S^2$ has a different meaning than for a relation. – Hagen von Eitzen Apr 09 '18 at 06:21

2 Answers2

1

Your proof lacks generality - $R$ can have more (or less) than three elements.

Transitivity of $S$ is equivalent to $S\cdot S\subseteq S$. On the other hand, reflexivity means $I_B\subseteq S$, hence $S=I_B\cdot S\subseteq S\cdot S$.

Hagen von Eitzen
  • 374,180
  • but how do we know that antisymmetry doesn't introduce some "new" elements in $S^2$? – Yos Apr 09 '18 at 06:33
1

$S \subseteq S^2$:

Let $(a,b) \in S$. We must show that $(a,b) \in S^2$.

Since $S$ is reflexive, $(b,b) \in S$.

Therefore, $(a,b) = (a,b) \circ (b,b) \in S^2$.

$S^2 \subseteq S$:

Let $(a,b) \in S^2$, i.e. there is $x$ such that $(a,x) \in S$ and $(x,b) \in S$. We must show that $(a,b) \in S$.

Since $S$ is transitive, $(a,x) \in S$, $(x,b) \in S$, we conclude that $(a,b) \in S$.

Kenny Lau
  • 25,049