This tag is intended for questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric,...), composition of relations and similar stuff. More-or-less the things about relations taught in the first elementary set theory or discrete math course.

learn more… | top users | synonyms

1
vote
0answers
97 views

Total order and inf,min,max,sup of set?

i have a relation $\mathbb{R\subseteq M\times M}$ , which is not even a partially order : $M=\{x\epsilon\mathbb{R}$:$-3$$\leq x\leq3\}, R=\{(x,y):x>y\}$ Well what i'm trying to do; to make this ...
2
votes
2answers
872 views

Problem about Hasse diagrams

Can someone help me to solve this problem. Are these Hasse diagrams lattices?
-2
votes
2answers
203 views

Does complementary relation($\overline R$) is transitive?

Let $R$ be a relation that is transitive. Does complementary of $R$ ($\overline R$) is transitive?($\overline R$is hold transitive)
72
votes
12answers
11k views

Are there real-life relations which are symmetric and reflexive but not transitive?

Inspired by Halmos (Naive Set Theory) . . . For each of these three possible properties [reflexivity, symmetry, and transitivity], find a relation that does not have that property but does have ...
-2
votes
2answers
165 views

Proving equivalence,partial order on a binary relation

Let $R$ be a relation on the set $\Bbb R$ of real numbers where real numbers $x,y$ satisfy $xRy$ if and only if $e^{x-y}$ is an integer. Is $R$ an equivalence relation on $\Bbb R$? Is it a partial ...
6
votes
2answers
976 views

Can a relation with less than 3 elements be considered transitive?

The generalize rule for a transitive relation is a -> b b -> c therefor a -> c If an element has less than 3 elements, can it still be transitive? If ...
2
votes
3answers
335 views

Proving that a relation is transitive

During one of my recent tests, I was given the following problem: "Let the relation $R$ be defined on all finite sets so that $ARB$ if and only if there exits a bijection from $A$ to $B$. Verify that ...
1
vote
0answers
171 views

Partially ordered set proof

I'm trying to proof if the following Relations R ⊆ M×M total order or partially order are. $M = \{1,2,3\} , R = \{(x,y) : x|y\}$ $M = {\bf Z} , R = \{(x,y) : x\vert y\}$ $M = {\bf N}, R = \{(x,y): y ...
0
votes
1answer
157 views

About proving $f(S \cup T) = f(S) \cup f(T)$

I have an example is like this Let f be a function from the set A to the set B. Let S and T be subsets of A. Show that $f(S \cup T) = f(S) \cup f(T)$ $answer:$ $y\in f(S\cup T) ...
3
votes
3answers
3k views

Prove that the intersection of two equivalence relations is an equivalence relation.

I am reading this chapter of the Book of Proof, and I'm stuck at the Exercise 10 of section 11.2. It is as follows. Suppose $R$ and $S$ are two equivalence relations on a set $A$. Prove that $R ...
3
votes
4answers
90 views

Different equivalence relations of the set $\{a,b\}$

In the book of Richard Hammack, I come accross with the following question: There are two different equivalence relations on the set $A = \{a,b\}$. Describe them. OK, I found that the solution ...
1
vote
1answer
88 views

Is this relation really transitive?

$$A=\{(0,0),(0,1),(1,0),(1,1),(0,2),(2,0),(2,2)\}$$ Hi guys can somebody tell me why this relation is not transitive? I know that is reflexive and symmetric and also thought that is transitive but my ...
0
votes
1answer
229 views

Composition of two relations

Among all students in a classroom we have a binary relations $\mathcal {R,S}$. Student A is in relation with student B, formally (A,B) $\in$ $\mathcal R$, iff - "A sits in the same row as B and B is ...
1
vote
4answers
481 views

Proving reflexivity, symmetry and transitivity on a relation.

