Write functions genUnion and genIntersect for generalized list union and list intersection. The functions should be of type [[a]] -> [a]. Note that genIntersect is undefined on the empty list of lists.

Solution 1 - 1st attempt:
genUnion :: Eq a => [[a]] -> [a]
genUnion [] = []
genUnion (x:xs) = gu2 x xs where
  gu2 :: Eq a => [a] -> [[a]] -> [a]
  gu2 xs [] = xs
  gu2 xs (y:ys) = gu2 (u2 xs y) ys where
    u2 :: Eq a => [a] -> [a] -> [a]
    u2 xs [] = xs
    u2 xs (y:ys)
      | elem y xs = u2 xs ys
      | otherwise = u2 (xs++[y]) ys

genIntersect :: Eq a => [[a]] -> [a]
genIntersect [] = error "general intersection is undefined on the empty list of lists"
genIntersect (x:xs) = gi2 x xs where
  gi2 :: Eq a => [a] -> [[a]] -> [a]
  gi2 xs [] = xs
  gi2 xs (y:ys) = gi2 (i2 xs y) ys where
    i2 :: Eq a => [a] -> [a] -> [a]
    i2 [] _ = []
    i2 (x:xs) ys
      | elem x ys = x : i2 xs ys
      | otherwise = i2 xs ys

Solution 2 - much nicer:
genUnion' :: Eq a => [[a]] -> [a]
genUnion' [] = []
genUnion' (x:xs) = union x (genUnion' xs)      

genIntersect' :: Eq a => [[a]] -> [a]
genIntersect' [] = error "general intersection is undefined on the empty list of lists"
genIntersect' [xs] = xs
genIntersect' (x:xs) = intersect x (genIntersect' xs)

# posted by rot13(Unafba Pune) @ 11:27 PM 0 comments

Write a function splitList that gives all the ways to split a list of at least two elements in two non-empty parts. The type declaration is:

  splitList :: [a] -> [([a],[a])]

  [([1],[2,3,4]),([1,2],[3,4]),([1,2,3],[4])]

splitList :: [a] -> [([a],[a])]
splitList xs | length xs < 2 = error "Input list must have at least 2 elements"
splitList (x:xs) = splitList' [] [x] xs where
  splitList' :: [([a],[a])] -> [a] -> [a] -> [([a],[a])]
  splitList' rs xs [] = rs -- rs holds the result
  splitList' rs xs (y:ys) = splitList' (rs++[(xs,y:ys)]) (xs++[y]) ys

splitList2 :: [a] -> [([a],[a])]
splitList2 [x,y] = [([x],[y])]
splitList2 (x:y:ys) = ([x],(y:ys)) : splitList2' [x,y] ys where
  splitList2' :: [a] -> [a] -> [([a],[a])]
  splitList2' xs [] = []
  splitList2' xs (y:ys) = (xs, (y:ys)) : splitList2' (xs++[y]) ys

# posted by rot13(Unafba Pune) @ 8:14 PM 0 comments

Write your own definition of a Haskell operation "reverse" that reverses a list.

Solution:

  myreverse :: [a] -> [a]
  myreverse [] = []
  myreverse (x:xs) = myreverse xs ++ [x]

# posted by rot13(Unafba Pune) @ 8:09 PM 0 comments

Prove that [(A - C) × B] ∪ [A × (B - D)] ⊆ (A × B) - (C × D)

Proof:

  Suppose p ∈ [(A - C) × B] ∪ [A × (B - D)]
  Then either (i) a ∈ A - C and b ∈ B, or (ii) a ∈ A and b ∈ B - D exist such that p = (a,b)

  (i) From a ∈ A - C and b ∈ B, we get a ∈ A ∧ b ∈ B ∧ ¬(a ∈ C)
      A fortiori, a ∈ A ∧ b ∈ B ∧ ¬(a ∈ C ∧ b ∈ D)
      Thus p ∈ (A × B) - (C × D)

  (ii) From a ∈ A and b ∈ B - D, we get a ∈ A ∧ b ∈ B ∧ ¬(b ∈ D)
      A fortiori, a ∈ A ∧ b ∈ B ∧ ¬(a ∈ C ∧ b ∈ D)
      Thus p ∈ (A × B) - (C × D)

  Thus [(A - C) × B] ∪ [A × (B - D)] ⊆ (A × B) - (C × D)

