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
0answers
33 views

How do I prove this relation is an equivalence relation?

Given a set $A=RxR$, consider a relation R defined by $(a,b)R(c,d)$ iff $b=d$ How do I prove that R is an equivalence relation?
1
vote
3answers
35 views

Proving $xRy\iff xy^{-1}\in\ker(f)$ is equivalent relation, where $f:(G,.) \to (H,.)$ is homomorphism of groups $G$ and $H$.

I know for sure it is but I failed to prove how. I tried to use the homomorphism definition where $f(x*y^{-1}) = f(x)*f(y^{-1})$ but I didn't see a pattern.
0
votes
2answers
21 views

Why do we sum to prove the transitive property?

In the relation $x − y = 4m$, to prove the transitive property, we do the following: $$(x − y) + (y − z) = 4m + 4n = 4(m + n)$$ Why?
0
votes
1answer
22 views

Equivalence classes for a relation between integers

I have the following relation in $\mathbb Z$: $x \sim y$ iff $x-y$ is a multiple of $4$. How do I approach this?
1
vote
1answer
29 views

Suppose $[a], [b] \in \mathbb{Z}_n$ and $[a]\cdot[b] = [0]$. Is it necessarily true that either $[a] = [0]$ or $[b] = [0]$?

Let $n \in \mathbb{N}$. Let $R$ be the equivalence relation $\equiv \pmod{n}$. Suppose $[a], [b] \in \mathbb{Z}_n$ and $[a]\cdot[b] = [0]$. Is it necessarily true that either $[a] = [0]$ or $[b] = [0]$...
1
vote
1answer
34 views

A binary relation contained in its square

My colleague (I guess, investigating structure of specific semigroups) is looking for references about binary relations $R\subset X\times X$ such that $R\subset R\circ R$, that is for each $(v,u)\in R$...
2
votes
1answer
27 views

Use a reflexive and transitive closure to transform an antisymmetric and acyclic relation into a partially ordered set.

The relation $R=\{(x,S_1),(S_1,S_2),(S_2,S_3),(S_3,S_4),(S_4,y)\}$ is antisymmetric and acyclic but not transitive or reflexive. We know that any antisymmetric and acyclic relation can be turned into ...
1
vote
2answers
14 views

Showing that a relation is neither an equivalence relation nor a partial order

Say we have a relation $R$ on $\mathbb{Z} \times \mathbb{Z}$ such that $(a, b) R (c, d)$ if $a^2 + b^2 \leq c^2 + d^2$ So to prove that $R$ is not an equivalence relation we need to show that $R$ ...
1
vote
1answer
25 views

Show that $P$ is a partition of the corresponding set $A$ and define the equivalence relation induced by partition $P$.

$A = \mathbb N$ and $ P = \{ \{ m \in \mathbb N: m \ \ \text{is a multiple of} \ \ 3\}, \{ m \in \mathbb N: m \ \ \text{is not a multiple of 3}\} \} $. How can I define the equivalence relation ...
0
votes
1answer
17 views

Union of equivalence relation, problem If R ∪ S is an equivalence relation on A, then R and S are equivalence relations on A.

Let A be a non-empty set and let R and S be relations defined on A. If R ∪ S is an equivalence relation on A, then R and S are equivalence relations on A. how can i prove it? i think it is not ...
1
vote
1answer
33 views

Equivalence relation proof, problem $x∼y \iff x^2 − 2x + 1 = y^2 + 4y + 4$

Determine if the following relationships are equivalent. If they are, determine the equivalence classes, give a set of indices and the quotient set. Sketch out the graph of each relationship (whether ...
0
votes
1answer
46 views

Are sets predicates?

In so many different instances we need to be able to construct sets of functions. The first axiom of set theory (at least in the order that I learned) says that $a\in b$ is only a proposition if a and ...
0
votes
1answer
26 views

Is $G=\{(x,y)\in \mathbb{Z}\times\mathbb{Z}:x+y<4\}$ irreflexive?

Let $G=\{(x,y)\in \mathbb{Z}\times\mathbb{Z}:x+y<4\}$ Is $G$ irreflexive? I know $<$ is an irreflexive relation. But how to show it? How do I do this? The Reflexive and Irreflexive property ...
0
votes
1answer
35 views

Is this Hasse diagram drawn correctly? [closed]

Is this Hasse diagram of the divisibility relation when $A = \{3,4,5,6,7,8,9,10,11,12\}$ correct? Thanks for help. Image
0
votes
1answer
7 views

How does a transitive extension differ from a transitive closure?

Quoting an example from C.L Liu's Discrete Mathematics: Let R be a binary relation on A. The transitive extension of R (let's denote it as $R_1$) is a binary relation on A such that $R_1$ contains R. ...
0
votes
2answers
71 views

Are the set of all convergent geometric series whose sum is a rational number is countable? [closed]