I am trying to see if the following relation is reflective, symmetric and transitive: $(i, j),(k, l)$ are in relation R if: $(i < k$ $\land $ $k \le j \le l) \lor (k < i$ $\land$ $i \le l \le j ...
0
votes
1answer
28 views

Relations on N+, that show specific properties.

Im struggling to understand whether the relation "is a permutation of" on N+
2
votes
3answers
5k views

Antisymmetric Relations

Given a set $\{1,2,3,4\}$, how is the following relation $R$ antisymmetric? $$R = \{(1, 2), (2, 3), (3, 4)\}$$ Note: Antisymmetric is the idea that if $(a,b)$ is in $R$ and $(b,a)$ is in $R$, then ...
0
votes
1answer
106 views

How to determine properties of a given relation?

I would like a more thorough understanding of how to determine the properties (reflexivity, symmetry, anti-symmetry, transitivity, completeness, asymmetry) of relations. I understand the idea in ...
1
vote
1answer
907 views

Antisymmetric and irreflexive relation which is not asymmetric

Can anyone give me a counterexample for a relation $R\subset M\times M$ for the statement $$R\text{ antisymmetric} \wedge R\text{ not reflexive}\implies R\text{ asymmetric}$$
0
votes
1answer
82 views

Set Relation question

Let each of $A, B$, and $C$ be a set and suppose $A \subseteq B \cup C$. Prove that $A \cap B \cap C = \varnothing$. I start this problem by letting $x$ be an element of $A \subseteq B \cup C$ and ...
1
vote
1answer
58 views

Is the relation $\geq$ always a partial order for the real numbers and integers

I was looking at particular examples and I observed that they were always reflective, antisymmetric and transitive.
1
vote
1answer
70 views

Operations and relations

To what extent do operations and relations overlap? Is there some more general structure that encompasses both of these things? Thanks
0
votes
2answers
1k views

How can I prove that if a relation is symmetric then its inverse is also symmetric?

Prove that if $R$ is symmetric, then $R^{-1}$ is symmetric, $R$ being a relation over $A$, and $\lnot(A = \varnothing)$. This came as an exercise in my book. I couldn't do anything - there is ...
2
votes
3answers
62 views

How to verify if $aRb \leftrightarrow a - b \le 10$ is total?

Book exercise: $R$ is a relation over $\mathbb Z$. $aRb \leftrightarrow a - b \le 10$ Verify if it is reflexive, symmetric, transitive, antisymmtetic or total. I can tell it is ...
1
vote
4answers
204 views

If $aRb \land bRc$ never occurs, is a relation considered transitive?

Studying relation properties. My definition of a transitive relation is as follows: A relation is transitive if and only if $\forall a,b,c \in A [aRb \land bRc \implies aRc]$ My question is: if ...
4
votes
2answers
112 views

Equivalence relations on classes instead of sets

Can someone please explain to me how to deal with equivalence relations on classes instead of sets? Is there some sort of generalisation of relations? Thank you
0
votes
3answers
53 views

What is $D$ in $G \cap G^{-1} \subseteq D$?

My book has an example that goes like this: $$A = \{1,2,3,4\}$$ $$R = (G,A,A)$$ Prove that $R$ is antisymmetric if and only if $G \cap G^{-1} \subseteq D$ We have to prove two implications. The ...
2
votes
0answers
619 views

Equivalence of norms is a equivalence relation

Two norms $||-||_1 $, $||-||_2$are equivalent if: for two constants $a,b$ and $x$ from $V$ a vector space over a field it holds that : $$a||x||_1\leqslant ||x||_2\leqslant b||x||_1.$$ This is a ...
3
votes
2answers
228 views

Tricky transitive relations

I have a set $A = \{1, 2, 3\}$. Relation $S = \{(1, 1), (1, 2), (3, 1) \}$ Relation $T = \{(1, 1), (3, 2), (3, 1) \}$ $S$ is not transitive, but $T$ is transitive. Why is that? A relation $R$ ...
0
votes
3answers
64 views

Why is the composition of relations $R$ and $S$ written $S \circ R$ instead of $R \circ S$?

This is really basic (I'm new to this stuff), and doesn't even matter at all - But I'm just curious: From my book: If $R = (G,A,B)$ and $S = (H,B,C)$ the composition of $R$ and $S$ is known as ...
1
vote
1answer
2k views

Relations , Discrete Mathematics: SETS

Let $A = \{a, b, c\}$ and $R = \{(a, c), (b, b), (c, a)\}$ be a relation on $A$. Determine whether $R$ is reflexive, symmetric, transitive and anti-symmetric, or not.
0
votes
2answers
61 views

How do you find $R^2$ and $R^3$ and $R\circ T$?

Given relations $R$ and $T$ on $\{a,b,c,d,e\}$ where $R = \{(a,b), (a,e), (b,c), (c,e), (e,e)\}$ where $T = \{(a,d), (d,e), (e,a)\}$ I don't have an equation, so how do I find $R^2$ and $R^3$ and ...
1
vote
2answers
942 views

How to prove reflexive property of equality of two mappings

Title says it all. To give a concrete example: Let $X$ and $Y$ be non-empty sets and $f: X \rightarrow Y$ a mapping. Prove that for relation defined by $\{(x_1,x_2) \in X^2 : f(x_1) =f(x_2)\}$ ...
1
vote
2answers
74 views

Equivalence relations, operator

$\def\op{\mathbin{\#}}\def\R{\mathbin R}$Original question: A logical operation between two propositions $p$ and $q$ is denoted as $p\op q$. It is only true when $p$ is true and $q$ is ...
1
vote
2answers
1k views

Proving a relation is partial ordering

I have a problem proving that a very simple relation is partial ordering. It is defined explicitly (i.e. with pairs of numbers) and I have no idea how to do a formal proof for its antisymmetric ...
2
votes
1answer
1k views

Amount of transitive relations on a finite set

In counting the amount of relations on finite sets, we can quite easily count the amount of reflexive and symmetric relations on a finite set. We just consider (in accordance with the definition of a ...
0
votes
1answer
131 views

Quotient set univocally defined

I know that what I am going to ask is pretty basic, borderline stupid, nevertheless it is bugging me. By definition I know that given a set $A$ and a equivalence relation $\rho$, then the items ...
1
vote
1answer
119 views

Is the relation $x+3y = 0$ antisymmetric for all real numbers?

I don't think so, because it is never $aRb$ nor $bRa$ and it is never $aRa$ or $bRb$, thus it is always false, but I don't know if I understood what antisymmetric means exactly.
1
vote
1answer
97 views

How come the relation $\subseteq $ on the power set $2^N$ is antisymmetric?

where $2^N$ is the power set with $n$ elements (subsets). Does it hold true to any set or just the power set $2^N$?
1
vote
1answer
76 views

What's the payoff associated with the definition of a relation as an ordered triple?

We can define a binary relation as a set of ordered pairs. Alternatively, we can call the set of ordered pairs the "graph" of the relation, and define the relation itself as a triple $(X,Y,f)$, where ...
1
vote
1answer
250 views

Transitive closure of binary relation

How would you make a transitive closure on something like this: Among all students in a classroom we have a binary relation $\mathcal R$. Student A is in relation with student B, formally (A,B) $\in$ ...
1
vote
2answers
1k views

Finding all partial order relations on a set

Suppose I have a set $A$ such that $A$ = $\{1, 2, 3, 4, 5\}$ (or $A$ = $\{1, 2, 3, 4\}$ or $A$ = $\{1, 2, 3\}$ or any other finite small set). How can I find the total number of partial order ...
2
votes
2answers
897 views

Answering Questions For A Poset.

The question I am looking at is, "Answer these questions for the poset $(\{3,5,9,15, 24,45\},|)$." a) Find the maximal elements. b)Find the minimal elements. c) Is there a greatest element? d) Is ...
6
votes
4answers
3k views

Understanding equivalence class, equivalence relation, partition

Im having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions. 1) The collection of ...
2
votes
3answers
2k views

