Order theory deals with properties of orders, usually partial orders or quasi orders but not only those. Questions about properties of orders, general or particular, may fit into this category, as well as questions about properties of subsets and elements of an ordered set.

learn more… | top users | synonyms

1
vote
0answers
58 views

Generalized semilattice morphism

Join-semilattice morphism from a join-semilattice $\mathfrak{A}$ to a join-semilattice $\mathfrak{B}$ is a function $\alpha$ conforming to the formula $\alpha(X\sqcup Y) = \alpha X\sqcup\alpha Y$ ...
2
votes
1answer
48 views

Difficulty understanding “antichains”

I'm having a difficulty understanding the concept of "antichains". An antichain in a poset $P$ is a subset $C \subseteq P$ such that no 2 elements are comparable I understand the definition, ...
0
votes
0answers
12 views

Can we distinguish direct from transitive partial orders

If I have a set L and a partial order ≤ defined on L, and (L, ≤) is a lattice. We know that ≤ is transitive, i.e. if l1 ≤ l2 and l2 ≤ l3 then l1 ≤ l3. Well. I ...
3
votes
2answers
41 views

How to prove that if R is a partial order then also $R^{-1}$ is also a partial order?

My guess was to divide the problem into 3 cases: prove that $R^{-1}$ is reflexive, antisymmetric and transitive. To prove that $R^{-1}$ is reflexive, I did: If $R$ is reflexive, that follows that ...
0
votes
0answers
30 views

Does this combinatorial object have a name?

I have come across the need to with subsets of meet-semilattices. Specifically, my setting is that I need posets that have a meet operation that is unique when defined, but is not necessarily defined ...
1
vote
2answers
40 views

Prove the relation on $\Bbb N \setminus \{0,1\}$ is a partial order

I'm a bit new to this material and trying understand some problem I'm solving Let $R$ be a relation on the set set = $ \{ N \setminus \{ 0,1\}\} $ that's defined like this: $aRb$ if there is an ...
0
votes
0answers
42 views

Are the face posets of CW-complexes Eulerian?

Suppose we had a CW-complex $X$ with decomposition $X_{i}$ Is its face poset, consisting of cells and covers generated by the attachment of cells to one another, an Eulerian poset? What would be the ...
3
votes
2answers
85 views

Are the Hyperreals complete?

Since $^*\mathbb{R}$ does not form a metric space then it can not satisfy the Cauchy conditions for completeness. However, my intuition is telling me that it would satisfy conditions of completeness ...
2
votes
1answer
59 views

Proving distributivity of Heyting algebras with the Yoneda lemma.

How can one prove distributivity of a Heyting Algebra via the Yoneda lemma? I'm able to prove it using the Heyting algebra property $(x \wedge a) \leq b$ if and only if $x \leq (a \Rightarrow b)$. ...
0
votes
1answer
23 views

for any subset S of finite group G and any g,h∈G, show |gSh|=|S|

Let $G$ be a finite group. For any subset $S$ of $G$, and any group elements $g,h \in G$, I want to show that $|gSh|=|S|$, i.e. that the cardinality of $S$ is preserved when multiplying on the left ...
1
vote
1answer
77 views

Question about supremum $\implies$ infimum

For all the proofs I've seen that if a set has the least upper bound property, then that set also has the greatest lower bound property, they assert something like if a set has lower bounds, then the ...
0
votes
1answer
49 views

Is relation a partial order?

