[<< wikibooks] Set Theory/Review
Need help creating math symbols?

= Definitions =

== Subset ==

A
⊆
B

{\displaystyle A\subseteq B}

{
x
∣
x
∈
A

then

x
∈
B
}

{\displaystyle \{x\mid x\in A{\hbox{ then }}x\in B\}}
Subset means for all x, if x is in A then x is also in B.

== Proper Subset ==

A
⊂
B

{\displaystyle A\subset B}

{
x
∣
x
∈
A

then

x
∈
B

and

A
≠
B
}

{\displaystyle \{x\mid x\in A{\hbox{ then }}x\in B{\hbox{ and }}A\neq B\}}

== Union ==

⋃
A

{\displaystyle \bigcup A}

{
x
∣
x
∈
⋃
A

iff

y
∈
A

s.t.

x
∈
y
}

{\displaystyle \{x\mid x\in \bigcup A{\hbox{ iff }}y\in A{\hbox{ s.t. }}x\in y\}}

A
∪
B

{\displaystyle A\cup B}

{
x
∣
x
∈
A

or

x
∈
B
}

{\displaystyle \{x\mid x\in A{\hbox{ or }}x\in B\}}

== Intersection ==

⋂
A

{\displaystyle \bigcap A}

{
x
∣

for all

a
∈
A
,
x
∈
a
}

{\displaystyle \{x\mid {\hbox{for all }}a\in A,x\in a\}}

A
∩
B

{\displaystyle A\cap B}

{
x
∣
x
∈
A

and

x
∈
B
}

{\displaystyle \{x\mid x\in A{\hbox{ and }}x\in B\}}

== Empty Set ==

∅

{\displaystyle \emptyset }

There is a set

A

s.t.

{
x
∣
x
∉
A
}

{\displaystyle {\hbox{There is a set }}A{\hbox{ s.t. }}\{x\mid x\notin A\}}

== Minus ==

A
−
B

{\displaystyle A-B}

{
x
∣
x
∈
A

and

x
∉
B
}

{\displaystyle \{x\mid x\in A{\hbox{ and }}x\notin B\}}

== Powerset ==

P

(
A
)

{\displaystyle {\mathcal {P}}(A)}

{
x
∣
x
⊆
A
}

{\displaystyle \{x\mid x\subseteq A\}}

== Ordered Pair ==

⟨
a
,
b
⟩

{\displaystyle \langle a,b\rangle }

{
{
a
}
,
{
a
,
b
}
}

{\displaystyle \{\{a\},\{a,b\}\}}

== Cartesian Product ==

A
×
B

{\displaystyle A\times B}

A
×
B
=
{
x
∣
x
=
⟨
a
,
b
⟩

for some

a
∈
A

and some

b
∈
B
}

{\displaystyle A\times B=\{x\mid x=\langle a,b\rangle {\hbox{ for some }}a\in A{\hbox{ and some }}b\in B\}}
or

{
⟨
a
,
b
⟩
∣
a
∈
A

and

b
∈
B
}

{\displaystyle \{\langle a,b\rangle \mid a\in A{\hbox{ and }}b\in B\}}

== Relation ==
A set of ordered pairs

=== Domain ===

{
x
∣

for some

y
,
⟨
x
,
y
⟩
∈
R
}

{\displaystyle \{x\mid {\hbox{ for some }}y,\langle x,y\rangle \in R\}}

=== Range ===

{
y
∣

for some

x
,
⟨
x
,
y
⟩
∈
R
}

{\displaystyle \{y\mid {\hbox{ for some }}x,\langle x,y\rangle \in R\}}

=== Field ===

dom(

R

)

∪

ran(

R

)

{\displaystyle {\hbox{dom(}}R{\hbox{)}}\cup {\hbox{ran(}}R{\hbox{)}}}

== Equivalence Relations ==
Reflexive: A binary relation R on A is reflexive iff for all a in A,  in R
Symmetric: A rel R is symmetric iff for all a, b if  in R then  R
Transitive: A relation R is transitive iff for all a, b, and c if  in R and  in R then  in R

== Partial Ordering ==
Transitive and,
Irreflexive: for all a,  not in R

=== Trichotomy ===
Exactly one of the following holds

x < y
x = y
y < x

= Proof Strategies =

== If, then ==
Prove if x then y

Suppose x
...
...
so, y

== If and only If ==
Prove x iff y

suppose x
...
...
so, y

suppose y
...
...
so, x

== Equality ==
Prove x = y

show x subset y
and
show y subset x

== Non-Equality ==
Prove x != y

x = {has p}
y = {has p}
a in x, but a not in y