Reflexive Transitive Closure

The problem I am working on is, "Show that a finite poset can be reconstructed from its covering relation. [Hint:Show that the poset is the reflexive transitive closure of its covering relation.]" I ...
0
votes
1answer
126 views

Establishing A Covering Relation

The problem I am working on is, "What is the covering relation of the partial ordering $\{(A,B)|A⊆B\}$ on the power set of $S$, where $S=\{a, b, c\}$?" I am reading the answer key, and I can follow ...
1
vote
1answer
2k views

Constructing A Hasse Diagram Using The Covering Relation

I am still having a little difficultly with the covering relation, specifically that when y covers x, $x \prec y$ there is no element in between them, $ x \prec z \prec y$, where x,y, and z are ...
2
votes
1answer
324 views

reflexive, transitive and symmetric relations.

Problem Let $R:=\{(a,b) \in \mathbb{N^2}\mid a \leq b\}$. Is $R$ reflexive, symmetric, antisymmetric, transitive? The portrayed relation is reflexive because both $a \leq b$ and $b \leq ...
1
vote
3answers
3k views

Definition Of Lexicographic Ordering

I am reading about about lexicographic ordering, and I want to make sure I am understanding it properly. Lexicographic ordering is defined to be the cartesian product of two, or more, posets. So, $A_1 ...
3
votes
1answer
398 views

Incomparable Elements In A Poset

The problem I am working on is, Find two incomparable elements in these posets. a) $(P(\{0,1,2\}),⊆)$ b) $(\{1,2,4,6,8\},|)$ For a, I said that $R \subseteq p(\{0,1,2,3\}) \times p(\{0,1,2,3\})$, ...
0
votes
1answer
84 views

Am I correct? State the necessary and sufficient condition for R to be an equivalence relation on A.

Let R be a relation on a given nonempty set A. State the necessary and sufficient condition for R to be an equivalence relation on A. My attempt The conditions for any equivalence relation are ...