Set Theory Solved Exercises

(1) Define by intension (by description or comprehension) the following sets defined by extension (or by enumeration):

 

[Exercise 1] P={Alabama, Alaska, Arizona, Arkansas, California, Colorado...}

P= {x/ x is a state of the United States}

[Exercise 2] P={England, Scotland, Wales, Northern Ireland}

P= {x/ x is a country of the United Kingdom}

[Exercise 3] P={1,2,3,4,5,6,7,8,9...}

P= {x/ x ∈ ℕ} (x is a natural number)

[Exercise 4] P={...-3, -2, -1, 0, 1, 2, 3...}

P= {x/ x ∈ ℤ} (x is an integer)

[Exercise 5] P={Set theory, Model theory, Proof theory, Computability theory...}

P= {x/ x is a branch of mathematical logic}

[Exercise 6] P={⟨John Lennon, Julian Lennon⟩, ⟨John Lennon, Sean Lennon⟩}

P= {⟨x,y⟩ ∈ MxM/ y is the son of musician x} Where M={x/x is a musician}

[Exercise 7] P={5, 10, 15, 20...}

P= {x/ x is a multiple of 5}

[Exercise 8] P= {...⟨1,-1⟩, ⟨2, -2⟩ ⟨3, -3⟩, ⟨4, -4⟩, ⟨5, -5⟩...}

P= {⟨x,y⟩ ∈ ℤxℤ/ y = -x}

[Exercise 9] P={⟨John Smith, 123-45-6789⟩, ⟨Jane Doe, 987-65-4321⟩, ⟨Bob Wilson, 456-78-9012⟩}

P= {⟨x,y⟩ ∈ HxD/ y is the SSN of x} Where H=persons and D=social security numbers

[Exercise 10] P={⟨1,1⟩, ⟨2,4⟩, ⟨3, 9⟩, ⟨4,16⟩, ⟨5,25⟩...}

P= {⟨x,y⟩ ∈ ℕxℕ/ y = x²}

 

(2) Define by extension the following sets defined by intension:

 

[Exercise 11] P={x ∈ H/ x is a member of the Jackson Five}

P= {Michael Jackson, Jackie Jackson, Tito Jackson, Jermaine Jackson, Marlon Jackson}

[Exercise 12] P={x/x is a member of the Beatles}

P= {John Lennon, Paul McCartney, George Harrison, Ringo Starr}

[Exercise 13] P= {x/ x² - 4=0}

x² - 4 = 0 → x² = 4 → x = ±2

P= {2, -2}

[Exercise 14] P={x/ x² - 48x + 578 = 0}

Using the quadratic formula: x = (48 ± √(2304-2312))/2

Since the discriminant is negative, P= Ø (empty set)

[Exercise 15] P={x / x is one of the Harry Potter books}

