Study your flashcards anywhere!
Download the official Cram app for free >
 Shuffle
Toggle OnToggle Off
 Alphabetize
Toggle OnToggle Off
 Front First
Toggle OnToggle Off
 Both Sides
Toggle OnToggle Off
 Read
Toggle OnToggle Off
How to study your flashcards.
Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key
Up/Down arrow keys: Flip the card between the front and back.down keyup key
H key: Show hint (3rd side).h key
A key: Read text to speech.a key
105 Cards in this Set
 Front
 Back
Set Identities
A⋃∅ A⋂U 
Identity Laws
A A 

Set Identities
A⋃U A⋂∅ 
Domination Laws
U ∅ 

Set Identities
A⋃A A⋂A 
Idempotent Laws
A A 

Set Identities
A⋃B A⋂B 
Commutative Laws
B⋃A B⋂A 

Set Identities
A⋃(B⋃C) A⋂(B⋂C) 
Associative Laws
(A⋃B)⋃C (A⋂B)⋂C 

Set Identities
A⋂(B⋃C) A⋃(B⋂C) 
Distributive Laws
(A⋂B)⋃(A⋂C) (A⋃B)⋂(A⋃C) 

Set Identities
(A⋂B)⋃(A⋂C) (A⋃B)⋂(A⋃C) 
Reverse Distributive Laws
A⋂(B⋃C) A⋃(B⋂C) 

Set Identities
~(A⋃B) ~(A⋂B) Those should be lines over the whole top 
De Morgan's Laws
~A⋂~B ~A⋃~B Those should be lines over individual letters 

Set Identities
~A⋂~B ~A⋃~B Those should be lines over individual letters 
Reverse De Morgan's Laws
~(A⋃B) ~(A⋂B) Those should be lines over the whole top 

Set Identities
A⋃(A⋂B) A⋂(A⋃B) 
Absorption Laws
A A 

Set Identities
A⋃~A A⋂~A Should be lines on top 
Complement Laws
U ∅ 

Truth sets
{xP(x)} explain the parts 
The elements of the set for which the values of x make the second part true  the elementhood test


y∈{xP(x)}

P(y)


y∉{xP(x)}

~P(y)


A is a truthset for the proposition P(x)
What is A in set form What is meant by y∈A y∉A 
P(y)
~P(y) 

Redefine
{x∈UP(x)} 
{xx∈U^P(x)}


Redefine
{xx∈U^P(x)} 
{x∈UP(x)}


Redefine
y∈{x∈UP(x)} 
y∈U^P(y)


Redefine: What is it?
A⋂B 
It is a set
{xx∈A^x∈B} If A and B have truth tests, then it could mean P(x)^Q(x) 

What is it?
x ∈ A⋂B 
It is a statement
x∈A^x∈B and if they had propositions P(x)^Q(x) 

Redefine: What is it?
A⋃B 
It is a set
{xx∈A v x∈B} If A and B have truth tests, then it could mean P(x) v Q(x) 

What is it?
x ∈ A⋃B 
It is a statement
x∈A v x∈B and if they had propositions P(x) v Q(x) 

Redefine: What is it?
A/B 
It is a set
{xx∈A ^ x∉B} If A and B have truth tests, then it could mean P(x) ^ ~Q(x) 

What is it?
x ∈ A/B 
It is a statement
x∈A ^ x∉B and if they had propositions P(x) ^ ~Q(x) 

Redefine:
{xx∈A^x∈B} 
A⋂B


Redefine:
x∈A^x∈B 
x ∈ A⋂B


Redefine:
{xx∈A v x∈B} 
A⋃B


x∈A v x∈B

x ∈ A⋃B


Redefine:
{xx∈A ^ x∉B} 
A/B


Redefine:
x∈A ^ x∉B 
x ∈ A/B


What is it? Name it
Redefine: A∆B (2 definitions) 
It's a set
Symmetric Difference (A\B)⋃(B\A) (A⋃B)\(A⋂B) 

Redefine: what is it?
A⊆B (2 definitions) 
It is a statement:
∀x(x∈A → x∈B) ∀x∈A(x∈B) 

Redefine: What is it?
A=B (2 definitions) 
It is a Statement
∀x(x∈A ↔ x∈B) A⊆B ^ B⊆A 

Redefine:
(A\B)⋃(B\A) (A⋃B)\(A⋂B) 
A∆B


Redefine:
∀x(x∈A → x∈B) ∀x∈A(x∈B) 
A⊆B


Redefine:
∀x(x∈A ↔ x∈B) A⊆B ^ B⊆A 
A=B