can you give me few hints how to solve this problem ? Relation R on the set P(A) A = {a,b,c,d} is a set of four elements. We also have relation R on the set P(A), which is defined R={(A,B)│A ⊆ B. ...
0
votes
1answer
41 views

How can find this matrix?

Let $U$ be an $k\times n$ matrix and $G$ an $n \times n$ matrix over $\mathbb F_q$. We know that valuation of $UG$,$UG^2$,...,$UG^{k-1}$. ($k$ is the order of $G$) If we dont know components of $U$ ...
0
votes
1answer
59 views

Möbius inversion for locally finite poset

I'm trying to understand this paper: Rota, Gian-Carlo. "On the foundations of combinatorial theory I. Theory of Möbius functions." Or at least, to understand the first few pages. In particular, I'm ...
0
votes
1answer
26 views

Minimal and maximal element in a subset of a Kolmogorov space.

Let $X$ be a Kolmogorov space and define on it a specialization order, ie.: for any $x,y \in X$, we have $x \leq y$ if and only if $x \in \overline{ \{y\} }$, where $\overline{ \{y\} }$ is the ...
12
votes
3answers
584 views

Sole minimal element: Why not also the minimum?

A minimal element (any number thereof) of a partially ordered set $S$ is an element that is not greater than any other element in $S$. The minimum (at most one) of a partially ordered set $S$ is an ...
1
vote
2answers
44 views

Difficulty understanding Zorn's Lemma.

This is a question on chap. 9 of Introduction to Set Theory of Hrbacek and Jech. The book define that the Zorn's Lemma is: If every chain in a partially ordered set has an upper bound, then the ...
1
vote
1answer
78 views

Another way to express certain filter

Let $\mathfrak{A}$, $\mathfrak{B}$ be posets, $\mathfrak{A} \subseteq \mathfrak{B}$ (and $\mathfrak{A}$ is the induced order of $\mathfrak{B}$). Let $\mathcal{A}$ be a filter on $\mathfrak{A}$. Help ...
2
votes
1answer
154 views

Does the ordered set from Zorn's lemma have a lowest element?

The ordered set in the Zorn's lemma needs to have supremums for all chains, that is, including the empty chain. The supremum of an empty chain is its lowest upper bound. Since any element is an upper ...
0
votes
2answers
91 views

an example of the Scott topology

Let $X=A\cup B$ where $A$ is set of all positive integers w.r.t the Scott topology and $B$ is singleton set $\{b\}$. A set $U$ is open in $X$ iff $U$ is open in $A$ or $A\subseteq U$ and $U\cap B ...
0
votes
1answer
32 views

I can not understand some steps in Tverberg's proof on Dilworth theorem

As is shown in the underlined part of the picture above. First, why after $c^+ \not\in S^-$, we can use induction hypothesis? how does it imply $S^-$ contains no antichain of cardinal $m + 1$? ...
0
votes
1answer
18 views

What are the maximal chains and antichains of $S=\{0,1,4,6,7,8,9\}$ under the order of divisibility?

I just really don't understand what 'maximal' is.
1
vote
1answer
21 views

How would i apply Dilworths Theorem to the following set: $S=\{ 0,1,4,6,7,8,9\}$ where any element $a$ is less than or equal to $b$?

This is the set $S=\{ 0,1,4,6,7,8,9\}$ under the order defined by divisibility. I know we have to find antichains and chains, and that the maximum number of partitions of $S$ into chains should equal ...
0
votes
1answer
24 views

Linear order where every initial segment is finite

It's true that a set with a linear order where every initial segment is finite is necessarily countable? I don't think so but I can't find a counterexample (or make a proof)
7
votes
1answer
157 views

Is there a linear order with this property

I was trying and failing to construct a linear order L each of whose uncountable subsets contains an uncountable well ordered subset but L is not a countable union of well ordered subsets. Is this ...
4
votes
0answers
136 views

Is there a name for those relations that behave a bit like $<$?

Consider a fixed but arbitrary preordered set $X$. Is there a name for those binary relations $R$ on $X$ satisfying the following? They seem to show up a lot. (Note that every such $R$ is necessarily ...
6
votes
2answers
95 views

Embedding $\omega_1$ in the hyperreals

I've been trying to show that there exists a subset of the hyperreals which has order type $\omega_1$, that is, that there exists a subset $A \subseteq {}^*\mathbb{R}$ for which there is an order ...
1
vote
1answer
35 views

Showing certaing Integral domain is not well ordered.

Let $\mathbb{Z}[\sqrt2]=\{ a+b\sqrt2 ~| a,b\in \mathbb{Z}\} $ be an integral domain. Let $p=\{ a+b\sqrt2 ~|a,b\in\mathbb{Z} ~~~ and ~~~ a+b\sqrt 2 ~~is~~a~positive~real~number \} $ Show that ...
3
votes
1answer
82 views

Why is this not a category?

Why need the composite of two monotone functions not be monotone? This is from Rings and Categories of Modules, Anderson., Fuller., page 7
0
votes
0answers
16 views

Form Poset from (Non-zeta) Matrix

I have a matrix (well, really a table) of values that are the results of various indicator systems. Naturally, each system is slightly discordant, so no one true ranking exists. I'm looking to form ...
2
votes
1answer
45 views

Chain of elements of a chain of order ideals

Let $P$ be a partially ordered set, and let $I(P)$ be the set of order ideals (i.e. downward-closed sets) in $P$ ordered by inclusion. Suppose that $X$ is a chain of non-empty elements of $I(P)$. ...
0
votes
0answers
47 views

Dedekind(?) representation lemma on posets?

Here's an easy lemma: Any poset $(S, \preceq)$ is order-isomorphic to a subset of the powerset $\mathcal{P}(S)$ ordered by set-inclusion. I seem to recall having seen this attributed to Dedekind. ...
2
votes
1answer
41 views

Is there an orderpreserving bijection from $\mathbb R$ to $\mathbb R-\{0\}$?

Looking at $(\mathbb R,<)$ where $<$ denotes the usual order I understand that $\mathbb R-\{0\}$ will inherit an order (as every subset of $\mathbb R$). I could not find essential differences ...
1
vote
1answer
30 views

When can $\sup_x$ and $\sup_y$ be swapped?

$f$ is a mapping from $X \times Y$ to $Z$. $X$ and $Y$ are sets. $Z$ is a set with $\sup$ defined ( I am not very sure how to formulate that. Is $Z$ required to have some total order?), and can be ...
1
vote
1answer
32 views

A question about cofinal and coinitial order-preserving injections between linearly ordered sets

There is an inclusion $f : \mathbb{Z} \hookrightarrow \mathbb{R}$. Furthermore, if $A \subseteq \mathbb{R}$ has a maximum element, then so too does $f^{-1}(A)$. There is also an inclusion $g : ...
2
votes
1answer
36 views

Lower Bound for subsets of $\mathbb{N}$ [duplicate]

Let $P = \{A \in \mathbb{N} : A \neq \emptyset, |A|<\infty, |A| = 2k, k\in \mathbb{Z}^{+}\}$. Consider $X = \{ A \in P: 1 \in P \}$. Does $X$ have a lower bound in $(P,\subseteq)$. We can see that ...
0
votes
1answer
40 views

Does X have a lower bound?

Let P={A $\subseteq$ $\mathbb N$: A is non-empty, finite and has an even number of elements}. Consider X={A $\in$ P : 1 $\in$ A}. Does X have a lower bound in (P,$\subseteq$)? I think that there is a ...
2
votes
1answer
46 views

For any $a\in S_\Omega$, either it has an immediate predecessor or there is an increasing sequence in $S_\Omega$ whose l.u.b. is $a$. [duplicate]

Specifically I would like to show: Let $S_\Omega$ be the minimal uncountable well-ordered set. For any $a\in S_\Omega$, either $a$ has an immediate predecessor in $S_\Omega$, or there exists an ...
0
votes
1answer
22 views

does isomorphic Hasse diagrams represent two different posets or same poset?

I want to have a clear picture of isomorphic hasse diagrams, what do they represent, same poset or two different posets?
1
vote
0answers
31 views

Why is every monomial order a well-ordering?

Let $R$ be a commutative, unital ring. According to wikipedia, a monomial order is a total order $\leq$ on the space of monomials of a given polynomial ring of $R$ such that If $u\leq v$ and $w$ is ...
0
votes
1answer
19 views

Prove that, for all ordered sets P, Q and R,

$\langle P \rightarrow \langle Q \rightarrow R\rangle \rangle \cong \langle P \times Q \rightarrow R\rangle $ where $\langle Q \rightarrow R\rangle $ is the set of all order-preserving maps from Q ...
2
votes
2answers
77 views

Positive elements of a $C^*$-algbera form a poset

My knowledge of $C^*$-algebras is very little. We call an element positive if $a=b^*b$ for some $b$ and make a relation on all positive elements by saying $$ b \geqslant a \iff b-a \text{ is ...
2
votes
1answer
28 views

Is there a nice characterization of those posets in which $\vartriangle_P$ is transitive?

Whenever $P$ is a poset and $x,y$ are elements of $P$, write $x \vartriangle y$ to mean that $x$ and $y$ have a lower bound. Then $\vartriangle_P$ is always reflexive and symmetric, but it may or may ...
3
votes
1answer
45 views

Categorial description of the subposet of $\prod_{i \in I}P_i$ of all $x \in \prod_{i \in I}P_i$ with $\{i \in I \mid x_i = \bot_{P_i}\}$ cofinite

By a grounded poset, I mean a poset $P$ with a least element $\bot_P$. Definition. Whenever $P$ is a family of grounded posets, write $\bigotimes_{i \in I}P_i$ for the subposet of $\prod_{i \in ...
2
votes
2answers
74 views

When multiplying by $i$ in inequalities, does the sign flip?

Take $1>-1$, when you multiply by $-1$, to get $-1<1$ you have to flip the sign. What if you are multiplying by $i$? Would you flip the signs? If you didn't it would net the expression ...
0
votes
1answer
74 views

Does there exist an amazing poset that is neither totally-ordered nor well-founded?

Definition. Let $P$ denote a poset. Then $P$ is amazing iff every $A \subseteq P$ has the property that if $A$ has a unique minimal element (call it $m$), then $A$ has a minimum element (namely $m.$) ...
0
votes
1answer
57 views

A question about cofinal totally ordered sets.

Let $A$ be an uncountable set, and let $L$ be the poset consisting of all finite subsets of $A$ (the ordering on $L$ is inclusion). Show that $L$ does not have a totally ordered cofinal subset. I am ...
0
votes
0answers
47 views

mapping functions for power set graphs

Let $G(\mathcal{P}(n),E)$ be a power set graph for $[n]$ elements with the inclusion relation. The width of such graph is known by Sperner's theorem $w=\binom{n}{n/2}$. By Dilowrth's theorem we can ...
0
votes
1answer
44 views

Notation for rank of weakly ordered elements

I'm looking for a mathematical notation for the following algorithm where $D$ is a diagonal square matrix and $w$ a scalar value. Sort $D$ by the diagonal entries ascending for the first entry ...
1
vote
1answer
36 views

Number of linear extensions

Let $le(X, \preceq)$ denote the number of linear extensions of a partially ordered set $(X, \preceq)$. Prove $le(X, \preceq) = 1$ iff $\preceq$ is a linear ordering $le(X,\preceq) = n!$ where $n = ...