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.

learn more… | top users | synonyms

0
votes
1answer
59 views

Is $xRy$ iff $x$ and $y$ were born less than one week apart reflexive?

So I asked this question before without getting a solid answer. I went and studied a bit more about binary relations and reflexive relations. I understand the theory, but am unsure about whether my ...
1
vote
2answers
41 views

Determine which of the following relation is a function?

Given two set $ A = \{0, 2, 4, 6\}$ and $B = \{1, 3, 5, 7\}$, determine which of the following relation is a function? $(a) \{(6, 3), (2, 1), (0, 3), (4, 5)\}$, $(b) \{(2, 3), (4, 7), (0, 1), (6, ...
2
votes
2answers
61 views

Why Is $x \ne y$ Not Transitive on the Set of All integers?

I know this is a pretty simple question, but I'm just not getting the textbook... I'm taking a basic CS course and on one of the problems (not an assigned homework problem, just one I'm practicing ...
0
votes
1answer
34 views

Properties of the relation $(x,y) \in R$ if $| x-y | = 2 $

Is the following relation reflexive, symmetric, transitive, anti-symmetric and/or partial order : $$(x,y) \in R \text{ if }| x-y | = 2 $$ I think it's reflexive, I don't understand how to find for ...
2
votes
1answer
32 views

The binary relation $S=\phi$ on set $A=\{1,2,3\}$

I came across this question: The binary relation $S=\phi$ (empty set) on set $A=\{1,2,3\}$ is a) Neither reflexive nor symmetric b) Symmetric and reflexive c) Transitive and refelxive d) Transitive ...
0
votes
2answers
25 views

I need to prove that a relation is transitive.

I got $(x,y)R(u,v) \Leftrightarrow x + v = y + u$ I have to prove that this is a transitive relation. We did not do any examples how to do this at school so as far as I came was: $(x,y)R(a,b) ...
1
vote
1answer
39 views

Projection in n-ary relation.

So I got this question in my exam and I couldn't solve it. Later my professor gave me the solution but I'm not getting it properly. I guess my concepts on projection are not that strong. Can you ...
0
votes
1answer
34 views

Why relation divisibility is not relation partially ordered set on set Integer?

I try get it why relation divisibility is not relation partially ordered set. $A=\{−2, 2, 4, 6, 8, 10\}$ with relation divisibility "|" $R$ is relation divisibility | when $a,b,c \in Z : a = b ...
-1
votes
2answers
49 views

How would i visualize the set to be able to understand and answer this question

Let $A$ be the set of all people who have ever lived. For $x, y \in A$, $xRy$ if and only if $x$ and $y$ were born less than one week apart. Determine: (i) Whether or not the relation $R$ is ...
0
votes
0answers
24 views

Hasse diagram, find: max, min

We have got set of students in lecture room. Every student is in relation with yourselft, student X and student Y are in relation, if X is on left of Y (from view of teacher). Relation R: $(X,X) \in ...
0
votes
2answers
29 views

Proving or disproving statements about operations with integers

I'm really stuck with this one and I'm thankful for any help. Consider the following operations on the set of integers: $\hspace{8em} a\star b := a^2 + b^2 \hspace{5em} a\diamond b := a+b+2ab$ ...
0
votes
0answers
10 views

Few websites that generate random questions based on Set Theory and functions for practice

Are there any good websites that generate random sets so that a student can identify if the relations are reflexive | irreflexive | symmetric...etc As a whole, any websites that generate random ...
0
votes
1answer
28 views

Algebraic structures [closed]

I can't wrap my head around this area in mathematics. What is a group, a, semigroup, what is a field, a ring, an abelian group? I read all sorts of texts, but it's so abstract. I can't solve problems ...
1
vote
1answer
20 views

Check if ρ is an equivalence relation

Check if $$xρy \iff (x^2-y^2)(x^2y^2 - 1) = 1$$ is an equivalence relation. I know that for it to be an equivalence relation, a relation must have these properties: reflexivity, symmetry and ...
2
votes
2answers
25 views

Definition of the domain of a partial function

I have seen various places define the domain of a partial function $f$ on $S$ to be the set $S'\subseteq S$ of elements that $f$ is defined on. So then what do you call $S$ in terms of $f$? You ...
0
votes
1answer
43 views

Why does $xRy$, where $R$ is equivalence relation, imply that $[[x]]_R=[[y]]_R$?

We have two objects, $x$ and $y$. Let there be an equivalence relation $R$ between them, such that $xRy$. How does this imply that their equivalence classes, $[[x]]_R$ and $[[y]]_R$, are equal? A ...
9
votes
1answer
143 views

Counting number of mathematical objects and structures

Regarding the numbers of certain mathematical objects and structures, especially sets, relations and functions, I've compiled a list of the counts from various sources: Partitions of a set with $k$ ...
0
votes
2answers
37 views

Equal equivalence classes proof

