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
0answers
12 views

Book on theory of relations

Could someone recommend an introductory book on Theory of Relations for undergraduate level mathematician? Something gentle and intuitive.
3
votes
2answers
28 views

Transitive relations on sets

So I'm having a bit of an issue understanding transitive relation property. I feel like I understand the rule well enough. On: the set $\{1, 2, 3, 4\}$ on this relation $\{(2, 2), (2, 3), (2, 4), ...
-5
votes
0answers
28 views

Composition of Relations solving p 0 σ and σ 0 p [closed]

Explain me difference between p 0 σ and σ 0 p and how to get the answer.
0
votes
0answers
19 views

Minimal posets and chains [closed]

Given a poset (X, P ) we can say that an element x ∈ X is minimal if it doesn’t cover any other element y ∈ X. Think about the relation between finding a maximal chain and the minimal elements. Isn't ...
0
votes
1answer
26 views

Relation $R = \{(1,2), (2,2), (2,3), (3,2)\}$ is defined on $A = \{1,2,3\}$. Draw the digraph for the relation $R^3$.

So I don't want an explicit answer, but I do need help getting it from $R^1 \rightarrow R^2 \rightarrow R^3$. Relation $R = \{(1,2), (2,2), (2,3), (3,2)\}$ is defined on $A = \{1,2,3\}$. Draw the ...
0
votes
0answers
28 views

Graph, Relation $xRy \Leftrightarrow$ There is a path between $x$ and $y$ - symmetry

I have the relation $xRy$ is equivalent to "There is a path between $x$ and $y$" If I now want to check symmetry, $xRy$ is equivalent to $yRx$, I read that this is true. I thought this is only the ...
0
votes
1answer
17 views

Binary Relations Counting

Are these answers correct? I'm having a little trouble with $d$. and $e$. Set $S$ has $n$ elements. ($a$) How many elements are there in $S \cdot S$? $n^2$ ($b$) How many binary relations are there ...
-3
votes
2answers
36 views

What is the matrix and directed graph corresponding to the relation $\{(1, 1), (2, 2), (3, 3), (4, 4), (4, 3), (4, 1), (3, 2), (3, 1)\}$?

Let $R$ be a relation on set $A = \{1, 2, 3, 4\}$ defined by $$R = \{(1, 1), (2, 2), (3, 3), (4, 4), (4, 3), (4, 1), (3, 2), (3, 1)\}.$$ Find the matrix and directed graph of relation $R$.
0
votes
0answers
11 views

Examples of Relation Algebras

Would anyone please direct me to a host of examples of relation algebras. Is there an intuition for what these algebras are to model? That is, groups, for example, model a notion of symmetry; ...
-1
votes
1answer
28 views

partial order relation over a subset relation [closed]

Given a non empty set A i need to contradict those 2 sentences: 1.For every relation R over A (R is transitive relation) exists partial ordered relation K over A so that R ⊆ K 2.For every relation R ...
1
vote
1answer
30 views

Discrete Math - Relations and Matrix Representations

Are these answers correct? Do we assume $p$ is created from $S$ twice? Binary relation $p$ on the set $S = \{a,b,c,d,e\}$ is defined as: $p = \{(a,c),(a,e),(b,a),(e,d)\}$.  What is the matrix ...
0
votes
0answers
12 views

Representation of an $n$-ary relation as a function - terminology

Let $f$ be an $n$-ary function (where $n$ is an index set). Is there any customary term or notattion for the set $\{ X \mid L\cup\{(i;X)\} \in f \}$ where $i\in n$ and $L$ is an ...
0
votes
1answer
19 views

Is $ R = \{ (A,B) \in \Omega² \quad| \quad A \land B \} \quad$ with $\Omega = \{ A\quad| $ A is a proposition $ \}$ reflexive?

Is $ R = \{ (A,B) \in \Omega² \quad| \quad A \land B \} \quad$ with $\Omega = \{ A\quad| $ A is a proposition $ \}$ reflexive? I assume that you have to consider untrue propositions, too. $A \land ...
1
vote
2answers
20 views

Prove that transitive closure has at the most $n^2$ elements

Given a relation $R \subseteq A \times A$ with $n$ tuples, I am trying to prove that its transitive closure $R^+$ has at the most $n^2$ elements. My initial idea was to use the following definition ...
3
votes
1answer
25 views

Which relations are partial orders

I have come across the following question on a practice test: Which of the following relations defined on $X = \{1, 2, 3\}$ are partial orders? $(1) \; \{(1, 1),(2, 2),(3, 3)\}$ $(2) \; ...
3
votes
3answers
50 views

