Skip to main content

Questions tagged [relations]

For questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric, etc), a composition of relations, or anything else concerning a relation on a set.

Filter by
Sorted by
Tagged with
0 votes
0 answers
11 views

Inverse Relation for Allocating an Amount

This question came up in the context of project finance. It is my original question. Quick Version A project has upfront cost $X$, and ongoing cost $Z$. (Z is less than X). There are the same $N$ ...
VISQL's user avatar
  • 193
-1 votes
0 answers
17 views

How to prove that $f$ inverse: $Y \to X$ is one-one and onto given that $f^{-1}:X \to Y$ is one-one and onto? [closed]

If $f:X \to Y$ is one-one and onto, then prove that $f^{-1}:Y \to X$ is also one-one and onto.
Aashi Brijpuria's user avatar
0 votes
0 answers
57 views

Why do we care about well-founded sets? [closed]

Well-founded sets are frequently studied in set theory. I wonder what are the motivations for caring about them ? We study them just for sake of curiosity or are there any reasons/problems/...
InTheSearchForKnowledge's user avatar
0 votes
1 answer
50 views

A relation coming both transitive and not transitive

A relation $R$ is defined as $(x,y)\in R \implies x^y=y^x$ for $x,y\in\mathbb{I}-\{0\}$, where $\mathbb{I}$ is the set of integers. Find whether the relation $R$ is transitive or not. Let $x^y=y^x$ ...
MathStackexchangeIsNotSoBad's user avatar
2 votes
0 answers
38 views

Name for a property of a binary relation

Is there a common name for the following property of a binary relation $R$: $$x\mathrel{R}y\quad\text{and}\quad x\mathrel{R}z\quad\Longrightarrow\quad y\mathrel{R}z\quad\text{or}\quad z\mathrel{R}y\...
Bartosz's user avatar
  • 121
0 votes
2 answers
60 views

Why is the relation $\{(1,1),(2,2),(3,3)\}$ antisymmetric and transitive? [duplicate]

Today, my teacher said that $R=\{(1,1),(2,2),(3,3)\}$ is reflexive, symmetric, antisymmetric and transitive on set $A=\{1,2,3\}$. I can see that it is reflexive clearly. Moreover when I think $x=1,y=1$...
user avatar
7 votes
2 answers
350 views

Number of One-One Functions

This question has been asked in my exam and I have stuck. The question says:Let $S=\{1,2,3,4,5,6\}$. The number of one-one functions $f$ defined from $S$ to $P(S)$, where $P(S)$ stands for power set ...
20DPCO190 Amanul Haque's user avatar
0 votes
0 answers
24 views

Computing transitive closure for relation via other relation

The closure of a relation $R$ over a set $S$ is denoted $R[S]$ and calculated via $\bigcup_{i\in\mathbb{N}}Y_i$ where $Y_0=S$ and $Y_{n+1}=Y_n\cup R(Y_n)$. ($R(Y_n)$ is the image of $Y_n$ under $R$). ...
Aresiel's user avatar
1 vote
2 answers
40 views

Is there a left extensional relation which is not right extensional?

