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

2
votes
1answer
165 views

Is there a name for this type of binary relation?

Suppose that $X$ is a set and $\sim$ is a binary relation on $X$ that satisfies for all $x,y \in X$; if $x \sim y$ then $x \sim x$ and $y \sim y$. Is there a name for this type of relation? I am ...
1
vote
2answers
514 views

Relations: is the composition of an empty set with a nonempty set empty? And the other way around

Given $T\circ S=\emptyset$ and $R$ nonempty, would $$(T \circ S) \circ R$$ be anything other than the empty set? I'm also curious the other way around. I think that it would be just empty.
3
votes
1answer
163 views

Relation: pairwise and mutually

Suppose we can define a relation $R$ over the sets $X_1, …, X_k$ for any natural number $k$, note not specified for a particular $k$. I was wondering if there is some definition or conditions ...
8
votes
1answer
227 views

How to prove an extension of ZFC is conservative

Working in ZFC. I've defined a function-like binary predicate $R$ on a proper class. It has to be recursive; i.e. $R(a,b)$ must usually depend on one or more $R(c,d)$ for some $c$s and $d$s ...
3
votes
3answers
515 views

Can a partial order be symmetric aside from being reflexive, antisymmetric, and transitive by definition?

Can a partial order by symmetric in addition to being reflexive, antisymmetric, and transitive? Also, can an equivalence relation be antisymmetric aside from being reflexive, symmetric, and ...
1
vote
1answer
528 views

Prove something is a partial order

A relation $\mathrm{R}$ is defined on the set of all positive integers by: $x\mathrm{R}y$ if and only if $y = 3^k\cdot x$ for some non-negative integer $k$. Prove that $\mathrm{R}$ is a partial ...
4
votes
3answers
180 views

Books and Papers that have treatment of properties like Idempotence and related operations

Please recommend resources to study Idempotence and other similar properties of processes and operations in depth. I want to know what other properties like Idempotence are there for an operation. I ...
2
votes
4answers
825 views

Prove $\sim$ is an equivalence relation: $x \sim y$ if and only if $y = 3^kx$, where $k$ is a real number

The relation $\sim$ is defined on $\mathbb{Z}^+$ (all positive integers). We say $x\sim y$ if and only if $y=3^kx$ for some real number $k$. I need to prove that $\sim$ is an equivalence relation. ...
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
459 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
255 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
486 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
747 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
320 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$ ...