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
22 views

Can someone present an example of linear ordering less trivial than $A = [1,2,3,4,5,6…]$

A linear ordering (loset) is a poset that also satisfies the trichotomy law. For any $x,y \in A$, we have $x \leq y$ or $y \leq x$ A common example is presented as $A = [1,2,3,4,5,6...]$ Can ...
1
vote
1answer
29 views

How can an asymmetric relation be antisymmetric?

Let R be asymmetric. So we have: Assumption: (x,y)∈R⟹(y,x)∉R We need to show R is antisymmetric, i.e. (x,y)∈R∧(y,x)∈R⟹x=y Since 2 is a conditional, we can assume Assumption:(x,y)∈R∧(y,x)∈R ...
2
votes
1answer
22 views

Can someone present a visualization of the partitioning of a $L^p$ space into equivalent classes?

I am a bit confused by what it means for a $L^p$ space to be partitioned into equivalent classes instead of functions. I understand that give two or more functions $f$, $g$, $h,\ldots$ of which are ...
0
votes
3answers
41 views

Why ordered sequences can be reduced to sets?

I am trying to understand why ordered sequences can be reduced to basic sets. I understand most of the following proof: Sequences can be defined as functions Functions are a special case of ...
0
votes
1answer
16 views

antisymmetric operators

Is the symbol ">" antisymmetric? For example, if I say $(x>y) \wedge(y>x) \rightarrow \exists(x,y)|x=y$ is vacuously true since the premise cannot be true. This means that $x>y$ is ...
0
votes
2answers
21 views

Shouldn't this be transitive relation also?

$ R = \{ (a,b) ∈ R ; 1 + ab > 0 \} $ It is clearly reflexive and symmetrical but I feel that it is transitive also because the relation R can be stated as $ R = \{(0,0), (0,1), (1,2)...\}$ and as ...
1
vote
1answer
33 views

why this is not transitive yet a reflexive relation?

The relation given is $ R = \{(a,b); 1ab>0; a,b ∈ R \} $ I clearly understand that this is symmetric since $a*b = b*a$ but I'm not able to understand that why is this reflexive also and not at all ...
1
vote
1answer
35 views

Is this relation symmetric and transitive?

Set A is given as $A = \{1,2,3,4,5,6,7,8,9,10,11,13,14\} $ And is defined as $R = \{(x,y) : 3x = y\}$ The relation that I'm getting is: $ R = \{(3,3), (6,6), (9,9), (12,12)\} $ Over here, it is ...
1
vote
2answers
44 views

counterexample in relations of sets

Suppose $R$ is a relation from $A$ to $B$ and $S$ and $T$ are relations from $B$ to $C$. Can anyone produce a counterexample to $(S \setminus T)◦R⊆(S◦R) \setminus (T◦R)$?
1
vote
0answers
24 views

How to prove partial ordering formally?

The question is: The set $S$ is defined as $\varnothing \in S$, If $x \in S$, then also $\{x\} \cup x \in S$. Prove or disprove it is partial ordering. So the set $S$ looks ...
0
votes
2answers
62 views

Confusion about the definition of reflexive relation

The definition of a reflexive relation over $A$ is: $R$ is reflexive over $A$ iff $\forall a \in A :(a,a) \in R$ Why the '$\forall a \in A$'? Def. of transitive and symmetric relations don't have ...
1
vote
1answer
21 views

Graphically representing relations of ordered pairs

I am having problems trying to picture what this relation of ordered pairs 'looks' like: Let R be the relation on the set of ordered pairs of positive integers such that ((a, b),(c, d)) ∈ R if and ...
0
votes
1answer
31 views

What is usually understood as DOMAIN and CODOMAIN of a Relation

Suppose I have a relation declaration as $R \subseteq A \times B$, such that $A=\{1,2,3,4\}$ and $B=\{10,20,30,40\}$. And suppose that the definition of this relation is $R=\{(1,20),(3,40)\}$ We ...
1
vote
1answer
18 views

Two “adjunct” (quasi-inverse) functions

Let $A$, $B$ be fixed sets. What "means" the formula $Y \cap \alpha X \neq \emptyset \Leftrightarrow X \cap \beta Y \neq \emptyset$ for functions $\alpha:\mathscr{P}A\rightarrow\mathscr{P}B$ and ...
0
votes
2answers
23 views

Define a relation $D_n$ on $S$ by $xD_ny$ if and only if $x\mid y$. Determine if it's a poset.

