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.

0
votes
0answers
17 views

Transitive closure of $(x,y)\in R \iff x-y=c $

I am trying to figure out what the transitive closure of this is. (Correct me if I'm wrong), but I see that it is transitive since $$x-y=c, y-z=c \implies x-z=(c+y)-(c+z)=y-z=c$$ However, I'm not ...
0
votes
1answer
24 views

If $(X,F)$ is a measurable space and $∼$ is an equivalence relation, is there a $σ$-algebra on $X/∼$ which can be canonically embedded into $F$?

Let $(X,\mathcal X)$ be a measurable space $\sim$ be an equivalence relation on $X$ $X/\sim$ denote the quotient space of $X$ by $\sim$ Is there a $\sigma$-algebra $\mathcal X/\sim$ on $X/\sim$ ...
2
votes
1answer
38 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$ ...
-1
votes
2answers
91 views

Discrete mathematics, equivalence relations, functions.

I'd like some insight on how to 'solve' this problem (more towards understanding what the problem is asking) Suppose that $A$ is a nonempty set and $\mathcal{R}$ is an equivalence relation on $A$....
0
votes
2answers
41 views

Is there a notion of “maximally intransitive” relation, or “maximally nonassociative” operator?

Transitivity on relations $R\subseteq X\times X$ and associativity on binary operators $+:X\times X \to X$ are defined as: $$\forall x,y,z, \quad xRy\land yRz\to xRz$$ $$\forall x,y,z, \quad (x+y)+z=...
0
votes
1answer
15 views

Proof statement for binary relation or show it is wrong by counterexample

Proof or show following statement is false $$ (R \circ S) \cap (R \circ T) \subseteq R \circ (S \cap T) $$ Statement is false by counterexample Let $ \langle x,y \rangle \in (R \circ S) \cap (R \...
0
votes
2answers
33 views

Can the use of several relations on the same left-hand side be abbreviated so that the LHS is only written once?

Can someone tell me whether I can express $$a ≈ 922\text{ trillion}, a > 922\text{ trillion}, a = 922,337,203,685,477.5808$$ using the following notation: Possible way to abbreviate notation for ...
-1
votes
0answers
49 views

How to prove that any partial order on a finite set $S$ is a subset of a total order on $S$?

Let $S$ be a finite set. Prove that any partial order on $S$ is a subset of a total order on $S$. I've tried to explain it with definitions of partial and total orders. Let $X$ be any set and let $...
0
votes
1answer
22 views

How do I compare relative importance of observations when number of observations is different in different datasets

Let me first describe what I mean by dataset and relative importance: Dataset is discrete observations, where identical observations may be recorded. Assume we have dataset A with values ...
0
votes
1answer
28 views

Proof that for binary relation $ R \circ (S \cup T) \subseteq (R \circ S) \cup (R \circ T) $

Proof that for binary relation following is true $$ R \circ (S \cup T) \subseteq (R \circ S) \cup (R \circ T) $$ Attempt to proof let $\langle x , y \rangle \in R \circ (S \cup T)$ $$ \iff \exists ...
4
votes
3answers
19k views

Composition relation of R1 ∘ R2

Let $R_1$ and $R_2$ be the relations on $\{1, 2, 3, 4, 5\}$ defined by $$R_1 = \{(1,1),(2,3),(2,4),(3,5),(5,2),(5,5)\}$$ $$R_2 = \{(1,1),(2,2),(2,3),(2,5),(4,3),(5,5)\}$$ The answer for ...
0
votes
2answers
51 views

Relations as Sets

Wikipedia defines a relation as a set of ordered pairs. An example of this is {(1,1), (2,4), (3,9)} But how could this set fully define a relation? Can’t the relation have one of many different ...
-1
votes
1answer
38 views

Define the relation $R$ so that $xRy$ if and only if $x+4y$ is dividable with $5$

We define the relation R on the set $A=\{ -8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8 \}.$ so that $xRy$ if and only if $x+4y$ is dividable with $5$. Ok so how should i define this $R$ with $...
0
votes
4answers
33 views

Give an example of R over A so that: symmetric and transitive but not reflexive

Let $A = \left \{ 1,2,3,4 \right \}$. Give an example of $R$ over $A$ so that it is symmetric and transitive but not reflexive. My answer: $R = \begin{Bmatrix} (2,1)(1,2)(2,3)(1,3) \end{Bmatrix}$ ...
0
votes
1answer
15 views

2-dimensional relation with 4 variables

I am trying to reason about a relation ($ \sim $) on $A \times A$ that is like this: $A = \{1,2,3,4\}$ $ (a,b) \sim (x,y)\,\text{iff} \begin{cases} a|x &\text{if}\, a \neq x\\ b|y &\text{...
1
vote
1answer
50 views

Introduction to Set Theory, Hrbacek and Jech exercises 3.5.7 and 3.5.8

I am working on the exercises in chapter 3, section 5, of Introduction to Set Theory by Hrbacek and Jech. I wanted to check and see if my proofs of the following exercises are valid. I will list the ...
1
vote
1answer
43 views

Prove that “equiprobable” is an equivalence relation

Let $X$ be a set of cardinality $n$ and let $R$ be the set of all relations over $X$. Consider the probability space $(R,P)$ with uniform distribution, that is, $P[\{R_1\}]] = P[\{R_2\}]$ for all $ ...
0
votes
1answer
13 views

Transitivity of $R$ when it is a relation such that $R^2 = R$ and Vice-Versa.

My question is about Set and Relation Theory. $R$ is a relation on a set $S$. 1) Show that if $R^2 = R$ then $R$ is transitive. 2) Show that if $R$ is transitive and "Reflexive or Symmetric" Then $...
0
votes
3answers
36 views