# posted by rot13(Unafba Pune) @ 11:50 AM 0 comments

Given ∀i∈IAi ⊆ X, show that (∪i∈IAi)c = ∩i∈IAic

Proof:

⊆: Suppose x ∈ (∪i∈IAi)c
   We will show that x ∈ ∩i∈IAic

   From x ∈ (∪i∈IAi)c, we get ¬∃i∈I(x ∈ Ai)
   It follows that ∀i∈I(x ∉ Ai), i.e., ∀i∈I(x ∈ Aic)
   Thus x ∈ ∩i∈IAic

⊇: Suppose x ∈ ∩i∈IAic
   We will show that x ∈ (∪i∈IAi)c

   From x ∈ ∩i∈IAic, we get ∀i∈I(x ∈ Aic), i.e., ∀i∈I(x ∉ Ai)
   It follows that ¬∃i∈I(x ∈ Ai)
   Thus x ∈ (∪i∈IAi)c

# posted by rot13(Unafba Pune) @ 10:39 AM 0 comments

Show that B ∪ (∩i∈IAi) = ∩i∈I(B ∪ Ai)

Proof:

⊆: Suppose x ∈ B ∪ (∩i∈IAi)
   We will show that x ∈ ∩i∈I(B ∪ Ai)

   From x ∈ B ∪ (∩i∈IAi), we get x ∈ B ∨ ∀i∈I(x ∈ Ai)
   Which means ∀i∈I(x ∈ B ∨ x ∈ Ai)
   Thus x ∈ ∩i∈I(B ∪ Ai)

⊇: Suppose x ∈ ∩i∈I(B ∪ Ai)
   We will show that x ∈ B ∪ (∩i∈IAi)

   From x ∈ ∩i∈I(B ∪ Ai), we get ∀i∈I(x ∈ B ∨ x ∈ Ai)
   Which means x ∈ B ∨ ∀i∈I(x ∈ Ai)
   Thus x ∈ B ∪ (∩i∈IAi)

# posted by rot13(Unafba Pune) @ 10:27 AM 0 comments

Show that B ∩ (∪i∈IAi) = ∪i∈I(B ∩ Ai)

Proof:

⊆: Suppose x ∈ B ∩ (∪i∈IAi)
   We will show that x ∈ ∪i∈I(B ∩ Ai)

     From x ∈ B ∩ (∪i∈IAi), we get x ∈ B ∧ ∃i∈I(x ∈ Ai)
     Which means ∃i∈I(x ∈ B ∧ x ∈ Ai)
     Thus x ∈ ∪i∈I(B ∩ Ai)

⊇: Suppose x ∈ ∪i∈I(B ∩ Ai)
   We will show that x ∈ B ∩ (∪i∈IAi)

     From x ∈ ∪i∈I(B ∩ Ai), we get ∃i∈I(x ∈ B ∧ x ∈ Ai)
     Which means x ∈ B ∧ ∃i∈I(x ∈ Ai)
     Thus x ∈ B ∩ (∪i∈IAi)

# posted by rot13(Unafba Pune) @ 10:04 AM 0 comments

Is it true that for all sets A and B, Ƥ(A ∩ B) = Ƥ(A) ∩ Ƥ(B) ?

I think so, and here is the proof:

  Let X ∈ Ƥ(A ∩ B)
  We will show that X ∈ Ƥ(A) ∩ Ƥ(B)

    From X ∈ Ƥ(A ∩ B), we get X ⊆ A ∩ B i.e., X ⊆ A and X ⊆ B
    It follows that X ∈ Ƥ(A) and X ∈ Ƥ(B), i.e., X ∈ Ƥ(A) ∩ Ƥ(B)
    Thus Ƥ(A ∩ B) ⇒ Ƥ(A) ∩ Ƥ(B)

  Let Y ∈ Ƥ(A) ∩ Ƥ(B)
  We will show that Y ∈ Ƥ(A ∩ B)

    From Y ∈ Ƥ(A) ∩ Ƥ(B), we get Y ∈ Ƥ(A) and Y ∈ Ƥ(B), i.e., Y ⊆ A and Y ⊆ B
    Let m ∈ Y.  Then m ∈ A and m ∈ B, i.e., m ∈ A ∩ B
    So Y ⊆ A ∩ B
    It follows that Y ∈ Ƥ(A ∩ B)
    Thus Ƥ(A) ∩ Ƥ(B) ⇒ Ƥ(A ∩ B)

