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
11
votes
5answers
13k views

'Does not necessarily equal' symbol

What symbol would I use if I wanted to express that, in the context of some binary relation $P$ implied from context, that $\exists (a,b)\in P: a\ne b$, but not to the extent that $\forall (a,b) \in P:...
2
votes
1answer
28 views

Does every infinite graph contain a maximal clique?

The original problem is stated in terms of the tolerance relation (reflexive and symmetric, but not necessarily transitive): Is every tolerance subset contained in a maximal tolerance subset? For a ...
0
votes
1answer
37 views

Multiple-select question on chinese remainder theorem [closed]

Which of the following integers can be written in the form $595m+252n$ where $m$ and $n$ are integers. $1$ $5$ $7$ $63$ Now can we use the Chinese remainder theorem in this? I don't know how could ...
0
votes
0answers
27 views

Question on equivalence classes in a relation

Let $S$ = $\{(x,y)^T : x,y \in \Bbb{R}\}$. Define a relation $R$ on $S$ by $aRb$ iff there exists a $2\times2$ invertible matrix $A$ such that $Aa$ = $b$. I have shown that $R$ is an equivalence ...
1
vote
1answer
76 views

Prove that the functions $F$ and $G$ which have same domain and range are equal.

The question is stated as: Consider any functions $F$ and $G$. Prove that, if $F$ and $G$ have the same domain $A$, For any $x$ in $A$, $F(x) = G(x)$, Then $F=G$ (Hint: Show that $(x,y) \in F \...
0
votes
1answer
34 views

What concept of order is introduced in the twentyfold way?

Four of the folds not present in the twelvefold way but introduced in the twentyfold way, rows $5$ and $6$ of the linked table, are defined by the statement that order matters. However, my ...
2
votes
1answer
52 views

Prob. 3 (d), Sec. 1, in G.F. Simmon's INTRO TO TOPOLOGY & MODERN ANALYSIS

Here is Prob. 3, Sec. 1, in the book Introduction To Topology And Modern Analysis by George F. Simmons. (a) Let $U$ be the single-element set $\{ 1 \}$. There are two subsets, the empty set $\...
0
votes
0answers
10 views

Should the formula for Confidence of association rule contain union or intersection? [closed]

the strength of an association rule is measured in terms of its support, the frequency of transactions that contain both I and J, and its confidence, the frequency of transactions that contain J when ...
2
votes
1answer
23 views

$f^*(U_1 \times … \times U_k) = \bigcap_{i=1}^k f^*_i(U_i)$

I’m trying to prove this result and I would really appreciate if you could give some feedback in my proof. Result: Let $A,A_1,...,A_k$ be sets, for some positive integer $k$, let $f: A \rightarrow ...
0
votes
0answers
28 views

Determine if relation $R$ is an equivalence relation and if it is describe the equivalence classes. $(x-y) \cup (y-x)$

The question is stated as: Determine if the relation $R$ is an equivalence relation on $A$ and If it is, describe the equivalence classes. $A$ is the set of all subsets of the set of integers $R = \{(...
6
votes
3answers
5k views

Is the empty set partially ordered ? Also, is it totally ordered?

I am not sure on how to go about this. Please provide clear explanations.
2
votes
1answer
39 views

Number of asymmetric partial functions over a finite non-empty set

Let $S$ be a finite non-empty set. I recently used the presumed fact that the number of asymmetric partial functions over $S$ is $3^{|S|-1}(|S|-1)!$, after I became quite convinced of it, since it ...
0
votes
3answers
67 views

Proving $xRy\iff xy^{-1}\in\ker(f)$ is equivalent relation, where $f:(G,.) \to (H,.)$ is homomorphism of groups $G$ and $H$.

I know for sure it is but I failed to prove how. I tried to use the homomorphism definition where $f(x*y^{-1}) = f(x)*f(y^{-1})$ but I didn't see a pattern.
2
votes
1answer
51 views

Find a relation which is reflexive and symmetric but not transitive on integers

The question is stated as: Let $A$ be the set of integers, find a relation $R$ which is reflexive and symmetric in $A$ but not transitive in $A$. By definition we have that. $R$ is reflexive in $A$$ \...
0
votes
0answers
35 views

What is a binary relation and transitive closure?

-Self studying 2Yr Undergraduate Discrete Math -Background: Calculus 3, probability 1, statistics 1, linear algebra 1, ODEs 1, stochastics 1 Hi, I'm studying relations and want to confirm I ...
7
votes
1answer
4k views

$R$ is transitive if and only if $ R \circ R \subseteq R$

Question: Let $R$ be a relation on a set $S$. Prove the following. $R$ is transitive if and only if $ R \circ R \subseteq R$. Definition 6.3.9 states that we let $R_1$ and $R_2$ be relations on a ...
0
votes
4answers
181 views

Does symmetry and transitivity imply reflexivity for nonempty binary relation?

I've seen a few answers to this, like here and but they are not satisfying to me (possibly too advanced). The definitions in my book are as follows: A binary relation $\mathrel{R}$ on two sets $A$ ...
0
votes
2answers
53 views

Is equality under the integers {…-2,-1,0,1,2,…} symmetric and antisymmetric?

I am reading a scripture from my university in discrete mathematics. It says that equality under the integers is reflexive, symmetric and transitive. However, isn’t it also antisymmetric? Since if (a,...
2
votes
5answers
452 views

Determine whether each of the relations $f=\{(a,b), (c,d), (e,f), (g,h), (i,j)\}$ is a function with domain $\{1,2,3,4\}$

1.) Determine whether each of the following relations is a function with domain $\{1,2,3,4\}$. For any relation that is not a function, explain why it isn't. a.) $f=\{(1,1), (2,1), (3,1), (4,1), (3,3)...
1
vote
1answer
41 views

Relation $S$ is equivalence reltion in set $A$. Is relation $S^{-1}$ equivalence relation in set $A$ either?

Let $S \subset A^2$ and $S=\{(a,b): aSb\} .\ $Then $\ S^{-1}=\{(b,a):aSb\} \subset A^2.$ That means $S^{-1}$ is also equivalence relation, because every pair is in the same relation as in relation $S$ ...
2
votes
1answer
33 views

I have a problem understanding the proof of numbers (Derangements)

I am reading the book of mezo 2016 . This is part of it . Definition 1. An FPF permutation on $n + r$ letters will be called FPF r-permutation if in its cycle decomposition the first r letters appear ...
1
vote
0answers
46 views

Give an example of a strictly monotone function which is not injective.

The following question/task is from Taylor's, "Practical Foundations of Mathematics," page 175, ISBN 0 521 63107 6 hardback. I kind of answered it myself in typing this up, but I'll share it ...
2
votes
1answer
53 views

What is meaning of $X/P$? ($X$ is a set and $P$ is a partition)

The definition of $x/E$ when $E$ is an equivalence relation is : $$x/E = \{y\in X \mid (y,x)\in E \},$$ and the definition of $X/E$: $$X/E = \{x/E\ \mid x\in X\}.$$ Now, what is $X/P$ when $P$ is a ...
0
votes
1answer
2k views

Proving transitivity of a relation

Let R be a reflexive relation on a nonempty set X. The asymmetric part of R is defined as the relation $P_r$ on X as $xP_ry$ iff $xRy$ but not $yRx$. The relation $I_r$ = $R\setminus P_r$ on X is ...
0
votes
2answers
27 views

How does relation R on A not satisfy these conditions?

I think my math professor might have corrected my test questions wrong. I got wrong on 3 questions that look right to me, they are about relationships on sets. The questions: Let A = {1, 2, 3, 4} and ...
0
votes
0answers
31 views

Partially ordered set- maximum and minimum elements.

In the set of positive rational numbers, consider partially order relation, defined as follows : $$\frac{x}{y} \prec \frac{a}{b} \iff \frac{x}{y},\frac{a}{b} \text{are non-reduced fractions}\ \land \ ...
0
votes
1answer
27 views

Smallest lattice which is a boolean algebra can contain only one element?

if we have ({1},>=) then 1>=1 therefore reflexive ,anti-symmetric as (1,1) ,transitive . so it is a POSET and 1^1=1 and again 1LUB1=1 so 1 is the complement of itself the set has LUB and GLB for ...
0
votes
1answer
12 views

Confusion regarding number of ordered pairs for symmetry/asymmetry

My Discrete Mathematics textbook says the following : A relation is symmetric/antisymmetric/transitive even if there’s one pair/triplet that satisfies the condition. This probably means that if I ...
4
votes
1answer
534 views

On $N \times N $ define the relation R, setting $(a,b),(c,d) \in R$ if and only if $a+d=b+c$. Show that $R$ is an equivalence relation.

On $N \times N $ define the relation R, setting $(a,b),(c,d) \in R$ if and only if $a+d=b+c$ a. Show that $R$ is an equivalence relation. My attempt: By definition 6.2.3 $R$ is an equivalence ...
0
votes
1answer
48 views

A binary relation contained in its square

My colleague (I guess, investigating structure of specific semigroups) is looking for references about binary relations $R\subset X\times X$ such that $R\subset R\circ R$, that is for each $(v,u)\in R$...
1
vote
4answers
33 views

If R is a symmetric binary relation, what are x and y in set A?

everyone: I've been reading my textbook for discrete math and a few other textbooks on the topic of binary relations, and finding that I'm struggling to understand the definitions. I think a lot can ...
2
votes
1answer
63 views

Preordering on a set

I am given a definition which states that a 'preodering on a set is a relation that is reflexive and transitive.' Show that a relation $\leq$ defined on $\mathbb{C}$ by $z_1 \leq z_2$ iff $|z_1| = |...
1
vote
1answer
96 views

Properties Of Relations

The question asks if there can be a relation on a set that is neither reflexive or irreflexive. The example the book give makes perfect sense: "Yes, for instance $\{(1,1)\}$ on $\{1,2\}$." I ...
2
votes
2answers
66 views

A set as an algebraic structure

A set is collection of distinct objects: https://en.wikipedia.org/wiki/Set_(mathematics). The word distinct implies the identity relation on each set: an element of a set is equal to itself, or $a = a$...
3
votes
1answer
161 views

Restriction to equivalence relation is equivalence relation

Let $\mathcal{R}$ be relation on $A$ and $A_0 \subseteq A$. The $\mathbf{restriction}$ of $\mathcal{R}$ to $A_0$ is defined to be the relation $\mathcal{R} \cap (A_0 \times A_0) $. $\mathbf{Homework \...
1
vote
1answer
48 views

Is $R=\{(x,y):x-y \in \mathbb{R}-\mathbb{Q}\ \forall x,y \in \mathbb{R}-\mathbb{Q}\}$ an Equivalence Relation

Is $R=\{(x,y):x-y \in \mathbb{R}-\mathbb{Q}\ \forall x,y \in \mathbb{R}-\mathbb{Q}\}$ an Equivalence Relation Reflexivity: Obviously it is not Reflexive since $x=\sqrt{2}$ and $y=\sqrt{2}$ and $\...
1
vote
1answer
71 views

Prove that ¬ is an equivalence relation

Let $¬$ be a relation on $\mathbb{R}$ defined by $x¬y$ if $$y-x\in\mathbb{Z}$$ Prove that $¬$ is an equivalence relation on $\mathbb{R}$. How would one go about doing this? My gut instinct tells me ...
0
votes
1answer
32 views

Number of relations which are reflexive but not symmetric

I have following doubt. Pls have a look To find number of relations which are reflexive but not symmetric ——————————————————————————————— one way $n(R-S)=n(R)-n(R \cap S) = 2^{(n^2-n)} - 1* 2^{n(n-1)/...
0
votes
1answer
24 views

Prove, that $M=\{(a,b)\mid a,b \in \mathbb{N_0} \land (a-b) \text{ mod } 4 = 0\} $ is a equivalence relation

Prove, that $M=\{(a,b)\mid a,b \in \mathbb{N_0} \land (a-b) \text{ mod } 4 = 0\} $ is an equivalence-relation. Refl.: $a-a=0 \text{ mod } 4 =0$ Sym.: $\forall x,y \in M: (x,y) \implies (y,x)$ (Not ...
0
votes
0answers
24 views

Cartesian product and relations of multisets and hybrid sets

I recently encountered multisets and hybrid sets (allowing negative multiplicities), and have a feeling they might be useful for something I'm trying to model. The definitions of both are clear to me, ...
2
votes
1answer
27 views

What are the ordered pairs when A = {1, 3, 5, 15, 18} and R be defined by xRy if and only if x|y.

I just wanted to confirm I understand correctly: When trying to find the pairs for: A = {1, 3, 5, 15, 18} and R be defined by xRy if and only if x|y First I determine the factors: x|y 1 is a factor of ...
0
votes
1answer
28 views

If $R = \{(1,2),(1,4),(3,3),(4,1)\}$, then is $(1,2) \in R^2$? (Powers of Relation)

I basically got this: $R^2 =\{(4,4),(1,1),(3,3),(4,2)\}$ But I'm not sure if I should include (1,2) as well since 2 maps to nothing? Thanks
0
votes
1answer
11 views

Quick question about antisymmetric relationship.

Here we go, It is a really yes or no question. If aRb is a|b then is this antisymmetric? a, b belongs to integers including 0*
0
votes
3answers
40 views

How many equivalence classes will there be?

Consider the subset $T\subseteq \mathbb{Z}\times \mathbb{Z}\times \mathbb{Z}$ where the three numbers will be the corner angles (in degrees) of a (real) triangle. For example $(30, 70, 80)\in T$ but $(...
0
votes
2answers
34 views

Let R = $\{ (n+4,n) \mid n \in \Bbb Z^+\}$, Find $R^2$

I found that this relation is not transitive, does this mean that $R^2$ does not exists? Any help is appreciated thanks!
1
vote
4answers
37 views

$A = \{1 , 2 , 3\}$ and $R = \{(1 , 1) , (2 , 2) \}$. Can anyone please tell me how would I explain that the relation $R$ is transitive?

Let $A$ be a set. $A = \{1 , 2 , 3\}$. $R = \{(1 , 1) , (2 , 2) \}$. Can anyone please tell me how would I explain that the relation $R$ is transitive ? My Attempt: I taught my student first what is ...
0
votes
1answer
53 views

Show whether the reflexive closure of R is an equivalence relation or not

Let $R$ be a subset of the set of ordered pairs of integers defined recursively by: $(0,0) \in R$ $(a,b)\in R \rightarrow (a+2,b+3) \in R \wedge (a+3,b+2)\in R$ I think that the reflexive closure of R ...
0
votes
0answers
22 views

How to express the relation between two matrices (or two vectors)?

If a=5 and b=12 then I can can express the relation between a and b as: a<b or b=a+7 But, if a=[2 5 17 29] and b=[2 3 30 15] How can I express the relation between a and b?
0
votes
1answer
30 views

Logical implication and conjunction in transitive relation definition

In the properties of relations, the transitive relation is defined as follows: If I read it informally, it says, "If $(a,b) \in R$ and $(b,c) \in R$, then $(a,c) \in R$ What surprised me was ...
0
votes
0answers
28 views

Analog of codomain and image in context of relations

I was reviewing relations and functions and I came across the definition serial which is new to me. This more or less throws a wrench in what I thought I understood and I'm seeking clarity. If I think ...

1
2 3 4 5
76