What is the probability that P and Q have no common elements?

A is a set containing n elements. A subset P of A is chosen at random. The set A is reconstructed by replacing the elements of the subset of P. A subset Q of A is again chosen at random. Find the ...
1
vote
1answer
14 views

$P$ — partial preorder. $\theta(P)=\{(x, y)\in A^2 | (x, y) \in P \land (x,x) \in P \}.$ $\theta(P)$ is an equivalence relation: can't see symmetry.

Let $P$ be a partial preorder (which is a reflexive and transitive relation) on an arbitrary set $A$. Consider binary relation $\theta(P)=\{(x, y)\in A^2 | (x, y) \in P \land (x,x) \in P \}.$ My ...
0
votes
1answer
16 views

Construct a relation on a given set (discrete mathematics)

Consider the set $S=[-8,8] \cap \mathbb{Z}$. Define a relation $R$ such that $(a, b) \in R$ if and only if $[a]_4 = [b]_4$. Now the way that I understand this question is that $[x]_4$ is a remainder ...
0
votes
1answer
36 views

Keep the relationship between two values

I have two variables. $x$ represent the number of months that a human will live, and $y$ is the quality of his life for those months. I want to use these two values to get a new one. If I do that $x ...
0
votes
1answer
14 views

Equivalence relation for the union of 2 sets [closed]

If R1 and R2 are 2 equivalence relations on set S, then Prove that R1 U R2 is reflexive, symmetric but needn't be transitive. This is the question and I understand why it needn't be transitive but ...
1
vote
1answer
28 views

Notation for symmetric closure of a relation

Given a binary relation $r$, its reflexive closure, $r \cup id$, is sometimes written as $r^?$ or $r^=$. Its transitive closure is written as $r^+$. Its reflexive, transitive closure is written as $r^*...
2
votes
2answers
32 views

Why are some sets neither symmetric or anti-symmetric?

In this relation set R1 = {(2, 2),(2, 3),(2, 4),(3, 2),(3, 3),(3, 4)}, when finding its property of relation- antisymmetric, transitive, symmetric etc the answer states that its neither antisymmetric ...
2
votes
2answers
34 views

Check whether the relation is symmetric/transitive or not

Let us define a relation $\rho$ on the set $A=\{1,2,3 \} $ by $ \rho=\{(1,1)\}$. Is the relation symmetric, transitive or not? I have confusion abut symmetry or transitive. If $(a, b) \in \rho\...
1
vote
1answer
33 views

Prob. 7, Sec. 5, in G.F. Simmon's INTRO. TO TOPOLOGY & MODERN ANALYSIS: Equivalence relation iff reflexive and circular iff reflexive and triangular

Here is Prob. 7, Sec. 5, in the book Introduction to Topology and Modern Analysis by George F. Simmons: Let $X$ be a non-empty set. A relation $\sim$ in $X$ is called circular if $x \sim y$ and $y \...
1
vote
2answers
42 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
vote
1answer
866 views

Properties of binary relations

I am so lost on this concept. We are doing some problems over properties of binary sets, so for example: reflexive, symmetric, transitive, irreflexive, antisymmetric. This particular problem says to ...
0
votes
1answer
987 views

How would I draw the diagram for this relation?

The question I am trying to solve is below. I have proven it is an order but am unsure how to draw the diagram for it. Can someone point me in the right direction? Let A = {1, 2, 3, 4}, and let R be ...
1
vote
1answer
51 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
1answer
38 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}=\{(...
4
votes
2answers
72 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
38 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
32 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
0answers
40 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 ...
0
votes
1answer
16 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
43 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
36 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
21 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 ...
0
votes
0answers
18 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
21 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 ...
-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? ...
0
votes
3answers
19 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{ ...
0
votes
1answer
968 views

Binary relations on a set

I have a homework problem that asks this... a) List all the different binary relations on the set $\{0,1\}$ I assume that since the relation is not given then the answer must be the graph, or ...
1
vote
1answer
34 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
21 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

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 ...
1
vote
3answers
80 views

Determine whether $R$ is an equivalence relation: $xRy$ if $\cos(x)^2+\sin(y)^2=1$

I'm having troubles with this question. I understand that for a relation to be equivalent, it needs to be reflexive, symmetric, and transitive. So far I've split this problem into 3 sections, one to ...