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.

-1
votes
1answer
21 views
6
votes
4answers
430 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
23 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
50 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
11 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
21 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
22 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
64 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
26 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
18 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
24 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
47 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
34 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
25 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
27 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
42 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
9 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
30 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
9 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
35 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
15 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
33 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
43 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
12 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
48 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 ...
7
votes
1answer
63 views

Can every relation be defined from “set-ary” relations?

This is an extension of this question, suggested by Noah Schweber. Suppose I have some set of relations $(R_i)_{i\in I}$ over a set $D$: $R_i\subseteq D^{n_i}$, $n_i\in \mathbb{N}$. Noah defines a ...
0
votes
0answers
9 views

how to calculate growth rate from a semi-log plot?

In the following plot, if we model the population growth as a linear function of time, what would be a good estimate of the linear growth rate? I don't know if it's the slope of the line or where it ...
3
votes
3answers
368 views

Why does this relation fail symmetry and transitivity properties?

The question states, let $S$ be the set of all humans. Define $a ∼ b$ iff $a$ is a full-brother of $b$. Symmetry: Since $a$ shares both parents with $b$, then $b$ shares both parents with $a$. Would ...
1
vote
1answer
35 views

Correct definition of composite relations?

I can't seem to wrap my head around composite relations. According to Grimaldi in "Discrete and Combinatorial Mathematics", it is defined as: If $A, B$ and $C$ are sets with $R_1 \subseteq A \times ...
0
votes
1answer
21 views

What does “collect all mutually $R$-equivalnent elements in $A$” mean?

I am reading "Sets, Numbers and Topology" by Masahiko Saito. Let $R$ be an equivalence relation on a set $A$. If we collect all mutually $R$-equivalnent elements in $A$, we get a subset of $A$. ...
2
votes
1answer
56 views

Word for something that cannot be calculated “back”?

Sorry if this is a duplicate / not something allowed in here, I do not use the math section often. I am looking for a word to describe something that cannot be calculated "backwards", once it is ...
0
votes
1answer
32 views

Prove that a relation R on A is antisymmetric if and only if $R∘R^{-1} \subseteq I_A$

If: I tried to take some element $(a,b)∈R∘R^{-1}$ and show that we have some $c∈A$ s.t. $(a,c)∈R^{-1}$ and $(c,b)∈R$, and use the fact that $R∘R^{-1} \subseteq I_A$ which gives that $a=b$. I then ...
1
vote
0answers
32 views

Equivalence of various notions of injectivity for partial functions

Let $A$ and $B$ denote sets. Definition. Given a partial map $f : A \rightarrow B$, let us define that a partial inverse of $f$ is any partial map $g : B \rightarrow A$ satisfying $$fg \leq \mathrm{...
1
vote
2answers
105 views

Range of the “power set” function

Let $f: \mathcal{P}(A) \to \mathcal{U}$ be the function given by $f(x) = \mathcal{P}(x)$ for every $x \in \mathcal{P}(A)$. Here, $\mathcal{U}$ is the universe, and $A$ might be a set or it might be a ...
0
votes
1answer
32 views

Understanding definable set

I'm facing some difficulties in understanding what its mean to prove that a set is a definable set. Below is an example of a question that was given in our class, with the solution for this question. ...
1
vote
2answers
33 views

Binary Relations - Definition

I am familiar with the definition of a binary relation from set $A$ to set $B$ as a subset of their Cartesian product $A × B$. I do not understand, however, how one can view certain mathematical ...
1
vote
0answers
63 views

How many different relationships of couple's acquaintances exist in the company of N persons

How many different relationships of couple's acquaintances exist in the company of N persons, if in each of the three of this company there are both familiar and not familiar persons Somewhat similar ...
-2
votes
1answer
33 views

how can I visualize such graph If I am only given this formula

How can visualize it and prove it is the way it should be visualized? ∃y∀x(xRy) Thanks!
0
votes
2answers
38 views

Do I have errata in my measure book: Measure, Integral and Probability II by Capinski

The author goes to define what equivalence (from basic set theory) means on page 4. This book can be found online. But here is a short summary: Given any set $E$, an equivalence relation on $E$ is a ...
0
votes
2answers
20 views

Proving that a set of relating elements is infinite

I want to prove the following: Let $<$ be a well-founded relation on a set X such that $\leq$ is a total order. Show that the set $$\{x\in X: x < y\}$$ is infinite for some $y \in X$. I ...
0
votes
4answers
42 views

Symmetry, transitivity and reflexivity

I need some help on how to approach this problem. I can't seem to find any examples that help me understand this, so if anyone has an approach example to post I would be very grateful: "Consider a ...
0
votes
1answer
15 views

For a given type X, rigorously show that idX = (idX)^-1

For a given type X, rigorously show that idX = (idX)^-1 I have done the following so far: ...
0
votes
1answer
22 views

Finding how many distinct equivalence classes there are.

Define a relation R on the set of all integers Z by xRy (x related to y) if and only if x-y=3k for some integer k. I have already verified that this is in fact an equivalence relation. But now I ...
0
votes
1answer
17 views

Proving symmetry and transitivity of a relation

Let R be the relation {(1,1),(1,2),(2,2),(1,3),(3,3)} on the set {1,2,3}. I am having difficulty proving that it is symmetrical and transitive. I know for symmetry we have to prove if xRy then yRx (...
1
vote
1answer
28 views

Let $R = \{(x, y) : y = x + 5\ and\ x \lt 4\}$ be a relation in $\Bbb N$. Is it transitive?

Clearly $R = \{(1, 6), (2, 7), (3, 8)\}$. From this it follows that for any $R(a, b), \ R(b, c)$ does not exist. Does this imply that the relation is transitive? Edit: Since, there are no examples ...
1
vote
2answers
20 views

Symmetric relation and definition of even numbers

Let a relation $\rho$ be defined on $\mathcal{Z}$(set of integers) by '$a \rho b$ if and only if $a-b$ is even' for $ a,b \in \mathcal{Z}$. Then, is the above relation symmetric or anti-symmetric? ...
1
vote
1answer
27 views

Proof equivalence relation with functions

We define 2 function: $f : X \rightarrow X$ and $g : X\rightarrow X$ and we define $ V(f,g) = \{x \in X | f(x) \neq g(x) \} $. Next we define a relation $R$ on the set Fun($X,X$) of all functions ...