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.

learn more… | top users | synonyms

2
votes
2answers
20 views

Proving two Recurrence Relations

I encountered this problem in the International baccalaureate Higher Level math book, and my teacher could not help. If anyone could please take the time to look at it, that would be great. I need ...
-2
votes
2answers
26 views

Is the following relation transititve? [on hold]

Consider that the relation on $\{1,2,3,4\}$ is $\{(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)\}$ transitive. Please tell me the reason. Thanks.
0
votes
1answer
19 views

How would I convert this state-transition diagram into a regular expression ?

The state-transition diagram of a finite-state recogniser is as follows :
2
votes
1answer
55 views

Can a relation be both anti-reflexive and anti-symmetric?

Is it possible for a relation to be both anti-reflexive and anti-symmetric?
0
votes
1answer
18 views

How to work out the boolean matrix of a relation $S$?

I just wanted a little bit of guidance on how to work out this question in finding the boolean matrix of a relation : Consider the following Hasse diagram of a partial ordering relation $S$ on the ...
3
votes
2answers
27 views

Restricting a relation to an injective function

Given a relation between two finite sets, how can I determine whether it restricts to an injective function? The criterion or algorithm doesn't need to be constructive: It is enough to know that such ...
0
votes
1answer
13 views

Anti-symmetric or asymmetric for a relation between pairs in the set of Z x Z?

Is this anti-symmetric or asymmetric? I at first thought asymmetric because anti-symmetric would mean a = c and b = d which would not be true. But because the domain is the Cartesian product of ...
2
votes
3answers
111 views

Sets: How to show that relation R is not transitive?

I have a question which states: $R = \{ (t,t), (t,v), (t,z), (u,t), (u,u), (u,v), (u,x), (u,z), (v,v), (w,w), (w,z), (x,t), (x,v), (x,w), (x,x), (x,y), (x,z), (y,w), (y,y), (y,z), (z,z) \}$ ...
0
votes
1answer
21 views

A question on eqivalence relation

Please explain what the examiner means by asking: Also find [3,6] in Q 1 (a)(i)??
0
votes
2answers
26 views

Concrete explanation for how an equivalence relation is related to equivalence class and the notation employed

I'm fairly comfortable with the definition of what the three equivalence relations are. What I'm not comfortable and finding it above my head is how equivalence relation is closely related to ...
1
vote
2answers
28 views

Difference between domain and range for relations and functions?

What is the difference between the definition of domain and range for a relation, and that for a function?
0
votes
2answers
38 views

Well-defined and Equivalence relations

I am wondering why the following is well-defined... The definition of well-defined is given as; $g:(X/\sim) \to Z$ is well-defined if a mapping $f:X \to Z$ can be found where $f$ has the property $x ...
1
vote
1answer
17 views

Non-ordered n-tuple?

In many mathematics texts I've seen "ordered n-tuple" appear, and in such texts, there isn't any mention of just "n-tuple". So I'm wondering: are there really cases where one writes "n-tuple" and ...
0
votes
1answer
54 views

Proof of an equivalence relation

Let S be the relation on R defined by $xSy \Leftrightarrow x=|y|$, $\forall x,y\in\Re$ Is the relation reflexive, symmetric and/or transitive? By my proof that 1) $x=|y| \Rightarrow |y|=x$ ...
-1
votes
0answers
30 views

geometric description of equivalence classes [on hold]

For each of the following relations on $\mathbb{R}^{2}$, give a geometric description of the relation classes $[(0,0)]$ and $[(3,4)]$ 1) Let $S$ be the relation defined by $(x,y)S(z,w)$ iff ...
1
vote
1answer
47 views

Trouble Understanding a Combinatorics Problem

