Understanding the Order of Set $I_A$ - A Step-by-Step Guide

[evinda]

Hello! (Wave)

According to my notes, when we consider the order $I_A$ for $A \neq \varnothing$ each element of $A$ is minimal and maximal. If, in addition, $A$ has at least two elements then there isn't neither the greatest nor the least element of $A$.

Could you explain it to me? How can we check if there is for example a minimal element considering the set $I_A=\{ \langle x,x \rangle: x \in A \}$ ? (Thinking)

 

[Evgeny.Makarov]

A mathematical problem is difficult if it involves infinitely many possibilities. The question whether $a^{p-1}\equiv1\pmod{p}$ for all $a$ and $p$ is difficult because it involved infinitely many possible values of $p$. You can also say that a problem is difficult for a computer search if it involves, say, billions or more of possibilities, and it is difficult for a search by hands if it involves 100 or more possibilities. On the other hand, a problem whether there is an $x\in\Bbb Z_7$ such that $\Bbb Z_7=\{0,x^0,\dots,x^6\}$ is not hard because it involves testing at most 6 numbers and computing 6 powers for each number.

Considering finite $A$ with small number of elements in your problem and figuring out if the given statements are true is easy because it hardly involves any search. So please do this to get intuition about this question. This also pertains to other questions you may have that involve finite structures with few options to consider.

 

[evinda]

If we pick for example $A=\{ 1,2,3 \}$ then:

$$I_A=\{ \langle x,x \rangle: x \in \{1,2,3\}\}=\{ \langle 1,1 \rangle, \langle 2,2 \rangle, \langle 3,3 \rangle \}$$How can we find in this case the minimal element?

 

[Evgeny.Makarov]

If you don't understand a certain part of the definition of "minimal element", then show this part and say why you don't understand it. I don't think understanding the definition is a problem because we discussed the difference between minimal and least elements in other threads. If you do understand the definition, I don't see why you can't apply it to the given relation.

 

[evinda]

So, in order to find the minimal element are we looking for an element of the form $\langle a,a \rangle \in I_A$ such that $\forall \langle x,x \rangle \in I_A: \langle x,x \rangle \leq \langle a,a \rangle \rightarrow \langle x,x \rangle=\langle a,a \rangle$?
We have three different elements: $\langle 1,1 \rangle, \langle 2,2 \rangle,\langle 3,3 \rangle$.
So if it is like that it must hold:

$$ \langle 1,1 \rangle \leq \langle a,a \rangle \rightarrow \langle 1,1 \rangle=\langle a,a \rangle$$

$$ \langle 2,2 \rangle \leq \langle a,a \rangle \rightarrow \langle 2,2 \rangle=\langle a,a \rangle$$

$$ \langle 3,3 \rangle \leq \langle a,a \rangle \rightarrow \langle 3,3 \rangle=\langle a,a \rangle$$Therefore it must hold $a=1=2=3$ that is impossible. So does this mean that there is no minimal element? (Thinking)Or have I understood it wrong? (Worried)

 

[Evgeny.Makarov]

So, in order to find the minimal element are we looking for an element of the form $\langle a,a \rangle \in I_A$ such that $\forall \langle x,x \rangle \in I_A: \langle x,x \rangle \leq \langle a,a \rangle \rightarrow \langle x,x \rangle=\langle a,a \rangle$?

No. "Elements" here are members of $A$, not of $I_A$. If $A=\{1,2,3\}$, then the numbers 1, 2, 3 (not pairs of numbers) are being compared. The set $I_A$ is the relation playing the role of order on $A$. You should review the definition and examples of a binary relation and an order.

 

[evinda]

No. "Elements" here are members of $A$, not of $I_A$. If $A=\{1,2,3\}$, then the numbers 1, 2, 3 (not pairs of numbers) are being compared. The set $I_A$ is the relation playing the role of order on $A$. You should review the definition and examples of a binary relation and an order.

A ok... (Nod)
So, when we have $A=\{ 1,2,3\}$ we are looking for an element $a \in A$ such that $\forall x \in A: xI_A a \rightarrow x=a$. But since this is the definition of $I_A$ we conclude that all the elements of $A$ are minimal elements.
Also it holds that $\forall x \in A: a I_A x \rightarrow x=a$. Therefore the elements of $A$ are also maximal elements.
To check if there is a least element, we check if there is an $a \in A$ such that $\forall x \in A: a I_A x \Rightarrow \forall x \in A: x=a$ that cannot be true since we have three different elements. For the same reason we conclude that there is no greatest element.

Am I right? (Thinking)

 

[Evgeny.Makarov]

Yes, you are right.

 

[evinda]

So could we say the following for the general case ? (Thinking)If we consider the order $I_A$ for $A \neq \varnothing$, we conclude from the definition of $I_A$ that each element of $A$ is minimal and maximal.
Now we suppose that $A$ has at least two elements $x,y$ with $x \neq y$.
We will show that there is no least element.
Suppose that there is a least element $a$ in $A$.
Then $\forall x \in A: a \leq x \leftrightarrow aI_Ax \rightarrow x=a$.
We have that $x,y \in A$. So $x=a \wedge y=a \rightarrow x=y$, contradiction.
Therefore, there is no least element.
In the same way we conclude that there is no greatest element.

 

[Evgeny.Makarov]

I agree.

Regarding partial order in general and this problem in particular, I recommend understanding Hasse diagram. There is almost nothing to learn about them, but they are useful because they provide a visual instead of algebraic way of thinking about order.