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