What is it? What is it called?
Redefine A⋂B=∅ 
A statement
Called disjoint Allx, x is part of the first part iff x is part of the second part? or This first part is a subset of the second, and the second is a subset of the first? 

What is it?
Reexpress: {pii∈I} 
An indexed set, the set contains all numbers pi with i being the element of some set.
{x∃i∈I(x=pi)} 

What is it?
Reexpress: {x∃i∈I(x=pi)} 
An indexed set, the set contains all numbers pi with i being the element of some set.
{pii∈I} 

An indexed set, the set contains all numbers pi with i being the element of some set.
Give two ways 
{x∃i∈I(x=pi)}
{pii∈I} 

Reexpress the family of sets F in bracket notation:
using the classes of students Cs give two ways 
Each Cs is a set itself
{{1 2},{3,4},{5,6}} C1 = {1,2} F = {Css∈S} {X∃s∈S(X=Cs)} 

What is it?
Reexpress: F = {Css∈S} 
Indexed Family
Each Cs is a set itself {{1 2},{3,4},{5,6}} C1 = {1,2} {X∃s∈S(X=Cs)} 

What is it?
Reexpress: F = {X∃s∈S(X=Cs)} 
Indexed Family
Each Cs is a set itself {{1 2},{3,4},{5,6}} C1 = {1,2} F = {Css∈S} 

What is it?
Reexpress P(A) 
The power set:
{xx⊆A} x is a set 

What is it?
Reexpress {xx⊆A} x is a set 
The power set:
P(A) 

The family set is a subset of what?
Give reasoning 
If all courses were set C then each Cs is a subset of C
For each student Cs∈P(C) Every element then of the family is an element of P(c) so F ⊆ P(C) 

Equivalence
P(A⋂B) 
P(A)⋂P(B)


Equivalence
P(A)⋂P(B) 
P(A⋂B)


Explain and define:
⋂F 
F = {{1,2},{2,3},{3,4}}
this is the intersection of the family {1,2}⋂{2,3}⋂{3,4} {x∀A∈F(x∈A)} {x∀A(A∈F → x∈A)} 

What is this?/
{x∀A∈F(x∈A)} 
F = {{1,2},{2,3},{3,4}}
this is the intersection of the family {1,2}⋂{2,3}⋂{3,4} {x∀A∈F(x∈A)} {x∀A(A∈F → x∈A)} 

What is this?
{x∀A(A∈F → x∈A)} 
F = {{1,2},{2,3},{3,4}}
this is the intersection of the family {1,2}⋂{2,3}⋂{3,4} {x∀A∈F(x∈A)} {x∀A(A∈F → x∈A)} 

What is this?
{1,2}⋂{2,3}⋂{3,4} 
F = {{1,2},{2,3},{3,4}}
this is the intersection of the family {1,2}⋂{2,3}⋂{3,4} {x∀A∈F(x∈A)} {x∀A(A∈F → x∈A)} 

Explain and define:
⋃F 
F = {{1,2},{2,3},{3,4}}
this is the union of the family {1,2}⋃{2,3}⋃{3,4} {x∃A∈F(x∈A)} {x∃A(A∈F ^ x∈A)} 

What is this?/
{x∃A∈F(x∈A)} 
F = {{1,2},{2,3},{3,4}}
this is the union of the family {1,2}⋃{2,3}⋃{3,4} {x∃A∈F(x∈A)} {x∃A(A∈F ^ x∈A)} 

What is this?
{x∃A(A∈F ^ x∈A)} 
F = {{1,2},{2,3},{3,4}}
this is the union of the family {1,2}⋃{2,3}⋃{3,4} {x∃A∈F(x∈A)} {x∃A(A∈F ^ x∈A)} 

What is this?
{1,2}⋃{2,3}⋃{3,4} 
F = {{1,2},{2,3},{3,4}}
this is the union of the family {1,2}⋃{2,3}⋃{3,4} {x∃A∈F(x∈A)} {x∃A(A∈F ^ x∈A)} 

Define
⋂F=∅ 
undefined


What is it?
Redefine ⋂(i∈I) Ai 
Where F puts Ai as sets in a set, this is more like the union of all the sets, it is the same thing as ⋂F
{x∀i∈I(x∈Ai)} {x∀i(i∈I → x∈Ai)} It asks that all the sets have the same element 

What is it?
{x∀i∈I(x∈Ai)} 
⋂(i∈I) Ai
Where F puts Ai as sets in a set, this is more like the union of all the sets, it is the same thing as ⋂F {x∀i∈I(x∈Ai)} {x∀i(i∈I → x∈Ai)} It asks that all the sets have the same element 

