MHB Partial Order Relation where the Set is not Necessarily Finite

Yankel
Messages
390
Reaction score
0
Hello all,

I have another question about partial order relations, again, a few statements which are either true or false.

R is a partial order relation on a set A which is not necessarily finite.

1) With this order, A has at least one maximal and one minimal elements.

2) If with this order, A has a smallest and largest elements, then every two element of A are comparable.

3) If with this order, A has no maximal elements, then A is infinite.

4) if with this order, A has a single minimal element, then it is a smallest element.

5) If every two elements are comparable, then there is a smallest and largest elements.I think that 3 and 4 are true and the others are false, but I am not sure. Statement 3 is very intuitive. So is 4. I am quite sure over 5 as well (being false). Statements 1 and 2 are confusing a bit.

Can you think of an example which can show this ?

Thank you !
 
Physics news on Phys.org
Yankel said:
Hello all,

I have another question about partial order relations, again, a few statements which are either true or false.

R is a partial order relation on a set A which is not necessarily finite.

1) With this order, A has at least one maximal and one minimal elements.
False. The set of integers with the usual order is a counterexample.

2) If with this order, A has a smallest and largest elements, then every two element of A are comparable.
False. The set of all subsets of A, ordered by inclusion, is a counterexample. A itself is "largest", the empty set is "smallest".

3) If with this order, A has no maximal elements, then A is infinite.
This is true.
4) if with this order, A has a single minimal element, then it is a smallest element.
That looks like the usual definition of "smallest element"?

5) If every two elements are comparable, then there is a smallest and largest elements.
False. The set of integers, with the usual order, is a counterexample.
I think that 3 and 4 are true and the others are false, but I am not sure. Statement 3 is very intuitive. So is 4. I am quite sure over 5 as well (being false). Statements 1 and 2 are confusing a bit.

Can you think of an example which can show this ?

Thank you !
 
Yankel said:
4) if with this order, A has a single minimal element, then it is a smallest element.

HallsofIvy said:
That looks like the usual definition of "smallest element"?
No, the definition says the smallest element is less than or equal to every element. I think 4) is false.
 
Thank you both !

Can you explain number 2 ?

I don't get it. First of all, are you saying that if for example A=N (naturals), then P(N) has a largest element, which is N?

If so, how come not every two elements of P(N) are comparable?
 
Yankel said:
First of all, are you saying that if for example A=N (naturals), then P(N) has a largest element, which is N?
Yes, every subset of $A$ (i.e., element of $P(A)$) is a subset of $A$ (i.e., less than or equal to $A$).

Yankel said:
If so, how come not every two elements of P(N) are comparable?
I think you missed the definition of the order here ("by inclusion"). Otherwise I am puzzled by the difficulty you are having.
 
I might have missed the definition. If the relation is the subset relation, two elements are comparable if one is a subset of the other? For example, if A={1,2}, then P(A)={empty, {1}, {2},{1,2}}, and I say that {1} and {2} are NOT comparable?

Statement 3 say that if there is no maximal element, the set is infinite. And you guys are saying it's true. So it DOESN'T work on the other way, "if a set is infinite it doesn't have a maximal element", because of the example of the naturals with the subset relation. Did I understand correctly?

This is interesting...
 
Last edited:
Yankel said:
I might have missed the definition. If the relation is the subset relation, two elements are comparable if one is a subset of the other? For example, if A={1,2}, then P(A)={empty, {1}, {2},{1,2}}, and I say that {1} and {2} are NOT comparable?
Yes.

Yankel said:
Statement 3 say that if there is no maximal element, the set is infinite.
Yes, because for every element there is a greater one, and this chain cannot loop due to transitivity and irreflexivity of strict order.

Yankel said:
So it DOESN'T work on the other way, "if a set is infinite it doesn't have a maximal element", because of the example of the naturals with the subset relation.
I wouldn't say "So" because what follows is not implied by statement 3. But you are correct: an infinite set may have a maximal element. The simplest example is negative integers. An infinite set may be linearly ordered and have both least and greatest elements, e.g., $\{0\}\cup\{1/n\mid n\in\mathbb{Z}^+\}$.
 
Back
Top