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

0
votes
2answers
18 views

Proving a relation is anti-symmetric and transitive

$P$ is a binary relation. $P ⊆ \mathbb{R}^2$. $P = \{(x,y): y = |x|\}$. As I understand for relation to be transitive: $(a,b) \in P$ and $(b,c) \in P$ then $(a,c \in P)$ for this particular relation ...
1
vote
1answer
26 views

Equivalence relation and class, Proof.

The relation $P$ on $ℝ$ is defined by $xPy$ iff $x^2=y^2.$ (a) Prove that the the relation $P$ is an equivalence relation. (b) Describe the equivalence class of $3$ and $0$. In order to ...
1
vote
0answers
25 views

Prove that $R_1 \cup R_2 \cup (A_1 \times A_2)$ is antisymmetric on $A_1 \cup A_2$.

Suppose $R_1$ is a partial order on $A_1$, $R_2$ is a partial order on $A_2$, and $A_1 \cap A_2 = \emptyset$. Prove that $R_1 \cup R_2 \cup (A_1 \times A_2)$ is antisymmetric on $A_1 \cup ...
4
votes
4answers
483 views

Definition of smallest equivalence relation

I came across the term 'smallest equivalence relation' in the course of a proof I was working on. I have never thought about ordering relations. I googled the term and checked stackexchange and couldn'...
0
votes
0answers
21 views

Let $L= \{(x,y)\in \mathbb R \times \mathbb R : x \leq y\}$, and let $C=\{x \in \mathbb R : x > 7 \}$. Prove that C has no L-smallest.

Definition: Suppose R is a partial order on a set A, $B \subseteq A $ and $b \in B$ . Then b is called an R-smallest element of B iff $\forall x \in B [b R x]$ Goal is to prove the following: Let ...
-1
votes
1answer
21 views

Discrete Maths Relations on the set {1,2,3,4}

I just want to make sure that I am doing these correctly. Here is what I have: Reflexive, symmetric, antisymmetric and transitive: And i have - {(1,1) (2,2) (3,3) (4,4)}. not Reflexive, not ...
0
votes
0answers
19 views

What is a transitive relation on set S

MY answer: Given r,s,t$\in S$ a transitive relation on the set $S$ is when the elements $rRs$ and $sRt$ then $rRt$ i.e., $rRs\land sRt\rightarrow rRt$ Does my definition words correct?
0
votes
0answers
21 views

Define symmetric relation R on set S

Answer: A symmetric relation R on S is that For all $x,y\in S$ such that $xRy$ implies $yRx$. meaning if the element x is related to y, then it is also true the other way around that element y is ...
-1
votes
0answers
20 views

Define and give an example of a reflexive relation R on set S

My Answer: from the definition a reflexive relation is that for all $s\in S$ we have $sRs$ . this means that the elements in set S is related to itself. For example, a set A = {p, q, r, s}. The ...
0
votes
1answer
39 views

Can someone explain why is $R=\{(1,1), (1,2)\}$ transitive?

Using a digraph I understand transitive relation to be a loop, but $R=\{(1,1), (1,2)\}$ is not a loop. Thank you for your time!
3
votes
0answers
36 views

Restriction to equivalence relation is equivalence relation

