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

3
votes
1answer
128 views

Relations and transitivity

I am just now starting to grasp the concepts of transitivity in relations and I have the following question: In my textbook, it is noted that $R = \{(1, 1), (1, 2), (2, 1)\}$ is not transitive. ...
0
votes
3answers
115 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 := ...
2
votes
3answers
211 views

$(a,b)R(x,y) \iff ay=bx$ is an equivalence on $\Bbb Z \times (\Bbb Z\setminus\{0\})$ [duplicate]

Define a relation $R$ on $\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$ by $(a,b)R(x,y)\iff ay=bx.$ $a)$ Prove that $R$ is an equivalence relation. $b)$ Describe the equivalence classes ...
2
votes
1answer
66 views

Is this an equivalence relation?

I think the wording is throwing me off, and I also haven't done math in 4 months so basically my mind is scrambled eggs. Let $\sim$ be a relation on $\Bbb Z$ defined by letting $m \sim n$ if ...
1
vote
2answers
394 views

A function on binary relations

Let $\rho$ is a function mapping every binary relation $f$ (on some set $U$) into a function which maps binary relations into binary relations by the formula $$(\rho(f))(g) = f\circ g.$$ Is $\rho$: ...
0
votes
2answers
84 views

Prove $f(\cap \scr{C}) \subset \cap f(\scr{C})$. Confused on why it's not a symmetric relation?

If there are any minor mistakes in my proof, it would be great if they were pointed out - but let it not be the central discussion. I'm rather concerned why the answer is $\subset$ instead of $=$ ...
0
votes
1answer
55 views

Binary relations: Can someone see if I have done this correctly?

I would appreciate some help. Here are the binary relations: Below we are defining some binary relations over the set {a, b, c} S ₁: {〈a, a⟩, 〈a, b⟩, 〈b, b⟩, 〈b, c⟩} S ₂: {〈a, a⟩, 〈a, b⟩, 〈b, b⟩} ...
0
votes
1answer
171 views

Which one is a transitive relation?

I'm trying to figure out which one of these relations are transitive relation(s) ...
0
votes
1answer
182 views

Why is phi symmetric and transitive?

Take A={0,1}. Now if we find all the subsets of binary relation i.e. A × A we get one of them as R=Ø. Now I can understand that R does not have (0,0) and (1,1). So R=Ø is not reflective. But how is it ...
1
vote
4answers
110 views

Finding relation between elements

I have seen the following type of problems in reasoning tests: If $A \le B = C > F < G = L$ , then which of the following is true? a. $A < G$ and $A >F$ b. $C >F$ c. $G =B$ ...
0
votes
0answers
575 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 ...
2
votes
2answers
3k views

How to find the number of anti-symmetric relations?

I know that given a set $A = \{1, 2, 3, ... , n\}$, the total number of relations on $A$ is $$2^{n^2}$$ The number of reflexive relations is $$2^{n^2 - n}$$ The number of symmetric relations is ...
1
vote
1answer
421 views

Binary relation composition (with itself)

