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
2answers
152 views

Either two sets have the same cardinality, or one has cardinality greater than the other

This is a problem (10.11) from Munkres, Topology, 2 ed. Problem: Let $A$ and $B$ be two sets. Using the well-ordering theorem, prove that either they have the same cardinality, or one has cardinality ...
0
votes
1answer
147 views

Relation between concept lattice and Dedekind–MacNeille completion

While trying to unify the (mostly linearly) ordered attributes from Statistical classification with the binary attributes from formal concept analysis, I came across an interesting section in the ...
3
votes
1answer
117 views

Does model theory extend to partial functions?

I have been reading a bit about effect algebras and d-posets recently, sets $M$ on which you have a single partial binary operation (partial here meaning partially defined, i.e. the domain of this ...
0
votes
1answer
34 views

Ordering tuples over (0,1)

To understand the natural ordering of $\{0,1\}^N$ I first thought about $\{0,1\}^3$ which has this Hasse diagram: There's something interesting going on in the second and third rows. In 3-D it ...
2
votes
0answers
69 views

Set Theory - Well Order (Lexiographical combination)

Question: Prove constructively that if $(A_{1},\prec_{1})$ and $(A_{2},\prec_{2})$ are two well-ordered sets then their lexicographical combination $(A_{1} \times A_{2},<_{1,2})$ is also well ...
1
vote
1answer
85 views

Are there any known uncountable transfinite increasing sequences of real numbers?

The real numbers are uncountable, so assuming the axiom of choice there is at least transfinite sequence of real numbers $r_0, r_1, r_2, ..., r_\omega, r_{\omega + 1}, ..., $ up to (and possibly ...
2
votes
1answer
99 views

Help to understand a proof (about filters)

Niels Diepeveen claims that he has proved the following theorem: Theorem Consider the cofinite filter $F$ on an infinite set. Let $K$ be a collection of ultrafilters such that $\bigcap K=F$. Then for ...
6
votes
2answers
98 views

Existence of totally ordered ring with zero divisors

Does there exist a totally ordered ring with zero divisors? I can't think of an example right now.
0
votes
1answer
211 views

Could the empty set be complete partial order?

According to the definition, $(S,\leq)$ is cpo when each totally ordered subset of $S$ has supremum. I'm sure $(\emptyset,\emptyset)$ is a total order, but I don't know whether $(\emptyset,\emptyset)$ ...
5
votes
1answer
93 views

Existence of non-commutative ordered ring

Does there exist a totally ordered ring which is non-commutative? I have searched the web, but I have not found any examples.
5
votes
2answers
73 views

Countability of a certain set

Suppose $S$ is a totally ordered set such that for any $x,y\in S$ there are finitely many elements between them. Does it follow that $S$ is (at most) countable? It seems like the answer should be ...
5
votes
4answers
937 views

How long does a sequence need to be to be guaranteed to have a monotonic subsequence length k?

The sequence 7, 2, 4, 1, 4, 8 has an increasing subsequence length four (2, 4, 4, 8) and a decreasing subsequence length three (7, 4, 1). It has other monotonic (increasing or decreasing) subsequences ...
0
votes
2answers
141 views

Is a Lattice just a linearly ordered set?

The definition of Lattice I was introduced to recently was a poset for which every two elements had a supremum and infimum. Doesn't this just mean that the poset is a chain and tus a linearly ordered ...
1
vote
1answer
67 views

How many complete theory extend theory T are there?

$Т$ - theory of signature $\{\le\}$, defined by the axioms А1-А5: А1: $\forall x(x=x)$ А2: $\forall x,y\big((x\le y\land y\le x)\to x=y\big)$ A3: $\forall x,y,z\big((x\le y\land y\le z)\to x\le ...
1
vote
1answer
28 views

Does the closure of the set of all irreducible elements always equal the whole set?

Let $X$ denote a set and $\mathrm{cl}$ denote a finitary closure operator on its powerset. Call $x \in X$ irreducible iff for all $A \subseteq X$ we have that if $x \in \mathrm{cl}(A)$, then $x \in ...
2
votes
2answers
161 views

structure of the hypernaturals

I want to understand the structure of the hypernaturals a little better. Let me recall the ultraproduct construction of the hypernaturals. On the set of all sequences of $\mathbb{N}$, we define an ...
-1
votes
1answer
27 views

partially order

$( A,\le)$ and $(A',\le')$ are partially ordered sets. A map $\phi : A \to A'$ is called order preserving from $(A, \le)$ to $(A', \le')$ if for all $x, y \in A : x \le y \implies \phi(x) \le' ...
1
vote
1answer
59 views

Cardinality of a linear continuum

A linear continuum is a totally ordered set with more than one element, which is both dense and satisfies the least upper bound property. Is it true that every linear continuum has the same ...
1
vote
1answer
73 views

Proof that there is an order relation

For an arbitrary set M there is a relation $R \subseteq 2^M \times 2^M$ about $$ A \mathrel R B \Leftrightarrow A \cup \{x\} = B$$ The join is a disjoint join. There are not more details what is $x$. ...
2
votes
3answers
89 views

Non-trivial order on a set with infinitely many minimals/maximals

I am looking for an example of each: 1) A non-trivial order on a set A such that there are infinitely many minimal elements and 2) A non-trivial order on a set A such that there are infinitely many ...
0
votes
2answers
17 views

How would I show that this is a subset?

Let R1 and R2 be relations on N defined by xR1y if and only if y=a+x for some a ∈ N0. xR2y if and only if y=xa for some a ∈ N. for all x,y ∈ N. Also N0 denotes all integers x>=0, while N denotes all ...
4
votes
1answer
62 views

Does every orthocomplemented lattice satisfy the shuffle laws?

Let $L=(X,\wedge,\vee,^\bot)$ denote a non-empty lattice having a unary operation $x \mapsto x^\bot$ that satisfies both "shuffle" laws: $$x \wedge y \leq z \iff x \leq y^\bot \vee z.$$ $$x \leq y ...
1
vote
1answer
87 views

Effectively describing all elements of the Borel $\sigma$-algebra

Consider, for simplicity, the Borel $\sigma$-algebra of the unit interval $[0,1]$. Let $\{A_i\}$ be a family of Borel subsets which generate the sigma algebra (can be either countable or ...
2
votes
1answer
113 views

How to rigorously prove that these two sets have different order types?

Let $A$ and $B$ be two given ordered sets with the linear (or total) order relations $<_A$ and $<_B$, respectively. Then $(A,<_A)$ and $(B,<_B)$ are said to be of the same type if there ...
1
vote
1answer
89 views

Adjoint of forgetful functor

I want to solve an exercise about adjoints (but I am not sure about the steps). Let $U:\textbf{CL}\rightarrow\textbf{Posets}$ be the forgetful functor. Here we have a functor from the complete ...
0
votes
1answer
49 views

I want to be able to write proof's for each of these but I don't know where to start.

Let $\mathrel{R_1}$ and $\mathrel{R_2}$ be relations on $\mathbb N$ defined by $x\mathrel{R_1}y$ if and only if $y = a + x$ for some $a \in\mathbb N_0$. $x\mathrel{R_2}y$ if and only if ...
0
votes
1answer
76 views

Expected value of round robin scores and ranks

Suppose you have $n$ players play a round robin tournament. A win adds 1 to the winning score of a player while a loss adds nothing. After the round robin tournament is finished the players are ...
2
votes
2answers
637 views

Total Order Relation

Given $X = \{ a , b , c \}$ and $R = \{ (a,a) , (b,b) , (c,c) , (a,b) , (a,c)\}$ Is $R$ a total order on $X$? I know that total order requires the relation to be comparable on all elements, ...
1
vote
1answer
66 views

I want to show that $\mathrel{R_1}$ and $\mathrel{R_2}$ are a partial order on $\mathbb N$, how would I do this?

Let $\mathrel{R_1}$ and $\mathrel{R_2}$ be relations on $\mathbb N$ defined by $x\mathrel{R_1}y$ if and only if $y = a + x$ for some $a \in\mathbb N_0$. $x\mathrel{R_2}y$ if and only if ...
2
votes
1answer
40 views

Is this complete partial order?

Is $(\mathbb{N} , \#)$ complete partial order, where $m\#n$ iff $(\exists k \in \mathbb{N})m=kn$. I proved it's partial order. For completeness I take directed subset and I know there is upper bond ...
0
votes
1answer
57 views

Let $A$ denote a closed subset of $\mathbb{R}.$ Is it true that for all $B \subseteq A,$ if $B$ has a supremum, then $\mathrm{sup}(B) \in A$?

Let $A$ denote a closed subset of $\mathbb{R}.$ It seems obvious that for all $B \subseteq A$ we have that if $B$ has a supremum, then $\mathrm{sup}(B) \in A$. Perhaps this is trivial, but I cannot ...
2
votes
1answer
70 views

Can the obvious “product” of complete atomistic Boolean algebras be realized as a categorial product?

Let $X$ and $Y$ denote sets, and $\eta_X,\eta_Y : X,Y \rightarrow X+Y$ denote the natural injections to the disjoint union. Then intuitively, the "product" of the Boolean algebras $2^X$ and $2^Y$ ...
6
votes
1answer
160 views

Reference Request on Order Theory topics

I am looking for some references (especially a good recent book) that covers important topics involving partial orders such as: order polytopes, sorting/selection in partially ordered sets, upper and ...
2
votes
1answer
30 views

When can complete dense linear orders be made into topological fields?

By a "complete dense linear order," I mean a dense linear order in which every nonempty subset with an upper bound has a least upper bound. The canonical example, $\mathbb{R}$, is a topological field ...
1
vote
1answer
56 views

Is this a partially ordered set?

I was wondering if partially ordered sets could have loops in their diagrams. For example isn't the $S=\{1,2,3\}$ and relation $R=\{(1,1),(2,2),(3,3),(1,2),(2,3),(3,1)\}$ a partially ordered set that ...
1
vote
1answer
481 views

If a partial order has just one unique maximal element, must that element be a greatest element of x?

I believe that it does not have to be a greatest element, because to be a greatest element it must be comparable to all the x in X. I just don't know how to go about proving this.
3
votes
1answer
110 views

Is there anything wrong with this use of the axiom of choice?

I have a proof of the following theorem: Let A be a finite set and X be a perfectly normal topological space, and let $\{(A,\succsim_x): x\in X\}$ be a family of binary relations on $A$ satisfying ...
1
vote
2answers
888 views

How to prove a total order has a unique minimal element

Let $R$ be a total order on set $S$. Prove that if $S$ has a minimal element, than the minimum element is unique. I have difficulties with proofs. I know any graph of a total order is a straight ...
1
vote
1answer
131 views

How to tell if relation on set is a partial order when relation is defined as a set of ordered pairs?

Determine whether $R$ is a partial order on set the $S$ and justify your answer. $S=\{1,2,3\}$ and $R=\{(1,1),(2,3),(1,3)\}$. So the job is to consider if $R$ is reflexive, antisymmetric and ...
1
vote
2answers
121 views

$\mathbb R\times\mathbb R$ not order isomorphic to $\mathbb R$

I am trying to show that if you use the lexicographic ordering induced by $\mathbb R$ on $\mathbb R\times\mathbb R$ they are not isomorphic. Is it enough to use the counter-example that whilst $(1,0) ...
2
votes
1answer
69 views

A representation of well-orderings?

Is there a well-ordering $P$ of the set of real numbers $\mathbb{R}$ such that there is NO function $f: \mathbb{R}->\mathbb{R}$ satisfying the property: for all $x,y \in \mathbb{R}$, $xPy$ iff ...
1
vote
1answer
74 views

Contractibility of topological spaces associated to posets

Suppose $\mathcal{P}$ is a partially ordered set. To $\mathcal{P}$ we can associate a simplicial complex $K(\mathcal{P})$ whose $n$-simplices are the chains of length $n+1$ in $\mathcal{P}$. Since ...
0
votes
1answer
183 views

union of cyclic groups

Let $p$ be a prime integer. Let $C(p^n)$ be the cyclic group of order $p^n$ ($C(p^n)=\{z \in C\mid z^{p^n}=1\}$ and let $C(p^\infty)$ be the union of the groups $C(p^n)$, i.e., $C(p^\infty)=\{z\in ...
1
vote
1answer
72 views

Prove anti-symmetric-ness of partial ordered set in lattice.

Prove anti-symmetric-ness of partial ordered set in lattice. Definition: If $(A, \le_{A})$ is a lattice and $C$ is a set, $([C \rightarrow A], \le)$ is also a lattice. And $\rightarrow$ is defined ...
0
votes
1answer
141 views

Prove transitivity of partial ordered set in lattice.

Prove transitivity of partial ordered set in lattice. I am given this If $(A, \le_{A})$ is a lattice and C is a set, $([C \rightarrow A], \le)$ is also a lattice. And $\rightarrow$ is defined as ...
4
votes
1answer
101 views

order preserving implies isomorphism

Let $M = (M, <)$ and $N = (N, <)$ be two dense totally ordered sets without endpoints. Let $F$ be the collection of order preserving maps between finite subsets of $M,N$ respectively. ...
2
votes
1answer
33 views

Finding order properties in the relation $aSb \iff \exists k \in \mathbb{N} : b = ak$

An order relations exercise I just did. I think it's fine, but the second proof felt a bit too wordy or discursive, instead of going straight to the point with brief and accurate statements. How could ...
0
votes
0answers
224 views

Finding the first, last, minimal and maximal elements in these relations.

I'm now learning about relations of order. This is what I gather: First element: Precedes all elements Minimal elements: Have no predecessors. The first element is always a minimal. Last element: ...
2
votes
1answer
309 views

How many possible DAGs are there with $n$ vertices

I am have $n$ vertices and trying to enumerate all possible DAGs $\theta$ over $n$. How many DAGs are there? For example when $n=2$, there are 3 possible DAGs and when $n=3$ I tried the following: ...
3
votes
0answers
254 views

Power-set in Hypercube: historical background of indexing each term like Hasse Diagram?

My instructor wants references about the indexation over the hypercube, related question here, he does not believe that I was the first who used it -- [update] thanks to a comment, the name is Hasse ...