Questions tagged [relations]

For questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric, etc), a composition of relations, or anything else concerning a relation on a set.

Filter by
Sorted by
Tagged with
0
votes
1answer
28 views

If R,S, and T are binary relations on a nonempty set, which of these following statements are true and why? [closed]

$T \circ (R \cap S) = (T \circ R) \cap (T \circ S)$ $T \circ (R - S) = (T \circ R) - (T \circ S)$ $(R \cup S) \circ T = (R \circ T)\cup(S \circ T)$ $(R-S)\circ T = (R \circ T ) - (S \circ T)$
0
votes
1answer
25 views

equivalence relation and corresponding equivalence classes

On the set of integers $\mathbb{Z}$ consider the following relation: $$ xRy \Leftrightarrow x-y\; is\; even $$ Prove that R is an equivalence relation and specify the corresponding equivalence classes....
0
votes
0answers
30 views

Can this be solved by mathematical induction?

So this is my question: $R$ is a binary relation on set $S$. $R_0$, $R_1$, $R_2$…. are defined as below: $R_0 := I = \{(x,x) : x ∈ S\}$ $R_{n+1} := R_n ∪ (R;R_n)$ for $n >= 0$ ($(R;R_n)$ implies R ...
0
votes
1answer
14 views

How is transitive closure of a relation related to the cardinality of the set?

This is my question, and I don't know how to approach it. $R$ is a binary relation on set $S$. $R_0$, $R_1$, $R_2$…. are defined as below: $R_0 := I = \{(x,x) : x ∈ S\}$ $R_{n+1} := R_n ∪ (R;R_n)$ for ...
1
vote
1answer
17 views

Prove that for every $X \in \mathscr{P}(A)$ there is exactly one $Y \in [X]_R$ such that $Y \cap B = \emptyset$

This is an exercise from Velleman's "How To Prove It". I strugled with this problem for a while, so I just want to make sure that it is correct. Suppose $B \subseteq A$, and define a ...
-1
votes
1answer
55 views

How do I answer this question on relations?

I am unable to understand what this question means (except that I is the identity relation). Would really appreciate a simple explanation of what it is saying, and also some hints/tips on how to ...
3
votes
1answer
5k views

Example of an antisymmetric, transitive, but not reflexive relation

The question I'm tackling right now is this: Give an example of a relation R on a set S that is not reflexive, transitive and not symmetric. My answer: Let S = {1,2,3} and let R = {(1,1), (2,2), (1,...
0
votes
0answers
45 views

Why, exactly, does reflexivity depend on the domain of the relation?

For many properties of binary relations, like symmetry, asymmetry, and transitivity, it does not depend on what domain of the relation we are considering. More precisely, given a binary relation $R$ ...
0
votes
0answers
22 views

Is the relation $fRg$ iff $\exists k > 0 \mid f(x) + k < g(x + k)$ on real functions transitive?

Is the relation on the set of real functions $fRg$ iff exists $k > 0$ such that for all $x \in \mathbb{R}$, $f(x) + k < g(x + k)$ transitive? I have proved that it's not reflexive, not symmetric,...
0
votes
0answers
19 views

Which of the following relations on $\mathbb{R}$ are equivalence relations?

This is an exercise from Velleman's "How To Prove It": Which of the following relations on $\mathbb{R}$ are equivalence relations? For those that are equivalence relations, what are the ...
0
votes
0answers
24 views

Questions on determining if some relations are reflexive, symmetric or transitive. [closed]

Math Question: Suppose that R1={(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}, R2={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}, R3={(2,4),(4,2)}, R4={(1,2),(2,3),(3,4)}, R5={(1,1),(2,2),(3,3),(4,4)}, R6={(1,3),(1,4),(...
7
votes
4answers
2k views

What binary relation is neither symmetric, nor asymmetric nor antisymmetric?

I thought it was the relation $\varnothing$, but the answer in the textbook I am using does not mention this as a possible answer. I don't understand why it can't be the answer. Could anyone explain?
6
votes
1answer
926 views

Is a transitive and Euclidean relation necessarily symmetric?

The Wikipedia article on Euclidean relation reads: A transitive relation is Euclidean only if it is also symmetric. Only a symmetric Euclidean relation is transitive. It seems to be claimed that ...
0
votes
0answers
10 views

Equivalence of partial cyclic orders

I am studying partial cyclic orders (https://en.wikipedia.org/wiki/Partial_cyclic_order). Assuming we have two arbitrary partial cyclic orders of the same size on a set of letters, e.g. (from the ...
0
votes
1answer
41 views

If a relation is euclidean, is it necessarily asymmetric?

$R$ is relation on set $A$, that is $R\subseteq A \times A $. $R$ is euclidean if $(\forall x,y,z\in A)(xRy\land xRz \Rightarrow yRz)$. $R$ is asymmetric if $(\forall x,y\in A)(xRy\Rightarrow \lnot(...
21
votes
2answers
666 views

What is the smallest digraph whose reflexive, symmetric, transitive closures (in all combinations) are distinct?

For any given directed graph, we may consider the various closures of it with respect to reflexivity, symmetry, and transitivity, in any combination, like this: For the particular graph shown above, ...
3
votes
1answer
58 views

Closure-sequence-lengths in graphs

There are three familiar operations on digraphs: symmetric closure, transitive closure, reflexive closure. If we call these $S, T, R$, then we can take sequences of them, computing things like $TSTSR(...
4
votes
3answers
2k 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
2answers
28 views

is the binary relation "strictly higher than'' antisymmetric?

A order on a set X is a binary relation ≻,defined as:x≻y if x≽y and ¬y≽x. Is that binary relation antisymmetric?
0
votes
3answers
33 views

A real life example of equivalence class? [closed]

It's easy to find an example of equivalence relation, but I am not able to find a real-life example for equivalence class.
1
vote
1answer
13 views

Should a partial order and total order be related in the context of the “condition” specified in the relation?

I think using examples would convey my question the fastest. Let there be a set $A = \{ 1,2,3,5,10 \}$. Let $R$ be relation such that $a | b$. Note that in this case $a | b$ is what I mean by "...
0
votes
1answer
19 views

What does it mean by “A total order,$T$, $⪯$ is said to be compatible with the partial order $R$ if $aRb$ implies a $⪯$ b”?

In this definition: A total order, $T$, $⪯$ is said to be compatible with the partial order $R$ if $aRb$ implies a $⪯$ b There are 2 parts I am confused about. The 1st part: "with the partial ...
2
votes
1answer
24 views

Is the relation $R:=\{(1,2),(1,3)\}$ transitive on $M=\{1,2,3\}$ with $R\subseteq M\times M$?

Is the relation $R:=\{(1,2),(1,3)\}$ transitive on $M=\{1,2,3\}$ with $R\subseteq M\times M$? I think it's transitive, because we don't have elements that satisfy $xRy \land yRz $ and therefore $\...
1
vote
1answer
49 views

Transversal of an equivalence relation

Define a relation on $\mathbb{R}^2$ by $(a, b)\sim(c, d)$ if and only if $(c-a, d- b) \in \mathbb{Z}^{2}$. Prove that $\sim$ is an equivalence relation. Identifying $\mathbb{R}^2$ with the plane in ...
0
votes
0answers
21 views

need help proving the functions to be injective. [closed]

I am trying to prove the functions to be injective and in my opinion G is not injective. Even if I am right, i have no idea how to prove other than simple direct proof. Same with the function F. ...
0
votes
2answers
30 views

Is this ordered set a Lattice?

So I have this problem: Let $S$ be the set of all reflexive, symmetric relations on $\mathbb N$, $A$ the set of all reflexive antisymmetric relations on $\mathbb N$. Now consider the set $M=S\cup A$. ...
0
votes
1answer
41 views

Proving equivalence relation

Let $Q$ be the following subset of $\mathbb{Z}\times \mathbb{Z}$: $Q=\left \{ (a,b)\in \mathbb{Z}\times \mathbb{Z}: b\neq 0 \right \}$ Define the relation $\sim $ on $Q$ as $(a,b)\sim (c,d)\...
0
votes
2answers
51 views

Is $|x-y| \le 7$ symetric relation?

to prove $(x-y)$ divisible by $3$ as symmetric we use this method: let $xRy$ belongs to $A$ $$ \begin{align} (x-y)&=3k \\ -(x-y)&=-3k \\ (y-x)&=3(-k) \end{align} $$ therefore $yRx$ also ...
-1
votes
1answer
70 views

Value For Which $x^k+y^k=1$ Matches $(x-1)^2+(y-1)^2=1$

Compute the real value $k$ for which the graph of $x^k+y^k=1$ is the same as the lower half of $(x-1)^2+(y-1)^2=1$ over $(0,1)$ or show that no such $k$ exists. I came up with this while daydreaming. ...
0
votes
1answer
35 views

Hasse diagram for the relation $\{(a,a),(a,b),(a,c),(b,a),(b,b),(b,b),(b,c),(c,a),(c,b),(c,c)\}$ on set $M=\{a,b,c\}$

Hasse diagram for the the relation $\{(a,a),(a,b),(a,c),(b,a),(b,b),(b,b),(b,c),(c,a),(c,b),(c,c)\}$ on set $M=\{a,b,c\}$ I tried to make the Hasse-Diagram for the relation. But as every element is ...
-1
votes
0answers
19 views

math2 relations

please help me with answering this question In a list of two hundred numbers, some numbers are written in red pencil and some are written in blue pencil. If we erase all red numbers, we are left with ...
1
vote
1answer
27 views

Fake proof, symmetric and transitive relation is already reflexive

Let $R$ be a symmetric, transitive relation. If $(x, y) \in R$ then the symmetric property implies that $(y, x) \in R$. Using the the transitive property upon $(x, y)$ and $(y, x)$ we can conclude $(x,...
-1
votes
2answers
39 views

Transitive relation.

I have read transitive relation, if $a\mathrel R b$ and $b\mathrel Rc$ then $a\mathrel Rc$. But suppose we have a set of first cousins. $$\mathrel R: \{(a,b),(a,c)\}$$ Where $a$, $b$ and $c$ are first ...
0
votes
1answer
18 views

Proving transitivity with Power Set Relation?

I have this question and am having trouble proving transitivity for this: For every $n \in \mathbb{N}$ let $\sim_n$ be the relation on $\mathcal{P}([n])$ specified by $A \sim_n B$ if and only if $A \...
0
votes
4answers
49 views

Can someone please help me on this reflexive, transitive, and symmetric problem?

Let $A = \{1,2,3\}$. Write the ordered pairs for a binary relation R on A which is reflexive and symmetric, but not transitive. From my understanding is when listing if we want reflexive we need every ...
0
votes
0answers
55 views

Number of Antisymmetric Relations that are both Reflexive and Symmetric

I came across this question that tells us to validate the following statement- For every non-empty finite set X, there exists a unique antisymmetric relation on X that is both reflexive and symmetric ...
1
vote
1answer
44 views

Subtracting a relation from a set

I encountered the notation $A/ \sim_{N}$ where $(A, +)$ is an abelian group and $N \subset A$ is a subgroup. The relation $\sim_{N}$ on $A$ is defined by: $a\sim_{N}b \iff a-b \in N$. What exactly ...
0
votes
2answers
42 views

Total Order Definition Motivation

A Relation $R$ is a strict total order on $A$ if the following are true for all $x,y \in A$: $(i) \hspace{.75in}\neg xRx \hspace{.75in} \text{(irreflexive)}\\ (ii) \hspace{.30in} xRy \wedge yRz \...
1
vote
2answers
16 views

$A = \{1; 2; 3; 4; 5; 6\}$ and define $aRb$ if a has remainder ≤ 1 when divided by b. Give the domain and range of $R$.

$A = \{1; 2; 3; 4; 5; 6\}$ and define $aR\mkern 1mub$ if $a$ has remainder ≤ 1 when divided by $b$. E.g. $4R\mkern 1mu3$ since $ \ 4/3 \ $ has a remainder of $1$, but not $2R\mkern 1mu5$ since $2/5$ ...
0
votes
1answer
40 views

Show that a binary relation ($a \le b$) or ($a = b$ and $c \leq d $) is an order relation

I have to show that if there are $a + bi$, $c + di$ where $a,b,c,d\in C$ and $i=\sqrt(-1)$ and also $a + bi \preceq c + di \iff $ $(a <b)$ or ($a=b$ and $c \leq d$) the $ \preceq$ is an order ...
0
votes
1answer
19 views

How do I prove or disprove these relation compositions? [closed]

So I am not told if these statements are true or not (although they appear true). I am asked to either prove them in general terms, or disprove them with specific examples. I am confused about ...
0
votes
1answer
16 views

Composition of a Realtion with identity is the relation itself

I am completely lost as to how to prove the following, although it appears straightforward. I know how this holds for functions, but how do I prove it specifically for relations? I need to provide a ...
1
vote
4answers
46 views

Let $R$ be an equivalence relation on set $A$. Prove that for any $x,y \in A$ either $[x] = [y]$ or $[x] \cap [y] = \varnothing$.

For any $x$ and any $y$ $(x,x) \in R$ and $(y,y) \in R$ (since $R$ is reflexive) So there exist $[x]$ and $[y]$ equivalence classes for $R$. When $[x]$ and $[y]$ are equivalence classes of $R$ then, ...
0
votes
1answer
43 views

Let $R$ be an equivalence relation on a set $A$. Prove that if $y\in [x]$ then $[x] = [y]$ for any $x\in A$.

$y \in[x]$ $\to (x,y) \in R$ $\to (y,x) \in R$ (since $R$ is symmetric) $\to x \in [y]$. Therefore $$\tag{1} y\in [x] \to x \in [y].$$ Let $x \in [y]$ $\to (y,x) \in R$ $\to (x,y) \in R$ (sine $R$ ...
1
vote
1answer
60 views

If a relation is defined such that $R=\{(A,B)\mid A \subseteq B\}$ then, I understand that, it's reflexive and transitive but is it symmetric.

$$R=\{(A,B)\mid A \subseteq B\}$$ $R$ is assumed to be a relation on a collection of sets Since $A$ is a subset of itself, the relation is reflexive. And if $A$ is a subset of $B$ which is, in turn, a ...
0
votes
1answer
46 views

Reflexivity of a relation $R$ transfered to other relations

Let $ R $ be a relation on $ E $. Demonstrate that: $ R $ is reflexive then $R \subseteq R.R$ and $R$.$R$ are reflexive too; Here is my work though confused about few steps: $R$.$R$ = {$(x,y) | \...
0
votes
1answer
23 views

Relation that is reflexive but not transitive or similar.

During class we had to come up with relations that are reflexive, but are not transitive or similar. I know the definitions of these terms. If we have a relation defined by the triple $$r = (A, B, R)$$...
1
vote
1answer
973 views

Correct definition of composite relations?

I can't seem to wrap my head around composite relations. According to Grimaldi in "Discrete and Combinatorial Mathematics", it is defined as: If $A, B$ and $C$ are sets with $R_1 \subseteq A \times ...
1
vote
1answer
845 views

Discrete math: how to start a problem to determine reflexive, symmetric, antisymmetric, or transitive binary relations

I need to determine if the following relation is reflexive, symmetric, antisymmetric, and/or transitive. I have been reading a lot of similar posts about these topics on here, but I am still stumped. ...
2
votes
2answers
34 views

proving a relation has the transitive property

I am trying to solve the following question: For all $ f,g∈ \Bbb N^ \Bbb N $ we say that f and g are almost identical if there does not exist $ X⊆ \Bbb N,where|X|=∞$ ,such that $ ∀i∈X:f(i)≠g(i) $ ....

1
2 3 4 5
79