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
843 views

Determine whether each of these combinations of R 1 and R 2 must be an equivalence relation.

I have this question but not really sure how to do it when there is union and interception symbol. I am easily confuse when this 2 symbol appear. From my understanding I know that equivalence relation ...
-1
votes
1answer
57 views

What is a geometric relation?

We will call a relation geometric if $∀x, y, z(xRy ∧ xRz → yRz)$ Prove that if a relation is geometric and reflexive, then it is also symmetric. I'm trying to solve this problem but I don't ...
0
votes
0answers
33 views

Counting binary relations

Let $A$ and $B$ be finite sets, $|A| = m$ and $|B| = n$. How many binary relations are there from $A$ to $B$? As far I read from various resources, binary relations is nothing but just a typical (...
1
vote
2answers
28 views

Number of reflexive relations on the set {1,2,…,n}

I am solving questions of a bachelors exam and was unable to solve this question and i am looking for help!! Find Number of reflexive relations on the set {1,2,...,n}. I know that R is called ...
0
votes
1answer
34 views

Number of common elements in $A \times B $ and $B \times A$

This question was part of maths worksheet of my brother and I was unable to solve it. He studies in High Shcool. So, I am asking for help here. Let there are 5 common elements between A and B set. ...
1
vote
2answers
49 views

What does “$A \leq B : \Longleftrightarrow A \subseteq B$ is an order relation of $\mathcal{P}(N)$” mean?

I have read the following in some exercise for discrete mathematics. Let $N$ be a set and $\mathcal{P}(N)$ be its power set. Then $A \leq B : \Longleftrightarrow A \subseteq B$ is an order relation of ...
0
votes
0answers
32 views

Prime factors and relation

Consider the relation ~ on $ℕ$ defined as follows: $x$ ~ $y ⇔x * y$ is a square Interpret x ~ y in terms of prime factors of x and y. $ x = {P_1}^{n_1}{P_2}^{n_2}{P_3}^{n_3}{P_4}^{n_4}...{P_a}^{n_a}$ $...
-1
votes
1answer
22 views

Trying to define relationship between two numbers

I have 2 numbers 97 (F) and 415 (S) this is the key / legend. Given any number (S), commonly between 200 - 900, I am looking for "F". Where if (S) is above 415 "F" will be less ...
0
votes
1answer
20 views

Describe a specific equivalence class

Relation on $\mathbb N$: $x \sim y \iff xy$ is a square Give a description of the equivalence classes $[3]$, $[9]$, and $[99]$. I'm not sure what this question is really asking, but this is what I ...
1
vote
2answers
52 views

The relation $\sim$ in $\mathbb{R}$ is defined as: $x \sim y \iff x − y \in \mathbb{Z}$

$(a) \quad$ Show that $\sim$ is an equivalent relation. $(b) \quad$ Give $2$ distinct equivalent classes (must show they are distinct). $(c) \quad$ $[0, 1) = \{x \in \mathbb{R} \mid 0 \leq x < 1\}....
1
vote
1answer
21 views

How to find $R$ as a set of ordered pairs?

Suppose I am given a set $A = \{0,1,2,3,4,5,6,7,8,9\}$ and a relation $R$ on $A$ which is given by $x R y \iff y=2x+3.$ In order to write $R,$ how would I go answering this question? Would I just ...
0
votes
1answer
31 views

Find general solution of linear congruence equation

Congruences are beyond my understanding, I do not understand at all, if you could explain it to me as simply as possible on this example, I would be very grateful: Find a general solution of linear ...
0
votes
2answers
25 views

Algebra proof within relation problem

I need to show an equivalence relation on $ℕ$ defined as follows: $x$ ~ $y$ ⇔ $x \times y$ is a square Reflexivity: $x \times x$ is a square, so $x$ ~ $x$, so ~ is reflexive Symmetry: $x$ ~ $y$ ...
1
vote
1answer
18 views

equivalence relations counterexample

I'm asked to either prove or disprove if the relation on all integers Z is an equivalence relation for x~y if and only if x+y is divisible by 3. From my understanding, the relation can't be reflexive ...
1
vote
1answer
35 views

Determine $[1] =\{n \in\Bbb Z | 1 R n\}$

Let the relation $R$ be defined on the set $\Bbb Z$ of integers by $a R b$ if and only if $a^2 − b^2$ is an integer multiple of $3$. a) Determine whether $R$ is an equivalence relation. Either prove ...
-3
votes
1answer
44 views

If I have a certain relation R, how do I find R^2 and R^3? [closed]

Suppose I have A = {a,b,c,d} and R = {(a,b),(b,c),(c,b),(c,d)}. How do I find R^2 and R^3?
0
votes
1answer
28 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)$$...
0
votes
0answers
25 views

Relation with $sgn$

I have a problem with this task. If anyone had a similar problem it would help me. The task is: In the set $S\in[-\pi,\pi]$ a binary relation is defined ρ with $xρy⟺sgn(\sin(x-\pi))=sgn(\sin(y))$. ...
0
votes
1answer
26 views

