1
vote
1answer
14 views

Equivalence between different definitions of transitive closure

Let $W$ be an arbitrary, non-empty set and let $R$ be an arbitrary binary relation on $W$. Define the transitive closure of $R$ as $R^+ = \bigcap \{ R' \; | \; R' \text{ is a binary transitive ...
0
votes
0answers
27 views

Is this connected relation?

My task is to check if this is preference relation (connected and transitivited) $$ f \succeq g \Leftrightarrow \forall x\in [0,1] f'(x) \leq g'(x) $$ My solution is: that this relation is not ...
1
vote
0answers
29 views

A partial order with more properties than would be expected

Consider the relation: $$\langle x_1,x_2\rangle\prec\langle y_1,y_2\rangle\iff x_1,x_2,y_1,y_2\in\Bbb N\wedge x_1y_2<x_2y_1.$$ This is usually used for defining the (positive) fractions $\Bbb ...
1
vote
1answer
17 views

Antisymmetric relation (“strong” vs “weak”)

Defining: "weak antisymmetric relation": $\forall a, b \left< a,b \right> \in R \land \left< b,a \right> \in R \Rightarrow a=b$ "Strong antisymmetric relation": $\forall a, b \left< ...
3
votes
0answers
34 views

Divisibilty as relation set on $(\mathbb N \setminus \{0,1\})$

So i have to see if $\prec$ is order relation where two elements $(a,b)$ and $(c,d)$ are in relation $\prec$ if $a|c$ and $2b^{2}+6b\leq2d^{2} + 6 d$. This relation is defined on set $(\mathbb N ...
0
votes
2answers
28 views

Greatest lower and least upper bounds for a set of pairs

Had some trouble with this question in an exam recently, and wanted to make sure I reasoned correctly. The question was: $X$ is a set of pairs of real numbers $(x,y)$, with absolute values less than ...
0
votes
0answers
68 views

Have you seen this property of tolerance relations before?

Let $A$ be a set equipped with a binary reflexive and symmetric relation $\uparrow$ (such relations are often called tolerances, see also "Are there real-life relations which are symmetric and ...
1
vote
0answers
28 views

Prove/disprove questions on equivalence relations and ordered sets

If $R$ is an equivalence relation and a partial order over $A \neq \emptyset$ then every equivalence class contain at least one element. If $(A,\le)$ an ordered set, and $a\in A$ is a single ...
2
votes
1answer
72 views

what kind of relationship is “is prefix of”?

Consider the "is prefix of" relationship on a set that corresponds to the words of some alphabet. E.g. "ab" is prefix of "abc". This relationship is: antisymmetric transitive reflexive ("ab" is a ...
1
vote
0answers
15 views

Hasse Diagrams - Relations

I have the following question: Draw the Hasse diagram for the following partially-ordered set: The relation $X$ is a subset of $Y$, on the set $\{ \{0\}, \{2\}, \{0,1\}, \{0,2\}, \{2,4\}, ...
1
vote
1answer
121 views

Exercise in Well Orderings

Prove that if $\prec$ is a well-ordering on a set X and if $Y \subseteq X$, then $\prec_Y=\{(x,y) \mid (x \in Y) \wedge (y \in Y) \wedge (x \prec y)\}$ is a well ordering on Y. I am a little ...
1
vote
2answers
45 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 ...
1
vote
1answer
76 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
95 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
290 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
61 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
63 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
96 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
52 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
97 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
21 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
84 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
85 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
91 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
216 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
116 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
76 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
84 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
293 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
62 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
74 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
98 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
336 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
133 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
138 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
127 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
77 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
63 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
102 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
145 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
97 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
108 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
64 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
145 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
169 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
100 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 ...