Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [relations]

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.

1
vote
0answers
48 views

Proof: Equivalence relation for homogeneous coordinates

My geometry textbook states that the vectors $(a, b, c)^T$ and $k(a, b, c)^T$ represent the same line for any non-zero $k$; in other words, two such vectors related by an overall scaling are ...
0
votes
4answers
39 views

Discrete Math - Confused about relations where x + 2y ≤ 3

I'm a bit stuck with some questions for discrete math. For the relation R = {(x,y) : x + 2y ≤ 3}, defined by A = {0,1,2,3}, determine if it is reflexive, symmetric, antisymmetric and transitive. ...
0
votes
1answer
21 views

Proof that for binary relation following is true or prove by counterexample.

Problem Let $ R \subseteq A \times B $ and $ S,T \subseteq B \times C $. Proof following for combined binary relation or show that statement is false $$ (R \circ S) \cap (R \circ T) \subseteq R \...
0
votes
0answers
35 views

Equivalence relation for homogeneous coordinates

My geometry textbook states that the vectors $(a, b, c)^T$ and $k(a, b, c)^T$ represent the same line for any non-zero $k$; in other words, two such vectors related by an overall scaling are ...
0
votes
1answer
39 views

Suppose $(S, ∼)$ is an equivalence relation and suppose $a, b ∈ S$. Show $[a] = [b]$ if $a ∼ b$ and $[a] ∩ [b] = ∅$ if $a \not\sim b$.

I am a bit lost on this question to the point that I don't know where to start. I am confused as to how I am supposed to show this without a defined ~ relation. any help would be greatly appreciated, ...
3
votes
0answers
59 views

Proof that for binary relation following is true or prove statement is false.

Problem Let $ R \subseteq A \times B $ and $ S,T \subseteq B \times C $. Proof following for combined binary relation or show that statement is false $$ (R \circ S) \cap (R \circ T) \subseteq R \...
-2
votes
2answers
28 views

Finding the inverse function of a quadratic function [closed]

let $f:[-4,∞) \rightarrow \mathbb{R} , f(x)=-(x+4)^2 +3$. show that $f^{-1}:(-∞,3] \rightarrow \mathbb{R}, f^{-1}(x)=\sqrt{3-x}-4.$ a question from my 11th-grade maths assignment. I don't even know ...
2
votes
2answers
74 views

Proving $\cos^2x+\sin^2y=1$ is reflexive, symmetric, transitive.

I want to make sure that I got the hang of the following relations. For reflexivity, if $x=y,\cos^2x+\sin^2y=\cos^2x+\sin^2x=1 \implies xRx$, then it is reflexive. For symmetry, $xRy\implies\cos^2x+\...
1
vote
3answers
45 views

Proving $2x^2-3xy+y^2=0$ is transitive and anti-symmetric or symmetric and reflexive.

Let $R$ be the binary relation defined on $\mathbb{R}$ by $xRy$ iff $2x^2-3xy+y^2=0$ For reflexive we get $2x^2=2x^2\implies-x=x$ which means reflexive on $xRx$ $2x^2-3xy+y^2=0$ tried going for $...
0
votes
1answer
24 views

Help on Proving Reflexive, Symmetry and Transitivity for xy>= 1, with relation r E Z , xy E integers,IF AND ONLY IF xy >= 1

My working so far that: Reflexive: Yes as suppose x E in r, we get x^2 >= 1 which true for all so this is true. Symmetric: I think it is true since xy >= 1 and xy = yx order not important? ...
0
votes
1answer
45 views

Determing whether or not the relationships in each problem are symmetric, transitive, and/or reflexive

For each of the following relations on the set of all integers, determine whether the relation is reflexive, symmetric, and/or transitive: a. (𝑥,𝑦)∈𝑅 if and only if 𝑥<𝑦. b. (𝑥,𝑦)∈𝑆 if ...
1
vote
0answers
36 views

A “softmax”-like function for deciding on a partition

Softmax can be derived as follows. Say that we are given $k$ "log priors" $b_i$ that our data belongs to the $i$th category in some categorical distribution. Then we can solve for the category ...
0
votes
1answer
48 views

Relation, union, intersection

Let $R$ be a relation on a set $X$. Then prove that $R\cup R^{-1}$ is the smallest symmetric relation containing $R$ and $R\cap R^{-1}$ is the largest symmetric relation contained in $R$.
-1
votes
1answer
37 views

Minimal Transitive Closure

Any binary relation over any set (finite or infinite) must has a transitive closure. Moreover, every binary relation must has a minimal transitive closure. Who proved this well-known result in ...
1
vote
1answer
50 views

Prove that the transitive closure of a relation is transitive without using recursion

In Kunen's book Set Theory (from 2013) the transitive closure of a relation $R$ on $A$ is defined as $$ R^* = \{ (x,y) \in A^2 : \text{there is an $R$-path from $x$ to $y$} \} $$ where an $R$-path ...
0
votes
1answer
30 views

Is this antisymmetric? Why?