What is it?
Redefine ⋃(i∈I) Ai 
Where F puts Ai as sets in a set, this is more like the union of all the sets, it is the same thing as ⋃F
{x∃i∈I(x∈Ai)} {x∃i(i∈I ^ x∈Ai)} That at least one of the sets of Ai have the element 

What is it?
Redefine {x∃i∈I(x∈Ai)} 
Where F puts Ai as sets in a set, this is more like the union of all the
⋃(i∈I) Ai How is this different from a indexed set or indexed family? Because it's an element, not equal sets, it is the same thing as ⋃F {x∃i∈I(x∈Ai)} {x∃i(i∈I ^ x∈Ai)} That at least one of the sets of Ai have the element 

What is it?
Define AxB 
Cartesian Product
{(a,b) a∈A ^ b∈B} results in all ordered pairs 

What is it?
Define {(a,b) a∈A ^ b∈B} 
Cartesian Product
AxB results in all ordered pairs 

Equivalence:
Ax(B⋂C) 
(AxB)⋂(AxC)


Equivalence:
(AxB)⋂(AxC) 
Ax(B⋂C)


Equivalence:
Ax(B⋃C) 
(AxB)⋃(AxC)


Equivalence:
(AxB)⋃(AxC) 
Ax(B⋃C)


Equivalence:
(AxB)⋂(CxD) 
(A⋂C)x(B⋂D)


Equivalence:
(A⋂C)x(B⋂D) 
(AxB)⋂(CxD)


Subset:
(AxB)⋃(CxD) ⊆ 
(A⋃C)x(B⋃D)


Equivalence:
Ax∅ 
∅xA
∅ 

AxB = BxA if and only if

A =∅ or
B = ∅ or A=B 

Truth set of P(x,y)
two versions 
{(a,b)∈AxB  P(x,y)}
{(a,b)  (a,b)∈AxB ^ P(x,y)} 

{(a,b)∈AxB  P(x,y)}

Truth set of P(x,y)


{(a,b)  (a,b)∈AxB ^ P(x,y)}

Truth set of P(x,y)


Define a relation from A to B

R ⊆ AxB
does not need to imply a truth set for R, it can be any subset 

What is this?
R ⊆ AxB 
A relation


Domain of R for AxB

{a∈A  ∃b∈B((a,b)∈R}


{a∈A  ∃b∈B((a,b)∈R}

Domain of R


Range of R

{b∈B  ∃a∈A((a,b)∈R}


{b∈B  ∃a∈A((a,b)∈R}

Range of R


Inverse of R R1

{(b,a)∈BxA  (a,b)∈R}


{(b,a)∈BxA  (a,b)∈R}

Inverse of R R1


Composition of two relations
R⊆AxB S⊆BxC 
SoR
{(a,c)∈AxC  ∃b∈B((a,b)∈R ^ (b,c)∈S} 

{(a,c)∈AxC 
∃b∈B((a,b)∈R ^ (b,c)∈S} 
Composition of two relations
R⊆AxB S⊆BxC SoR 

(r,s)∈L1 if and only if

(s,r)∈L


(s,p)∈ToE if and only if

∃c( (s,c)∈E ^ (c,p) ∈ T


(x,y) ∈ R

xRy


xRy

(x,y) ∈ R


Relation equivalence:
(R1)1 
R


Relation equivalence:
Relation equivalence:Dom(R1) 
Ran(R)


Relation equivalence:
Ran(R) 
Dom(R1)


Relation equivalence:
Ran(R1) 
Dom(R)


Relation equivalence:
Dom(R) 
Ran(R1)


Relation equivalence:
To(SoR) 
(ToS)oR


Relation equivalence:
(ToS)oR 
To(SoR)


(SoR)1

R1 o S1


Equivalence Relation:
R1 o S1 
(SoR)1


the relation R is reflexive on A (or just reflexive if A is clear from context) if
(2 versions) 
∀x∈A(xRx)
or ∀x∈A((x,x)∈Rx) 

the relation R is symmetric if

∀x∈A∀y∈A(xRy → yRx)
or ∀x∈A∀y∈A((x,y)∈R → (y,x)∈R) 

The relation R is transitive if

∀x∈A∀y∈A∀z∈A
((xRy ^ yRz) → xRz) also can be done without shorthand 

R is reflexive iff

i(A) ⊆ R, where as before i(A) is the identity relation on A


R is symmetric iff

R=R1


R is transitive iff

RoR ⊆ R


∃!xP(x)
4 definitions 
∃x(P(x)^~∃y(P(y) ^ y≠x))
∃x(P(x)^∀y(P(y)→y=x)) ∃xP(x) ^ ∀y∀z[(P(y)^P(z))→y=z] Existence Uniqueness ∃x∀y(P(y)↔y=x) 