Questions tagged [relations]

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.

3,309 questions
38k 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 the ...
13k 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$ ...
3k views

1k views

Can a relation be transitive when it is symmetric but not reflexive? [duplicate]

Pretty much what the title asks. But here's some context: Suppose $X$ is finite and $R$ is a relation on $X$ that is not reflexive but it is symmetric. Also, suppose we can rule out $xRy$ and $yRz$ ...
1k views

How do I define exactly what a function is?

While it is easy to understand what a function is intuitively, I've been trying to wrap my head around how to precisely define what a function is using only mathematical notation. My attempt at this ...
9k 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 ...
677 views

How is the relation “the smallest element is the same” reflexive?

Let $\mathcal{X}$ be the set of all nonempty subsets of the set $\{1,2,3,...,10\}$. Define the relation $\mathcal{R}$ on $\mathcal{X}$ by: $\forall A, B \in \mathcal{X}, A \mathcal{R} B$ iff the ...
3k 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....
880 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 ...
1k 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 ...
34k views

27k 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 good ...
167 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$ ...
165 views

581 views

Understanding Equivalence Classes?

I am reading about equivalence classes and I would like to make sure I understood thins properly. My book says: The set of equivalence classes under this equivalence relation [$\pmod n$] will be ...
16k views

Whats the difference between Antisymmetric and reflexive? (Set Theory/Discrete math)

Antisymmetric: $\forall x\forall y[ ((x,y)\in R\land (y, x) \in R) \to x= y]$ reflexive: $\forall x[x∈A\to (x, x)\in R]$ What really is the difference between the two? Wouldn't all antisymmetric ...
508 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 ...
132 views

Finding $f(x)$ given a function $f : \Bbb N \to \Bbb N$ which satisfies $f\circ f(x) + f(x) = 2x+15$

I'm stuck on rewriting the function $f\circ f(x) + f(x) = 2x+15$ (into $f(x) = \dots)$. The answer given is $f(x) = x + 5$, which I can easily verify, but I do not know how to go about forming this ...
713 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$.
1k 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 ...
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 ...