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

1
vote
1answer
38 views

Discrete Mathematics - POSETs

My task is to find out what is the lowest # of elements a partial ordered set can have with the following characteristics. If such a set exists I should show it and if it doesn't I must prove it. 1) ...
0
votes
1answer
60 views

Prove or disprove that if a relation $R^2$ is transitive then $R$ is also transitive

Prove or disprove that if $R^2$ is transitive then $R$ is also transitive. I tried to prove $(R\circ R)^2\subseteq (R\circ R)\implies R^2\subseteq R$ this way $(R\circ R)\circ (R\circ ...
1
vote
1answer
23 views

prove or disprove reflexive of $R$

How to prove or disprove that if $R^2$ is reflexive then also $R$ is reflexive ? I tried to prove $R^2 \supseteq (x,x)\forall x \in R\implies R_{rex}$ but without success, maybe I have to find ...
1
vote
1answer
31 views

How is this relation transitive?

$$R = \{(0,1), (0,2)\}$$ I drew out a directed graph; however, I still do not see how this relation is transitive. If $0$ was reflexive, then it is transitive; however, that is clearly not the case ...
0
votes
1answer
28 views

Cartesian product of a set containing all real numbers?

Let S be the set of all sequences of real numbers. Let R be the relation $R = \{(a, b) \in S \times S | a_3 = b_3\}$ I'm trying to find out whether R satisfies the properties reflexive, ...
0
votes
1answer
19 views

Trouble with understanding transitive, symmetric and antisymmetric properties

If $A = \{1,2,3\}$, $R$ an equivalence relation on $A$ if $R = \{(1,1), (2,2), (3,3)\}$? I'm having trouble understanding when a relation is symmetric, antisymmetric, or transitive. Does the ...
0
votes
0answers
27 views

properties of relation product

I do know all definitions of relation properties such as reflexivity, transitivity, asymmetry etc. I have to answer questions if relation $R$ has property $A$, does $R^2$ has property $A$ too? ...
0
votes
1answer
28 views

$a^2 \equiv b^2$ mod 4 equivalence classes.

so we have the relation $a^2 \equiv b^2$ mod 4. And to find equivalence classes we say b or a = 0 so $a^2=4k$ so $a=+-2\sqrt{k} $ so all even numbers. But when we get to a=1 then $a^2=4k+1$ after ...
0
votes
1answer
27 views

Inverse relation of $x<y$ defined on $\mathbb N$

The relation is this: $R=\{(a,b):a<b\}$ on $\mathbb{N}$. How do I find an inverse of this relation? I can see that it is $R^{-1}=\{(a,b):b<a\}$ but I do not know how to prove it. Can someone ...
0
votes
0answers
31 views

Prove that this is a partial order

I am reading Charles Pinter's "Set Theory" and I found an exercise which I can't resolve. Maybe someone can help me. It says: We will consider pairs $(B,G)$ where $B \subseteq A$, and $G$ is an ...
0
votes
0answers
24 views

Proof on exponential Relation R

Prove that $(R^a)^b = R^{ab}$ for any integers $a,b >= 1$. A handy fact: The connectivity relation $R^*$ consists of the pairs $(x, y)$ such that there is a path of length at least $1$ from $x$ to ...
0
votes
0answers
28 views

What common relations on Z are the transitive closures of the following relations?

(a) aSb if and only if a+1=b (b) aRb if and only if |a-b|=2 (c) What common relation on Zis the transitive closure of the relation T, where aTb if and only if |a-b| = 4 or 6? Explain. I don't know if ...
0
votes
1answer
31 views

Reflexive, Symmetric, and Transitive. How to read?

I'm a little confused on these problems as far as the wording goes. I know how to tell if one is reflexive, symmetric, or transitive. The way the problem is set up is: ...
1
vote
2answers
52 views

Discrete math - confusion in onto functions

The question that I'm trying to solve is: At the CH Company, Joan, has a secretary Teresa, and three other administrative assistants. If seven accounts must be processed, in how many ways can ...
1
vote
0answers
24 views

Problem with understanding natural number difference

Proofwiki says the following about difference in natural numbers: In the context of the natural numbers, the difference is defined as: $n−m=p⟺m+p=n$ from which it can be seen that the ...
0
votes
1answer
66 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
42 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
67 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
36 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
28 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
61 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
45 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
30 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
11 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
31 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
21 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
27 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
45 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
149 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
43 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
43 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
26 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
36 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
36 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
18 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
34 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
76 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
160 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$ ...
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
46 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
22 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
32 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
28 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
32 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 ...