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
11 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
25 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), ...
0
votes
4answers
126 views

If $R=\{(x,y): x\text{ is wife of } y\}$, then is $R$ transitive?

If $R=\{(x,y): x\text{ is wife of } y\}$, determine whether the relation $R$ is transitive or not. My Try: For Transitivity, If $(a,b) \in R$ and $(b,c)\in R\;,$ Then $(a,c)\in R.$. Here If $x$ ...
-5
votes
0answers
28 views

Composition of Relations solving p 0 σ and σ 0 p [on hold]

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

Minimal posets and chains [on hold]

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 ...
1
vote
1answer
384 views

Classify relations “is greater than or equal to”

Classify the following relations as reflexive, irreflexive, symmetric, antisymmetric or transitive. Explain each property in the context of the question. “is greater than or equal to” on the set of ...
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 ...
-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
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 ...
-1
votes
1answer
26 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 ...
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
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
49 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 = ...
1
vote
2answers
39 views

Partition of Real Numbers

Let R be the set of all real numbers. Is $\{\mathbb R^+,\mathbb R^−,\{0\}\}$ a partition of $\mathbb R$? Explain your answer. My answer is no because of $\{0\}$. I am confused with $\{0\}$. please ...
0
votes
2answers
67 views

Prove or Counter example.For all nonempty sets $A$ and $B$ and for all functions $F: A \to B$, $F(A-B) = F(A) - F(B)$

Prove or Counter example.For all nonempty sets $A$ and $B$ and for all functions $F: A \to B$, $F(A-B) = F(A) - F(B)$ I am pretty lost on this question. I don't feel like its right since it would be ...
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, ...
1
vote
1answer
40 views

Characterization of monovalued functions

Let $f$ be a binary relation. Let $(\bigcap G)\circ f = \bigcap_{g\in G}(g\circ f)$ for every set $G$ of binary relations. Can we prove that $f$ is monovalued (a function)?
1
vote
1answer
345 views

Prove the relation to be a Linear Order.

Let (a, b),(x, y) ∈ R × R and define ≺ as follows: (a, b) ≺ (c, d) iff a < c or a = c and b < d: Define (a, b) ≼ (c, d) if and only if (a, b) = (c, d) or (a, b) ≺ (c, d). Show that ≼ is a ...
4
votes
0answers
77 views

Where can I learn more about the concept that is dual to “relation”?

Let $X$ and $Y$ denote sets. Then a relation $X \rightarrow Y$ is, by definition, a subset of $X \times Y$. Dually, we can define that a "corelation" $X \rightarrow Y$ is a partitioning of $X \uplus ...
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
23 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
52 views

Inverse image of an element in co-domain but not in range?

Sorry, quite new to this. I have a question that contains the image below of $g:X\rightarrow Y$ and it is asking for the inverse image of $u$. Am I correct in thinking that the answer is $\emptyset$? ...
0
votes
1answer
38 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 ...
5
votes
4answers
5k views

Is there a relation which is neither symmetric nor antisymmetric?

I've proved that there are relations which are both symmetric and antisymmetric ($\forall a \forall b (aRb \rightarrow (a=b))$) and now I'm trying to prove that there are relations which are neither ...
-8
votes
1answer
47 views

NUMBERE OF IDETITY RELATIONS ON A SET [closed]

number of non identity reflexive relations on a set
10
votes
4answers
1k views

Is any relation which contains only one ordered pair transitive?

I need clarification. Let $A=\{1,2,3\}$ be a set and $R=\{(1,2)\}$ be a relation on $A$. Is it a Transitive relation? I am confused because some text books say $R$ is transitive if it contains only ...
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, ...
1
vote
1answer
12 views

Equivalence Relation Properties

I have to define whether the following relation is symmetric, reflexive, and transitive. Define a relation R on Z as follows: (x, y) ∈ R if and only if x = |y|: This is my answer so far: Is ...
0
votes
1answer
65 views

The relation $a + d = b + c$ between pairs $(a, b)$, $(c, d)$ is an equivalence relation

Let R be the relation on $Z × Z$, that is elements of this relation are pairs of pairs of integers, such that $((a, b),(c, d))\in R$ if and only if $a + d = b + c$. Show that R is an equivalence ...
0
votes
4answers
458 views

If R is $(a,b)R(c,d) \iff a+d =b+c$ show that R is an equivalence relation.

The relation R is defined n all positive integers such that, $(a,b)R(c,d) \iff a+d =b+c$ . Show that R is an equivalence relation. In order to be an equivalence relation, R has to be reflexive, ...
4
votes
2answers
373 views

The fibres of a map form a partition of the domain.

This is a question from the free Harvard online abstract algebra lectures. I'm posting my solutions here to get some feedback on them. For a fuller explanation, see this post. This problem is from ...
4
votes
3answers
186 views

What's the name for the equivalence induced by a function on its domain?

Any function $f$ with domain $X$ induces an equivalence relation on $X$, with classes $$\{f^{-1}(\{y\})\,:\, y \in \operatorname{im}f\;\} .$$ Is there a name for this equivalence? Thanks!
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: ...
3
votes
2answers
145 views

Categories of $n$-ary relations?

Arrows in the category $\bf Rel$ are binary (2-valued) relations between set objects. Do ternary, 4-term, $n$-term and variadic (2-valued) relations form categories? (Or perhaps one category?). It ...
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 ...
1
vote
0answers
60 views

Finding Equivalence Classes for Infinite Sets

Let $R$ be the relation on the set of rational numbers $\Bbb Q$ defined as follows: for all $q, r \in \Bbb Q$, $qRr$ iff $q − r \in \Bbb Z$. Then $R$ is an equivalence relation on $\Bbb Q$. What is ...
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 ...