# 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,306 questions
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 ...
19 views

31 views

### Give an example of two sets A and B and a relation R from A to B which is not a function. [closed]

Any formulas or ordered pairs that show this?
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 ...
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 ...
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|$?
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 ...
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 ...
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 ...
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 ...
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 ...
48 views

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

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 ...
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?
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$ ...
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 ...