Why isn't the empty set an element of $A \times B$, while it is a relation from $A$ to $B$?

Let $A$ be $\{1,2\}$, let $B$ be $\{x,y\}$. According to the information I get from most textbooks, $$A \times B = \{(a,b): a\in A\text{ and } b\in B\}$$ $$A \times B = ...
0
votes
2answers
22 views

Help with defining binary relation image in ZFC

I need to define in ZFC the following things: image and domain of a binary relation ($\{ x \mid (x,y)\in f \}$ would be a definition of domain, but it is a class for which is for me is not quite ...
3
votes
0answers
49 views

Why is this not a proof of Schroeder-Bernstein?

We can show that if $f: A \rightarrow B$ is injective then $|A| \leq |B|$ and if $g: B \rightarrow A$ is injective then $|B| \leq |A|$ so $|A| = |B|$. By the definition of having equal cardinality, ...
2
votes
1answer
51 views

Trichotomy implies totality of partial order

Theorem: A partially ordered set is totally ordered if it obeys the law of trichotomy. Things I know: A relation on some set $A$ is said to be a partially ordered set if the relation is reflexive, ...
0
votes
1answer
25 views

Powers of relations problem

In a discrete mathematics course, I stumbled upon the following problem. I have an idea how to solve the problem based on the fact that the power of a relation repeats after 3 consecutive powers; that ...
2
votes
0answers
24 views

What is the irreflexive closure of an irreflexive relation?

I am working on a problem that states the following: When is it possible to define the irreflexive closure of a relation R, that is, a relation that contains R, is irreflexive, and is contained in ...
0
votes
1answer
39 views

What is a Monad in the two category $Rel$?

The 2-category $Rel$ is a category with sets as $0$-cells, relations as $1$-cells (with relation composition as composition), and inclusions as $2$-cells (with vertical composition being the fact that ...
0
votes
2answers
22 views

$R_1$ and $R_2$ are partial orders. What about $R_1 \cap R_2$?

Let $R_1$ and $R_2$ be two partial order relations defined on a set S. Show that $R_1 \cap R_2$ is also a partial order on S. I am struggling to represent $R_1$ and $R_2$ in a way I can operate with ...
4
votes
0answers
51 views

How to Prove It, Exercise 6.5.9

Suppose $R$ is a relation on $A$ and $S$ is the transitive closure of $R$. If $(a, b) \in S$, then there is some positive integer $n$ such that $(a, b) \in R^n$, and therefore by the well-ordering ...
0
votes
2answers
29 views

Is a composite function $g \circ f$ an injection? If so, is $f$ an injection, too?

Let $f: S \rightarrow T$ and $g: T \rightarrow U$. The function $h: S \rightarrow U$ given by $h(s)=g(f(s))$ is the composite function of $g$ and $f$, denoted by $h=g \circ f$. Prove that, if $g \circ ...
2
votes
1answer
31 views

Understanding this statement

Let R$_1$ and R$_2$ be two equivalence relations on the same set A. Not sure how to interpret this statement. Does it mean... A = {1, 2} $\quad$#for example AR$_1$A = {(1, 1), (1, 2), (2, 1), (2, ...
0
votes
0answers
20 views

Should I link these parts of the hasse diagram?

Where X divides by Y on the set A = {1,2,3,6,10,15,30} The answer I've been given in this example was: ...
1
vote
1answer
31 views

Transitive, Reflexive, and Symmetric, could someone explain these answers?

I've been looking at a past paper with solutions, and I can't quite make sense of the answers given here (which is odd considering I get these questions right every time on the online practice tests), ...
3
votes
0answers
33 views

A reflexive relation?

Suppose I have a set $\mathrm{A}=\{1,2,3,4,5\}$ and a reflexive relation $\mathrm R$ defined on $\mathrm A$, i.e., $$R\colon A\mapsto A\quad\textrm{and}\quad \mathrm R\textrm{ is reflexive.}$$ Is ...
3
votes
0answers
33 views

Proving Equivalence Relation $xPy$ iff $ y = x + n\pi$ on The Reals

I am trying to prove that the relation P on $\mathbb{R}$ by the rule $\forall x, y \in \mathbb{R}, xPy \text{ if and only if } \exists n \in \mathbb{Z} \text{ such that }y = x+ n\pi$ From what I can ...
0
votes
1answer
13 views

How many distanct equivalence classes are picked out by this relation?

Let $x\text{R}y \iff x-y=2k \quad k \in \mathbb{Z}$ How many distinct equivalence classes are there for this relation? I want to say thre are as many equivalence classes as there are integers, but ...
0
votes
1answer
32 views

Counting Positive Integer Divisors

Let $A$ be the set of all positive integer divisors of $3^6 5^8 11^{10} 17^{15}$. Define the relation $R$ on $A$ as follows. For $x, y \in A, xRy$ when $x | y$. Determine the number of ordered pairs ...
3
votes
1answer
66 views

Relationship between $S$ and $S^{-1}$

This is one of the problem I have been solving in Velleman's How to Prove book: Suppose $R$ is a relation on $A$, and let $S$ be the transitive closure of $R$. Prove that if $R$ is symmetric, ...
1
vote
5answers
51 views

How is “smaller than” defined on $\mathbb{R}$?

According to http://en.wikipedia.org/wiki/Binary_relation Binary relations are used in many branches of mathematics to model concepts like "is greater than", "is equal to", and "divides" in ...
0
votes
1answer
29 views

What is the definition of a binary relation?

According to http://en.wikipedia.org/wiki/Binary_relation it is first defined as "a collection of ordered pairs of elements of A" and then as "an ordered triple (X, Y, G) where X and Y are arbitrary ...
1
vote
1answer
17 views

Is this a transitive relation

I found this in a web site If $A = \{ 1, 2, 3\}$, then the relation $R = \{(2, 3)\}$ is not transitive. Why it is not transitive? The definition is if whenever an element $a$ is related to an ...
0
votes
3answers
46 views

Is a relation from a set $A$ to a set $B$ always a proper subset of $A\times B$?

Is a relation from a set $A$ to a set $B$ always a proper subset of $A\times B$? Or, is it possible that the relation covers the entire set $A\times B$?
2
votes
2answers
20 views

Proving two Recurrence Relations

I encountered this problem in the International baccalaureate Higher Level math book, and my teacher could not help. If anyone could please take the time to look at it, that would be great. I need ...
0
votes
1answer
25 views

How would I convert this state-transition diagram into a regular expression ?

The state-transition diagram of a finite-state recogniser is as follows :
2
votes
1answer
71 views

Can a relation be both anti-reflexive and anti-symmetric?

Is it possible for a relation to be both anti-reflexive and anti-symmetric?
0
votes
1answer
21 views

How to work out the boolean matrix of a relation $S$?

I just wanted a little bit of guidance on how to work out this question in finding the boolean matrix of a relation : Consider the following Hasse diagram of a partial ordering relation $S$ on the ...
3
votes
2answers
32 views

Restricting a relation to an injective function

Given a relation between two finite sets, how can I determine whether it restricts to an injective function? The criterion or algorithm doesn't need to be constructive: It is enough to know that such ...
0
votes
1answer
15 views

Anti-symmetric or asymmetric for a relation between pairs in the set of Z x Z?

Is this anti-symmetric or asymmetric? I at first thought asymmetric because anti-symmetric would mean a = c and b = d which would not be true. But because the domain is the Cartesian product of ...
2
votes
3answers
116 views

Sets: How to show that relation R is not transitive?

I have a question which states: $R = \{ (t,t), (t,v), (t,z), (u,t), (u,u), (u,v), (u,x), (u,z), (v,v), (w,w), (w,z), (x,t), (x,v), (x,w), (x,x), (x,y), (x,z), (y,w), (y,y), (y,z), (z,z) \}$ ...
0
votes
1answer
21 views

A question on eqivalence relation

Please explain what the examiner means by asking: Also find [3,6] in Q 1 (a)(i)??
0
votes
2answers
28 views

Concrete explanation for how an equivalence relation is related to equivalence class and the notation employed

I'm fairly comfortable with the definition of what the three equivalence relations are. What I'm not comfortable and finding it above my head is how equivalence relation is closely related to ...
1
vote
2answers
48 views

Difference between domain and range for relations and functions?

What is the difference between the definition of domain and range for a relation, and that for a function?
0
votes
2answers
42 views

Well-defined and Equivalence relations

I am wondering why the following is well-defined... The definition of well-defined is given as; $g:(X/\sim) \to Z$ is well-defined if a mapping $f:X \to Z$ can be found where $f$ has the property $x ...
1
vote
1answer
20 views

Non-ordered n-tuple?

In many mathematics texts I've seen "ordered n-tuple" appear, and in such texts, there isn't any mention of just "n-tuple". So I'm wondering: are there really cases where one writes "n-tuple" and ...
0
votes
1answer
54 views

Proof of an equivalence relation

Let S be the relation on R defined by $xSy \Leftrightarrow x=|y|$, $\forall x,y\in\Re$ Is the relation reflexive, symmetric and/or transitive? By my proof that 1) $x=|y| \Rightarrow |y|=x$ ...