Let there be two sets $A$ and $B$ and let their Cartesian product be $A{\times}B$. Let there be an equivalence relation $R:R\,{\subset}\,A{\times}B$. Let's define an equivalence class now: ...
2
votes
2answers
41 views

Is the relation {(2,3),(3,3),(4,2),(5,1)} a function with domain and co-domain {1,2,3,4,5}?

I got a question marked incorrect, however, searching around, I found that the general consensus was that I got the answer correct. I promise that I am not asking you to do my homework as it has ...
0
votes
0answers
25 views

How do the equal equivalence classes under the relation defined below imply the following?

First, we have a commutative semigroup $(S,*)$. Now let $(S_1,*_{↾_1})$ and $(S_2,*_{↾_2})$ be its two subsemigroups, with $*_{↾_1}$ and $*_{↾_2}$ being the restrictions of $*$ to $S_1$ and $S_2$. ...
0
votes
1answer
33 views

Show that $F: P(\mathbb{N} \times \mathbb{N}) \rightarrow P(\mathbb{N} \times \mathbb{N})$ defined as $F(r) = r \bullet r$ is not surjection

I have to show that $$F: P(\mathbb{N} \times \mathbb{N}) \rightarrow P(\mathbb{N} \times \mathbb{N})\\ F(r) = r \bullet r$$ is not surjection where $r \bullet r$ is composition of two (same) ...
-1
votes
1answer
31 views

Connections between Posets and WQO's

Here is the question that I posted on the Mathematics Chat Room that I was unable to find an answer to: Question: Under what conditions/properties is a poset ever a wqo (well-quasi-order)? Can we ...
0
votes
1answer
16 views

Composing equivalence relations

I´ve come across a problem regarding relation composition. The task is to show, whether a composition of two equivalence relations on a set X is again an equivalence on the set X. I´ve tried ...
0
votes
2answers
29 views

Reflexive relations problems

If U = {A, B, C, D, E} determine the number of relations on U that are reflexive my answer: 2^5 symmetric my answer:2^5C2 reflexive and symmetric my answer:2^5C2 * 2^5 reflexive, symmetric and ...
2
votes
3answers
74 views

Use of the symbol $\lneq$

This answer uses kind of a "proper less equal" symbol: $\lneq$ I would have expected that $<$ is sufficient, because it seems to be the same relation. For $\subset$ vs $\subsetneq$ some authors ...
2
votes
4answers
146 views

Symmetric relation definition - why is this false?

Can someone explain to me why the following statement is false, according to my study materials for discrete mathematics? If a relation $R$ on a set $X$ is symmetric, then $x\,R\,y$ and $y\,R\,x$ ...
-1
votes
1answer
35 views

How to prove these relations? [closed]

How do I prove that? $R^{*} = R^{⁺} ∪ R^{0}$ $R^{⁺} = R ∘ R^{*}$ $h_{sym(R)} = R ∪ R^{T}$ $h_{eq(R)} = ( R ∪ R^{T})^{*}$
2
votes
1answer
32 views

Prove that $g : B \rightarrow A_1 \times \dotsc \times A_n$ is unique

I was wondering if someone would not mind proofreading my demonstration for the following problem. Any sentences in brackets [] will be omitted in the formal proof. Problem Let $B$ be a set, let ...
3
votes
1answer
45 views

Prove $f^{-1}(U_1 \times \cdots \times U_n) = \bigcap_{i \in I} (f_i)^{-1}(U_i)$

I was looking through some problems in one of my books which does not have solutions in the back, and I found a problem stating to construct a proof for the following problem. If someone would not ...
1
vote
1answer
20 views

Language for finding a function to relate two tables

I have two tables Fiscal period contains the numbers 1-12 Actual period contains the same sequence However, they are related so that Fiscal Period 1 = Actual Period 4 and AP 1 = FP 10 I'm ...
0
votes
1answer
51 views

Prove there is a unique function $g : B \rightarrow A_1 \times \dotsc \times A_n$

I was wondering if someone would not mind proofreading my demonstration for the following problem. Any sentences in brackets [] will be omitted in the formal proof. Problem Let $B$ be a set, let ...
0
votes
2answers
28 views

Graph Generated by a Surjective Function

There are 2 non empty sets $A$ and $B$, such that $A \cap B = \emptyset $. And there is a function $f: A \rightarrow B$ which defines the undirected graph $G=(V,E)$ such that $V=A \cup B$ and $E= A ...
0
votes
2answers
35 views

Clarification needed, show it is not an equivalence relation: $a \sim b \Leftrightarrow (a>b \wedge b>a)$ for $a, b \in \mathbb{R}$.

A question from HW: $a \sim b \Leftrightarrow (a>b \wedge b>a)$ for $a, b \in \mathbb{R}$. Show it is not an equivalence relation. My problem - For instance, how can I even check for ...
0
votes
2answers
27 views

Relation is surjective iff $I_V=R^T \circ R$

There is a relation $R$ from $U$ to $V$ for which it is given that it is a function. How can I prove that $R$ is surjective iff $I_V=R^T \circ R$ Can anyone provide me a hint to solve this problem.
1
vote
0answers
29 views

