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
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 ...
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$ ...
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$ ...
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$....
41 views

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

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

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

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

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$. ...
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 ...
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 ...
51 views

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 ...
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 ...
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: ...
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 ...