A binary relation $R$ on a set $S$ is defined to be left extensional if the following property holds, where $x$, $y$, and $z$ refer to elements in $S$: $(\forall x)(\forall y)((\forall z)(zRx \...
user107952's user avatar
  • 20.7k
4 votes
2 answers
241 views

Are we assuming a relation to be transitive untill proven otherwise?

I do not know if the title would be correct title for the question but I think I am asking a valid question. While studying set theory and relations we were often asked about whether a relation $R$ is ...
madhurkant's user avatar
0 votes
0 answers
22 views

How to describe the transitive closure of a relation in terms of the ground relation

Let $X$ be a non-empty set and $\equiv$ a relation on $X$, which is symmetric and reflexive but is not transitive. I know that there exists a transitive closure of $\equiv$, saying, $\equiv_{cl}$. But ...
Kaique Roberto's user avatar
-2 votes
1 answer
25 views

Question about set. Reflexive, symmetric and transitive [closed]

For each of these relations below on the set {1, 2, 3, 4}, determine whether it is reflexive, symmetric and/or transitive. {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} {(1, 1), (1, 2), (2, 1), (2,...
Tan Tian Xiang's user avatar
0 votes
0 answers
28 views

Is there a Shorthand/notation for "R is a relation form A to B"?

The question is essentially what the title says; is there a shorthand/notation for "$R$ is a relation form $A$ to $B$" or the general version "$R$ is a relation between $A_1$, ..., $A_n$...
Markus Brun Olsen's user avatar
0 votes
0 answers
58 views

Is there an inconsistency with the usually relation definitions?

If we want to use sets for relations then the domains and ranges must be functions $dom$ and $ran$, but then we have a problem; if a relation $R$ from $A$ to $B$, and $S$ from $C$ to $D$, are equal R =...
Markus Brun Olsen's user avatar
0 votes
0 answers
42 views

Properties of $(m, n) ∈ R \iff m > n$

Given the following relation, which properties does it fulfill? Is my reasoning correct or am I missing something? $(m, n) ∈ R \iff m > n$ 1.) reflexivity no, $1 > 1$ (trivially false) 2.) ...
einzigartigerhummer's user avatar
0 votes
0 answers
7 views

Smooth partial orders

Suppose you have a partial order $<_o$ on $R^n$, and you restrict it to a relation $<_r$, where $x <_r y \iff x <_o y \wedge ||x - y|| < r$. Now it might happen that $<_o$ happens to ...
causative's user avatar
  • 273
1 vote
0 answers
56 views

Is this formula for number of binary relations correct?

I'm trying to determine the number of binary relations between sets $A$ and $B$ that are both left-unique and right-unique, which we call one-to-one. That is, relations $R$ such that every $a \in A$ ...
markusas's user avatar
  • 346
-1 votes
1 answer
59 views

Let f be a function f: A → B, and let A1, A2 ⊆ A. Then f(A1 ∩ A2) = f(A1) ∩ f(A2).

Question: Let f be a function f: A → B, and let A1, A2 ⊆ A. Then f(A1 ∩ A2) = f(A1) ∩ f(A2). Answer: $$ f(A_1 \cap A_2) \subseteq f(A_1) \cap f(A_2) :$$ Let $ y $ be an arbitrary element in $ f(A_1 \...
peterparker321's user avatar
0 votes
2 answers
33 views

Relations Symmetry and Transitivity

Given the following Relations over the set $M := \{α, β, γ\}$ $R1 := \{(α, α), (α, β), (β, α), (β, β), (γ, γ)\}$ How is $R1$ transitive? The condition for transitivity is $(a,y)\in R1 \text{ and }(...
robsmayer's user avatar
0 votes
0 answers
11 views

finding symmetric closure of inequality

In Discrete math and its app book from Kenneth H. Rosen says that What is the symmetric closure of the relation $R=\{(a,b) | a >b\}$ on the set of positive integers ? The answer of book following:...
user avatar
3 votes
2 answers
70 views

Generalization of the fact that pre-images of a function preserve more set operations than images

Given a function $f: A \rightarrow B$ images of subsets of $A$ preserve only inclusion and union of sets whereas pre-images of subsets of $B$ are better behaved, so to speak, and preserve (in addition ...
Marcus Junius Brutus's user avatar
1 vote
1 answer
38 views

Question regarding Transitivity of a Relation

Suppose we define a relation $R$ in the natural set $\mathbb N$ which says: $$(x,y)\in R\iff x^2-4xy+3y^2=0$$ and we would like to find which of the following properties does $R$ satisfy. My book ...
20DPCO190 Amanul Haque's user avatar
1 vote
1 answer
35 views

Is there a similar notion to the domain dual to codomain and range

Given a function $f\colon X \to Y$, $X$ is called the "domain", $Y$ is called the "codomain" and the range of $f$ is defined to be the set, $\{ y \in Y \mid \exists x \in X \colon ...
Shthephathord23's user avatar
0 votes
1 answer
34 views

Does the range of a one-one function need necessarily to be equal to its co-domain?

I came across a question which says- "If a set A contains 7 elements and the set B contains 8 elements, then number of one to one mappings from A to B is:" The answer is given zero The ...
Synthia's user avatar
4 votes
0 answers
76 views

Equivalence Relation Textbook Mistake

I found a question in my textbook but I think the answer provided is wrong. The question says: Let $S$ be a relation defined over $\mathbb R$ such that $(a,b) \in S \iff ab≥0$. Is $S$ equivalence? ...
20DPCO190 Amanul Haque's user avatar
2 votes
1 answer
188 views

Number of possible relations with following restrictions | Discrete Mathematics [closed]

I am new to math. stack exchange, I am really not sure how I am supposed to ask this but I need a logical explanation and a way to logical way to approach questions like these. I tried doing it myself....
Alwaysneedhelp's user avatar
0 votes
1 answer
38 views

Prove: Given that $R,S$ are equivalence relations then if $R \circ S$ is transitive then $R \circ S \subseteq S \circ R$.

In another post entitled: "Proof that composition of equivalence relations $R$ and $S$ is transitive if and only if $R \circ S = S \circ R$" the following proof is given for the forward ...
Geoffrey Critzer's user avatar
2 votes
2 answers
71 views

The number of relations over a set

I need to calculate the number of relations over $A$, when the size of $A$ is $n$, and want to understand why my approach is not correct. I denoted $A_i$ as subset of $A$, and I said general relation ...
miiky123's user avatar
  • 217
0 votes
0 answers
45 views

Is there a way to find if there relationship of numbers

I have a challenge. This may be little tricky or even not possible but wanted to check if anyone has any thoughts on this? PS : This question is in general and not related to only to R. May be I can ...
manu p's user avatar
  • 111
4 votes
2 answers
204 views

Determine the pairs of integers $(x,y)$ that verify the relation: $x^2y^2+2xy+36=3y^2+8x^2$

the question Determine the pairs of integers $(x,y)$ that verify the relation: $$x^2y^2+2xy+36=3y^2+8x^2$$ the idea Fist of all I tried getting everything on the LHS and write it as a product of ...
IONELA BUCIU's user avatar
  • 1,389
0 votes
1 answer
53 views

Can a relation be non reflexive, non symmetric, non antisymmetric and not transitive?

Lets say I have {a,b,c,d} I though of (a,b)(b,c) - but this is antisymmetric, right? Then I though of (a,b)(b,a)(b,c) but this time is transitive Finally I tried with (a,b)(b,c)(c,d) but again, is ...
Rodrigo Schillaci's user avatar
12 votes
3 answers
2k views

Can a function be defined as the union of two other functions?

So I read from various sources that a function can be defined as a binary relation. Then is it valid to say, for example, $f = \{ (1, 2), (2, 3) \}$? And suppose I have another function $g = \{ (4, 5) ...
Krystof's user avatar
  • 131
0 votes
0 answers
43 views

Cartesian multiplation

I got a little confused about Cartesian multiplication. Until now, I mainly used Cartesian multiplication over relations, and today my professor started combinatorics. He showed us that performing ...
miiky123's user avatar
  • 217
0 votes
1 answer
235 views

Precise axiomatic definition for the equality "=" as a binary relation

Question: What is a simple yet precise definition for "=" as a binary relation? My try: I find two definitions for "equality relation" which seems to be contradictory. The first ...
dodo's user avatar
  • 766
0 votes
1 answer
74 views

Let $A = \{1, 2, \ldots , n\}$ and R be the set of all equivalence relations on $A$.

Let $A = \{1, 2, \ldots , n\}$ and R be the set of all equivalence relations on $A$. Let $∼$ be the relation of equivalence over the set R, defined by: $R ∼ S \iff |A/R| = |A/S|$. Find $|R/∼|$. The ...
SAQ's user avatar
  • 365
1 vote
3 answers
133 views

Is the relation $(a,A)R(b,B)\iff A\cup[0;b]=B\cup[0;a]$ transitive?

Let $R$ be a relation on $\mathbb{N}\times\text{power set}(\mathbb{N})$, defined as $$(a,A)R(b,B)\iff A\cup[0;b]=B\cup[0;a]$$ Is $R$ transitive? As the notation $[0,x]$ caused confusion in one of the ...
SAQ's user avatar
  • 365
0 votes
1 answer
54 views

Determine whether a relation is symmetric

Let $R$ be a relation on $\mathbb{N}\times \text{power set}(\mathbb{N})$, defined as $$(a,A)R(b,B)\iff A\setminus B\subseteq\{a,b\}$$ Determine which of the properties reflexivity, symmetry, ...
SAQ's user avatar
  • 365
0 votes
1 answer
77 views

Proving Subtraction without using it??

Definition: $(a, b) \sim (c, d)$ iff $a + d = b + c$. Explain how this relation represents subtraction. (Do not prove that it's an equivalence relation.) I'm not sure how to answer this/what the final ...
DougHorn's user avatar
0 votes
0 answers
35 views

$\equiv$ is an equivalence relation on $P(\mathbb{N})$

$\equiv$ is an equivalence relation on $P(\mathbb{N})$ ($P(A)$ denotes the power set of the set $A$) defined as $$A\equiv B \iff A,B\subseteq \mathbb{N} \land (\forall X\subseteq\mathbb{N})[A\cup X=\...
SAQ's user avatar
  • 365
2 votes
0 answers
35 views

Number of partial orders such that a given function is monotone (order homomorphism)?

Given a set $X$, a poset $(Y, \preceq)$, and an arbitrary function $f: X \to Y$, how many partial orders $\le$ can one construct on $X$ such that $f$ becomes an order homomorphism $(X, \le) \to (Y, \...
hasManyStupidQuestions's user avatar
0 votes
0 answers
39 views

Find the number of all relations which are both both symmetric and antisymmetric. [duplicate]

Let $A=\{1,2,\ldots,n\},n\ge1$. Find the number of all relations $R\subseteq A\times A$ which are both both symmetric and antisymmetric. Okay, so a relation is symmetric if $(\forall a\forall b)(aRb\...
SAQ's user avatar
  • 365
0 votes
0 answers
42 views

Can an equivalence relation contain the null set?

An arbitrary partition $F$, for some equivalence relation $R$, importantly does not contain any set $X$ such that $X = \emptyset$. However, is it possible for a constituent equivalence class, $[x]_R$ ...
idk's user avatar
  • 125
1 vote
2 answers
57 views

Algebraic Proof that the Amplitude does not affect Frequency

In Simple Harmonic Motion, the Amplitude is defined as the maximum displacement. Consider a pendulum (SHM) or a mass on a horizontal or vertical spiring. If the amplitude increases, which means ...
Kyotiq's user avatar
  • 39
0 votes
1 answer
53 views

Write all injective, surjective and bijective functions with given domain and codomain

Edit: Adding the task condition: Write in explicit form, choosing a suitable representation, all functions f that are: a) injections b) surjections c) bijections and have the following domain and ...
strangeSausageXYM343's user avatar
1 vote
1 answer
64 views

What is the smallest equivalence relation containing two equivalence relations

I'm struggling with the following problem: Given two equivalence relations $q,s$ on set $X$. Prove that there exists the smallest (in a sense of inclusion) equivalence relation $r$ such that $g \cup s ...
user avatar
1 vote
0 answers
67 views

Axioms for equality [duplicate]

For first order logic without equality, what are the exact axioms we give to define the relation of equality ? I can't find the exact axioms even in Wikipedia... Any reference to any article or a list ...
user avatar
0 votes
2 answers
84 views

Proving $A \sim B \iff (\exists k\in \mathbb{N}^+)(\forall n \in \mathbb{N}^+)nk\in A \iff nk\in B$ is equivalence relation.

In an exercise I'm asked to prove that (not whether, the prompt assumes it is true) $$For \ A,B \subseteq \mathbb{N}\ \ A \sim B \iff (\exists k\in \mathbb{N}^+)(\forall n \in \mathbb{N}^+)nk\in A \...
4-4's user avatar
  • 13
0 votes
0 answers
46 views

Are all Relations statements? Or are all Statements relations?

Discrete math topic: Statements, to my understanding, can be predicates or quantifiers. Predicates and quantifiers are relations of Logical systems. Statements can be negated, I think. So, statements ...
Tyler Bakeman's user avatar
1 vote
0 answers
43 views

Question regarding monotone relations

I read on a paper that a relation $\mathcal{R} \subset \mathbb{R}^n \times \mathbb{R}^n$ is monotone if \begin{equation} (x_1 - x_2)^\top (y_1 - y_2) \geq 0 \end{equation} holds for any pair $(x_1, ...
Trb2's user avatar
  • 378
32 votes
12 answers
4k views

Is a function a set or a rule?

My textbook says that a function is a set, and that it is a kind of relation, which is also a set. Now: $$f(x) = x+5$$ is called a function, but the above expression is not a set. This is also true ...
Bhaskar Ghildiyal's user avatar

1
2 3 4 5
94