Suppose $R$ is a relation on $A$, and $∀x \in A∀y \in A(x Ry \lor y Rx)$. Prove that for every finite, nonempty set $B ⊆ A$ there is some $x \in B$ such that $∀y \in B((x, y) \in R ◦ R)$. Below we will refer to such $x$ as LSE of $B$.
My attempt:
By induction.
Base case:
Take $B \subseteq A$ such that $|B| = 1$. Let $B = \{b\}$. Since $R$ is reflexive, $bRb$ and thus $(b,b) \in R \circ R$. $b$ is LSE of $B$
Induction step:
Suppose for any set $K \subseteq A$ with $n$ elements exists LSE
Let $B \subseteq A$ such that $|B| = n+1$. Take arbitrary $b \in B$.
Let $B' = B \setminus \{b\}$
By inductive hypothesis, we know $B'$ has LSE, call it $c$.
Consider set $B$.
We know that either $cRb$ or $bRc$
Suppose $cRb$. Since $cRc$, $(c,b) \in R \circ R$. $c$ is LSE of $B$.
Suppose $bRc$
Suppose exists $a \in A$ such that $cRa$ and $aRb$. Then $(c,b) \in R \circ R$. Hence $c$ is LSE
Suppose there doesn't exist $a \in A$ such that $cRa$ and $aRb$.
- Since $bRb$, we have $(b,c) \in R \circ R$.
- Take arbitrary $y \in B'$. We know that $(c,y) \in R \circ R$. Exists some $k$ such that $cRk$ and $kRy$. By assumption, we know that $bRk$. Which means that $(b,y) \in R \circ R$. Since $y$ was arbitrary, we have $\forall x \in B'\bigl((b,x) \in R \circ R\bigr)$.
- Hence $\forall x \in B\bigl((b,x) \in R \circ R\bigr)$. $b$ is LSE of $B$.
Therefore, in all cases, $B$ will have LSE. $\Box$
Is it correct?