Stack Exchange Network

Stack Exchange network consists of 174 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.

0
votes
1answer
26 views

How to prove that a relation is transitive when the binary operation is commutative?

Let $A$ be a non-empty set and suppose that $*$ is a binary operation on $A$. We define a relation $R$ on the set $A$ as follows: $R = \{ (x,y) \in A \times A: x*y=y*x\}$. In other words, given $x,y ...
-1
votes
2answers
38 views

How to prove that a relation on a set with two elements is transitive? [closed]

Let $A$ be a non-empty set and suppose that * is a binary operation on $A$. We define a relation $R$ on the set $A$ as follows: $R=\{(x,y) \in A \times A : x * y = y * x \}$. In other words, given $...
0
votes
0answers
31 views

Relation between two functions defined by and integral

Let us consider the two functions $$F(x) = \int\limits_x^1 {h(s - x,s)ds - } \int\limits_{1 - x}^1 {h(2 - s - x,s)ds} $$$$G(x) = \int\limits_0^x {h(x - s,s)ds - } \int\limits_0^{1 - x} {h(x + s,s)ds} $...
0
votes
2answers
35 views

Proving transitivity: Let $a,b,c \in A$. We want to show $(a,b) \in A$ and $(b,c) \in A$, then $(a,c) \in A$. [closed]

Will this be enough to prove transitivity? I am still new to proofs. Let $a,b,c \in A$. We want to prove that for all $(a,b) \in A$ and $(b,c) \in A$, then $(a,c)$ are in $A$. Assume $(a,b)$ are ...
2
votes
0answers
28 views

Terminology/notation for set of all images of a preimage (and vice versa) in a relation

Let $R \subseteq X \times Y$ Is there a commonly used term for the functions $f:X\rightarrow \mathcal{P}(Y)$ and $g:Y\rightarrow \mathcal{P}(X)$ defined as follows?: $$f(x) = \{ y \mid (x, y) \in R\}...
0
votes
1answer
33 views

Sufficient and necessary binary relation for given metric