# posted by rot13(Unafba Pune) @ 9:31 PM 0 comments

Show that A ∩ B = A - (A - B)

Proof:

    A - (A - B)
  = x ∈ A ∧ x ∉ (A - B)
  = x ∈ A ∧ ¬(x ∈ A ∧ x ∉ B)
  = x ∈ A ∧ (x ∉ A ∨ x ∈ B)
  = (x ∈ A ∧ x ∉ A) ∨ (x ∈ A ∧ x ∈ B)
  = x ∈ A ∧ x ∈ B

  ⇔ A ∩ B

# posted by rot13(Unafba Pune) @ 8:57 PM 0 comments

Show that A ⊄ B ⇔ A - B ≠ ∅

Proof:

    A ⊄ B 
  = ¬∀x(x ∈ A ⇒ x ∈ B)
  = ¬∀x(x ∉ A ∨ x ∈ B)
  = ∃x(¬(x ∉ A ∨ x ∈ B))
  = ∃x(x ∈ A ∧ x ∉ B)

  ⇔ A - B ≠ ∅  

# posted by rot13(Unafba Pune) @ 8:29 PM 0 comments

Assume that A is a set of sets.  Show that {x ∈ A|x ∉ x} ∉ A.

Proof:

  Let P(x) = x ∈ A ∧ x ∉ x, and F = {x|P(x)}
  We will show that F ∉ A

    Assume the contrary, F ∈ A
    There are only two possibilities: either F ∉ F or F ∈ F

    Suppose F ∉ F
    From F ∈ A and F ∉ F, we get P(F)
    From F = {x|P(x)}, it follows F ∈ F.  A contradiction.

    Suppose F ∈ F
    From F = {x|P(x)}, we get P(F)
    From P(F) = F ∈ A ∧ F ∉ F, it follows F ∉ F.  A contradiction.

  Thus F ∉ A, which means {x ∈ A|x ∉ x} ∉ A

# posted by rot13(Unafba Pune) @ 10:35 AM 0 comments

Prove that 11 is the only prime of the form p^2 + 2, with p prime

Proof:

  Let n = p^2 + 2
  If n is 11, p is 3
  If n is not 11, p must be either of the form 3a+1 or 3a+2, with a ∈ ℕ

  Suppose p = 3a+1
  n = p^2 + 2 = (3a+1)^2 + 2 = 9a2 + 6a + 3

  Suppose p = 3a+2
  n = p^2 + 2 = (3a+2)^2 + 2 = 9a2 + 12a + 6

  In both cases, n is divisible by 3 and therefore not prime
  Thus 11 is the only prime of the form p^2+2, with p prime

# posted by rot13(Unafba Pune) @ 12:47 PM 0 comments

Show that if n is composite, 2n - 1 is composite too.

(Hint: Asume that n = ab and prove that xy = 2n - 1 for the numbers x = 2b- 1 and y = 1 + 2b + 22b + ... + 2(a-1)b)

Solution:

  Assume n = ab where a, b ∈ ℕ
  Let x = 2b - 1 and y = 1 + 2b + 22b + ... + 2(a-1)b

  xy = (2b - 1)(1 + 2b + 22b + ... + 2(a-1)b)
     =        2b + 22b + ... + 2(a-1)b + 2(a-1)b+b
       - (1 + 2b + 22b + ... + 2(a-1)b)
     = 2ab - 1
     = 2n - 1

  This shows that if n is composite, 2n - 1 is also composite since we can always find integers x and y of the form above.

# posted by rot13(Unafba Pune) @ 9:31 PM 0 comments

Let A = {4n + 3 | n ∈ ℕ}.  Show that A contains infinitely many prime numbers.

(Hint: any prime > 2 is odd, hence of the form 4n + 1 or 4n + 3.)