Let $\mathcal{R}$ be relation on $A$ and $A_0 \subseteq A$. The $\mathbf{restriction}$ of $\mathcal{R}$ to $A_0$ is defined to be the relation $\mathcal{R} \cap (A_0 \times A_0) $. $\mathbf{...
1
vote
1answer
39 views

Can someone explain antisymmetric versus symmetric relation of sets?

If $$A = \{1,2,3,4\} $$ and $$R = \{(3,3), (4,4), (1,4)\}$$ This example is antisymmetric but not symmetric. However, the definition of Antisymmetric taken from Merriam-Webster is this: ...
1
vote
2answers
23 views

Hasse diagrams for sorts of size 3 and 4?

Does anyone know what does the following mean? I understand that a Hasse diagram represents a given partial order but I don't seem to get this example. Below is a Hasse diagrams for sorts of size 3 ...
0
votes
2answers
22 views

What is the reflexive closure of the empty relation ∅ over a set A?

What is the reflexive closure of the empty relation ∅ over a set A? I understand that R is reflexive if A=∅, and isn't if A is nonempty. But what about the reflexive closure of R?
0
votes
1answer
29 views

Transivity / Binary relation? [closed]

Discuss the Transitivity of Binary Relations $\mathcal{S} $ $a$ on $\Bbb R $ defined by $a (x, y)$ $\in \Bbb R^2 $--> $x \leq ay$ ( for some a $ \in \Bbb R$ ) I have this assignment about ...
-2
votes
1answer
37 views

Recurrence relation general solutions [closed]

how would I go about tackling this kind of question? I'm struggling with the concept of recurrence relations. Any advice would be apreciated. Find the general solution of each of the following ...
1
vote
2answers
30 views

Where is the transistivity in this equivalence relation

The following set has been given: $A = \{1,2,3\}$, and the following relation on $A$ has been given: $S = \{(1,1),(2,1),(1,2),(2,2),(3,3)\}$. The answer says this is a valid equivalence relation. I ...
1
vote
1answer
45 views

Is the following relation a partial order?

Is the relation $R$ on $A=$ the set of all word of English, defined by $R=\{(x,y)\in A\times A: $ the first letter of the word $y$ occurs at least as late in the alphabet as the first letter of the ...
0
votes
0answers
33 views

Prove the relation $R = \{(x,y)\in \mathbb{R} \times \mathbb{R}: \text{ |x|< |y| or x=y} \}$ is antisymmetric.

Prove the relation $R = \{(x,y)\in \mathbb{R} \times \mathbb{R}: \text{ } |x|< |y|\text{ or $x=y$} \}$ is antisymmetric. Proof: Suppose $ x R y$ and $ yRx $. Then $|x|<|y|$ or $x=y$. ...
0
votes
1answer
22 views

Antisymmetric relation between two transitive relations

My task is the following: elements in set A: {a,b,c,d,e,f} relations between them: {(a,b),(b,f),(c,b),(c,d),(d,e),(e,a),(f,d),(f,e)} Question is, is the relation between them antisymmetric and ...
0
votes
0answers
10 views

Give an example showing Ran(R1 ∩ R2) ⊆ Ran(R1) ∩ Ran(R2) may not hold as an equality.

I have managed to prove Ran(R1 ∩ R2) ⊆ Ran(R1) ∩ Ran(R2), but I am having trouble finding an example that shows it doesn't hold as an equality.
2
votes
1answer
24 views

How many transitive and symetric relations that are not equivalence are in a set of $n$ elements?

I have a Set $S$, $|S|=n$, and I need to count how many symetric and transitive relations are in $S$ that are not equivalence relations. I know how to count equivalence relations (Bell number) but I ...
-3
votes
2answers
26 views

Why is this relation $R=\{ (a,b), (b,c), (a,c) \}$ transitive? [closed]

I am confused here. For the set $\{ a, b, c\}$ how is the relation $\{(a, b), (b, c), (a, c)\}$ transitive ?
0
votes
3answers
24 views

Prove transitivity or not of some relation

I'm trying to prove if this equation is an equivalence relation or not. $R =\{(x,y) \in N\times N: \mbox{There exist }m,n \in N\mbox{ such that } x^m = y^n\}$ It's relatively easy to prove both ...
1
vote
1answer
36 views

What is the term for relation whose inversion is a function?

Do we have a conventional term/name for such a relation $R$ (which is not necessarily a function) that $R^{-1}$ is a function? If not, what are your suggestions?
-1
votes
1answer
17 views

How do we show that $A$ is polynomial time reducible to itself? [duplicate]

How do we show that $A$ is polynomial time reducible to itself, i.e. that $A \le_p A$? I know how to prove that it is transitive, but I don't know how to prove it's reflexive. I'm aware that it's ...
2
votes
1answer
35 views

Why is this function well definded?

I have to take a look at the relation of $ x \sim y: \Leftrightarrow \exists k \in \mathbb{Z} : x-y=5k$ in $\mathbb{Z}$. I have no idea how to show at $\mathbb{Z} / \sim$ that the addition is well ...
0
votes
1answer
33 views

How to derive relationship between two functions

I have two functions: $f(x) = x^2 + 200$ $g(x) = (x + 8)^2$ I am interested in the relationship between the two functions in the region between the two minimums (from x = -8 to x = 0), which ...
1
vote
1answer
23 views

Let $A$ be a finite set and $\mathcal R$ an equivalence relation in A. Prove that exists a function …

Let $A$ be a finite set and $\mathcal R$ an equivalence relation in A. Prove that exists a function $f: A \to \Bbb N$ such that $\forall a, b \in A$ the following is true: $$a \mathcal R b \iff f(a) = ...
1
vote
1answer
30 views

Interpreting a first order sentence

I've been given this first order sentence with a binary relation symbol $R$: $\forall x \exists y (R(x, y) \land \forall z(R(x, z) \implies (R(y, z) \land (y=z)) ) $ We are then given two ...
1
vote
1answer
21 views

Solution check. How many relations of equivalence $R$ are there in $\Bbb N$ that verify silmultaneously the following properties.

I'm revising some old psets while preparing an exam and going through some things that I left unverified. How many relations of equivalence $R$ are there in $\Bbb N$ that verify silmultaneously the ...
0
votes
1answer
34 views

Relations and functionss

I am unsure how to do this, is it possible someone could give me a step by step guide so I can have a good understanding of it. f(x) and g(x) are defined over the real number set R as follows: $g(x) =...
1
vote
1answer
13 views

Let $H = \{2^m : m \in \mathbb{Z}\}$ & define a relation $R$ on the set $\mathbb{Q^{+}}$ of positive rationals by $a\mathbin{R}b$ iff $a/b \in H$.

Let $H = \{2^m : m \in \mathbb{Z}\}$ and define a relation $R$ on the set $\mathbb{Q^{+}}$ of positive rational numbers by $a\mathbin{R}b$ if and only if $a/b \in H$. Prove that $R$ is an equivalence ...
1
vote
1answer
82 views

How do you pronounce $\preceq$?

I've been reading about partial orders and partially ordered sets and have come across sentences like "Suppose that $\preceq$ is a partial order on $X$" and "If $x\preceq y$ and $y \preceq z$ then $x \...
2
votes
1answer
33 views

Count a Partial Equivalence Relations on a set

A Partial Equivalence Relation is a relation that is symmetric and transitive, and to count the number of equivalence relations on a set exists Bell Numbers, my question is How I can count the number ...
0
votes
0answers
14 views

Let $A$ be a nonempty set. Prove that if $S$ and $R$ are equivalence relations on $A$, then $S \cup R$ is both reflexive and symmetric.

Let $A$ be a nonempty set. Prove that if $S$ and $R$ are equivalence relations on $A$, then $S \cup R$ is both reflexive and symmetric. My method: Let $x \in A$ be given. Then $x \in S$ or $x \in R$....
3
votes
2answers
29 views

A relation $R$ is defined on $\mathbb{Z}$ by $aRb$ if and only if $2a + 2b\equiv 0\pmod 4$. Prove that $R$ is an equivalence relation.

A relation $R$ is defined on $\mathbb{Z}$ by $aRb$ if and only if $2a + 2b\equiv 0\pmod 4$. Prove that $R$ is an equivalence relation. My method: Let $a \in \mathbb{Z}$ be given. So, for any $a \in \...
1
vote
0answers
17 views

Let A be a set with $\lvert A \rvert$ = $4$. What is the max number of elements tht a relation R on A can contain so tht $R \cap R^{-1}$ = $\emptyset$

Let A be a set with $\lvert A \rvert$ = $4$. What is the maximum number of elements that a relation R on A can contain so that $R \cap R^{-1}$ = $\emptyset$? I am not sure at all how to start this ...
0
votes
1answer
14 views

Let A be the set of U. S. states. One example of a relation on A is $R = [(s,t) : s = t or s shares a border with t].

Let A be the set of U. S. states. One example of a relation on A is R = {(s,t) : s = t or s shares a border with t}. Notice that the domain of R is A, and the range of R is A. Give a different ...
0
votes
0answers
14 views

Determine whether the following relation is reflexive, symmetric, antisymmetric and/or transitive?

Q is defined on P(N) by aQb iff |a ∩ b| ≥ 2. I've concluded that it's symmetric, not reflexive, not antisymmetric and not transitive. Is this right?
0
votes
1answer
16 views

Relation that is reflexive, transitive, but not antisymmetric

A = {1,2} R = {(1,2)} I was just wondering if this relation meets the criteria.
1
vote
1answer
62 views

Are R,S and T equivalence relation or partial order relation?

Let $R$, $S$ and $T$ be binary relations defined as follows R is defined on $P(\mathbb{N})$ by $ARB$ if and only if $|A∩B| ≥ 2$ $S$ is defined on $Q$ by $x\mathbin{S}y$ if and only if $|x|=|y|$. (...
0
votes
2answers
37 views

How to tell if the relations R, S and T are reflexive, symmetric, anti-symmetric or and transitive?

Let $R$, $S$ and $T$ be binary relations defined as follows R is defined on $P(\mathbb{N})$ by $ARB$ if and only if $|A∪B| ≥ 2$ $S$ is defined on $Q$ by $xSy$ if and only if |$x$|=|$y$|. (Note that ...
0
votes
0answers
17 views

Determine whether this relation is reflexive, symmetric, antisymmetric and/or transitive?

R is defined on N × N (where N are natural numbers) by (a, b)R(c, d) iff a ≤ c and b ≤ d. I think it's reflexive and transitive. Not too sure about it being symmetric or antisymmetric. Any help ...
0
votes
1answer
33 views

What is the difference between total order relations and well order relations?

I know it has to be a partial order relation in order for it to be a well order relation or total order relation, but what are the differences between them.
0
votes
1answer
23 views

What is the difference between partial order relations and equivalence relations?

From googling it i understood that a relation is both partial order relation and equivalence relation when they are reflexive, symmetric and transitive. So it appears they are the same. But as far I ...
1
vote
1answer
21 views

Write out relation from a function

I have this problem: "Let $R$ be a binary relation $(x,y)\in R$ if and only if $f(x) = f(y)$ where $f: \{a, b, c, d\} \rightarrow \{0, 1\}$ given by $f(a) = 0$, $f(b) = 1$, $f(c) = 0$, $f(d) = 0$ ...
2
votes
1answer
44 views

Functions: Relations

I'm stuck on this question and would appreciate the solution, thanks! Let $R$ and $S$ be the relations on $A = \{1,2,3,4,5\}$ given by$$R = \{(1,2),(2,3),(3,4),(4,5)\}\\S=\{(2,3),(2,4),(3,4)\}$$...
0
votes
2answers
31 views

Prove by contradiction that If $R$ is a transitive relation on set $A$ then $R^2$ is transitive.

I saw this problem and read through it but I am still kind of confused as to what $u_1$ and $u_2$ stand for. Prove by contradiction that for a transitive relation $R$ on $A$, $R^2$ is also transitive ...