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.

10
votes
2answers
677 views

How is the relation “the smallest element is the same” reflexive?

Let $\mathcal{X}$ be the set of all nonempty subsets of the set $\{1,2,3,...,10\}$. Define the relation $\mathcal{R}$ on $\mathcal{X}$ by: $\forall A, B \in \mathcal{X}, A \mathcal{R} B$ iff the ...
0
votes
1answer
19 views

Understanding transitive relations on set $\{0,1,2,3\}$

I'm having a hard time understanding the transitive property for the following relation. I believed it to be transitive and I can't determine why it is not: Example 1: $$\{(0,0),(1,1),(1,3),(2,2),(2,...
1
vote
1answer
22 views

Is this relation on the set ${1,2,3,4}$ transitive?

Based the definition that a relation $R$ on a set $A$ is called transitive: $∀_a ∀_b ∀_c (((a,b)∈R∧(b,c)∈R)→(a,c)∈R)$ I thought the relation ${(1,3),(1,4),(2,3),(2,4),(3,1),(3,4)}$ would be ...
1
vote
2answers
30 views

Define a Relation R on the set of real numbers as follows:

(x,y) ∈ R if and only if |x+y| = |x|+|y|. Is this reflective? Symmetric? Transitive? Is it an equivalence relation? My attempt: Reflective: Yes, it is reflective. |x+x| = |x|+|x| => 2|x|=2|x| which ...
0
votes
4answers
30 views

Equivalence relation for $X \sim Y \iff X \cap T = Y \cap T$

For the question Let $T$ be a fixed subset of a nonempty set $S$. Define the relation $\sim$ on power set of S by $$X \sim Y \iff X \cap T = Y \cap T$$ Show that $\sim$ is an equivalent relation. ...
1
vote
1answer
24 views

Getting the amount of elements of an equivalence class of a set

Let $S = \{1,2,3,4,5,6,7,8,9\}$ and let $T = \{2,4,6,8\}$. Let $R$ be the relation on $\mathcal{P}(S)$ defined by $\forall X, Y \in \mathcal{P}(S), (X,Y) \in R$ iff $|X - T| = |Y - T|$. How many ...
1
vote
0answers
26 views

Proving that these statements on relations are false

Let $A = \{1,2,3,4\}$. For any function $f : A \rightarrow A$ and any relation $R$ on $A$, we define the relation $S$ on $A$ by: for any $a,b \in A, aSb$ iff $(f(a),(f(b)) \in R$. Prove / Disprove: ...
2
votes
1answer
34 views

If $a \mid c$ and $b \mid c$ where $a, b, c \in \mathbb{N}$, under what conditions does it follow that $a \mid b$?

The following question is pretty basic, and the underlying idea was used in the "proof" of a statement in this hyperlinked answer to another MSE question. The question is as follows: If $a \mid c$ ...
0
votes
1answer
26 views

How do i approach finding the number of equivalence classes of a relation?

(Question too long to post as title) The question is, Let S = {1,2,3,4,5,6,7,8,9} and let T = {2,4,6,8}. Let R be the relation on P(S) defined by for all X, Y ∈ P (S), (X, Y ) ∈ R if and only if |X − ...
0
votes
1answer
58 views

Show that the product of nonzero elements of $\mathbb Z_p$ ($p$ prime) is nonzero.

This is the second part of an assignment in which the first part was the following: Show, if $n \in \mathbb{N}$ is not prime, then there exists $[a],[b] \in \mathbb{Z}_n$ such that $[a] \neq [0] \neq ...
0
votes
1answer
28 views

Matrices- Is this relationship transitive? [closed]

Let $Z$ be the set $\{1,2,3\}$ Then the relation $R: \{(1,1) (2,2) (3,3) (3,1) (3,2) (1,3) (1,2)\}$ is transitive? How to represent matrix?
0
votes
0answers
34 views

How single elements belong to partition though they can't satisfy equivalence relation?

Let $A = \{2, 3, 5, 15\}$ and $G$ is the equivalence relation of elements divisible by 3 and $H$ is the equivalence relation divisible by 5. Now the quotient set $A/G = \{\{3, 15\}, \{5\}, \{2\}\},$ ...
1
vote
2answers
32 views

What is this notation $( \mathbb{N},|)$

My book has this notation for examples of a poset $( \mathbb{N},|)$ and $(\mathbb{Z^*},|)$ and I need to verify it if it is a partially ordered set. Can someone tell me how to read this notation?
0
votes
1answer
30 views

Error in my proof that $f \circ f^{-1} \subseteq I_B$

I was marked off on this, and am thinking it has to do with the inverse relation not necessarily being a function? Problem: For non-empty sets $A$ and $B$, if $f: A\to B$ is a function, then $f \...
0
votes
1answer
64 views

How l can draw Hasse diagram

How can l draw a Hasse diagram of the divisibility relation, when $$B=\{2,4,5,6,7,10,18,20,24,25\}$$ Would any help, thank you.
1
vote
2answers
30 views

Is this relation reflexive if it “chains” to itself?

During studying I stumbled upon a thought regarding reflexive relations. I'm familiar that a relation is reflexive if for each element $x$ in a set $S$, $xRx$. (∀x ∈ S: xRx)? Such as something like ...
1
vote
1answer
42 views

How to prove that a closure is well defined by intersection of sets?

I was told that if we want to prove a definition is well defined, usually what we should do is to prove the existence and uniqueness of the definition. For the question below, what we should do is to ...
1
vote
0answers
19 views

Consider the relation $U$ on the set $\mathbb{Z}^*$ is defined as $aUb \iff a|b$

I have two problems for which I need to find whether it is reflexive, irreflexive, symmetric, antisymmetric, or transitive. 1 Consider the relation $T$ on $\mathbb{N}$ as defined by $$aTb \iff a|b$...
0
votes
1answer
37 views

Form relation inside set $ A = \{1,2,3\} $ so that $\text{R}:\text{A}\leftrightarrow \text{A}$

Problem Form relation inside set $ A = \{1,2,3\} $ so that $\text{R}:\text{A}\leftrightarrow \text{A}$ Attempt to solve I know that $\text{R}:\text{A}\leftrightarrow \text{A}$ is true when ...
0
votes
1answer
34 views

Let $A$ = {2, 3, 4, 7} and $B$ = {1, 2, 3, …, 12}. Define $aSb$ if and only if $a | b$

I just started learning about set relations and there is a question in the book Let $A$ = {2, 3, 4, 7} and $B$ = {1, 2, 3, ..., 12}. Define $aSb$ if and only if $a | b$. Use the roster method to ...
1
vote
1answer
28 views

Proving that the composition of relations are equal to each other

Please excuse my English if it's not understandable, exercises are translated so I don't know all the English terms in math. So I'm doing exercises regarding relations and compositions, and one of the ...
1
vote
2answers
80 views

Set theory question regarding $A\overline{\sim} B = \{x+y : <x,y>\in A\times B\}$

Given $A,B \in P(N)$ We mark $\overline{\sim}$ as $$A\overline{\sim} B = \{x+y : \langle x,y\rangle\in A\times B\}$$ Now, order R will be as following $ARB$ iff $\exists M\in P(N)$ so $A\overline{\sim}...
-1
votes
1answer
31 views
7
votes
4answers
499 views

Why is a symmetric relation defined: $\forall x\forall y( xRy\implies yRx)$ and not $\forall x\forall y (xRy\iff yRx)$?

Why is a symmetric relation defined by $\forall{x}\forall{y}(xRy \implies yRx)$ and not $\forall{x}\forall{y}(xRy \iff yRx)$? (I have only found a couple of sources that defines it with a ...
-1
votes
1answer
26 views

When is a relation a function?

Can you explain the difference between a function and a relation and how a function is a subset of a relation, and when a relation is a function and when not? Also, what is the domain, co-domain and ...
1
vote
1answer
60 views

is there a bijection for $f: \mathbb R \to \mathbb C$? [duplicate]

I imagine no since the dimensions do not match but they have the same cardinality $|\mathbb R |= |\mathbb C|$?
0
votes
1answer
21 views

Equivalence/(Partial order) relation or any other suitable known relations?

Let $G$ be an indirected graph, let $V(G)$ and $E(G)$ be the set of vertices and edges of $G$, respectively. Define a relation $R$ on $G$ as: for all $v\in V(G)$ and $e\in E(G)$, $vRe$ if and only if ...
1
vote
0answers
57 views

Is a topological sorting of a poset a total ordering?

I have been taught by my professor that the topological sort gives a total ordering of a partial order. However, I do not see how this is the case. You are simply rearranging the elements in the ...
0
votes
3answers
45 views

Relations, cartesian product of sets and ordered pair

I don’t understand these terms. They came up in a math class the teacher rushed through. Can you illustrate these terms with examples? I’m not really looking for an in-depth understanding of these (I ...
1
vote
2answers
73 views

Necessary and sufficient condition for existence of a partial order

I'm trying to find a necessary and sufficient condition for the existence of a partial order such that an arbitrary relation on a set X is a subset of the partial order. So far all I have is that ...
0
votes
0answers
34 views

Is equipotent $\sim$ relation?

Problem: $\sim$ is the mark for bijection between two set. Let $A$, $B$, $C$ be sets. Then$$A \sim A\\A\sim B \Rightarrow B\sim A\\(A\sim B \land B\sim C )\Rightarrow A\sim C$$ I know that is not a ...
1
vote
1answer
48 views

Are these two extensionality-axioms equivalent?

Let $\epsilon$ be a binary relation on a set $U$. A subset $A \subseteq U$ is called $\epsilon$-transitive iff $$a \mathrel{\epsilon} b \wedge b \in A \Rightarrow a \in A$$ for all $a,b \in U$. For $...
1
vote
1answer
30 views

Ordered Set example. Why is partially ordered?

I am studying these concepts of order for the first time, and I am having a certain difficulty: I define an Order relation in $A=\mathbb{R_{+}^{2}}$ as : $x,y \in A$, $x\geq y \iff x_{1} \geq y_{1}$ ...
0
votes
1answer
23 views

Let S be the set of nonzero integers. Define a relation R on S by letting aRb mean that b/a is an integer. Is R an antisymmetric relation on S?

A question from the back of my Discrete Math classes textbook. I cant think of any example where (a,b) belongs to R and (b,a) belongs to R but a $\neq$ b. The answer in the back literally just says "...
-1
votes
1answer
27 views

Error in proving a relation transitive

In the homework solution in the image the professor represents s as a ratio of integers, despite s itself being defined as an integer. Is this allowed? I proved the relation transitive without using ...
1
vote
1answer
60 views

Need help with mathematical induction on transitive relation problem.

Problem as follows: Let $R$ be a transitive relation. Let $aR^nb$ for $n \geqslant 1$, mean that there is a sequence of tuples: $$ ⟨a_0,a_1⟩,⟨a_1,a_2⟩, \ldots , ⟨a_{n-1},a_n⟩ $$ from $R$ such that $...
0
votes
2answers
42 views

Let $A = \mathbb{N}$ and let $aRb$ mean that $b|a$…

Let $A = \mathbb{N}$ and let $aRb$ mean that $b\mid a$. Is $R$ reflexive on $A$? Is $R$ symmetric on $A$? Is $R$ anti-symmetric on $A$? Is $R$ transitive on $A$? Is $R$ an equivalence ...
0
votes
0answers
39 views

How many equivalence classes does this equivalence relation have?

Let Σ={0,1}, ≡L is an equivalence relation for set L Let s = 10100 and L = {s} be the language containing only string s L−x = {y:xy∈L} x ≡L y ⟺ L−x = L−y I can count 6: L-empty L-1 L-10 L-101 ...
0
votes
0answers
30 views

Counting the number of equivalence classes (expecting 7 from the DFA states but seeing only 6)

Let Σ={0,1}, ≡L is an equivalence relation for set L Let s = 10100 and L = {s} be the language containing only string s L−x = {y:xy∈L} x ≡L y ⟺ L−x = L−y I can count 6: L-empty L-1 L-10 L-101 ...
1
vote
1answer
65 views

Help me understand what this Equivalence Relation $≡_L$ is (so I can prove it is one)

I'm trying to answer the following exercise question: Exercise 1. Let $Σ =\{0, 1\}$ and let $L$ be a set of strings. As seen in lectures, $L$ induces an equivalence relation denoted $≡_L$ over the ...
0
votes
1answer
17 views

Proportionality without linear restriction?

Is there a word to express the property $\frac{dy}{dx}>0$ of a relation? I've heard the word "proportional" used to express this colloquially, although it is incorrect when $y=kx$ does not hold ...
1
vote
2answers
41 views

Commutative monoid with natural order is a poset

Let $(M,+,0)$ be a commutative monoid and write for $x,y\in M$, $x\leq y \iff \exists t\in M: x+t=y$. I want to show $(M,\leq)$ is a poset. I am stuck at showing antisymmetry. Obviously $x+0=x \...
0
votes
0answers
11 views

Transitive closure in bidirected graph

I have big structure with data that relations with each other in my programm. I need to find all transitive relations for all items. I duplicate all links and use transitive closure. E.g.: ...
0
votes
1answer
46 views

Prove that two transitive closures are equal

Suppose I am given two transitive closures $R^{+}_1$ and $R^{+}_2$ on the same binary relation $R$ over a set $A$, what steps would I take to show that $R^{+}_1 = R^{+}_2$ ? $R^{+}_1$ is defined ...
1
vote
1answer
16 views

On transitive relations

Link to similar post: Set theory relation: irreflexive and transitive My question is a little bit different from the one above. My question is why we say that transitivity property is satisfied "by ...
1
vote
1answer
41 views

Equivalence relation on $\mathbb{R}^2 \times \mathbb{R}^2$?

I have already gotten around that ${\mathbb R}^2$ = ${\mathbb R}$ $\times$ ${\mathbb R}$. I have the relation $C$ on ${\mathbb R}^2\times {\mathbb R}^2$: $((a_1, b_1), (a_2, b_2)) \in C$ iff $a^...
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 ...
-2
votes
1answer
13 views

How to find ordered pairs in smallest transitive relation?

Let R={(1,2),(2,3),(3,4),(2,1)} . How many ordered pairs belong to the smallest transitive relation Rt that contains R?
0
votes
2answers
27 views

Graphing Relations on the Complex Plane

I am able to grasp most complex relations and their respective depiction on the complex plane however I am unable to get my head around relations such as these: $Arg(z + 1 + 2i) - Arg(z-1-3i) = \pi$ ...
0
votes
2answers
51 views

Conceptualizing the (set theoretic) universe as a relation?

The universe is the class $\mathcal{U} = \{x: x = x\} = \{x: x \text{ is a set}\}$. Is there a way to define the universe in terms of a relation $R = \{(x,y): \psi(x,y)\}$, where $\psi(x,y)$ is some ...