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

83
votes
12answers
15k views

Are there real-life relations which are symmetric and reflexive but not transitive?

Inspired by Halmos (Naive Set Theory) . . . For each of these three possible properties [reflexivity, symmetry, and transitivity], find a relation that does not have that property but does have ...
31
votes
3answers
4k 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$ ...
13
votes
3answers
945 views

Symbol for unknown relation?

When solving equations like $$\begin{align} 4x-4 &=\frac{(2x)^2}{x} \\ -4 &= \frac{4x^2}{x} -4x \\ -4 &= 4x -4x \\[0.2em] -4 &= 0\end{align}$$ using the equality-symbol feels like ...
13
votes
5answers
228 views

Does “=” have to be interpreted as equality?

To put it briefly: In model theory, we are allowed to interpret any relation symbol in any way we like. So why do people seem to require that "$=$" is interpreted as the actual equality? Let me ...
12
votes
3answers
584 views

Sole minimal element: Why not also the minimum?

A minimal element (any number thereof) of a partially ordered set $S$ is an element that is not greater than any other element in $S$. The minimum (at most one) of a partially ordered set $S$ is an ...
12
votes
2answers
343 views

When does “pairwise” strengthen and when does it weaken?

"Pairwise disjoint" is stronger than "disjoint"; it sometimes happens that $\displaystyle\bigcap\limits_{i\in I} A_i=\varnothing$ but for every $i,j$, or at least for some, one has $A_i \cap ...
12
votes
2answers
373 views

Can we extend the definition of a continuous function to binary relations?

Let $X,Y$ be topological spaces. A function $\phi:X\to Y$ is continuous iff for any open subset $A\subseteq Y,$ the preimage $\phi^{-1}(A)$ is open in $X.$ We could similarly define a relation ...
10
votes
4answers
366 views

A problem about symmetric relations on finite sets.

