1
vote
2answers
26 views

Lattice from Preorder

I have seen many examples defining a lattice over a partially ordered set $(P, \sqsubseteq)$ together with a greatest lower bound $\sqcap$, a least upper bound $\sqcup$ and a top $\top$, and bottom ...
0
votes
0answers
16 views

order definition [closed]

i'm in desperate need of your much appreciated expertise with trying to define the following order relation, guess it might be somewhat near a lexicographical order, not a straightforward alphabetical ...
0
votes
0answers
22 views

Prove that this partial order relation is a chain with infinite length.

The natural numbers are denoted as a divisibility partial order prove that this relation is a chain with infinite length.
1
vote
1answer
56 views

Proving the dual and self-dual of a poset.

The dual of a poset $(S \leq)$ is the poset $(S, \geq)$, where for all $x,y \in S$ $x \leq y$ if and only if $ y \geq x$. A poset is self-dual if it is isomorphic to its dual. Questions: Verify ...
4
votes
2answers
90 views

Is $a \le b$ a true statement if $a < b$? [duplicate]

My question is: Is $a \le b$ true if $a < b$? For instance: Is $3 \le 4$ a true statement? I think yes, because $a \le b$ is defined as $a < b\vee a = b$ and this should be true, even if $a = ...
6
votes
2answers
263 views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
5
votes
1answer
57 views

Question about sets of well-orders and isomorphisms between well-orders