This is from a past paper exam I am revising. Please can someone explain if this is antisymmetric or not. According to the answer it says it isn't, but I can't for the life of me understand why. ...
0
votes
1answer
20 views

what is the cardinality of equivalence classes of relation $ R=\{<A,B>\in P(\mathbb{N} )|A\cap T=B\cap T\} $?

given :$$T\subseteq \mathbb{N} $$ $$ R=\{<A,B>\in P(\mathbb{N} )|A\cap T=B\cap T\} $$ what is a equivalence relation what is the cardinality of equivalence classes of relation R ? how can I ...
1
vote
1answer
26 views

R is the relation defined on the set of integers by xRy when ⌊x/2⌋ = ⌊y/2⌋. Prove that R is an equivalence relation and find the equivalence classes.

So just to go through this real quick the Relation $R$ is an equivalence relation because it is Reflexive - Yes, because for all $x$, $⌊x/2⌋ = ⌊x/2⌋$, so $xRx$. Symmetric - Yes, because for all $x$...
2
votes
2answers
44 views

Relation defined on the set of real numbers by xRy when $x^2 + y^2 = 1$. Show whether or not R is reflexive, symmetric, antisymmetric or transitive.

Let R be the relation defined on the set of real numbers by $xRy$ whenever $x^2 + y^2 = 1.$ Show whether or not $R$ is reflexive, symmetric, antisymmetric or transitive. All right so I think I've ...
4
votes
1answer
63 views

What is a standard name for a “relation” as a subset of $X\times \mathcal P(X)$ rather than of $X\times X$

(Binary) relations on $X$ are formalized as subsets of $X\times X$. But there are also times when a "relation" is a subset of $X\times \mathcal P(X)$. For example, in topology, we may say that $x$ is ...
1
vote
1answer
94 views

Finding and proving if a relation is reflexive/transitive/symmetric/anti-symmetric

Let R be binary relation on N (natural numbers) defined by xRy if and only if x − 2 ≤ y ≤ x + 2. Is R reflexive? Is R symmetric? Is R antisymmetric? Is R transitive? I'm not sure if I'm ...
0
votes
0answers
24 views

Three dimensional representation of a set

A graph $G$ with vertex set $V$ has $\dim(G) \leq d$ if and only if there exists a sequence $<_{1},<_{2}, \ldots , <_{d}$ of total orders on $V$ satisfying the following conditions: the ...
1
vote
2answers
50 views

How to prove transitive relations

Let $R$ be a binary relation on $\mathbb{N}$ defined by $xRy$ if and only if $x − 2 ≤ y ≤ x + 2$ How do you find if it is a transitive relation when there is only $xRy$? Isn't transitivity the ...
0
votes
0answers
26 views

Relational properties of a composition of a relation and its inverse

Let R : A —> B be a binary relation. Each of the following formulas expresses the fact that R has a familiar relational “arrow” property such as being surjective or being a function. Identify the ...
1
vote
0answers
25 views

Inverses of Surjective and Injective Functions