To start off on the right foot. I've read: Relations (Binary) - Composition but I still can't really figure it out because those deal with finite sets. I have a infinite set: $R= \{(n,n+2)|n \in ...
2
votes
1answer
46 views

What is the term for a relation whose inverse relation is serial?

A relation $R$ is serial iff $\forall x, \exists y, xRy$. What is the name of the inverse property stating that $\forall y, \exists x, xRy$? And is there a name for the property which is the ...
0
votes
1answer
27 views

Create a simple expression that is larger than zero if and only if a-b > 0 and c-d < 0

Ok, this is simple but I cant figure out a solution to it. I have four signals, a, b, c, d. I want to generate a signal when a-b > 0 and c-d < 0. This signal should be in the form of an algebraic ...
0
votes
1answer
577 views

How to prove “If $R$ is transitive, then $R^n$ is transitive.”?

I can understand $R^n$ is $R$'s subset, but I can't understand why $R^n$ is transitive,too. I used mathematical induction: Basis step: Let $n = 2$. If $a R^2 b$, $b R^2 c$, I need to prove $a R^2 c$. ...
2
votes
1answer
436 views

Composition of two symmetric relations

Let $R1$, $R2$ be symmetric relations on a set. I want to prove that $R1\circ R2$ is symmetric if and only if $R1\circ R2=R2\circ R1$. I have tried a few problems of this type by doing something like ...
1
vote
1answer
55 views

$xRx'$ and $yRy'$ implies $f(x,y)Rf(x',y')$

Let $R$ be a binary relation. Is there a name for the following property? $f(x,y)Rf(x',y')\quad$ if $xRx'$ and $yRy'$ Note:$f$ is a function.
1
vote
1answer
33 views

Relations properties

Let $\mathrm M = \Bbb R; \mathrm R = \{(x,y)\mid x = y\}$ Investigate wheter the relation is reflexive, transitive, symemtric, antisymmetric. Reflexivity $\rightarrow (\forall x \in \mathrm ...
0
votes
2answers
56 views

Justify a relation

let $\mathrm A = \Bbb Z \text{ and } R = \{(a,b) \in \mathrm A\times \mathrm A | a \lt b \}$ investigate whether the relationship is symmetric or antisymmetric. So (...) Symetric [...
0
votes
1answer
216 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 ...
3
votes
2answers
252 views

Elegant solution of a problem about binary relations

Let $f$, $g$, $a$, $b$ are binary relations on some set. I want an elegant proof that $(a\circ f^{-1})\cap(g^{-1}\circ b) \ne \varnothing \Leftrightarrow ...
1
vote
1answer
117 views

Relations that are: reflexive but not transitive; transitive but not symmetric; symmetric but not reflexive

I have an incomplete answer to my question. Can anyone help me answer the last two parts. My question is: Find example of a set $S$ and three relations $R_1$, $R_2$, $R_3$ on it such that ...
0
votes
0answers
56 views

using entropy to calculate the relatedness of two columns in a database

There are two columns(x, y) in a database, I want to define the "relatedness" of the two columns. First i try to use I(x, y) (mutual information) to define the relatedness, then: date, ...
-1
votes
1answer
46 views

Proof the following - language

Theorem $4$. A language $A$ is regular iff there exists a regular expression $\alpha$ such that $A = L(\alpha)$. Check whether the following equations are correct. $\left((a\cup ...
0
votes
2answers
153 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?
1
vote
2answers
1k views

Reflexive but not Transitive relation

What is an example of a relation $\mathscr{R}$ on a set $S$ such that $\mathscr{R}$ is reflexive but not transitive? Here is what I have come up with. Let $S = \mathbb{Z}$. Then let $\mathscr{R} = ...
1
vote
1answer
632 views

Transitivity of Relations and Eulerian Cycles

Question: Let $R$ be the relation $\{(1,1),(2,3),(2,2),(3,2),(3,3)\}$ on the set $S=\{1,2,3\}$. Is $R$ an equivalence relation? If $R$ is, describe the partition $\mathscr{P}$ determined by $R$ by ...
2
votes
1answer
116 views

Deriving the Axiom of Infinity

I'm currently reading about recursion, working on various exercises since I haven't formally studied the material before. The main book that I'm following is Kunen's Set Theory book There's an ...
0
votes
4answers
104 views

bijection in $\mathcal P \left({S}\right)$ and $\mathcal P \left({S}\right) \times \mathcal P \left({S}\right)$

given that ${S}$ is countably infinite set. is there any bijection exist between $\mathcal P \left({S}\right)$ and $\mathcal P \left({S}\right) \times \mathcal P \left({S}\right)$. Here $\mathcal ...
0
votes
1answer
71 views

Bijection between $\mathbb{R} \times \mathbb{R}$ and $\mathbb{R}$

How can we define bijection in between $\mathbb{R} \times \mathbb{R}$ and $\mathbb{R}$? Even giving a injection from $\mathbb{R} \times \mathbb{R}$ to $\mathbb{R}$ and vice-versa will work.
1
vote
2answers
176 views

smallest element in Partial ordered set

Every finite partial order has a smallest element, where an element x $\epsilon$ S is said to be the smallest if for all y $\epsilon$ S; it is the case that (x,y)$\epsilon$R. here R is relation ...
1
vote
1answer
137 views

Reflexive, symmetric, transitive tests - did I do it right?

Z = { ..., -2, -1, 0, 1, 2, ... } Relation ~ is defined such that a~b <=> a evenly divides b. I said that this function IS reflexive because a evenly divides a. I said that this function is NOT ...
3
votes
1answer
149 views

$\beta$ as the relation “is a brother of”

So I have a question about relations. In particular, here is the formal question: Let $\beta$ be the relation "is a brother of" and let $\sigma$ be the relation "is a sister of". Describe ...
0
votes
2answers
235 views

Prove the set relation without using Venn diagrams

Prove the set relation without using Venn diagrams: $$(A \cup B) \cap (B \cup C) \cap (C \cup A) = (A \cap B) \cup (A \cap C) \cup (B \cap C) $$ I have proven that the RHS leads to LHS, but not the ...
3
votes
2answers
94 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 ...
3
votes
1answer
62 views

Relation as the Union of 4 Relations

I'm trying to write the relation $$\rho=\{\langle{x},y\rangle\in{\mathbb{R}\times\mathbb{R}}: |x|+2|y|=1\}$$ as the union of 4 relations. Is it enough to just think of this as a diamond and use the ...
3
votes
2answers
79 views

Proving that if $\bar{R}$ transitive (where $R$ equivalence relation), $|A/R|=1$

Let $A\neq\emptyset$ a set and $R\subseteq A\times A$ equivalence relation s.t the complementary relation $\bar{R}=(A\times A)\setminus R$ is transitive. Prove that $|A/R|=1$ (cardinality of ...
3
votes
1answer
133 views

About binary relations under certain conditions and their composition

(I have edited it. The previous version was with errors.) Let $A$ be a set. Let $\pi_0$, $\pi_1$ be projections from $A\times A$. Let $F_0$, $F_1$, $G_0$, $G_1$ be binary relations on $A$. Let ...
-1
votes
2answers
81 views

Abstract Algebra topic: Equivalence relations [duplicate]

If R1 is reflective and not transitive, R2 is transitive but not symmetric and R3 is symmetric but not reflexive. We need to find an example of a set S and the three relations R1 R2 R3.
5
votes
2answers
513 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
76 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 ...
3
votes
0answers
45 views

A relation on 2 countable sets [duplicate]

Let $R$ be a relation on two countable sets $A$ and $B$, where $R\subset A\times B$, with the following properties: $\forall a\in A$ the set $\{b\in B: (a,b)\in R\}$ is finite. For any finite set ...
0
votes
1answer
84 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
54 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 ...
1
vote
1answer
170 views

relations - examples and counterexamples

The question is to find an example of a set $S$ and three relations $R_1$, $R_2$, and $R_3$ on it, such that $R_1$ is reflexive but not transitive, $R_2$ is transitive but not symmetric and $R_3$ is ...
2
votes
1answer
60 views

Set Theory Relations

Given set $A={1, 2, 3}$ consider the following relation on $A$ $R=\{(1, 1), (2, 1), (3, 3), (3, 2)\}$ Which one of the following statements are true $R$ is antisymmetric and transitive $R$ is ...
1
vote
2answers
328 views

The bijective property on relations vs. on functions

I recently encountered what seems to me like an inconsistency in the usage of the term bijective. This is pretty basic stuff, but it somehow never occurred to me before. I'd like to make sure I'm ...
4
votes
1answer
113 views

Prove that $D_r \circ D_s = \{ (x,y) \in \mathbb{R}^2 \ | \ |x-y|<r+s \}$, where $D_a = \{ (x,y) \in \mathbb{R}^2\ | \ |x-y| < a \}$

Suppose $r$ and $s$ are two positive real numbers. Let $D_r = \{ (x,y) \in \mathbb{R}^2\ | \ |x-y| < r \}$ and $D_s = \{ (x,y) \in \mathbb{R}^2 \ | \ |x-y| < s \}$. Prove that $D_r \circ D_s = ...
1
vote
1answer
36 views

On equality of quotient relations

I am a non-mathematician who is taking a self-learning course in mathematics. I am studying a chapter on (equivalence)relations and I have the following question: Suppose $R$ and $S$ are ...