MHB Partial Order Relation where the Set is not Necessarily Finite

AI Thread Summary
The discussion centers on the properties of partial order relations on potentially infinite sets. Participants evaluate several statements regarding maximal and minimal elements, comparability, and the implications of having or not having these elements. Statement 3 is agreed to be true, asserting that a set without maximal elements must be infinite, while statement 4 is debated, with some concluding it is false. The confusion arises particularly around statements 1 and 2, with examples provided to clarify the definitions of comparability and maximality. Overall, the conversation highlights the complexities of understanding partial orders in both finite and infinite contexts.
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