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

99
votes
15answers
21k 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 ...
42
votes
4answers
6k 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$ ...
21
votes
7answers
2k views

Proof that the empty set is a relation

In the book Naive Set Theory, Halmos mentions that the "The least exciting relation is the empty one." and proves that the empty set is a set of ordered pairs because there is no element of the empty ...
14
votes
3answers
2k 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 ...
14
votes
3answers
1k 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 ...
13
votes
5answers
236 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
37k 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 ...
12
votes
2answers
360 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 A_j\ne\...
12
votes
2answers
480 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 $\rho\...
11
votes
4answers
5k 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 ...
11
votes
5answers
1k 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$ ...
11
votes
4answers
382 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 A:a\...
10
votes
4answers
3k 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 ...
10
votes
4answers
21k 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
3answers
3k 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 ...
9
votes
2answers
533 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
1answer
152 views

Counting number of mathematical objects and structures

Regarding the numbers of certain mathematical objects and structures, especially sets, relations and functions, I've compiled a list of the counts from various sources: Partitions of a set with $k$ ...
9
votes
2answers
156 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 ∈ A(...
8
votes
10answers
4k 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.
8
votes
3answers
978 views

Is every relation which is transitive and symmetric also reflexive?

I have seen a proof that every relation which is symmetric and transitive is also reflexive. if $A=\{1,2,3\}$ Then if $R=\{(1,2)(2,1)(1,1)\color{blue}{(2,2)}\}$ here $R$ is symmetric and transitive ...
8
votes
3answers
980 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
3answers
226 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
2answers
13k 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 any ...
8
votes
6answers
4k 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 - $...
8
votes
1answer
687 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$.
8
votes
1answer
242 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 ...
8
votes
4answers
358 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 x_1+y_1=x_2+...
8
votes
1answer
97 views

Is there a first-order formula expressing this property?

Suppose $R$ is a binary relation on $\{0,1\}^*$ (where $\{0,1\}^*$ is the set of all finite words over the alphabet $\{0,1\}$), and suppose that for all $x \in \{0,1\}^*$, the number of $y$ such that $...
7
votes
4answers
1k 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
418 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
2answers
965 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}$$ ...
7
votes
3answers
410 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
181 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 ...
6
votes
10answers
470 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
4answers
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 ...
6
votes
5answers
552 views

Example of a relation that is reflexive but not symmetric

By definition, $R$, a relation in a set X, is reflexive if and only if $\forall x\in X$, $x\,R\,x$, and $R$ is symmetric if and only if $x\,R\,y\implies y\,R\,x$. I think $x\,R\,x$ can also be ...
6
votes
5answers
24k 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 $...
6
votes
5answers
13k 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
4answers
2k views

Is the empty set a relation?

Is the empty set is a relation? In Enderton's book A Mathematical Introduction to Logic, a relation is defined as a set of ordered pairs. If the empty set is a relation, why is that? In the text, ...
6
votes
1answer
1k views

Modus Ponens: implication versus entailment

Would it be inconsistent to write Modus Ponens using only implication, not entailment? $(p \wedge (p \to q)) \to q$ The way I understand is that implication ($ \to$) is an operator that yields a new ...
6
votes
3answers
329 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
820 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
4answers
339 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?
6
votes
2answers
841 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$ s....
6
votes
2answers
153 views

Is my understanding of Binary relations correct?

On my assignment it asks Determine with reason if the binary relation is reflexive, symmetric, antisymmetric or transitive. $$R = \{(a, b) \in \mathbb{Z} \times \mathbb{Z} \mid a \text{ is ...
6
votes
2answers
1k 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
221 views

Counting non-isomorphic relations

On a set $X$ of $n$ elements, how many non-isomorphic relations are there? The number of relations on a set of $n$ elements is $|\mathcal{P}(X \times X)|=2^{n^2}$, but is there any way to give a ...
6
votes
5answers
728 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 ...
6
votes
2answers
761 views

Ordering the field of real rational functions

Perusing the Wikipedia article on ordered fields, I encountered an interesting statement, a variation of which I am now trying to prove. Basically, I am trying to show that the set of real rational ...
6
votes
3answers
190 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 ...