P= {Harry Potter and the Philosopher's Stone, Harry Potter and the Chamber of Secrets, Harry Potter and the Prisoner of Azkaban, Harry Potter and the Goblet of Fire, Harry Potter and the Order of the Phoenix, Harry Potter and the Half-Blood Prince, Harry Potter and the Deathly Hallows}

[Exercise 16] P={x/x is a body type}

P= {Ectomorph, Mesomorph, Endomorph}

[Exercise 17] P={⟨x,y⟩ ∈ N x N/ y= x+1}

P= {⟨1,2⟩, ⟨2,3⟩, ⟨3,4⟩, ⟨4,5⟩, ⟨5,6⟩...}

[Exercise 18] P={⟨x,y⟩ ∈ NxN/ x+y=170}

P= {⟨1,169⟩, ⟨2,168⟩, ⟨3,167⟩, ... ⟨85,85⟩, ... ⟨169,1⟩}

[Exercise 19] P={⟨x,y⟩ ∈ SxA/ y is the ASCII code of x} Where S is a computer symbol and A is an ASCII number.

P= {⟨NULL,0⟩, ⟨SOH,1⟩, ⟨STX,2⟩, ⟨ETX,3⟩, ... ⟨A,65⟩, ⟨B,66⟩, ... ⟨a,97⟩...}

[Exercise 20] P={⟨x,y⟩ ∈ NxR/ x is the number corresponding to y} Where N is natural numbers and R is numbers in Roman numeral notation.

P= {⟨1,I⟩, ⟨2,II⟩, ⟨3,III⟩, ⟨4,IV⟩, ⟨5,V⟩, ⟨6,VI⟩, ⟨7,VII⟩, ⟨8,VIII⟩, ⟨9,IX⟩, ⟨10,X⟩...}

 

(3) Perform the following set operations and represent them graphically using Venn diagrams:

 

Given A= {0,1,2}, B={0,1,{2}} C={4,5} represent and calculate the following operations:

 

[Exercise 21] A ∩ B

A ∩ B = {0, 1}

The common elements of A and B are 0 and 1. Note: {2} ∈ B but 2 ∈ A, they are different.

[Exercise 22] A ∪ B

A ∪ B = {0, 1, 2, {2}}

The union includes all elements from both sets.

[Exercise 23] A - C

A - C = {0, 1, 2}

Since A and C are disjoint (have no common elements), A - C = A

[Exercise 24] A ∪ B ∪ C

A ∪ B ∪ C = {0, 1, 2, {2}, 4, 5}

[Exercise 25] A ∩ (B ∪ C)

B ∪ C = {0, 1, {2}, 4, 5}

A ∩ (B ∪ C) = {0, 1}

[Exercise 26] (B ∪ C) - (A ∩ B)

B ∪ C = {0, 1, {2}, 4, 5}

A ∩ B = {0, 1}

(B ∪ C) - (A ∩ B) = {{2}, 4, 5}

[Exercise 27] P(A) ∩ B

P(A) = {Ø, {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}}

P(A) ∩ B = {{2}}

The only element in both P(A) and B is {2}

[Exercise 28] A ∪ (B ∩ C) - A ∩ (B ∪ C)

B ∩ C = Ø

A ∪ (B ∩ C) = A ∪ Ø = {0, 1, 2}

B ∪ C = {0, 1, {2}, 4, 5}

A ∩ (B ∪ C) = {0, 1}

A ∪ (B ∩ C) - A ∩ (B ∪ C) = {0, 1, 2} - {0, 1} = {2}

[Exercise 29] A ∩ A - A ∪ A

A ∩ A = A = {0, 1, 2}

A ∪ A = A = {0, 1, 2}

A - A = Ø

[Exercise 30] [A ∪ (B ∩ C) - A ∩ (B ∪ C)] - [(B ∪ C) - (A ∩ B)]

From Exercise 28: A ∪ (B ∩ C) - A ∩ (B ∪ C) = {2}

From Exercise 26: (B ∪ C) - (A ∩ B) = {{2}, 4, 5}

{2} - {{2}, 4, 5} = {2}

Note: {2} ≠ 2, so 2 is not in the second set.

 

(4) Determine the validity of the following arguments using Venn diagrams:

 

[Exercise 31] "No empiricist is a rationalist. Positivists are empiricists. Therefore, no positivist is a rationalist."

Sets: E={x/x is an Empiricist}, R={x/x is a rationalist}, P={x/x is a positivist}

Formalization:

1. E ∩ R = Ø (No empiricist is a rationalist)

2. P ⊆ E (Positivists are empiricists)

Conclusion: P ∩ R = Ø

The argument is VALID. If P ⊆ E and E ∩ R = Ø, then necessarily P ∩ R = Ø.

[Exercise 32] "Some mathematicians are rigorous. Some mathematicians make calculation errors. All mathematicians who make calculation errors are not rigorous. Therefore, all rigorous mathematicians do not make calculation errors."

Sets: M={x/x is a mathematician}, R={x/x is rigorous}, F={x/x makes calculation errors}

Formalization:

1. M ∩ R ≠ Ø

2. M ∩ F ≠ Ø

3. (M ∩ F) ∩ R = Ø

Conclusion: (M ∩ R) ∩ F = Ø

The argument is VALID. Premise 3 states that those who make errors are not rigorous, which is equivalent to saying that the rigorous do not make errors.

[Exercise 33] "There are agnostic believers and non-agnostic believers. No atheist is a believer. All agnostics are atheists. Therefore, some atheist is neither a believer nor an agnostic."

Sets: C={x/x is a believer}, G={x/x is agnostic}, A={x/x is an atheist}

Formalization:

1. C ∩ G ≠ Ø (There are agnostic believers)

2. C - G ≠ Ø (There are non-agnostic believers)

3. A ∩ C = Ø (No atheist is a believer)

4. G ⊆ A (All agnostics are atheists)

Problem: Premises 1 and 4 together imply C ∩ A ≠ Ø, but premise 3 says A ∩ C = Ø.

The premises are INCONSISTENT.

[Exercise 34] "All dancers are egocentric. Some egocentrics like being watched, although others do not. Those who like it are dancers and those who don't are also dancers. Therefore, all egocentrics are dancers."

Sets: B={x/x is a dancer}, E={x/x is egocentric}, G={x/x likes being watched}

Formalization:

1. B ⊆ E (All dancers are egocentric)

2. E ∩ G ≠ Ø and E - G ≠ Ø (Some egocentrics like it, others don't)

3. (E ∩ G) ⊆ B and (E - G) ⊆ B

From 3: E ⊆ B

Conclusion: E ⊆ B (All egocentrics are dancers)

The argument is VALID.

[Exercise 35] "Philosophers are lovers of wisdom. Some lovers of wisdom pursue the good. Therefore, some philosophers pursue the good."

Sets: F={x/x is a philosopher}, A={x/x is a lover of wisdom}, P={x/x pursues the good}

Formalization:

1. F ⊆ A (Philosophers are lovers of wisdom)

2. A ∩ P ≠ Ø (Some lovers pursue the good)

Conclusion: F ∩ P ≠ Ø

The argument is NOT valid. That some lovers of wisdom pursue the good does not guarantee that those are the philosophers. There could be lovers of wisdom who pursue the good but are not philosophers.

 

(5) Simplify the following sets:

The letter "c" indicates the complement.

 

[Exercise 36] (A ∩ B) ∩ (A ∩ Bᶜ)

(A ∩ B) ∩ (A ∩ Bᶜ)

= A ∩ (B ∩ Bᶜ) [Associativity]

= A ∩ Ø [B ∩ Bᶜ = Ø]

= Ø

[Exercise 37] (Aᶜ ∩ B)ᶜ ∪ (B ∪ Aᶜ)ᶜ ∪ A

(Aᶜ ∩ B)ᶜ ∪ (B ∪ Aᶜ)ᶜ ∪ A

= (A ∪ Bᶜ) ∪ (Bᶜ ∩ A) ∪ A [De Morgan]

= (A ∪ Bᶜ) ∪ A [Absorption: (Bᶜ ∩ A) ⊆ A]

= A ∪ Bᶜ [Absorption: A ⊆ (A ∪ Bᶜ)]

= A ∪ Bᶜ

[Exercise 38] (A ∩ Bᶜ) ∩ (Aᶜ ∩ B)

(A ∩ Bᶜ) ∩ (Aᶜ ∩ B)

= (A ∩ Aᶜ) ∩ (Bᶜ ∩ B) [Commutativity and Associativity]

= Ø ∩ Ø

= Ø

[Exercise 39] (A ∪ A) - (A ∩ B)

(A ∪ A) - (A ∩ B)

= A - (A ∩ B) [Idempotence: A ∪ A = A]

= A ∩ (A ∩ B)ᶜ [Definition of difference]

= A ∩ (Aᶜ ∪ Bᶜ) [De Morgan]

= (A ∩ Aᶜ) ∪ (A ∩ Bᶜ) [Distributivity]

= Ø ∪ (A ∩ Bᶜ)

= A ∩ Bᶜ (or A - B)

[Exercise 40] (A ∩ B) ∪ (Bᶜ ∪ Aᶜ)

(A ∩ B) ∪ (Bᶜ ∪ Aᶜ)

= (A ∩ B) ∪ (A ∩ B)ᶜ [De Morgan: Bᶜ ∪ Aᶜ = (A ∩ B)ᶜ]

= U (Universe)

 

(6) Perform the following operations using the cardinality of the following sets:

 

Given #(A)=2, #(B)=5, #(C)=20, perform the following operations.

 

[Exercise 41] If A and B are disjoint, #(A ∪ B)

If A ∩ B = Ø (disjoint):

#(A ∪ B) = #(A) + #(B) - #(A ∩ B)

#(A ∪ B) = 2 + 5 - 0 = 7

[Exercise 42] If C is disjoint from (A ∩ B) and A={a,b} and B={b, c, d, f, g}, what is the cardinality of #((A ∩ B) ∪ C)?

A ∩ B = {b}, therefore #(A ∩ B) = 1

Since C is disjoint from (A ∩ B):

#((A ∩ B) ∪ C) = #(A ∩ B) + #(C) = 1 + 20 = 21

[Exercise 43] If A={a,b}, B={b, c, d, f, g} and C={a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, r, s, t, v}, what is the cardinality of #((B ∩ C) ∪ A)?

B ∩ C = {b, c, d, f, g} (B ⊂ C), #(B ∩ C) = 5

A = {a, b}

(B ∩ C) ∪ A = {a, b, c, d, f, g}

#((B ∩ C) ∪ A) = 6

[Exercise 44] If all sets are disjoint, calculate #((A ∪ B) - (A ∩ B))

If A and B are disjoint: A ∩ B = Ø

#(A ∪ B) = #(A) + #(B) = 2 + 5 = 7

(A ∪ B) - (A ∩ B) = (A ∪ B) - Ø = A ∪ B

#((A ∪ B) - (A ∩ B)) = 7

[Exercise 45] If C is disjoint and A and B have two elements in common, calculate #([(A ∩ B) ∪ C] - [(B ∩ C) ∪ A])

#(A ∩ B) = 2

C is disjoint from A and B: B ∩ C = Ø, A ∩ C = Ø

(A ∩ B) ∪ C: has 2 + 20 = 22 elements

(B ∩ C) ∪ A = Ø ∪ A = A, has 2 elements

Since (A ∩ B) ⊆ A: [(A ∩ B) ∪ C] - A = C

#([(A ∩ B) ∪ C] - [(B ∩ C) ∪ A]) = #(C) = 20

[Exercise 46] Suppose a bank has conducted a survey on the economic situation of families. According to the results, 30% of families were paying a mortgage, 40% were paying a car loan, and 10% were paying both. The bank wants to know what percentage of families are paying neither mortgages nor car loans.

H = families with mortgage, C = families with car loan

#(H) = 30%, #(C) = 40%, #(H ∩ C) = 10%

#(H ∪ C) = #(H) + #(C) - #(H ∩ C) = 30 + 40 - 10 = 60%

Families with neither loan: 100% - 60% = 40%

[Exercise 47] (Exercise pending statement)

Exercise pending statement.

[Exercise 48] Suppose at a meeting there are 40 people who speak German, Spanish, or English. We know that 22 speak German, 26 do not speak English, 30 speak only one language, 30 speak English or German, 7 speak English but not Spanish, and 17 speak German but not Spanish. We want to answer questions like: How many speak all three languages? How many speak only Spanish? How many speak Spanish but not English?

G = German, S = Spanish, E = English

Total = 40, #(G) = 22, #(Eᶜ) = 26 → #(E) = 14

Only one language = 30, #(E ∪ G) = 30

#(E - S) = 7, #(G - S) = 17

#(G ∪ E) = #(G) + #(E) - #(G ∩ E) → 30 = 22 + 14 - #(G ∩ E) → #(G ∩ E) = 6

Only Spanish = 40 - 30 = 10

People who speak all three languages: Using inclusion-exclusion, #(G ∩ S ∩ E) = 4

Only Spanish: 10

Spanish but not English: #(S) - #(S ∩ E) = 13

[Exercise 49] A survey shows that one in four Americans is a football fan and one in ten is a basketball fan. There is no data on how many Americans share both interests. Under these circumstances, it is not possible to determine exactly how many Americans have one of these two interests, but it can be assured that the percentage of Americans who have one of these interests does not exceed 35%.

F = football fans (25%), B = basketball fans (10%)

#(F ∪ B) = #(F) + #(B) - #(F ∩ B)

Minimum of #(F ∩ B) = 0 (disjoint)

Maximum of #(F ∪ B) = 25 + 10 - 0 = 35%

If there is intersection, the percentage will be less than 35%.

[Exercise 50] If 80% of students in a course pass subject X and 70% pass subject Y, out of every 100 students, the set A of those who pass X has cardinality 80 and the set B of those who pass Y has cardinality 70. How many have passed both subjects?

#(A) = 80, #(B) = 70, #(U) = 100

#(A ∪ B) ≤ 100

#(A ∪ B) = #(A) + #(B) - #(A ∩ B)

100 ≥ 80 + 70 - #(A ∩ B)

#(A ∩ B) ≥ 150 - 100 = 50

At least 50 students have passed both subjects.

The maximum would be 70 (if all of B also passed A).