Can you explain if the inverse of a bijective function is always a bijection, and the same for the inverses of a surjection and injection (i.e. is the inverse of a surjective function always ...
1
vote
1answer
31 views

I need to come up with a rule for a set and their relation

2 different Set Relations. I need to come up with a rule for each Relation. R1 = {(a,b) ∈ A x A : rule} where A = {1, 2, 3, 4, 6, 12} I know that they're all positive integer and are divisors of ...
0
votes
0answers
10 views

Composition on a subset

I was reading through the proof for: The relation $R$ is transitive iff $ \forall n\ge1$ $$R^n \subseteq R$$ In the proof for 'if' part, through induction(strong), the hypothesis was $$\forall k\...
-1
votes
1answer
23 views

Counting the number of equivalence classes given the relation (a,b),(c,d) elements of AXA where (a,b)R(c,d) if and only if a+b=c+d

So i have a discrete math final and I don't know why but the profs decided not to post answer key for this one final and I need to check my understanding of this question. Let $A = \{1, 2, 3, 4, \...
1
vote
2answers
53 views

Finding an equivalence classes for the relation $(x_1,y_1)\sim(x_2,y_2)\ \iff\ x_1^2+y_1^2=x_2^2+y_2^2$.

Let R be the relation defined on the set of integer pairs by $(x_1,y_1)R(x_2,y_2)$ when $x_{1}^{2}$ + $y_{1}^{2}$ = $x_{2}^{2}$ + $y_{2}^{2}$. Prove that R is an equivalence relation and determine ...
0
votes
1answer
17 views

Need help with relation properties using logical operators

I was wondering how should I proceed to determine what will be in the relation and what will not given these properties. Operating with integers: $R: \{(a, b)|(a= 0∧b= 0)∨ GCD(a, b) = 5\}$
0
votes
1answer
60 views

How do you find a defined relation? [closed]

So this may be a really simple obvious question, but this is something that kind of trips me up. I'm a beginner at this type of stuff, and still learning. In my past experience if I see the relation ...
0
votes
1answer
46 views

Is this the correct relation for a finite set?

Given a finite set S, let the relation R = {(S1, S2) | |S1| < |S2|, S1, S2 ⊆ S}. Show whether or not R is reflexive, symmetric, antisymmetric or transitive. So if S = {1,2} $R = \{(\emptyset,\...
0
votes
0answers
22 views

Ted's new Partner Relationship Formula: How probabilistic is it through the eyes of Mathematicians here?

Finding the best partner by Ted According to Ted's idea, it turns out your probability of stopping and settling down with the best person (denoted by P in the equation above) is linked to how many of ...
1
vote
1answer
31 views

Basics of Relations Help

I am working out of a textbook for self study past what will be covered in a class I am taking, and I am wondering if someone could explain a couple of questions to that I am just not grasping. The ...
0
votes
1answer
28 views

How to prove this fact about the discrete closure? [closed]

The content is given two relationships: R₁ and R₂ prove that s(R₁ ∩ R₂)=s(R₁) ∩ s(R₂) My teacher has taught us the UNION versions in class, and I figure it's easy. Also I have already finished the ...
1
vote
0answers
53 views

Given a finite set S, let the relation R = {(S1, S2) | |S1| < |S2|, S1, S2 ⊆ S}. Is R reflexive, symmetric, antisymmetric or transitive.

Given a finite set S, let the relation R = {(S1, S2) | |S1| < |S2|, S1, S2 ⊆ S}. Show whether or not R is reflexive, symmetric, antisymmetric or transitive. I'm shaky on how to approach this ...
0
votes
1answer
23 views

The Matrix of an Equivalence Relation

Perhaps I'm missing something from just the definition of an equivalence relation but wouldn't a matrix representing an equivalence relation on any set be only ones and anything less than that is just ...
1
vote
0answers
24 views

Tangent vectors as equivalence classes of triples and ordinary vectors

I am using this document as a reference on tangent spaces etc. In the section on tangent spaces, the author provides three equivalent definitions of a tangent vector, the first being the intuitive ...
0
votes
1answer
18 views

What does it mean to calculate a relation's quotient set (the set of all of equivalence classes)?

The set in question: T = {(a,a),(b,b),(c,c)}. I am confused what it means by this, and I haven't found any resources online that helps explain this to me well enough. Any help is much appreciated.
2
votes
1answer
24 views

Why is this example not antisymmetric?

R = {(a,a),(a,b),(b,a),(b,b),(b,c),(c,b),(c,c)} I know that to be anti-symmetric aRb and bRa, which this example has, but this example also means that a does not equal b (which anti-symmetry needs to ...
-1
votes
2answers
29 views

How is this example NOT transitive? [closed]

R = {(a,a),(a,b),(b,a),(b,b),(b,c),(c,b),(c,c)} Relations are seriously driving me insane. I am revising for my exams and I'm so confused on this stuff. I felt like I was getting a grip of it, then I ...
0
votes
2answers
143 views

If R is an equivalence relation, and S is only symmetric and transitive, what is R ∪ S?

I have a question that asks the following: Let R and S be binary relations on a set A. Suppose that R is reflexive, symmetric, and transitive and that S is symmetric, and transitive but is not ...
1
vote
1answer
63 views

Suppose R is a partial order on A and S is a partial order on B. Define a relation T on A × B such that (a1, b1) T (a2, b2) iff a1 R a2 and b1 S b2.

Suppose R is a partial order on A and S is a partial order on B. Define a relation T on A × B such that (a1, b1) T (a2, b2) iff a1 R a2 and b1 S b2. Is T a partial order on A x B? So far: R is a ...
1
vote
2answers
39 views

Why are functions as a type of relations special? [duplicate]

I.E. Why are relations where each member of the domain having one and only one mapping to a member in the range so important? I was wondering since most of mathematics that I'm familiar with (high ...
-1
votes
3answers
51 views

How to show that the relation $xRy$ if $\sin(x-y)=0$ is transitive? [closed]

"Logically" it seems transitive as if $x-y=k(𝜋)$ and $y-z=k(\pi)$ then $x-z=k'(\pi)$ but how to put it into a good proof? also what would we be its equivalence classes since if it is transitive then ...
0
votes
1answer
34 views

Prove relation is reflexive and transitive but not symmetric [closed]

A bit confused on how to approach this problem since I have only worked with sets for a similar question. Any help would be great! Given two integers $a$ and $b$, we say that $a$ divides $b$ is there ...
2
votes
1answer
35 views

Relational properties preserved under quotients

Suppose R is a binary relation on a non-empty set S. Let E be an equivalence relation on S. Now form the obvious quotient structure: Let S' be the set of all E-equivalence classes [s] of members s of ...
0
votes
1answer
39 views

How to show $(T \circ S) \circ R=T \circ (S \circ R)$?

I am a bit new to computer mathematics, and therefore struggle a bit to understand the process of proving the equality in relation sets like this. I can both see and understand that it is correct, but ...
1
vote
1answer
31 views

Is there a name for a transitive and reflexive but not symmetric relationship?

How do you call a relationship that is transitive and reflexive but not symmetrical? Not antisymmetrical or asymmetrical or anything - just not symmetrical? Where there exist a and that a is in a ...