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

4
votes
2answers
217 views

Logical relations between relations

I'm interested in properties of relations. Things like completeness (connected, total), transitivity, euclideanness, symmetry and so on. I am interested in the logical connections between these ...
1
vote
2answers
339 views

Execution process with properties of relations

So, I had a quiz last night in my discrete structures class and this question came up: "There are 3 processors in a computer. The instructions to a computer are labeled 1,2,3,4,5,6,7,8,9,10 each ...
2
votes
4answers
2k views

Equivalence Relations

Suppose $A$ is the set composed of all ordered pairs of positive integers. Let $R$ be the relation defined on $A$ where $(a,b) R (c,d)$ means that $a + d = b + c$. (a) Prove that $R$ is an ...
5
votes
2answers
458 views

Cardinality of relations set

I was thinking about cardinality of all symmetric relations, for example in $\mathbb{Z}$. I know, that if I have finite set (which contains $n$ elements), there are $2^{\frac{n(n+1)}{2}}$ symmetric ...
3
votes
1answer
211 views

Problem with a strange relation; what is cardinality

I've tried solve this for hours, but I still stuck in the beginning. Here's my problem: Let $R \subseteq P(\mathbb{N} \times \mathbb{N})^2$ be the following equivalence relation: $\langle r,s\rangle ...
4
votes
2answers
252 views

Defining compatibility between a function $F\colon A\times A\to A$ and an equivalence relation $R$ on $A$

I'm working my way through Enderton's Elements of Set Theory, and one of the theorems from the book has a final note that is giving me some trouble. The theorem is found on page 60, and is as follows: ...
3
votes
3answers
485 views

“Converting” equivalence relations to partitions

There is a direct relationship between equivalence relations and partitions. Is there a way to simply use an equivalence relation's definition to get the matching partition? And what about the other ...
3
votes
3answers
1k views

Proving a relation is antisymmetric

For part b, I'm getting a little stuck. So I'm trying to show that if $(x,y,r)R(a,b,s)$ and $(a,b,s)R(x,y,r)$, then $(x,y,r)=(a,b,s)$ And so $(x,y,r)R(a,b,s)$ implies $\sqrt{(x-a)^2+(y-b)^2} \leq ...
4
votes
5answers
5k views

Number of relations that are both symmetric and reflexive

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive? The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is ...
2
votes
1answer
1k views

Transitive and reflexive graph

The answer for this turns out to be only irreflexive. However, how is this not transitive? The definition I have for transitive states "whenever there is a path from x to y then there must be a ...
6
votes
2answers
745 views

What is the difference between Categories and Relations?

For a common basis, I'll state basic definitions of a category and the relation type I'm thinking of. They're here for quick clarity, not precision, so feel free to revise for an answer. Category: A ...
1
vote
1answer
2k views

Equivalence relation: showing that an operation is well-defined

Let $r \in \mathbb{N}$. Observe the equivalence relation $\sim \subseteq \mathbb{Z} \times \mathbb{Z}$ defined as $x \sim y :\Leftrightarrow (\exists k \in \mathbb{Z})(y=x+kr)$. Show that an operation ...
2
votes
1answer
158 views

Equivalence relation/kernel/projection: exactly one $F$ such that $f=F\circ \pi$

$M$, $N$ are sets, $f: M \rightarrow N$ is a function, $R \subseteq M\times M$ is an equivalence relation on $M$, $\pi: M \rightarrow M/R$ is the canonical projection (i.e. $\pi(x)=[x]_R$), and $\ker ...
0
votes
1answer
314 views

Binary relation powers and path length

Let $R\subset A\times A$ a binary relation, and note $a\sim b$ for $(a,b)\in R$. We define $$(a,b)\in R\circ R\Leftrightarrow \exists b\in A : a\sim b, b\sim c$$ and $R^n=R\circ\dots\circ R$. My ...
3
votes
1answer
316 views

Confusion between operation and relation: Clarification needed

I'm doing some old exams and found following question: Set $S={{1,2,3}}$ is given. Provide an example of binary operation in set S, binary relation in set S and a function $f:S\rightarrow ...
4
votes
5answers
535 views

Interesting properties of ternary relations?

Many people are familiar with some properties of binary relations, such as reflexivity, symmetry and transitivity. What are the commonly studied properties of ternary (3-ary) relations? If you ...
27
votes
3answers
2k views

Why isn't reflexivity redundant in the definition of equivalence relation?

An equivalence relation is defined by three properties: reflexivity, symmetry and transitivity. Doesn't symmetry and transitivity implies reflexivity? Consider the following argument. For any $a$ ...