Relation by induction

Suppose we have the element $a$ and $b$ in some algebra $A$ and $0<q<1$ subject to the relations: $$a^2b-(q+q^{-1})aba+ba^2=0$$ $$b^2a-(q+q^{-1})bab+ab^2=0$$ I want to deduce from this a ...
0
votes
0answers
27 views

Relations on the set of all functions from Z to Z

I know a similar question has been asked before, but I don't get what a relation on a set of functions means exactly... The problem is determine if the relation $R=\{(f,g)|f(0)=g(0)\text{ or ...
1
vote
1answer
25 views

Let $f: A \to B$ and let $\{D_{α} : α\in Δ\}$ Prove that $f\left( \bigcup_{α\in Δ} D_{α}\right ) = \bigcup_{α\in Δ} f( D_{α})$

So I know that I need to show that each is a subset of the other but other than that, I don't know where to start. Any help is appreciated.
2
votes
1answer
16 views

Finding an Equivalence Relation from a Partition?

I've been looking around and found questions related to deriving partitions from equivalence relations; however I was wondering if there is a method to finding an equivalence relation from a given ...
2
votes
1answer
42 views

Decide whether a relation is reflexive, symmetric, and transitive?

I have a problem to do that is similar to this: $R_1$ is over the set of real numbers (a) $(x, y) \in R_1$ if and only if $xy = 5$ decide whether it is reflexive, anti-reflexive, symmetric, ...
0
votes
0answers
13 views

prove $R \subseteq S \Rightarrow R^+ \subseteq S$

$R$ is an endorelation and given is that $S$ is Transitive. I need to prove $R \subseteq S \Rightarrow R^+ \subseteq S$ Does anybody have hint to tackle this problem.
1
vote
1answer
15 views

to prove $(R\circ S)^*\circ R = R\circ (S\circ R)^*$

For 2 relations $R$ and $S$, need to prove is (1) $(R \circ S)^n \circ R = R\circ (S\circ R)^n$ for all $n \ge 0$ (2) $(R\circ S)^*\circ R = R\circ (S\circ R)^*$ My Work: I was able to prove (1) ...
0
votes
1answer
22 views

I want to prove that $R^+ = R$ if $R$ is transitive.

I want to prove that $R^+ = R$ if given $R$ is transitive. I tried to prove it as follows: $ R^+$ $ \bigcup\limits_{n=1}^\infty R^n$ It reduces as : $ R^n = R$ for all $n\ge 1$ I use Induction ...
1
vote
1answer
57 views

Define a relation and find its equivalence classes.

Define a relation $\sim$ on $\Bbb{N}$ as follows. For any $a,b∈\Bbb N$, $a\sim b$ if and only if $ab$ is a perfect square. Show that $\sim$ is an equivalence relation. What are the equivalence ...
0
votes
1answer
21 views

Partial ordering of natural numbers

How can I prove that the partial ordering of natural numbers has no least element? I genuinely have no idea how to do this. Q3c. This is not a homework/assignment task. It's a past exam paper which I ...
-1
votes
2answers
15 views

Defining Equivalence Relations on a Set

Given the sets, $A=\{0,1\}$ and $B=\{12,1,2\pi\}$, define (by listing the ordered pairs): $a$) A relation from $A$ to $B$ that is not a function. $b$) A relation from $A$ to $B$ that is a function. ...
1
vote
0answers
31 views

equivalence relations example

determine if the relation on $\mathbb{Z} \times \mathbb{Z}$ is an equivalence relation. $$R=\{((a,b),(c,d)) \in A \times A: a+3b=c+3d\}$$ What I have thus far I need to show that R is reflexive, ...
0
votes
2answers
29 views

Reflexivity of Relations

Explain why the relation $$T=\{(a,b)\in\mathbb{R}\times\mathbb{R}:a≤b\}$$ is reflexive, but the relation $$ Q=\{(a,b)\in \mathbb{R}\times\mathbb{R}:a<b\}$$ is not reflexive. Is $T$ reflexive ...
0
votes
0answers
29 views

Consider the relation … What are the domain and range of R? Define the inverse relation. What are its domain and range?

Consider the relation R={(x,y)∈ℝ×ℝ:y=2x}. What are the domain and range of R? Define the inverse relation. What are its domain and range? So I was thinking since there is no set given that it would ...
0
votes
0answers
18 views

Need to prove $R^{n+1} \subseteq R^n$

$R$ is a relation on set $U$, Given that $R$ is transitive. Need to prove $R^{n+1} \subseteq R^n$ for all $n \geq 1$ I tried it by Induction base case for $n=1$ $ R^{2}$ $= R \circ R $ ...
2
votes
3answers
45 views

Finding the equivalence class of a relation |a| = |b|

For the following relation $R$ on the set $X$ determine whether it is $(i)$ reflexive, $(ii)$ symmetric and $(iii)$ transitive. Give proofs or counter examples. In the case where $R$ is an equivalence ...