Problem: Let $p$ be binary relation on the set $X$, for any $x,y$ $\in$ $X$ let: $$ d(x,y) = \begin{cases} 3, & \text{for } \hspace{0.5cm}xpy \\ 0, & \text{for} \hspace{0....
-1
votes
0answers
30 views

Base enlargement/isomorphism of models over a model [on hold]

How can I see that if models $M_0$ and $M_1$ are isomorphic over $N_0$ and $N_0\leq_{\frak K} N_1$ then they are isomorphic over $N_1$? It is almost obvious but not quite.Any simple argument will help....
0
votes
1answer
14 views

Can sets A, B and C be transitive or does transitivity hold just for individual relations. Also does missing relation prove this false?

Can sets A, B and C be transitive or can we describe only individual relations as being transitive. Also does missing a single relation between two sets mean we can't describe the relation as ...
0
votes
1answer
28 views

sets theory-Realation proof question

Let $A,B,C$ and $R,S,T$ be sets. And assume that $$ R \subseteq A \times B, ~~ S \subseteq B \times C, ~~ T \subseteq B \times C.$$ Then, I want to show that $$ \begin{equation} (S \circ R) \cap (...
2
votes
0answers
49 views

Why are mathematical theories based on functions rather than relations?

While the concept of a function is intuitive, it involves a lot of quantifiers that seem arbitrarily chosen. Why must every source be sent to one, and only one target? We don't demand codomains to be ...
0
votes
2answers
42 views

Direct mapping and inverse mapping: when they can be equal?

I read the following phrase from a textbook Bijection $\ f : M \rightarrow M$ known as symmetry if $\ f^{-1} = f$. I am curious, are there any examples of $\ f^{-1} = f$ outside of identity ...
1
vote
2answers
39 views

Order properties of the empty relation on the empty set, and a related question

Context / Disclosure on the Origins of the Question: My question is motivated by an MSE question posted earlier today which ultimately was closed. I was thinking about it when it was posted, just for ...
2
votes
1answer
60 views

Number of relations on a set of $n$ elements [closed]

http://mathonline.wikidot.com/the-number-of-distinct-relations-on-a-finite-set From the link above I'm having trouble understanding how from $n^2$ ordered pairs which are either true or false there ...
5
votes
0answers
73 views

Relation induced topology

For an ordered space $X$ there is the term of ordered topology generated by sets of the form: $l(x)=\{ y\in X: y<x\} $ and $r(x)=\{ y\in X: y>x\} $ I was wondering if someone had encountered ...
0
votes
1answer
40 views

Is a set together with an operation always a relational structure?

I'm reading Algebraic Methods in Philosophical Logic, an introductory book on Universal Algebra by by J. Michael Dunn, Gary Hardegree. This book start its presentation by introducing the notions of "...
-1
votes
0answers
62 views

Show that $\langle a , b | a^2 = b^3 = e \rangle$ is infinite and nonabelian. [duplicate]

Prove that the group $G$ defined by generators $a,b$ and relations $a^2 = b^3 = e$ is infinite and nonabelian. This is a question from Algebra by Hungerford, Section I.9, page 69. This question may ...
0
votes
1answer
17 views

Equivalence relation and a function

Suppose $A$ is a nonempty set and $R$ is an equivalence relation on $A$ . Show that there is a function $f$ with $A$ as its domain such that $(x,y) \in R$ if and only if $f(x)=f(y)$
6
votes
6answers
98 views

How can $y=\sqrt{4-3x}$ be a function? [duplicate]

can someone please explain how can $y=\sqrt{4-3x}$ be a function? I thought any equation that has a square root sign is not a function, because of the ± sign in front of it? For example, lets say we ...
0
votes
1answer
14 views

How do I precisely characterise this “extension” of transitivity?

A binary relation $R$ over a set $X$ is transitive if: $$\forall a,b,c \in X.(aRb\wedge bRc) \Rightarrow aRc$$ Let me define a particular relation $R$ over $\mathbb{N} = \{0, 1, 2,\dots\}$: $$aRb :...
0
votes
2answers
52 views

Set membership and a box of bananas

Suppose that I have two boxes $A$ and $B$, each of which contains some number of identical (indistinguishable)* bananas. If I treat $A$ and $B$ as multisets whose elements are bananas, it follows ...
1
vote
2answers
31 views

Prove that $R\subseteq X\times X$ is an equivalence relation and construct its equivalence class

Prove that relation $R\subseteq X\times X$, where $X= \mathbb{R}\times\mathbb{R}$, is an equivalence relation and construct its equivalence class. $R$ is defined as: $$\langle x_1, y_1\rangle R \...
0
votes
1answer
20 views

Given two posets $\preccurlyeq$, prove that the following relation $R$ using both of them is transitive

We're given the following relation $R$ for two posets $(S_1, \preccurlyeq_1)$ and $(S_2, \preccurlyeq_2)$: For $a_1,b_1 \in S_1$ and $a_2, b_2 \in S_2$: $(a_1, a_2)R(b_1,b_2) \Leftrightarrow (a_1 \...
-1
votes
1answer
46 views

Discrete mathematics, defining (+, *) operations on a equivalence relations.

In a set: $\mathbb N/xSy$ ($xSy$ defined on natural numbers and as $k|(x - y)$ and $k$ is a natural number) We define: $+_k, *_k$ as: $$[x]_S +_k[y]_S = [x + y]_S$$ $$[x]_S *_k[y]_S = [xy]_S$$ ...
-1
votes
1answer
38 views

Equivalence relation! Make formula saying that R is not an equivalence relation [closed]

I don't know how to do this particular thing. Using quantifiers and logical links as $$and, or, =>, <=>$$ and expressions like $$x\in A, x\notin A, R(x, y), \lnot R(x, y)$$ Make formula ...
2
votes
1answer
61 views

Equivalence relations and their classes

Check for which $k$ given relations on set $\mathbb{N}$ are reflexive, symmetric or transitive. For these relations, that are equivalence relations, describe their equivalence classes. $xR_ky \...
1
vote
1answer
18 views

Canonical factorization of a certain function

Given the sets $A=${$x_i|1\leq i\leq 9$} and $B=${$y_j|1\leq j\leq 6$} we consider the map $f:A\to B$ defined by: $$f(x_1)=y_1 \qquad f(x_2)=y_1 \qquad f(x_3)=y_3 \\ f(x_4)=y_3 \qquad f(x_5)=y_3 \...
0
votes
1answer
21 views

Number of relations on 6 element set which are both symmetric and reflexive but not anti-symmetric.

I did this by imagining a Venn diagram. Number of relations which are Reflexive and Symmetric would be given by $2^{\binom{n}{2}}$ . Now, this also contains some Anti-symmetric relations. Number of ...
0
votes
1answer
38 views

What are isomorphic partitions?

Let $R_1, R_2 ∈ R(X)$ be equivalence relations on $X$. Define $R_1$ and $R_2$ to be isomorphic if there exists a bijection $f : X → X$ such that the following holds: For all $y, z ∈ X : (y, z) ∈ R_1$ ...
1
vote
1answer
29 views

Notion of submodel relation

There is no definition of the essential notion of substructure (=submodel) in Shelah's introduction E56 to AEC, 1st Volume. Could someone please define this for me? I think that $$M \subseteq N$$ ($M$ ...
0
votes
2answers
43 views

Isomorphic equivalence relations and partitions

Let $R_1$, $R_2$ ∈ R(X) be equivalence relations on X. Define $R_1$ and $R_2$ to be isomorphic if there exists a bijection f : X → X such that the following holds: For all y, z ∈ X : (y, z) ∈ $R_1$ ...
2
votes
1answer
53 views

How to solve a recurrence relation with generating functions?

I don't really understand how to solve (with generating functions) for the recurrence relation of $$a_n = a_{n-1}+2(n-1)$$ with initial conditions of $a_1 = 2$ when $n \geq 2$ This is what I was ...
1
vote
1answer
40 views

What are the equivalence classes of this relation?

Let $f \colon X → X$ be an injective function. For $y, z ∈ X$, define $y \sim z$ to mean there exists an integer $n ≥ 0$ such that either $f^n(z) = y$ or $f^n(y) = z$. (Here $f^0(z) = z$ for all $z ∈ ...
2
votes
1answer
26 views

Möbius function - understanding of relations

I am trying to understand Möbius function from the wikipedia article (and also few others that I have come across so far). This function is defined in posets and so the relations in Special elements ...
-1
votes
1answer
17 views

Equation of a peak diagram

May you please help me how can I extract the equation for this diagram? This is the diagram (Click) I know that the right side is y=2-2x
0
votes
1answer
23 views

What properties does $R$ have to satisfy for $R=\operatorname{graph}(f)$ for some function $f:A\to B$?

Given a relation $R$ between $A$ and $B$, what properties does $R$ have to satisfy for $R=\operatorname{graph}(f)$ for some function $f:A\to B$?
0
votes
1answer
35 views

Arrange people at round table so that everyone knows the two people next to them

Each of the guests know: a) more than half of the guests b) at least half of the guests. Prove that in both of these cases it is possible to arrange them to sit around a round table so that everyone ...
2
votes
1answer
36 views

Relations and understanding anti-symmetry

The below picture is a problem involving relations from a review set. I have only seen problems with relations involving matrices and solving for the properties of reflexive, symmetric, and transitive....
0
votes
2answers
28 views

What does this relation represents ?

so i have a hard time understanding what would this relation looks like, we aren't given any precise function so it's hard to know what this would look like. We have to establish the relation and then ...
1
vote
2answers
35 views

How to determine if a set relation is Transitive?

So, as far as binary relations go, I have a firm grasp on the symmetric, anti-symmetric, and reflexive relations. However, when it comes to transitive relations, I run into a block. In this problem, ...
0
votes
1answer
25 views

Subtraction in Building a Set from Nonnegative Reals

When defining equivalence classes using elements contained by the nonnegative reals, may I use subtraction in the function that defines equivalence between those classes? My thinking is that if ...
0
votes
1answer
16 views

Determining whether or not a relation involving absolute value is transitive

I needed help doing a relation problem the specific problem is $|x+y|$ = $|x|$ + $|y|$ I first tried thinking of some counter-examples but I couldn't think of any so i tried showing it. So to show ...
0
votes
1answer
23 views

Reflexive, symmetric, and transitive closures

The problem: I am having difficulty with this problem. How do I even start? I know what reflexive, symmetric and transitive closures intuitively mean but I am struggling to find s(r(R)), (symmetric ...
0
votes
1answer
38 views

Question in Proof That Every Well-Ordering is a Total-Ordering

I am trying to make sense of the following: Theorem: Let $R$ be a relation on a set $A$. If $R$ is a well-ordered relation on $A$, then $R$ is a total-order relation on $A$. Proof: Suppose $x,y\...
0
votes
0answers
14 views

Domain relational calculus

There are 2 relations: Prediction(cname, etype) Measures(etype, provider) cname - city name of predicted future disaster. etype - event type. earthquake, tsunami... provider - police, ambulance......
2
votes
2answers
40 views

Is there a name for this relation: for all $x$ there is $y$ such that $xRy$, and for all $x,y,z$, if $xRy$ and $xRz$, then $y=z$?

Suppose for all $x$ there is $y$ such that $xRy$, and for all $x,y,z$, if $xRy$ and $xRz$, then $y=z$. Does there exist such a binary relation $R$ on some set such that the above properties are ...
0
votes
1answer
21 views

question on showing transitivity of a relation

Define a relation on Z as xRy if |x−y|<1. I have shown this relation is symetric and reflexive and i am pretty sure its transitive because this is the equality relation isnt it? thats my first ...
2
votes
0answers
86 views

What is $ {\square}_{\mathscr A \triangledown \mathscr B} $?

I'm currently working trough a set of notes on uniform spaces. I came upon a problem that I'm having some difficulties solving, so I am seeking assistance in the form of clarifications, hints or ...
0
votes
1answer
26 views

Reflexive property of relations? [duplicate]

If a relation is both symmetric and anti-symmetric, isn't it always reflexive? I am supposed to consider a set, S, where some Relation A is both symmetric and anti-symmetric. I thought that anti-...
0
votes
1answer
32 views

Prove, that for any A, B, C sets, $A\times (B\setminus C) = (A\times B)\setminus (A\times C)$ is true.

I have to prove the equation $$A\times (B\setminus C) = (A\times B)\setminus (A\times C)$$ knowing that $$A\times B = \{<a,b> |\: a\in A \wedge b\in B\}$$ which I attempted to do the following ...
0
votes
1answer
18 views

The relation $T$ on $\mathbb{R}\times \mathbb{R}$ given by $(x,y)T(a,b)$ iff $x^2+y^2=a^2+b^2$. Sketch the equivalence class of $(1,2)$; of $(4,0)$.

The relation $T$ on $\mathbb{R}\times \mathbb{R}$ given by $(x,y)T(a,b)$ iff $x^2+y^2=a^2+b^2$. Sketch the equivalence class of $(1,2)$; of $(4,0)$. $T$ is an equivalence relation on $\mathbb{R}\...