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.

3,307 questions
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 ...
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. ...
21 views

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 ...
74 views

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? ...
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 ...
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 ...
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$.
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 ...
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 ...
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. ...
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 ...
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$...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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\...
23 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
28 views

For relations that are not equivalence relations, what does it mean to calculate the smallest equivalence relation that contains it? [closed]

One set in question: S = {(a,a), (a,b), (b,b), (c,b), (c,c)}.
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...