I tried this way: As the sum of convergent geometric series is $\frac{a}{1-r}$ and $-1<r<1$. Moreover sum is also a rational number. So $a$ and $r$ should be rational numbers. As rational ...
-1
votes
0answers
31 views

Binary Relation [closed]

I am not sure how to solve these problems. Can someone guide me through the steps. Prove that for any binary relation $R$ and $S$, the following identities hold: (a) $(R^{-1})^{-1}=R$ , where $R^{-1}...
2
votes
1answer
56 views

Prove if $B$ has a smallest element, then this element is unique.

Working on the book: Daniel J. Velleman. "HOW TO PROVE IT: A Structured Approach, Second Edition" (p. 206) Theorem 4.4.6. Suppose $R$ is a partial order on a set $A$, and $B \subseteq A$. If $...
-2
votes
1answer
19 views

How to find the pre-image for [-3,3] [closed]

question image Determine wether or not each of the following relations are functions. If a relation is a function, find its range. If it is not a function, give reasons. Find the inverse if it has ...
0
votes
1answer
14 views

Define a relation R on Z × N by (a, α)R(b, β) if and only if aβ = bα. Prove that R is a reflexive relation.

I'm a bit confused about how to prove that R is reflexive. By definition, R, a relation in a set S, is reflexive if and only if ∀x∈S, xRx. Since (a, α)R(b, β), we know that aβ = bα. Then to prove ...
0
votes
1answer
28 views

Find these relations on $\mathbb{N}$.

Give an example of a relation on $\mathbb{N}$ which is, reflexive, transitive but not symmetric transitive, symmetric but not reflexive reflexive, symmetric but not transitive anti-symmetric, ...
-1
votes
1answer
52 views

Find $f(x,y)$ when $f(x)$ and $f(y)$ are known [closed]

I have a problem related to the combination of 2 relations. I know the relation between the diffusion coefficient and the temperature (say D(T)) and I know the relation between the diffusion ...
0
votes
1answer
16 views

How to find the pre-image of a relation given the intrrval

enter image description here The questions are in the link above, can someone please explain how to find the pre-image of the interval B[-2,2]?
6
votes
1answer
59 views

What do you call a relation that isn't finer than any equivalence, besides the full relation?

In other words, this is a relation whose "equivalence closure" is the full relation. The term "weakly connected" comes to mind naturally, since if you draw a directed graph, with a vertex coming from $...
0
votes
1answer
26 views

Find the number of symmetric closure

There is a set A with n elements. R is relation of set A. R has 3 elements. When n ≥ 4, the symmetric closure of the R was obtained. Find a minimal and maximum value of number of R elements. I want ...
0
votes
1answer
25 views

Why the homegeneous relation $\mathcal{R}$ over a set $E$ below, isn't transitive? I concluded that it was a transitive property.

Why the homegeneous relation $\mathcal{R}$ over a set $E$ below, isn't transitive? I concluded that it was a transitive property. A couple has 5 children: Andrew, Billy, Carl, Dariel and Elizabeth: ...
0
votes
0answers
16 views

Finding the turning point of a relation

I was wondering on how I can find the turning points of this relation: $(x^2-7x+5)^2-y^2+7y-5=0$ The relation is two oval shapes that are seperated. Theres a desmos graph. https://www.desmos.com/...
0
votes
0answers
9 views

Graphically represent ternary relation mapping

We usually see mapping in the form of 2-ary relations. binary mapping However, how do you represent mappings for 3-ary relations?
0
votes
1answer
24 views

Must a binary relation on a set $X$ be defined for all elements in $X$?

When defining a binary relation $R \subseteq X^2$, does there have to be a definite "true" or "false" value for a pair $(x,y) \in R$, or does it only have to be "true" to be included, and excluded ...
0
votes
1answer
30 views

Writing Euclid's proposition “Ratios which are the same with the same ratio are also the same with one another” in contemporary style [closed]

I need to write the Proposition 11 in Book 5 of Euclid's Elements according to contemporary style. It states that: Ratios which are the same with the same ratio are also the same with one another....
0
votes
0answers
14 views

Discrete mathematics proofs related in Relations [duplicate]

The question is: A cycle in a relation R is a sequence of k distinct elements a_0, a_1, ..., a_(k-1) of A where ∈ R for each i ∈ {0, 1, ..., k-1}. A cycle is nontrivial if k ≥ 2. Prove that there are ...
0
votes
0answers
21 views

Find the number of elements of reflexive relation on a set of $n$ elements

I do know that $2^{n^{2}-n}$ reflexive relations can be created on $n$-element set. The problem: Relation $R$ can be created on $n$-element set $A$. if such relation $R$ is reflexive, then how many ...
0
votes
0answers
26 views

Question on the meaning of cartesian product

I don't understand what they mean by on set $A$ and the meaning of binary expansion of same length does the question mean cartesian product?
1
vote
1answer
22 views

Prove that this function is a order relation