We have these assumptions: $X$ is a finite set. $\sim$ is an irreflexive symmetric relation on $X$. for any subset $Y\subseteq X$ we define $$\mathcal{Cl}(Y)=\{A\subseteq Y\mid(\forall a,b\in ...
9
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 ...
9
votes
4answers
11k views

Transitive Relations

For example, $$R = \{ (1,1),(1,2),(2,1),(2,2) \} \quad\text{for}\quad A = \{1,2,3\}.$$ This relation is symmetric and transitive. I understand that the relation is symmetric, but my brain does not ...
9
votes
2answers
364 views

Can we extend the definition of a homomorphism to binary relations?

This is going to be quite a long post. The actual questions will be at the end of it in section "Questions." INTRODUCTION After receiving an answer to this question about extending the definition of ...
9
votes
2answers
148 views

Question from 'How to Prove It'

Below is the question from the book mentioned above: Suppose $f : A \rightarrow B$ and $R$ is an equivalence relation on $A$. We will say that $f$ is compatible with $R$ if $∀x \in A\forall y ∈ ...
8
votes
4answers
4k views

Understanding equivalence class, equivalence relation, partition

Im having difficulty grasping a couple of set theory concepts, specifically concepts dealing with relations. Here are the ones I'm having trouble with and their definitions. 1) The collection of ...
8
votes
3answers
849 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 ...
8
votes
5answers
813 views

Dependence of Axioms of Equivalence Relation?

This question is problem 11(a) in chapter 1 in 'Topics in Algebra' by I.N. Herstein. These are the properties of equivalence relation given in this book. Prop 1 $a \sim a$ Prop 2 $a \sim b$ ...
8
votes
6answers
3k views

How do the Properties of Relations work?

This is simply not clicking for me. I'm currently learning math during the summer vacation and I'm on the chapter for relations and functions. There are five properties for a relation: Reflexive - R ...
8
votes
3answers
193 views

Can we take images of equivalence relations?

Given a function $f : X \rightarrow Y$, it is well-known that we can take the image under $f$ of any subset $A \subseteq X$, and we can take the preimage under $f$ of any subset $A \subseteq Y$. This ...
8
votes
1answer
234 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 ...
7
votes
3answers
1k views

Is Russell's paradox really about sets as such?

It seems to me that Russell's paradox rather is a "paradox" concerning relations. Suppose we want to construct a graph (with finite or infinite number of nodes) and want some node to be adjacent ...
7
votes
4answers
796 views

“$ x $ is a brother of $ y $.” Why is this not transitive?

I am working on a problem set at the moment, and while checking my answers I realized that I have listed "x is a brother of y" as a transitive relation, while the answers say that it is not. EDIT: I ...
7
votes
3answers
2k views

Can a relation with less than 3 elements be considered transitive?

The generalize rule for a transitive relation is a -> b b -> c therefor a -> c If an element has less than 3 elements, can it still be transitive? If ...
7
votes
3answers
337 views

Can only one ordered pair be a relation?

I'm sorry, but I really can't find an answer to this no matter how deep I dig. A relation is defined as any set of ordered pairs. But what about a set of only one ordered pair? Is it still a ...
7
votes
3answers
21k views

Is my understanding of antisymmetric and symmetric relations correct?

So I'm having a hard time grasping how a relation can be both antisymmetric and symmetric, or neither. Are my examples correct? symmetric & antisymmetric ...
7
votes
1answer
661 views

What is meant by “m|n”? Two letters separated by a vertical bar (|)

I am new to this subject, and not not sure what "|" symbol means on this statement. Let $R_2 \subset\Bbb N \times\Bbb N$ be defined by $(m, n) \in R_2$ if and only if $m|n$.
7
votes
3answers
284 views

Unambiguous terminology for domains, ranges, sources and targets.

Given a correspondence $f : X \rightarrow Y$ (which may or may not be a function) I generally use the following terminology. $X$ is the source of $f$ $Y$ is the target $\{x \in X \mid \exists y \in ...
7
votes
2answers
166 views

Is there a name for relations with this property?

Is there a name for relations $\rho : X \rightarrow Y$ such that for all $x,x' \in X$ and all $y,y' \in Y$ we have that the following conditions $$xy \in \rho$$ $$x'y \in \rho$$ $$xy' \in \rho$$ imply ...
7
votes
4answers
234 views

How to find the appropriate equivalence class?

I would like find the system of representatives & equivalence class for $[(1,-1)]_{\equiv 1}$ and $[(1,-1)]_{\equiv 2}$ given: $R_1=_{def.} (x_1,y_1)\equiv(x_2,y_2) \Leftrightarrow ...
6
votes
10answers
3k views

I need a relation which is not reflexive, not symmetric, and not transitive

I need an example of a relation which is simultaneously not reflexive, not symmetric, and not transitive. Any accessible examples? Thanks in advance.
6
votes
10answers
443 views

Sanity check, is $\{(-9,-3),(2,-1),(7,7),(-1,-1)\}$ a function?

EDIT#2: Yes, I'm crazy! This IS a function. Thanks for beating the correct logic into me everyone! I'm using a website provided by my algebra textbook that has questions and answers. It has the ...
6
votes
5answers
8k 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 ...
6
votes
3answers
309 views

Do there exist interesting binary relations satisfying reflexivity and symmetry, but not transitivity?

Given the usual set-theoretic definition of a binary relation[1], along with the usual notions of reflexivity symmetry transitivity Do there exist any interesting (i.e. surprising, yielding novel ...
6
votes
1answer
521 views

The relation “is strictly higher than” is considered antisymmetric?

I'm studying from Michael Carter's "Foundations" and in the answer key to exercise 1.15 he says that with regard to mountain peaks the relation "is strictly higher than" is antisymmetric. In other ...
6
votes
2answers
745 views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
6
votes
2answers
6k views

If a relation is symmetric and transitive, will it be reflexive? [duplicate]

Possible Duplicate: Why isn't reflexivity redundant in the definition of equivalence relation? We had a heated discussion in class today and i still cant be sure if the professor was ...
6
votes
2answers
486 views

Notation for a relation

I'm reading up on "Set Theory and Logic" by Stoll and came upon notation for relations that I haven't seen before. I've seen $x\sim{y},$ and $xRy$ before but Stoll uses this one. $$(x,y)\in{\rho}$$ ...
6
votes
3answers
165 views

Abuse of notation in declaring a variable is a function of another?

The standard way to write $ \text{ y is a function of x} $ is $ y = f(x) $ This is taken to mean that $y$ is the value of function $f$ evaluated at $x$. For simplicity let's take $f$ to be some ...
6
votes
1answer
24 views

How to determine an ordering relation?

I would like to determine an ordering relation: We are given a linear order on $\mathbb{N}$ $\leq'$ for all $m,n$ such that $ n\leq' m$ $\iff$ (n is odd and m is even) or ($n$$\leq$$m$ and $m-n$ is ...
6
votes
1answer
93 views

Let R be a relation on set A. Prove that $R^2 \subseteq R <=>$ R is transitive $<=> R^i \subseteq R ,\forall i \geq 1$

this is my first question here. I'm still relatively new to more advanced mathematics and don't have much experience with proofs yet. I'm self-studying at the moment and therefore have no one to check ...
5
votes
7answers
637 views

Branch of math studying relations

There are many branches of mathematics (analysis, algebra, group theory, logic, ...). Now, I'm interested in relations and their special kinds (like equivalence relation) and their properties. I'd ...
5
votes
4answers
738 views

is the empty set a relation?

Is the empty set is a relation? I wonder if the empty set is a relation.in enderton's a relation is a set of ordered pairs. If yes it's a relation why is that?. There is an example in the text for a ...
5
votes
2answers
6k views

How many equivalence relations on a set with 4 elements.

Let S be a set containing 4 elements (I choose {$a,b,c,d$}). How many possible equivalence relations are there? So I started by making a list of the possible relations: ...
5
votes
3answers
2k views

Why is the empty set finite?

On page 25 of Principles of Mathematical Analysis (ed. 3) by Rudin, there is the definition (excluding the irrelevant parts for this question): Definition 2.4: For any positive integer $n$, let ...
5
votes
3answers
151 views

Is $\varsigma$ equivalence relation?

Let $\varsigma$ be a relation on $\wp(\mathbb{N})$ by defining $\langle A,B\rangle\in \varsigma$ iff exist natural $n$ such that $|A\Delta B|=n$. Is $\varsigma$ equivalence relation? Reflexive: For ...
5
votes
4answers
330 views

Can functions be defined by relations?

So let us say that for whatever reasons, we are not allowed to use function symbols in first-order logic. Then can we define and use a function only by relations?
5
votes
3answers
249 views

Determine if the following is a partial order, and if so, is it a total order?

I'm having trouble figuring out how I can solve this... I've never been good with formal proofs. $$(\mathbb{R},\preceq), a\preceq b\iff a^{2}\leq b^{2}$$ I can easily see that it's Reflexive: ...
5
votes
2answers
361 views

Main Theorems/Techniques for proving Homeomorphism?

General Question: what are the most common Theorems/Methods used to prove Homeomorphism? I encountered: - find the map explicitly - use the Compact-to-Hausdorff Lemma - find cts maps $f$ and $g$ ...
5
votes
5answers
588 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 ...
5
votes
3answers
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 ...
5
votes
2answers
209 views

On the Definition of Posets…

In my book, the author defines posets formally in the following way: Let $P$ be a set, and let $\le$ be a relationship on $P$ so that, $a$. $\le$ is reflective. $b$. $\le$ is transitive. $c$. ...
5
votes
1answer
68 views

How does one charaterize functionhood (etc.) in the category of relations?

Question: How can I complete the following sentence: "For all $\mathsf{Rel}$-arrows $f : X \rightarrow Y$, $f$ is a function iff ..."? Of course, this is easily done: "For all $\mathsf{Rel}$-arrows ...