I was thinking about this problem in trying to better get a feel for and understand well-orders (I'm trying to learn some set theory) - right now, I'm not really hoping for anybody to supply me with a ...
1
vote
1answer
50 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$. ...
1
vote
1answer
67 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
51 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 ...
0
votes
1answer
87 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
1answer
20 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
66 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: ...
0
votes
1answer
71 views

Is this poset a lattice?

Given the set $\Bbb Z^+\times\Bbb Z^+$ and the relation $$\begin{align*} (x_1,x_2)\,R\,(y_1,y_2)\iff &(x_1+x_2 < y_1 + y_2)\\ &\text{ OR }(x_1 + x_2 = y_1 + y_2\text{ AND }x_1 \le y_1)\;: ...
0
votes
3answers
83 views

How to show that $ \succ acyclic \implies \succ asymmetric $

For a preference relation defined as $$ \succ := \{ (x,y) \in X\times X : x\ is\ better\ than\ y \}$$ one has to show that $$ \succ acyclic \implies \succ asymmetric $$ whereas $$ acyclic := ...
0
votes
0answers
175 views

Is = (equality) a partial order relation?

We know that a partial order relation is a relation which is reflexive , antisymmetric and transitive. Example: (x,y) belongs to R iff x=y. For A={1,2,3}, we get R= {(1,1), (2,2), (3,3)}. Now R is ...
0
votes
1answer
100 views

Partial order relation

Define the relation $\leq$ on a boolean algebra $B$ by for all $x,y\in B$, $x\leq y \iff x\lor y=y$, show that $\leq$ is a partial order relation. First of all what exactly does boolean ...
0
votes
2answers
69 views

Proving well ordering is total relation

Assuming R is well-ordered relation on a set A. Wikipedia claims that every well ordered relation is also a total one.Even tough in first sight it seems trivial, how can I prove it?
4
votes
2answers
83 views

Finitely many minimal elements

I've been working on various exercises to get a better understanding of some topics for an upcoming course. I have a relation $R$ on $\mathbb{N} \times \mathbb{N}$ defined as follows: $(x_0, x_1) R ...
5
votes
2answers
254 views

Ordering the field of real rational functions

Perusing the Wikipedia article on ordered fields, I encountered an interesting statement, a variation of which I am now trying to prove. Basically, I am trying to show that the set of real rational ...
1
vote
1answer
56 views

Question about suprema/infima of partially ordered subsets

This is another clarifying question; alas, I find myself confused once again by a seemingly innocuous statement in my lecture notes. Let $S$ be a subset of a partially ordered set $(T, \preceq)$, and ...
0
votes
1answer
69 views

Down-set closure of subsets

I am confused by the following statement in my lecture notes on down-set closure of subsets: "The family of down-sets containing a given subset $E \subseteq S$ is nonempty since $E \subseteq S$ and ...
3
votes
2answers
36 views

Question about the definition of the upper set

As I understand it, a subset $L$ of a partially ordered set ($S, \preceq$) is called a down-set or lower set if for any $s \in L$ and $s' \preceq s$, we have $s' \in L$. Now, my question is can we ...
2
votes
1answer
95 views

Some (in)equalities about binary relations

Let $\Phi\subseteq (A\times A)\times(A\times A)$, $F_0,F_1\subseteq A\times A$ (for some set $A$) be binary relations. I will denote $\pi_0$ and $\pi_1$ the projections of a cartesian product of ...
0
votes
1answer
52 views

Question about posets and maxima/minima

A thought just occurred to me, thinking about posets and maxima/minima... This is a "little" question just to make sure I am really grasping the definitions here: if $E$ is partially ordered by a ...
1
vote
2answers
315 views

equivalence relations and partial ordering

Let $A$ be a set with $6$ elements, $R$ be a relation on $A$ and $n = |\{(x, y) \in A \times A : xRy\}|$. (a) If $R$ is an equivalence relation on $A$, then what is the maximum value of $n$? (b) If ...
1
vote
2answers
124 views

Partially ordered set Question : $A=\{1,2,3,4,5,6\}$ ,$R =\mathcal P(A) \times \mathcal P(A) $

I`m trying to prove that this relation is partially ordered set: $A=\{1,2,3,4,5,6\}$ $R =\mathcal P(A) \times \mathcal P(A) $ $(B,C)R(D,E) \Longleftrightarrow (B \subset D) \vee ((B=D)\wedge(C ...
0
votes
1answer
114 views

Show that a relation is a partial ordering

Show that the relation $R$ on $\Bbb N$ given by $aRb \text{ iff } b = a2^k$ for some integer $k\ge 0$ is a partial ordering.
0
votes
1answer
121 views

Union of two partial orderings

Suppose S and R are partial orderings. Does is necessarily mean that $R \cup S$ (union) is a partial ordering? If not what conditions would have to be met for it to be a partial ordering?
2
votes
3answers
65 views

Composition $R \circ R$ of a partial ordering $R$ with itself is again a partial ordering

If $R$ is a partial ordering then $R\circ R$ is a partial ordering. I cannot seem to prove this can anyone help ?
2
votes
2answers
59 views

Name of the order with irreflexivity, antisymmetry and transitivity?

I have an order otherwise poset aka partial order but it is irreflexive so relationships such as 1R1 and 2R2 are impossible. What is the name of this order?
1
vote
1answer
98 views

A generalization of Galois connections

Let $f(x)\ast y \Leftrightarrow x\ast g(y)$ for some binary relation $\ast$ and functions $f$ and $g$. This is a generalization of Galois connections. Are things like this studied before? Note that ...
2
votes
1answer
61 views

“Lexicographic order” without priority, but with ties, how to define / what's the name?

I'm searching for an ordering principle which combines two (or more) preorders, akin to the lexicographic order, but not quite: I'm looking for an ordering principle that does not priorities, but ...
0
votes
0answers
131 views

Is lexicographic order complete?

I was wondering, if the lexicographic order in $\mathbb{R}^2$ is complete or not? I guess it isn't but I dont find any counterexample. Complete means: For every partition of $M$ into two disjoint ...
1
vote
1answer
76 views

How is the Power set without the original set a partial order?

This is a past exam question. Let S = {a,b,c} Define $\mathcal{P}(S)$ as the power set of S. Consider $\mathcal{P}(S)\setminus S$ Explain how this structure illustrates the concepts of partial ...
2
votes
1answer
100 views

Can a Partial Order be symmetric in addition to its properties?

For example,a relation,R defined on integers. $R = \{(a,b)\mid a^3=b^3\}$ Could this be partial order?
2
votes
1answer
63 views

Proof for a creating a partition of a countable set using chains in partial orders.

Definition: A partition of a set $A$ is a set of nonempty subsets of $A$ called the blocks of the partition, such that  every element of $A$ is in some block, and  if $B$ and $B'$ are different ...
0
votes
1answer
130 views

The proper subset relation and strict partial order

The proper subset relation, $\subset$, defines a strict partial order on the subsets of $[1,6]$, that is $pow[1,6]$. (a) What is the size of a maximal chain in this partial order? Describe one. (b) ...
5
votes
3answers
157 views

Determine if the following is a partial order, and if so, is it a total order?

I'm having trouble figuring out how I can solve this... I've never been good with formal proofs. $$(\mathbb{R},\preceq), a\preceq b\iff a^{2}\leq b^{2}$$ I can easily see that it's Reflexive: ...
0
votes
2answers
41 views

Why am I getting that minimal elements are equivalent to the minimum?

I have these two definitions, about minimals and minimums in an order relation: $b$ is minimal in $B<=>¬\exists:(x \in B \land x \prec b)$ and also equivalent to $ \forall x,[(x \in B \land x ...
1
vote
1answer
99 views

Total Ordering and relation

Consider the relation $<$ on $\mathbb{Q}$ defined by: $(m, n) < (j, k) \iff jn-mk \in \mathbb{N}.$ Where $m, j \in \mathbb{N}$ and $n, k\in\mathbb{Z}$ I want to show that $<$ is a total ...
3
votes
2answers
96 views

If $\sim$ is an equivalence relation on $X$, and there is a strict total order on $X/\sim$, what kind of ordering does $X$ have?

I would like to know if there's a special name for this kind of ordering. When I say there is a strict total order on $X/\sim$, what I mean is that two distinct elements in the same equivalence ...
2
votes
3answers
206 views

Why is 'Antisymmetry' named so?

So when we talk about order relations for the familiar number systems, we are always introduced to the antisymmetry property which is $x \le y, x \ge y \implies x=y$. When I think of the word ...
2
votes
1answer
156 views

Pointwise order of the Cartesian product of two preordered chains

Definitions: (From Categories for Types by Roy L. Crole.) A preorder on a set $X$ is a binary relation $\leq$ on $X$ which is reflexive and transitive. A preordered set $(X, \leq)$ is a set equipped ...
0
votes
1answer
124 views

$<$ on a preorder is a strict partial order

Definition: Suppose $X$ is a preorder. Define $x < y$ as $x \le y$ and $y \not\le x$ for each $x, y \in X$. Question: Show that this gives a strict partial order on $X$.
1
vote
1answer
166 views

Uniqueness of meets and joins in posets

Exercise 1.2.8 (Part 2), p.8, from Categories for Types by Roy L. Crole. Definition: Let $X$ be a preordered set and $A \subseteq X$. A join of $A$, if such exists, is a least element in the set of ...
2
votes
1answer
192 views

Preorders, chains, cartesian products, and lexicographical order

Definitions: A preorder on a set $X$ is a binary relation $\leq$ on $X$ which is reflexive and transitive. A preordered set $(X, \leq)$ is a set equipped with a preorder.... Where confusion cannot ...
4
votes
2answers
125 views

$<$ in a preorder

The author of the book I am studying defines $<$ for a poset as If $x, y \in X$, where $X$ is a poset, then we shall write $x < y$ to mean that $x \le y$ and $x \ne y$. From this, I can ...
4
votes
1answer
264 views

Lexicographical order - posets vs preorders

I found the following definition for lexicographical ordering on Wikipedia (and similar definitions in other places): Given two partially ordered sets $A$ and $B$, the lexicographical order on the ...
2
votes
0answers
190 views

Examples of proofs by induction with respect to relations that are not strict total orders.

I have read this Wikipedia article and found it fascinating. I came across it after I tried to prove a certain statement with a method resembling induction in the set of natural numbers but ordered by ...