Let M be a set and denote by $\mathbb{F}$ the set of all functions $f:M \rightarrow \mathbb{R}$, show that, $ f \leq g \Leftrightarrow \forall a \in M : f(a) \leq g(a) $ is a order relation for $(f,g) ...
2
votes
3answers
36 views

What is the inverse relation of R

Determine the inverse relation $R^{−1}$ for the relation $R = \{(x,y) : x + 4y \text{ is odd}\}$ defined on $\mathbb{N}$. does this mean that $R^{-1} = \{(y,x):y+4x \text{ is odd}\}$ ?
0
votes
1answer
22 views

How is it defined that $a_1 \times b_1 < a_2 \times b_1$ and that $a_1 \times b_3 < a_3 \times b_1$?

I am reading Topology by James Munkres and he defines the dictionary order relation as: Definition Suppose that $A$ and $B$ are both sets with order relations $<_A$ and $<_B$ respectively. ...
0
votes
0answers
26 views

Transitive Relationships

I am examining transitive relationships and understand the premise that if $x \rightarrow y \rightarrow z$, then the relation needs to contain $x \rightarrow z$ to be considered transitive. My ...
0
votes
2answers
23 views

Is a relation given by {(a,a), (b,b), (c,c), (a,b), (a,c)} on set {a,b,c} a partial order?

Is was a TRUE/FALSE question in a discrete math exam. I answered False because I believe the relation is neither transitive or not transitive so the definition for a partial order doesn't apply (...
0
votes
1answer
23 views

Calculating a seen height of an object from a scope

I have an object that is 0.6 meter in diameter that stand at 1000 meter away from me, I have a scope with magnification of X15-40. How can I calculate the size of the image that I will see through ...
3
votes
1answer
83 views

Algorithm for generating subsets of finite sets

Obviously there is no method to generate a sequence of subsets of $\mathbb N$ that, in analogue with diagonalizing elements in $\mathbb N^2$, gives an arbitrary number of arbitrary elements. But is ...
3
votes
2answers
82 views

Is this another definition for inverse relation?

We know that if $R\colon A\to B$, we can define the inverse relation as follows: $$R^{-1}=\{(y,x)\in B\times A\mid(x,y)\in R\}.$$ Now I want to know if this set, let's call it $R\:'^{-1}$, is the same ...
2
votes
0answers
29 views

Inductive closure of a relation?

I did not really know whether to ask this here or in MathOverflow. On the one hand, I have a maths degree and this is part of my PhD research on computer science, and I am pretty sure this is not a ...
0
votes
3answers
44 views

How do I prove this using an injection (if needed)?

I'm trying to prove the following: Show that if $A$ and $B$ are sets and $A\subset B$, then $|A|\leq |B|$. This is what I came up with: Proof: Let $A$ and $B$ be sets where $A\subset B$, therefore $...
1
vote
2answers
20 views

Listing the equivalence classes of a specific relation on a set

Say we have the set $S=\{1, 2, 3, ..., 20\}$ and we define our relation (R) as For every $x, y \in S$, $xRy$ iff for every prime $p, p | x \iff p | y$ This relation is an equivalence relation (as ...
0
votes
0answers
15 views

Check, if A ~ B have a relation

Let $$A \sim B \iff \exists v \in \mathbb{R}^2 \setminus \left( \begin{array}{c} 0\\ 0\\ \end{array} \right) : \mathcal{L}_{A,v} \cap \mathcal{L}_{B,v} \neq \emptyset$$ be a relation on $\mathbb{R}^...
0
votes
2answers
41 views

Prove the following statement are equivalent

Let $|A| = |B| = n$ and let $f : A \to B$ be everywhere defined function. Prove that the following three statements are equivalent. $f$ is one to one. $f$ is onto. $f$ is one-to-one correspondence (...
0
votes
3answers
57 views

Is the circle a function? [closed]

My friend asked me this question. 1) Are i) $y=x^3+1$ (or in general $y=f(x)$) & ii)$y-x^3=1$ (or in general $\phi(x,y) = c$) both same? He thinks 1st one is a function $f:x \to y$ and 2nd ...
0
votes
0answers
20 views

How do we factorize the path algebra by the relation?

I read Representation Theory of Artin Algebras by Auslander, Reiten and Smalo and I have a question about this example. Can you please explain why does the basis of $\Lambda \bar{e_1}$ contain $\bar{\...
0
votes
2answers
46 views

symmetric but not tranisitive nor reflexive function

Let's say there is a function $g: B \rightarrow B$ and $B$ is some set. A relation $Rx$ over set $B$ is when $a Rx b$ if $g(a) = b$. In this case, what kind of function $g: N \rightarrow N$ ...
0
votes
1answer
18 views

The complement of the converse relation is the converse of the complement

Given a binary relation (dyadic relation) $R$ over two sets $X$ and $Y$, The complement of the converse relation is the converse of the complement,in other words: $$\overline{R^{T}}={\overline ...

1
2 3 4 5
75