Relation p^3 on set

For the relation p = {(1, 4), (2, 1), (2, 3), (4, 2)} on the set {1, 2, 3, 4}, determine the relation p^3. I get that p^3 is p°p°...
0
votes
1answer
32 views

Fake proof, symmetric and transitive relation is already reflexive [duplicate]

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,...
3
votes
1answer
25 views

Finding relation of two sets

If A = {1, 2, 3} and B = {1, 2, 3, 4}, would R = {(a, b) ∈ A × B | b = a^2} be {(1,1), (2,4)} since the only time that b = a^2 is true is when (A,B) = (1,1) and (A,B) = (2,4)?
0
votes
2answers
28 views

Prove that a relation is Equivalent where: $7\mid x+6y$ where x and y both come from a set of numbers (1,2,3…10) [closed]

Like I've mentioned, I need to prove that it is equivalent, and get all of its classes. Proving that it is Reflexive is super easy and I did it myself. Proving symmetry and transitivity is what ...
1
vote
0answers
21 views

Transitive closure of the relation

X={1,5,7,9} What is the transitive closure of the relation {(1,5),(5,7),(7,9),(1,7),(1,9),(5,9)} on X? I think this relation is already transitive. (1,5) (5,7) --> (1,7) already exist (1,5) (5,9) -...
0
votes
0answers
17 views

How to approach this problem ? Do we use induction or some property of relations.

For a relation R on a set X we define the symbol $R^{n}$ by induction: $R^{1} = R, R^{n + 1} = R \circ R^{n}.$ (a) Prove that if X is finite and R is a relation on it, then there exist $r, s \in \...
1
vote
0answers
21 views

Functions as arguments in relations

I have here a little problem, where I am just not really sure how to tackle this: Let R be a relation on the real numbers, with R = {(log2(x), x)| x e R+}. Determine whether this is a function and if ...
2
votes
1answer
46 views

What does $\leq ^{-1}$ mean?

Just came across a question on my homework assignment. The only thing it says is: What is $\leq ^{-1}$? It is on chapter for relations. I'm guessing it means: $R \leq R^{-1}$, for $R$ being a ...
1
vote
1answer
47 views

Relation \ Equivalence relation

I have a problem with this task. If anyone had a similar problem it would help me. The task is: In the set $S={(-2,-1,0,1,2,3)}$ the relation is defined $\rho$ with $(\forall t,m \in S) t \rho m \iff ...
0
votes
0answers
35 views

Drawing Hasse diagram

I am trying to draw a Hasse diagram for Set {(1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(3,3),(4,4),(4,5),(5,5)} I drew a diagram like this. But I am not sure about the positioning number(level) and my ...
0
votes
1answer
27 views

Showing an equivalence relation on $\mathbb Z$

Using the fact that \begin{align*}(a|b \ \land \ a|c) &\implies a|(b+c) \\ a|b &\implies a| bc \\ (a|b \ \land \ b|c) &\implies a|c \end{align*} then I want to prove $\equiv_d$ is an ...
0
votes
1answer
32 views

Prove R is antisymmetric if $R^2$ is antisymmetric

Let $R^2$ be a binary relation on some set X. I need to prove or disprove the following claim: "If $R^2$ is antisymmetric, then R is antisymmetric." I know the opposite claim (if R is ANS ...
2
votes
0answers
46 views

Prove that $(R ∪ R^{-1}) _{k^2}$ is an equivalence relation

Let $R$ is a binary relation on set a $S$ and let $R_0, R_1, R_2 \dots$ be defined as follows. $$\begin{align} R_0 & := \Delta_{S} = \{(x,x) : x ∈ S\} \\ R_{n+1} & := R_n ∪ (R;R_n), && ...
0
votes
0answers
29 views

Finding the transitive closure by using Warshall Algorithm

Let A = {1, 2, 3, 4}. R is given by matrices R and S below. Find the transitive closure by using Warshall Algorithm. These are my answers for finding the transitive closure by using Warshall Algorithm....
2
votes
1answer
25 views

Given $R$, a symmetrical relation over $A$, if $(R \circ R)$ is a function, then $R$ is a function

Given a non-empty set $A$ and the symmetrical relation $R \subset A\times A$ such that $(R\circ R)$ is a function. The exercise asks if $R$ is a function. I'm not sure if my reasoning is correct here. ...
0
votes
1answer
11 views

Is a euclidic relation not asymmetric?

The relation ${\sim}\subseteq A^2$ is called euclidic if for all $x,y\in A$ it follows that: $$x\sim y ~~\wedge ~~ x\sim z \implies y\sim z$$ The relation ${\sim}\subseteq A^2$ is called asymmetric if ...
0
votes
1answer
37 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
0answers
33 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
21 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
24 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
64 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
49 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
23 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
26 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 ...
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
950 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
12 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
48 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(...
23
votes
2answers
706 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
62 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$ ...

1
2
3 4 5
80