maths.free › Set Theory & Logic › Relations, functions and equivalence

Relations, functions and equivalence

Relations as sets of pairs; reflexive, symmetric, transitive; functions and bijections.

A relation is a set of ordered pairs; an equivalence relation (reflexive, symmetric, transitive) partitions its set into classes; a function is a relation with exactly one output per input. Picture it: "same remainder mod 3" splits the integers into three columns. Think it: a bijection is how we say two sets have the same size — including infinite ones.

工作范例: truth table of p implies q

Discrete-Math · Propositional-Logic

Truth table of p implies q

一步

  1. p \Rightarrow q

    2 variable(s) → 4 rows. Fill in every combination.

  2. \

    Contingent: true for some inputs, false for others.

发送答案
p \Rightarrow q

Symbols used here

\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow
not, and, or, implies, iff
Logical connectives.
\neq
not equal
The two sides are different.
\infty
infinity
Not a number: "grows without bound" in limits and intervals.
\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}
number sets
Naturals, integers, rationals, reals, complex numbers.
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.
\forall,\ \exists
for all, there exists
Quantifiers: every x; at least one x.
\blacksquare\ \text{or}\ \square
end of proof (halmos)
Marks the point where the statement has been established.

How to: Relations, functions and equivalence

  1. 2 variable(s) → 4 rows. Fill in every combination.
  2. Contingent: true for some inputs, false for others.

Questions people ask

Are some infinities bigger than others?

Yes. The integers and the rationals can be listed; the real numbers cannot (Cantor's diagonal argument), so there are strictly more reals than integers.

What is the difference between a relation and a function?

A relation pairs inputs with outputs freely; a function is a relation in which every input gets exactly one output.

试试你自己试试

更多 Set Theory & Logic

Sets and operationsCardinality and infinityLogic and methods of proof