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
2answers
31 views

Equivalence classes of elements in $X$ vs. equivalence class of $X \times X$

To quote Halmos: If $R$ is an equivalence relation in $X$, and if $x$ is in $X$, the equivalence class of $x$ with respect to $R$ is the set of all elements $y$ in $X$ for which $x R y$. ...
-1
votes
0answers
31 views

How to prove that poset $(\mathbb{Q}, \leq)$ isn't well-founded? [on hold]

How I can create infinite descending chain with set negative?
-2
votes
2answers
32 views

How to find an equivalence relation?

How can the below given relation be or not be proved to be an equivalence relation ? $$_{a}R_{b} \iff a^{2} + b^{2} = 0$$ here relation $R$ is defined on $\mathbb{Z}$(integers)
0
votes
1answer
31 views

For each of the following relations, state its domain and range

1) Let $A = \{0, 1, 2, 3, 4 \}$. Define the relation $M$ from $P(A)$ to $A$ in the following way: $(X, x) \in M$ if and only if $x = \min X$. 2) Define the relation $L \subseteq \mathbb{N} \times \...
0
votes
1answer
30 views

Prove or disprove: $\lvert\mathcal{R}\rvert=\lvert\mathcal{R}^{-1}\rvert$

Prove or disprove: If $\mathcal{R}$ is a relation then $\lvert\mathcal{R}\rvert=\lvert\mathcal{R}^{-1}\rvert$. I think it is true but I do not know how to prove it. Facts: $\mathcal{R}^{-1}=\{(...
1
vote
0answers
23 views

Characterization of the Borel $\sigma$-algebra on a topological quotient space

Let $(E,\tau)$ be a topological space $\sim$ be an equivalence relation on $E$ $[x]$ denote the equivalence class of $x$ with respect to $\sim$ for $x\in E$ $E_\sim$ denote the quotient space of $E$ ...
4
votes
2answers
70 views

Is there a standard name for this relation property : “ aRb --> there is no c different from b such that aRc ”?

Maybe this property could be called "exclusivity" ? Does it have a standard name? It recalls the definition of a function as a " single-valued relation" (Enderton). But here, it is not required ...
1
vote
2answers
32 views

$ S = \{(x,y) \in B \times B | (\exists a,b \in A)[f(a)=x, f(b)=y, (a,b) \in R ] \} $ with R transitive, is S transitive?

Be the funtion $ f: A \to B $ and $ R \subseteq A \times A $ a transitive relation. Be the relation $ S \subseteq B \times B $ defined as: $ S = \{ (x,y) \in B \times B | (\exists a,b \in A)[f(a)=x, ...
0
votes
0answers
27 views

Cartesian product of R2 x R2 [on hold]

I need to work with a relation on $\mathbb{R}^2$ defined by $(x_1,y_1)R(x_2,y_2)$ with some condition. So far I've only done relations and Cartesian Products with single-dimension data (e.g., a ...
0
votes
0answers
28 views

If a relation is neither Symmetric nor Anti-Symmetric, can it still be an order of some kind?

Say I have a relation that is Irreflexive and Transitive, but neither Symmetric nor Anti-Symmetric, can it still be a strict partial and / or strict total ordering? I realise this is an edge case, I ...
0
votes
1answer
15 views

Showing a relation in NxN is an equivalence relation, N denotes a set of positive integers

Let $N∈Z^+$ and P represents a relation in$ N x N $defined by $(a,b)P(c,d) $ iff $a + d = b + c$ we have to show that P is an equivalence relation I tried to prove the reflexive property , then ...
0
votes
0answers
37 views

relations, injective functions and proof of total ordering

I have recently started learning about injective functions and can understand them to a basic level. injective functions essentially equate to ...
-2
votes
0answers
25 views

Please help me about Relation… [on hold]

I'm learning about Relation now, and I've usually solved the same type of problem (2,2). I was going to solve this type of problem for the first time, but I don't know how to solve the problem, as the ...
0
votes
0answers
42 views

Correctly understanding relations

I get that something such as R={(0, 0),(0, 1),(1, 1),(1, 2),(0, 2),(2, 2)} on the set {0, 1, 2} would be reflexive, anti-...
0
votes
1answer
33 views

Is denseness a antisymmetric relation?

Upon discovering that denseness is transitive, I wondered if denseness is a partial ordering ($\iff$ reflexive, antisymmetric, transitive). To be more precise: Let $X$ be a topological space. Then ...
0
votes
1answer
20 views

One one function set S

Consider the set $A ={1,2,3,4,5, \cdots ,n} .$ Let $S$ be the set of all one one function f from $A$ to $A$, such that $|f(1)-1|=|f(2)-2|=|f(3)-3|=.....=|f(n)-n|$ I need to find number of elements ...
1
vote
1answer
49 views

Question regarding ternary relation

How can the type of the following ternary relation $R$ on $\mathbb{Z}$ (set of all integers) be determined whether it is reflexive, transitive or symmetric ? $$ R = \{ a, b, c \in \mathbb{Z} : a \...
0
votes
0answers
15 views

Isometric grid sort relation

I need to define relation function, which will for any two elements A, B return -1 if A is ...
1
vote
1answer
20 views

Proving that a relation is an equivalence relation by proving it is transitive

I came up with this question , which I have to prove that it is an equivalence relation Define a function f : R → R by f(x) = x^2 + 1. For a, b ∈ R define a ≃ b to mean that f(a) = f(b) I have done ...
0
votes
3answers
17 views

Clarification for equivalence class

I've been reading about equivalence class lately and I've a question. In my book it's given, if there is a relation $R$ on set $\mathbb Z$ of integers, $$R=\{(a, b) : a, b \in \mathbb Z, a-b\text{ ...
-1
votes
1answer
44 views

To check that if this inequality is an equivalence relation on $\mathbb{Z}$ [closed]

I proved this inequality ; Which is a relation on $\mathbb{Z}$ s.t a and b belongs to $\mathbb{Z}$ $$a^2 - b^2 \le 7$$ is reflexive , I'm stuck at the symmetry of this relation, can anyone help? ...
1
vote
1answer
32 views

Alternative method for counting equivalence relations on {1,2,3,4}

So my method goes like this: We have 16 ordered pairs. If R is: Reflexive: It has to include $(1,1), (2,2), (3,3), (4,4)$. So $2$ choices for each of the remaining $12$ pairs. Symmetric: If it ...
0
votes
1answer
22 views

Equivalence classes of a relation

Define on R the relation $xTy$ if and only if $cos^2(x) + sin^2 (y) = 1$. Prove that this is an equivalence relation and find R/T About that second part, what do the equivalence classes look like? I ...
0
votes
1answer
20 views

Predicate logic deciding whether atomic formulae hold in interpretations

Consider the formula $\varphi $ of First-order logic defined as $\forall x\forall y((B(x,y) \land B(y,x)) \rightarrow (A(x)\land C(y)))$ State whether it holds in the following interpretations: ...
0
votes
1answer
23 views

How can a relation be both irreflexive and antisymmetric?

Summary Irreflexivity occurs where nothing is related to itself. Anti-symmetry provides that whenever 2 elements are related "in both directions" it is because they are equal. These two concepts ...
0
votes
0answers
28 views

S = { (a,b) be elements of Real Numbers| |a-b|<2 or |a-b|=2}. List three elements in S[4]?

I know or at least correct me if I'm wrong two elements are {3,2}. How would I come to find another element?
0
votes
1answer
48 views

How you call the relationship between variables $X$ and $Y$ if $X=1-Y$

How you call the relationship between two variables where one is equal to 1 minus the other. For example, if my variables are $X$ and $Y$ and I have that $X=1-Y$ I what to say the $X$ is the ________ ...
2
votes
3answers
56 views

Question involving proving equivalence relations

In order to prove if a relation is an equivalence relation, it needs to be show that is all of: Reflexive Symmetric Transitive Whilst I am familiar with this, I am unsure how to approach the ...
1
vote
2answers
34 views

on the set of all integer,For all $a, b ∈ Z, a R b,$ $ ⇔ a | b, $ is R antisymmetric?

on the set of all integer,For all $a, b ∈ Z, a R b,$ $⇔ a | b, $ is R antisymmetric? the answer is symmetric but i dont know how to prove it and how to find the counter example $a,b \in Z$ $ka=b$...
0
votes
1answer
29 views

Relations - Proving symmetry/anti-symmetry with a defined set

Struggling a bit on this question regarding relations. Would appreciate your help immensely. Determine if a relation is reflexive, symmetric, anti-symmetric & transitive, for: $$R = \{(x,y) : xy ...
1
vote
0answers
47 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
18 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
58 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
73 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
22 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
38 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
34 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
44 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
36 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
45 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
25 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
43 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 ...