Solution:

  Assume there are only finitely many primes of the form 4n + 3, say p1,...,pm
  
    Consider the number N = 4p1...pm - 1 = 4(p1...pm - 1) + 3
    We will show that N must have a factor p of the form 4n + 3
  
      Suppose N does not have a factor of the form 4n + 3
      Note the fact that (4a + 1)(4b + 1) is of the form 4c + 1
      If all factors of N is of the form 4n + 1, N will be of the form 4n + 1, but N is not
      Thus N must have a factor of the form 4n + 3
  
    Based on the assumption, it follows p is a member of {p1,...,pm} and p divides N
    But dividing N by p would result in the form 4c - 1/p which is a fraction (where c ∈ ℕ)
    So p cannot divide N.  A contradiction.
  
  Thus there are infinitely many primes of the form 4n + 3.

# posted by rot13(Unafba Pune) @ 11:02 PM 0 comments

Prove that

  ϕ ≡ ψ iff ϕ ⇔ ψ

Proof:

  The above statement can be expanded into a conjunction of two sub-statements

    ((ϕ ≡ ψ) ⇒ (ϕ ⇔ ψ)) ∧
    ((ϕ ⇔ ψ) ⇒ (ϕ ≡ ψ))

  which can be further expanded into

    ((ϕ ≡ ψ) ⇒ ((ϕ ⇒ ψ) ∧ (ψ ⇒ ϕ))) ∧
    (((ϕ ⇒ ψ) ∧ (ψ ⇒ ϕ)) ⇒ (ϕ ≡ ψ))

  1) Given: ϕ ≡ ψ
     To be proven: (ϕ ⇒ ψ) ∧ (ψ ⇒ ϕ)

     Suppose ϕ and ψ
     It follows (ϕ ⇒ ψ) ∧ (ψ ⇒ ϕ)

  2) Given: (ϕ ⇒ ψ) ∧ (ψ ⇒ ϕ)
     To be proven: ϕ ≡ ψ

     Suppose ϕ, then ψ
     Suppose ¬ϕ, then ¬ψ

     Thus ϕ ≡ ψ

Thus ϕ ≡ ψ iff ϕ ⇔ ψ

# posted by rot13(Unafba Pune) @ 8:27 AM 0 comments

Given

  ∀x∃y(xRy),
  ∀x∀y(xRy => yRx), 
  ∀x∀y∀z(xRy ∧ yRz => xRz) 

Prove that

  ∀x(xRx)

Proof:

  Let a be arbitrary
  From ∀x∃y(xRy), it follows ∃y(aRy)
  Let b such that aRb
  From ∀x∀y(xRy => yRx), it follows aRb => bRa
  From ∀x∀y∀z(xRy ∧ yRz => xRz), it follows aRb ∧ bRa => aRa

Thus ∀x(xRx)

# posted by rot13(Unafba Pune) @ 3:05 PM 0 comments

Given

  ∀y∃z∀xP(x,y,z)

Prove that

  ∀x∀y∃zP(x,y,z)

Proof:

  Let a,b be arbitrary
  We need to show ∃zP(a,b,z)
  Given ∀y∃z∀xP(x,y,z), it follows ∃z∀xP(x,b,z)
  Let c be such that ∀xP(x,b,c)
  So P(a,b,c)

Thus ∀x∀y∃zP(x,y,z)

# posted by rot13(Unafba Pune) @ 1:20 PM 0 comments

Given
∀x∀y(xRy ∧ x≠y => ¬yRx)
Prove that
∀x∀y(xRy ∧ yRx => x=y)
Proof:

  Suppose a and b are arbitrary objects, it follows (by definition)
aRb ∧ a≠b => ¬bRa
  Suppose: aRb ∧ bRa
  To be proven: a=b

  Proof:
    Suppose: a≠b
    To be proven: ⊥ (ie contradiction)

    Proof:
      From aRb ∧ a≠b => ¬bRa, and aRb ∧ bRa,
      it follows ¬bRa ∧ bRa ≡ ⊥

    Thus a=b

  Thus ∀x∀y(xRy ∧ yRx => x=y)

# posted by rot13(Unafba Pune) @ 8:55 AM 0 comments