Here is the question I am currently working on (screenshot): I'd appreciate some suggestions/guidance for part (a), proving that $D_n$ is a partial order. Reflexive: Let $x \in \mathbb{Z}$ ...
2
votes
2answers
47 views

What is the symbol to denote that two triangles are similar?

Does there exist a unique symbol to denote that two triangles are similar to each other without resorting to using the phrase "is similar"?
1
vote
1answer
38 views

Discrete mathematics, equivalence relations, functions.

I'd like some insight on how to 'solve' this problem (more towards understanding what the problem is asking) Suppose that $A$ is a nonempty set and $\mathcal{R}$ is an equivalence relation on ...
1
vote
1answer
36 views

Define a relation — with functions and derivatives

Here is the problem I am working on: I am in a beginning level abstract math/proofs class, and haven't had much experience with calculus in any proof (or in any relation). Here is my understanding ...
0
votes
3answers
34 views

Compute equivalence classes of equivalence relation

I have already proven that relation R={($x,$y) $\in$ $\mathbb Z$ x $\mathbb Z$ | $x+$y is even} is a equivalence relation by showing reflexive, symmetric, and transitive properties of the relation. ...
0
votes
2answers
66 views

Define a relation $M$ on $\mathbb{Z} \times \mathbb{Z}$…

Update #2 (7.21.15): Here is a screenshot of the corrected question, in case anyone was interested. No need to look at the first update or original post to anyone viewing this for the first ...
0
votes
1answer
28 views

What does the notation $M^{[2]}$ mean with regards to matrices?

I am busy studying transitive closures of relations. The Matrix of the relation, $M_R$ is $$M_R = \begin{pmatrix} 1&0&1\\ 0&1&0 \\ 1&1&0 \end{pmatrix}$$ As you might know ...
1
vote
1answer
25 views

Ternary equivalence relations that are not equivalent to some binary equivalance

1.Is there such a thing as ternary equivalence that is not equivalent or cant not be expressed as binary equivalence? 2.If there is such a thing as expressed in 1, are there any practical uses for ...
1
vote
1answer
29 views

Prove or disprove: $\forall\rho,\sigma,\phi\subseteq A^2: \ \rho \subseteq \sigma \rightarrow \rho \circ \phi \subseteq \sigma \circ \phi$

Where $\rho,\sigma,\phi$ are relations on a finite set $A$ and $\circ$ denotes the relation composition. I was neither able to prove it, nor to come up with a counterexample.
1
vote
0answers
14 views

Is there a term for irreflexive relations whose reflexive closures are equivalence relations?

Consider a relation $\sim$ which is irreflexive, that is: $$ \forall A \:A\nsim A $$ Further suppose the reflexive closure of $\sim$ is an equivalence relation. The reflexive closure of $\sim$, ...
-1
votes
2answers
83 views

Is an injective map from a set to itself a surjective map? Proof? [closed]

Same as title. Short, straight and easy answer required. Thanks in advance!
0
votes
1answer
27 views

Sum of a product of four Kronecker Deltas

The Kronecker delta has the following property: $$\sum_{k} \delta_{ik}\delta_{kj} = \delta_{ij}. $$ Does anyone know whether the following formula is correct? $$\sum_{i=1}^N ...
0
votes
0answers
46 views

How do I solve Exercise 6.2.4 (a) of 'How to Prove It' by Velleman?

I spent 6 hours on it, and I couldn't wrap my head around it. The problem is described below. I am stuck on Case 2. 6.2.4. (a) Suppose R is a relation on A, and ∀x∈A∀y∈A(xRy ∨ yRx). (Note that this ...
1
vote
1answer
41 views

$f : A \to B$ s.t. for all $x, y \in A, x R y \iff f(x) S f(y)$

Theorem. A relation $R$ on a set $A$ is reflexive and transitive if and only if there is a set $B$ with a partial order $S$ and a function $f : A \to B$ such that for all $x, y \in A, x R y \iff ...
2
votes
0answers
21 views

composition of relations and multiset relations

As is well known, composition of relations is defined as $$R\circ S = \{(a,b):\exists x: (a,x)\in S \land (x,b)\in R\} \tag 1$$ This is formally the very same definition as for function composition. ...
1
vote
0answers
14 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
34 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
1answer
28 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
19 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
13 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
35 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
20 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
51 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
23 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
52 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
53 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
28 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
41 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
24 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
62 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 ...