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
2answers
39 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)$?
0
votes
1answer
29 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
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
60 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
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}$ ...
1
vote
1answer
17 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 ...
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"?
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 ...
1
vote
1answer
37 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 ...
2
votes
1answer
93 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?
-4
votes
1answer
31 views

relation with formula [closed]

Let E be a non-empty set and let α ⊆ P(E) be such that ∀X, Y ∈ α, ∃Z ∈ α, Z ⊂ X ∩ Y . Define the relation ∼ on E by A ∼ B if and only if ∃X ∈ α, X ∩ A = X ∩ B. Prove that ∼ is an equivalence relation ...
0
votes
3answers
30 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. ...
1
vote
1answer
35 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 ...
1
vote
1answer
356 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 ...
0
votes
1answer
27 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
24 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 ...
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 ...
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
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!
1
vote
0answers
13 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$, ...
0
votes
2answers
250 views

to find the smallest and largest number of equivalence relation in a set

Let $s$ be a set of $n$ elements. The number of ordered pairs in the largest and smallest equivalence relation on set $s$ are $n^2$ and $n$. I am able to understand the largest set of equivalence ...
1
vote
1answer
40 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 ...
0
votes
1answer
25 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
44 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 ...
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. ...
3
votes
5answers
11k views

Antisymmetric Relations

Given a set $\{1,2,3,4\}$, how is the following relation $R$ antisymmetric? $$R = \{(1, 2), (2, 3), (3, 4)\}$$ Note: Antisymmetric is the idea that if $(a,b)$ is in $R$ and $(b,a)$ is in $R$, then ...
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
33 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
139 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$ ...
1
vote
1answer
389 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
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 ...
-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
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 ...
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
34 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 = ...
1
vote
2answers
40 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
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
51 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)?
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
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
27 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 ...