This question appeared on my combinatorics exam. I did not even understand the question. Determine the number of functions, $f:\{1,2,3\} \to \{1,2,3\}$, that satisfy $$f(1)+f(3)\equiv0\ (\text{mod ...
1
vote
3answers
24 views

Determine whether the relations are symmetric, antisymmetric, or reflexive.

This exercise is given in my textbook and I am trying to solve it. Determine whether they are symmetric, antisymmetric or reflexive. $R_1=\{(2,2), (2,3), (2,4), (3,2), (3,3), (3,4)\}$ ...
1
vote
2answers
33 views

Equivalence relation $x^m=y^n$

Show that $R=\{(x,y) \in\mathbb{N}^2:\exists m,n \in \mathbb{N} \text{ s.t. } x^m=y^n\}$ is an equivalence relation or disprove otherwise Reflexivity and symmetricity were really easy to show ...
0
votes
0answers
12 views

Characterization of monovalued functions

Let $f$ be a binary relation. Let $(\bigcap G)\circ f = \bigcap_{g\in G}(g\circ f)$ for every set $G$ of binary relations. Can we prove that $f$ is monovalued (a function)?
0
votes
2answers
23 views

simple clarification of equivalence relation and order relation notation meaning

So by definition an equivalence relation is a binary relation on a subset of the cartesian product of our set A, i.e $A\times A$ satisfying the 3 conditions. But I'm a little confused about ...
2
votes
3answers
51 views

Find the inverse of $f(x,y) = (x+3y,3x+y)$

Given the function $f : \mathbb{R}^2 \to \mathbb{R}^2$ as $f(x,y) = (x+3y,3x+y)$. Find $f^{-1}$ .( Assume $f$ is a bijection) I know how to find $f^{-1} (x) = (3x+2)$ or anything with one ...
0
votes
2answers
44 views

symmetry vs antisymmetry

So the problem I have is to write all the properties that a relation has (reflexive, symmetric, transitive, irreflexive, antisymmetric). The problem is the congruence relation on the set of triangles. ...
0
votes
2answers
36 views

Why is the number of subsets equal to the number of relations?

In this question I don't understand why the number of subsets is equal to the number of relations. Any help is welcome.
0
votes
2answers
36 views

Can this relation be transitive but not symmetric and reflexive?

Let $A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$. Give an example of a relation $T$ on $A$ with at least three elements that is not reflexive, not symmetric, but transitive. Explain clearly why ...
0
votes
2answers
42 views

Show that the function $f:\mathbb{Z} \rightarrow \mathbb{2Z}$ by $f(a)=a^3+3a+2$ is not onto

If the function $f:\mathbb{Z} \rightarrow \mathbb{2Z}$ by $f(a)=a^3+3a+2$, then show that $f$ is not onto. Hint: Show that $f(a)\neq 0$. I have a feeling I have to use the root theorem test, but I ...
3
votes
1answer
45 views

Does type-theory have a concept of “relation”?

Set theory cares about sets and relations. And then functions are relations betweens sets of inputs and outputs. Type theory, on the other hand, seems to say that there are no formal ideas of ...
0
votes
1answer
17 views

Prove that the relation $f$: ($\mathbb{Z^*} \times \mathbb{Z^*}$) $\rightarrow$ $\mathbb{Q}$ by $f(a,b)$ = $\frac{a+b}{a+b-3ab}$ is a function

Prove that the relation $f$: ($\mathbb{Z^*} \times \mathbb{Z^*}$) $\rightarrow$ $\mathbb{Q}$ by $f(a,b)$ = $\frac{a+b}{a+b-3ab}$ is a function I believe that f is a function and I am attempting to ...
0
votes
1answer
31 views

Is $f:\mathbb{Q^*} \rightarrow \mathbb{Q}$ by $f(\frac{a}{b}) = \frac{\max{(a,b)}}{\min{(a,b)}}$ a function?

Suppose that the relation $f:\mathbb{Q^*} \rightarrow \mathbb{Q}$ by $$ f \Bigl(\frac{a}{b} \Bigr) = \frac{\max{(a,b)}}{\min{(a,b)}} $$ is defined. Then is $f$ a function? If so, how would we prove ...
0
votes
0answers
16 views

Question Concerning a General Method to Show that a Relation is Not a Function

When showing that a relation is not a function, is there an efficient method for finding particular preimages that are mapped to more than one image, rather than attempting to find particular ...
2
votes
1answer
24 views

Intersection of two sets which are equivalence on set A is always equivalence?

If $R_{1}$ and $R_{2}$ are equivalence relations on set A ,then$ R_{1}\bigcap R_{2}$ must be equivalence relation. firstly, I am not understanding the function of R,I think that, this is only a ...
3
votes
2answers
30 views

why are equivalence relations called so?

"an equivalence relation is the relation that holds between two elements if and only if they are members of the same cell within a set that has been partitioned into cells such that every element of ...
2
votes
0answers
24 views

Hasse Diagram Correct?

I've had to make Hasse Diagrams before, but they've always been, for lack of a better word, pretty. The lines haven't had any complicated back and forth or the like. The jump that 4 and 6 have to do ...
2
votes
1answer
26 views

Calculate transitive closure of a relation

I am trying to understand how to calculate the transitive closure of a set and I have read several times the definition of the transitive closure but I still cannot understand some answers I see when ...
0
votes
2answers
36 views

Why is this an equivalence relation, and what does the equivalence classes contain?

I'm doing some discrete mathematics exercises, but I can't seem to wrap my head around this relation: $$R(x, y) \text{ if } \exists z(\text{LiesInPart}\circ\text{LiesInCountry}(x,z) \wedge ...
2
votes
1answer
30 views

Order relations and counting the number of cases (Fubini numbers)

I have $n=2$ numbers $a$ and $b$, $a\in\Bbb{N}$ and $b\in\Bbb{N}$. Then I have the function $f$ defined as: $ f(x,y) = \begin{cases} -1, & \text{if $x<y$} \\ 0, & \text{if $x=y$} \\ +1, ...
1
vote
1answer
31 views

Binary Relations - Reflexive, Symmetric, Transitive and anti symmetric

$R$ is defined on $P(N) − \{\varnothing\}$ by $ARB$ if and only if $A \cap B \ne \varnothing$ Identify if the relation is reflexive, symmetric, transitive and anti symmetric Finding it hard to work ...
0
votes
1answer
15 views

Describing equivalence classes over the set of natural numbers

So for this problem we are supposed to describe the equivalence class for the following relation. $x \thicksim y$ iff $x$ mod 2 = $y$ mod 2 and $x$ mod 4 = $y$ mod 4. I am confused on what is meant ...
1
vote
1answer
16 views

verifying properties of relations to test equivalence

We are doing some more with relations and this time we are given a relation and told that it is not equivalent. We need to find out which property it does not fulfill. So we at least know there is ...
1
vote
2answers
21 views

Determining whether a relation is transitive or not.

While trying to determine whether the following relations are transitive or not, I got stuck in between. The following are the two relations - Relation R in the set $\mathbb{N}$ of natural ...
3
votes
3answers
126 views

Whats the difference between Antisymmetric and reflexive? (Set Theory/Discrete math)

Antisymmetric: $\forall x\forall y[ ((x,y)\in R\land (y, x) \in R) \to x= y]$ reflexive: $\forall x[x∈A\to (x, x)\in R]$ What really is the difference between the two? Wouldn't all antisymmetric ...
1
vote
1answer
19 views

Equivalence Relation on the set of ordered pairs of positive integers

Have a homework question, but how can I show that the given relation R is reflexive, symmetric and transitive, so that it is an equivalence relation. Appreciate assistance from anyone. "Let R be the ...
0
votes
3answers
103 views

If $R=\{(x,y): x\text{ is wife of } y\}$, then is $R$ transitive?

If $R=\{(x,y): x\text{ is wife of } y\}$, determine whether the relation $R$ is transitive or not. My Try: For Transitivity, If $(a,b) \in R$ and $(b,c)\in R\;,$ Then $(a,c)\in R.$. Here If $x$ ...
0
votes
1answer
22 views

Is this relation P an equivalence relation or a partial order relation?

I am having trouble with partial order and equivalence relations. I was wondering if someone can guide me through this problem. Let $Σ$ be the set of letters {$a, b, . . . z$}. Let $Σ^∗$ be the set ...
0
votes
1answer
31 views

Help with equivalence classes for $x\sim$y iff $x-y\in\mathbb{Q}$.

Help with equivalence classes for $x\sim$y iff $x-y\in\mathbb{Q}$. I need to show the equivalence classes for $[0]_{\sim}$ and $[\sqrt{2}]_{\sim}$. Here is what I did: $[0]_{\sim}$ = ...
0
votes
1answer
25 views

Find transitive closure of $D_r = \{(x,y) \in \mathbb{R} \times \mathbb{R} \mid |x - y| = r\}$

This is one of the problems I have been solving in Velleman's How to prove book: Find the reflexive, symmetric and transitive closures of the following relations: $D_r = \{(x,y) \in ...
2
votes
1answer
27 views

how to prove that a relation is antisymmetric?

I have this question that I didn't know how to prove it and need your help. $R$ is a transitive and not reflexive relation on $A$. Prove that $R$ is antisymmetric. I tried to apply the definition of ...
-1
votes
1answer
32 views

Covering relation over functions

F is a group that includes all functions from N to N K is relation over F. For f,g ∈ F: (f,g) ∈ K iff ∀ n∈N, f(n)≤g(n). Obviously K is Partially ordered set and not Total Order. My problem is with ...
2
votes
1answer
23 views

The equivalence relation generated by a relation

Let $X$ be a non-empty set and let $r\subseteq X\times X$ be a relation on $X$. Let $R$ be the intersection of all equivalence relations on $X$ that contain $r$. Prove that if $xRy$, then one of the ...
0
votes
1answer
16 views

Equivalence Relations Reflexivity

Consider the relation on $\bf{R}$ defined by $n \simeq m$ if $(n-m)\in \bf{R}$ To say this is reflexive, I can say: Let $n\in \bf{R}$ and since $n-n = 0$ and $0 \in \bf{R}$ Then $n \simeq n$.
0
votes
1answer
24 views

Find transitive closure of the relation, given its matrix

Find transitive closure of relation $R$ described by the matrix $M_R$: $$M_R = \begin{bmatrix}1 & 0 &0 \\0 & 1 & 1 \\1 & 0 & 1 \end{bmatrix}$$ I tried doing it like this ...