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

77
votes
12answers
13k 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 ...
30
votes
3answers
3k 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
5answers
217 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
858 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 ...
12
votes
2answers
341 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 ...
11
votes
2answers
331 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
3answers
505 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 ...
10
votes
4answers
357 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
2answers
145 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
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 ...
8
votes
5answers
754 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
3answers
178 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
229 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
1answer
271 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 ...
7
votes
3answers
1k 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
328 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
1answer
644 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
4answers
8k 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 ...
7
votes
2answers
161 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
2k 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
434 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
3k 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 ...
6
votes
2answers
781 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 ...
6
votes
3answers
295 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
422 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
584 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
4k 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
301 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
227 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 ...
6
votes
3answers
144 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 ...
5
votes
7answers
590 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
5answers
6k 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 ...
5
votes
3answers
1k 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
149 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
321 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
206 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
240 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
563 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
4k 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
183 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
2answers
564 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 ...
5
votes
2answers
52 views

Two functions whose order can't be equated - big O notation

Our teacher talked today in the class about big O notation, and about order relations. she mentioned that the set of order of magnitude, is not linear Meaning, there are function $f,g$ such that $f$ ...
5
votes
1answer
283 views

Is this alternative definition of 'equivalence relation' well-known? useful? used?

I discovered that $$R \textrm{ is an equivalence relation on } A \;\equiv\; \langle \forall a,b \in A :: aRb \:\equiv\: \langle \forall x \in A :: aRx \equiv bRx\rangle \rangle$$ The nice thing about ...
5
votes
1answer
73 views

Question about sets of well-orders and isomorphisms between well-orders

I was thinking about this problem in trying to better get a feel for and understand well-orders (I'm trying to learn some set theory) - right now, I'm not really hoping for anybody to supply me with a ...
5
votes
3answers
396 views

Equivalence class of polynomials

$X$ is the set of all polynomials over $\mathbb{R}$. We define an equivalence relation on $X$ such that $p$~$q$ iff $p(0)=q(0)$. ($1$) What is the equivalence class of $p(x)=x$? ($2$) Give a ...
5
votes
2answers
390 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 ...
5
votes
2answers
224 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 ...
5
votes
1answer
90 views

Why is this binary-relation antisymmetric?

Definition of antisymmetric binary-relation is $$\forall a,b\in\mathrm{A},\left[ \left(aRb\wedge bRa\right)\rightarrow\left(a=b\right)\right].$$ Let $\mathrm{A}=\left\{a\mid ...
5
votes
1answer
78 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
2answers
534 views

Sets, functions and relations problem

Yes this is a homework problem but I have attempted to solve it and my work is below, also this is my first question here so I'm sorry for any mistakes: Question: Context: Let $A$ and $B$ be subsets ...