Week #7

Week #7

#17

get wrong right
S: forall x in X, forall y in Y, P(x,y) => Q(x,y)
To disprove S, should you prove
forall x in X, forall y in Y, P(x,y) => neg Q(x,y) X
What about
forall x in X, forall y in Y, neg[P(x,y) => Q(x,y)] X
We should prove:
neg S: exists x in X, exists y in Y, P(x,y) and neg Q(x,y) O

e.g. forall n in N, T(n) => T(n2)
Proof:
Assume n in N
Assume T(n)
Then n = 7i + 1, some i in N         # defn of T(n)
Then n2 = (7i+1)2 = 49i2 + 14i + 1   # algebra
= 7(7i2 + 2i) + 1   # more algebra
Then exists i0 in N, n2 = 7i0 + 1    # i0 = 7i2 + 2i in N
# 7, 2, i in N, N closed under *,+
Then T(n2)                           # defn
Conclude ...

e.g. Disprove forall n in N, T(n2) => T(n)
In order to disprove the statement, prove its negation, which is:
exists n i N, T(n2) and neg T(n)
Pick n = 3 /*this place can leave blank at first*/, Then n in N
Then n2 = 36 /*this place can leave blank at first*/
Then exists i in N, n2 = 7i + 1    # i = 5
But neg(exisits k in N, n=7k+1)    # 6 = 7*0 + 6
Then T(n2) and neg T(n)
Conclude ...

#18

Direct Prove Implication
assume A, derive C
Indirect Prove Implication
assume neg C, derive neg A
Prove things about typical representative
assume x in R, ... Conclude forall x in R, ...
Prove the existence of x in D, with property P(x)
pick x = ___, show x in D and P(x)


Sorting strategies
-insertion sort
    <-4
1  2  3    5  6  7
- selection
4<->1<->2<->3  5  6  7
- Radix
- Quick sort
- Tim
- Merge sort
- ...

# The speed of different algorithm depend on input/hardware

Abstract Steps
f(x) = x2, g(x) = 3(x)+50, h(x) = 15x2 + x

Week #6

Week #6

#15

non-boolean function
floor(x) is the largest integer <= x
Now prove forall x in R, floor(x) < x+1

Assume x in R           # generic
Then floor(x) <= x # from definition
Then x < x+1          # add x to both sides 0<1
Then floor(x) < x+1   # transitivity
Conclude forall x in R, floor(x) < x+1

Using more if the definition
forall x in R, y = floor(x) <=> (y in Z) and (y <= x) and (forall z in Z, z<=x => z<=y) # The full definition of floor.
Now prove forall x in R, floor(x) > x-1

Assume x in R                    # generic
Then floor(x) in Z             # from definition
Then floor(x) + 1 in Z         # Z closed under +
Then floor(x) + 1 > floor(x)   # add floor(x) to 1>0
Then floor(x) + 1 > x          # by contrapositive, since floor(x) > floor(x) and floor(x)+1 in Z
Then floor(x) > x-1            # subtract 1
Conclude ...

Proving something false
Define a sequence:
forall n in N, a_n = floor(n/2) == n//2
# 0, 0, 1, 1, 2, 2, 3, 3, ......
Now prove:
S: exists i in N, forall j in N, j>i => a_j = a_i
# This claim is false, disprove it.
neg S: forall i in N, exists j in N, j>i and a_j != a_i

Assume i in N
Pick j = i+2, Then j in  # N closed under +
Then j>i
Then a_j = floor(j/2) = floor((i+2)/2) = floor(i/2 + 1) > x+1 = i/2 >= floor(i/2)
Then a_i != a_j
Conclude ....




#16

e.g Prove: forall n in N, n2 + n is even
Proof:
Assume n in N
Then n is even or n is odd
Case 1: assume n is even
Then exists k in N, n = 2k,      # defn of even
Then n2 + n = n(n+1)
                    = 2k(2k+1)
Then exists k0 in N, n2+n = 2k0  # k0 = k(2k+1) in N
# k, 2, 1 in N, N closed under +,*
Then n2 + n is even              # defn of even
Case 2: assume n is odd
Then exists k in N, n = 2k + 1   # defn of odd
Then n2 + n = n(n+1)
= (2k+1)(2k+2)
= 2(2k+1)(k+1)
Then exists k0 in N, n2+n = 2k0  # k0 = (2k+1)(k+1) in N
# k, 2, 1 in N, N closed under +,*
Then n2 + n is even              # defn of even
Then n2+n is even, since it is so in both possible assumptions
Conclude ...


e.g. Prove forall e in R+, exists d in R+, forall x in R, |x-3|<d => |x2-3^2|<e

Proof:
Assume e in R+
Pick d=min(1,e/7) /*This place can be blank at first*/, Then d in R+
Assume x in R
Assume |x-3|<d
Then |x2-3^2|= |(x-3)(x+3)|
= |x-3||x+3|
< d|x-3|          # |x-3|<d, multiply by |x+3|
= d|x-3+3+3|
= d(|x-3|+6)      # |x+y|<=|x|+|y|
= d(d+6)
  <= d(1+6)         # d <= 1
<= e              # d <= e/7
Then |x2-3^2| < e
Conclude ...

Week #5

Week #5

#13

  e.g. Prove that for every pair of non-negative real numbers (x,y), if x is greater than y, then the geometric mean sqrt(xy) is less than the arithmetic mean, (x+y)/2

    P: x>y>=0, x-y>0, (x-y)2>0
    Q: sqrt(xy) < (x+y)/2

    scratch work:
    sqrt(xy) < (x+y)/2
    xy < (x2 + y2 + 2xy)/4
    4xy < x2 + y2 + 2xy
    0 < x2 + y2 + 2xy

  Proof:
    Assume x,y are typical non-negative real numbers.
      Assume x>y              # antecedent
        Then x-y>0            # subtracting y from both sides
        Then (x-y)2>0         # square positive number -> positive number
        Then x2+y2-2xy>0      # algebra
        Then x2+y2+2xy>4xy    # adding 4xy on both sides
        Then (x+y)2>4xy       # factor
        Then (x+y)2/4>xy      # divide both sides by 4
        Then x>y => (x+y)/2 > sqrt(xy) # assume the antecedent
                                       # got consequent
    Conclude ∀x,y∈R, x>y>=0 => (x+y)/2 > sqrt(xy) # assumed x,y are generic real number


Chain with (P=>Q)and(P=>R) <=> P=>(Q and R)

e.g Prove the square of an odd number is odd.
forall n in N, n odd => n2 odd.

scratch:
n = 2k + 1
n2 = 4k2 + 4k + 1
= 2(2k2+2k) +1

Proof:
Assume n is some typical natural number
Assume n is odd
Then exists k in N, n = 2k + 1       # definition of odd
Then n2 = 4k2 + 4k + 1
 = 2(2k2+2k) +1               # algebra
Then exists j in N, n2 = 2j + 1      # j = 2k2 + 2k in N
  # since k,2 in N, N closed under +,*
Then n2 is odd                       # definition of odd
Conclude forall n in N, n odd => n2 odd


Term-test #1
I got a full mark on this test. Since I was not doing so well on my assignment, I worked hard on this test. I did all the past papers that I can find and reviewed all the lecture notes. And I put everything of the sample test down on my cheat-sheet, which is very helpful because the test is very similar to the sample test.


#14

Proving Existence
To prove that a set is non-empty, it's enough to exhibit one element.

e.g. Exists x in R, x3 + 3x2 - 4x = 12
Proof:
Pick x = 2, Then x in R
Then x3 + 3x2 - 4x = 8 + 12 - 8 = 12
Conclude exists x in R, x3 + 3x2 - 4x = 12

Prove a claim about a sequence
e.g. Define a sequence a_n by: forall n in N, a_n = n2.
Now prove: exists i in N, forall j in N, a<=i => j<i
Proof:
Pick i = 2 Then i in N   # 2 in N
Assume j is a representative of N
Assume a_j <= i
Then j2 <= 2
Then j < sqrt(2)
so j <= sqrt(2) < 2
Conclude ...

Contradiction
A special case of contrapositive

e.g. Define the prime natural numbers by:
P = {p in N | p has exactly two distinct divisors in N}
How do you prove S: forall n in N, |p| > n # There are infinite prime numbers.
# F1 and F2 and F3 and ... and Fn => S
# neg S => neg F1 or neg F2 or ... or neg Fn
# Suppose the conclusion is False, find a fact that is false.

# neg S: exists n in N, |p| <= n
Proof(by contradiction):
Assume exists n in N, |p| <= n
Then exists k in {0,1,...,n}, |p| = k
Then {p1, p2, p3, ... pk} = P            # just list the primes
Then m = p1 * p2 * ... * pk in N         # N closed under *
Then m+1 in N                            # N closed under *
Then m+1 > 1                             # m >= 2 * 3 * 5 ...
Then exists p in P, p|(m+1)              # every in N > 1 has prime factor
also p|m                                 # since m = p1 * p2 * ... pk
Then p|(m + 1 - m) = 1                   # factor divides difference
Then p|1                                 # contradiction!!
So, our assumption that exists n in N, |p| <= n is false, since it leads to a contradiction.


Thoughts

Basicly this week we talked about structures of proof and some examples of some simple proofs. And here is something I summerized.

1. Proving Universal (e.g. forall x,y... P => Q)
Assume x,y...    # introduce forall
    Assume P    # assume antecedent
        Then ...   # something reduced from P
        ...    # more steps
        Then Q    # get Q
    Conclude P => Q    # get conclusion
Conclude forall x,y...    # get conclusion with quantifiers

2. Proving Existence (e.g. exists x,y... P=>Q)
Pick x=..., y=..., ...    # introduce exists
Assume P    # assume antecedent
    Then ...    # something reduced from P
    ...    # more steps
    Then Q    # get Q
Conclude P => Q    # get conclusion
Conclude forall x,y...    # get conclusion with quantifiers

3. Prove by contradiction (e.g. P)
Assume P    # assume the claim is true
    Then ...    # something reduced form P
    ...    # more steps
    Then (some contradiction)    # get contradiction
Conclude neg P    # get conclusion

Week #4

Week #4

#10

Transitivity
  forall x in X, (P(x)=>Q(x)) and (Q(x)=>R(x)) => (P(x)=>R(x))
  Proof:
  1) P=>Q means, as sets, P in Q.
     Q=>R means, as sets, Q in R.
     so, P in R, i.e. p=>R

  2) By Venn diagram.

  3) neg[(P=>Q) and (Q=>R) => (P=>R)]
  <=>((P=>Q) and (Q=>R) and neg(P=>R)
  <=>(¬P V Q) and (¬Q V R) and (P and ¬R)
  <=>(¬P and ¬Q) V ( Q and ¬Q) V [(¬P and R) V (Q and R)] and P and ¬R
  <=>[(¬P and ¬Q) V (¬P and R V Q and R)] and P and ¬R
  <=>(¬P and P and ¬Q and R) V (¬P and P and R and ¬R) V (Q and R and P and ¬R)
             False                     False                    False

For all, one, ... v.s. One, for all, ...
  ∀x∈S1, Ǝy∈S2, x+y=5 (1)
  Ǝy∈S2, ∀x∈S1, x+y=5 (2)
  S1=S2={1,2,3,4}

  (1) >>> all({any({x+y==5 for y in S2}) for x in S1})
      True
  (2) >>> any({all({x+y==5 for y in S2}) for x in S1})
      False

Pic Here!

#11

  ∀e∈R+, Ǝd∈R+, ∀e∈R, |x-0.6|<d => |x2-0.36|<e
  lim x2 = infinity
  x->infinity
  ∀e∈R+, Ǝd∈R+, ∀e∈R, x>d => x2>e
  Switch ∀,Ǝ do not preserve truth.

  ∀m∈N, ∀n∈N, mn∈N
  It changed nothing when switching ∀ pairs


Proof
  Argument to convince audience something is True/False.
  1) Think about why you believe the statement is true.
  2) Write up your reasoning in a clear way.

#12

Thoughts:
Assignment #1

I'm not doing very well at the first assignment. I messed up using word converting doc file into pdf. And I also didn't get the format of the last question right, so I lost all 40% of the last question. However as a friend of mine saying, what I have to do is to move forward and try my best on my following assignments and tests. The worst assignment is only weighting 6% or less in the total course. So I will learn how to use LaTeX and work hard in the future.

Week #3

Week #3

#7

Conjunction: ∧
  A(x) and B(x)    # python keyword "and" work like this
  A(x) ∧ B(x)      # ∧ is the symbol of "and"
  As sets: x∈A∩B

  Watch out for the English word "and"!
  1) There is a pen and a telephone.
    != P(x)∧T(x)
  2) The solution are x<10 and x>20
    # The word "and" here mean "or" in logic

Disjunction: ∨
  A(x) or B(x)     # python keyword "or" work like this
  A(x) ∨ B(x)      # ∨ is the symbol of "or"
  As sets: x∈A∪B

Negation: ¬
  Negate the statement "All employees earning over 110,000 are female." Usually prepending the word "Not" will work.

     ¬(∀e∈E, O(e) => F(e))
  -> Ǝe∈E, ¬(O(e) => F(e))
  -> Ǝe∈E,   O(e) ∧ ¬F(e)

  ¬¬(...) <=> (...)

  special
    ¬(∀x∈X, P(x) => Q(x))
  ->  Ǝx∈X, P(x) ∧ ¬Q(x)

    ¬(Ǝx∈X, P(x) ∧ ¬Q(x))
  ->  ∀x∈X, P(x) => Q(x)

Scope
  (P(x) V Q(x)) => R(x) v.s. P(x) V (Q(x) => R(x))

  (∀x∈R, Ǝy∈R, x<y) => (∀x∈R, Ǝy∈R, x2<y)
  (∀z∈R, Ǝw∈R, z<w) => (∀z∈R, Ǝw∈R, z2<w)

P(x) => (Q(x)  => R(x))
  Drawing Truth
  # I'm too lazy to draw the graph

  Tabulating Truth

  P  Q  R | Q=>R | P=>(Q=>R)
  T  T  T |  T   |    T
  T  T  F |  F   |    F
  T  F  T |  T   |    T
  T  F  F |  T   |    T
  F  T  T |  T   |    T
  F  T  F |  F   |    T
  F  F  T |  T   |    T
  F  F  F |  T   |    T

#8

Tantology, Satisfiability and Unsatisfiability
  ∀D∈D, ∀D,
  (P(x)=>Q(x)) <=> (¬P(x) V Q(x))

  ƎD∈D, ƎP∈P(D), ƎQ∈P(D), Ǝx∈D
  (P(x)=>Q(x)) <=> (Q(x)=>P(x))

  satisfiable: always true
  unsatisfiable: always false

De Morgan's Law(s):
  ¬(P V Q) <=> ¬P ∧ ¬Q
  ¬(P ∧ Q) <=> ¬P V ¬Q

P=>Q vs ¬P V Q
  P Q | P=>Q | ¬P V Q
  T T |  T   |   T
  T F |  F   |   F
  F T |  T   |   T
  F F |  T   |   T

Bi-implication
      P <=> Q
  (¬P∧¬Q)V(P ∧ Q)




Thoughts:

This week we talked conjunction/disjunction and negation, which are two of the most important concepts in this course. And I found that bi-implication is the most interesting parts.

-bi-implication
We already know that how to translate an implication into a disjunction and how to negate it. But how can we deal with bi-implication? For example if we get a bi-implication P <=> Q.
By its definition, it can be translate to (P=>Q) and (Q=>P). Then we can transform the implications into two disjunctions. Thus, we get (neg P or Q) and (neg Q or P).
Then if we open the brackets, we can get something like: (neg P and neg Q) or (neg P and P) or (Q and neg Q) or (Q and P).
Since (neg P and P) and (Q and neg Q) are unsatisfiable, we can get ride of them, then we get (neg P and neg Q) or (P and Q).
If we consider them in English, we can say that P iff Q means P and Q have to be both true or both false.


Problem Solving:

Folding

After first fold, we got a down crease
           D
After the second fold, we got an up crease on the left and a down fold on the right
     U     D     D
And then, we put UDUD into those empty spot between the three crease
  U  U  D  D  U  D  D
And then we do it recursively.


def get_creases(n):
    if n == 1:
        return ['D']
    else:
        a = ['U','D'] * (2**(n-2))
        b = []
        c = get_creases(n-1)
        i = 0
        for crease in a:
            b.append(crease)
            if i == len(c):
                break
            b.append(c[i])
            i += 1
        return b
     

Week #2

Week #2

#4

def qo(S1, S2):
    return not all({x in S2 for x in S1})

def q1(S1, S2):
    return any({x in S2 for x in S1})

def q1(S1, S2):
    return all({x in S2 for x in S1})

def q3(S1, S2):
    return not any({x in S2 for x in S1})

- All employees earn 42000
  q2(E, O)
- Some female earn over 42000
  q1(F, O)
- Some male doesn't earn over 42000
  q0(M, O)
- All male doesn't earn over 42000
  q3(M, O)

Universal/Existential duality
- To verify a universal ("for all") claim, show there is no counter-example.
- To falsify a universal claim, find at least one counter-example.
- To verify an existential claim, show there is at least one example.
- To falsify an existential claim, show there are no example.

Sentences
  Sentence refer to expression that we structured to evaluate to either ture or false

The employee earn over 55000
         --> which employee?
Every employee makes less than 55000
           --> which set of employees?

Symbols
  The value of symbols is not making the sentence short. It is to make teh statement symbolically and clearly emphasize the connection between two subjects.
  L(x): x∈L

  For all employees, the employee makes less than 5500.
->∀ employees x, x makes less than 55000.
->∀x ∈ E, L(x)
  # The first line & the third line are DIFFERENT
  # If L(x) is an empty set, the sentence is True, because there's no counter-example.

also:
  some employee earns over 55000
  ∃x ∈ E, L(x)
  # And this is not a statement about an element x

Implication

  There is a couple of ways to expression the definition.

  "If a employee is male, then he earns less than 55000."
  This could accurately be expressed using universal quantification by restricting the et we are considering.
∀x ∈E M, L(x)
  The form "if P, then Q." is called implication

Verifying implication
  which of the following statements are a counter-example to:
  ST1:"If the employee is male, then he earns less than 55000."

  Al       |  male  | 60000
  Ellen  | female | 50000
  Gwen | female | 95000
  Carlos|  male  | 40000


  If P then Q ---> counter-example: P and not Q

  If you eat vegetable, then you can have your dessert.

   eat veg, get des T
  Xeat veg, get des T
  Xeat veg,Xget des T
   eat veg,Xget des F

#5

Implication informaton
    x  E, if F(x), then L(x)
  If this implication is True, what can we deduce from about the following sets?
  1) F, the set of female employees? F
  2) L
  3) not F
  4) not L

Symbolic expression:
  ∀x∈E, F(x) => L(x)

Reverse the implication, you can get the converse.
  ∀x∈E, L(x) => F(x)
  We cannot say if the implication is true, the converse of the implication is also true.
  But if L == F, we can say so.

Negation and Contrapositive
  ¬: not

  ∀x∈E, F(x) => L(x)
  The contrapositive of the implication:
  ∀x∈E, ¬L(x) => ¬F(x)

  1) When x in F:
      impl: x in L
      cont: x in L
  2) When x not in F:
      impl: nothing
      cont: nothing
  3) When x in L:
      impl: nothing
      cont: nothing
  4) When x not in L:
      impl: x not in F
      cont: x not in F

  e.g. ∀n∈N, P(n) => Q(n)
    P(n): n is a multiple of 4
    Q(n): n^2 is a multiple of 4

    implication  : ∀n∈N,  P(n) =>  Q(n)
    converse     : ∀n∈N,  Q(n) =>  P(n)
   contrapostive: ∀n∈N, ¬Q(n) => ¬P(n)

    - n is a multiple of 4:
  impl: n^2 is multi of 4
conv: nothing
cont: n^2 is mulit of 4

- n is not a multiple of 4
impl: nothing
conv: n^2 is not a multiple of 4    # assume the converse is true
cont: nothing

- n^2 is a multiple of 4
impl: nothing
conv: n is a multiple of 4
cont: nothing

- n^2 is a multiple of 4
impl: n is not a multiple of 4
conv: nothing
cont: n is not a multiple of 4

Nature Language
    If nominated, I will not stand.
    If you think I'm lying, then you're a liar.
    Whenever I hear that song, I think about ice cream.
    Differentiability is sufficient for continuity.
    Matching fingerprints and a motive are enough for guilt.
    You can't stay enrolled in CSC165 without a pulse.
    Successful programming requires skill.
    I'll go if you insist.
    Don't knock it unless you've tried it.
=if not
    # P
    # Q


#6

Vacuous Truth
  P(x) => Q(x) False when T => F
  ∀x∈R, x2 - 2x + 2 = 0

  To find out if the implication is False. You have to find a counter-example true in P and false in Q.
  -> You can't find an x is true in P. -> You can't, so the implication is true.

  FALSE imply everything

Equivalence
  "Every male employee (M) earns between 25000 and 45000."
  Both the implication and its converse are true.

  ∀x∈R, x2-2x+2 = 0 <=> x > x+5
  is equivalent to
  ∀x∈R, x2-2x+2 = 0  => x > x+5
  ∀x∈R, x2-2x+2 = 0 <=  x > x+5

Idiom
  Every D that is a P is also a Q
  -> ∀x∈D, P(x) => Q(x)
  -> ∀x∈(D∩P), Q(x)
  -> ∀x∈, P(x)∧Q(x)
  # Those three statements are different!




Thoughts:

This week a key concept we talked about is the implication, and I found something really interesting about it. And here I'm mainly going to talk about -justify/falsify an implication, and -translate English to symbols.

-justify/falsify an implication
Firstly we know that an implication means an 'if, then' statement. For example, "If you eat vegetable, then you can have your dessert." or P => Q. And if we step forward, an 'if, then' statement means if P is true, then Q must be true. And this definition of implication does not mentioned anything about what will it happens if P is false. So, if P is false, then Q can be either True or False, which means that there are no restriction of Q. Thus if P is False, then whatever Q is the implication is still True; if P is True, the implication is True iff Q is True (This have the similar with truth table -- me from the future). So the only thing that can falsify an implication is a counter-example showing that there exists a situation that P is True and Q is False. Back to our dessert vegetable example, the only thing that can falsify the statement is ate some vegetables, but my mom didn't give me my dessert.So there is still some possibility that I didn't eat any vegetable but still getting the dessert. So whenever I heard my mom saying so, I'll risk not eating any vegetables and pray for the possibility to raise. So if I'm becoming a parent, I will tell my child something like "You can get your dessert if and only if you eat vegetables." (How I learned how to be a parent in a computer science class)

-translate English to symbols
During the lecture there is an exercise for us to find out what is P and what is Q from a English sentence (and it's also in the lecture note). And it is definitely the hardest question that class. Besides all the 8 sentences given, there are some challenging sentences I came up.
K(n): n is known
Pr(n): n is a programmer
Pm(n): n is a program
W(n,p): n writes p
  * All known programs are written by some known programmers.
    forall p, Pg(p) and K(p) => exists n, Pr(n) and K(p) and W(n, p)

Week #1

Week 1

#2
-Building sets in math

S = {1, 3, 5, 7, 9, 11}
5 in S? True
6 in S? False
{1,3} in S? True
{1,4} in S? False

{x| x in S and x>6}
{7, 9, 11}

{x+2| x in S and x>6}
{9, 11, 13}

-Building sets in Python

S = {1, 3, 5, 7, 9, 11}
# Python doesn't look like this

{x for x in S and x>6}
    |    ∈

# Use these
# In python, elements do not reappear
{x for x in S if x>6}
{x+2 for x in S if x>6}

>>> Danny = {x for x in S if x>6}
>>> Danny
{9,11,17}
>>> any({False, False, False})
False
>>> any({True, False, False})
True
>>> all({False, True, True})
False
>>> all({True, True, True})
True
>> all({})
True

#3
def qo(S1, S2):
    return not all({x in S2 for x in S1})
    # Some element of S1 is not an element of S2.


def q1(S1, S2):
    return any({x in S2 for x in S1})
    # Some element of S1 is an element of S2

def q1(S1, S2):
    return all({x in S2 for x in S1})
    # Every element of S1 is an element of S2
    # We include the situation that the set is an empty set

def q3(S1, S2):
    return not any({x in S2 for x in S1})
# Every element of S1 is not an element of S2
# This also works when S1 is an empty set

Rigor without morits
1) Understand the problem
 * Know what's given
 * What's required
 * Re-state the problem in your own words/ draw some diagrams

2) Plan solution(s)
 * Try come up different approaches

3) Carry out your plan:
 * WRITE IT DOWN

4) Review



Thoughts:

This week is the first week of university and our prof talked about sets.
And during the lecture, I found two things that are tricky, the 'for' and the duplicates.

-'for'
For example, in the lecture notes the python command Danny = {x for x in S if x > 6} is hard to understand and hard to precisely describe it in English. However, our professor suggested that we can understand it in the term of | of sets in maths. For example Danny = {x | x in S and x > 6}. In sets of maths, things before 'for' are the expression of element in the actual sets and things afterwards are the conditions that the item have to satisfy. So that {x | x in S and x > 6} means that for all the possible values of x in the universe, if that value is in S and it is greater than 6, then we append that value of x to the set. Thus we got {7, 9, 11} as the final result. And {x+2 | x in S and x > 6} means that for all the possible values of x in the universe, if that value is in S and it is greater than 6, then we append x+2 to the set. Thus we got {9, 11, 13}. We can apply similar idea to help us understanding 'for' in creating sets in Python. For instance, {x for x in S if x > 6} means that for all the xes in S, if that x is greater than 6, then append it to the set.

- duplicates
We know that sets have some wonderful features. One of them is it automatically merge all the duplicates. By my friend's Shrey's idea, we can write a python program with only one line to merge all the duplicates in a list or check if there is duplicates in the list. Here are the code.

def merge_duplicates(lst):
    """(list) -> list
    return a list with all duplicates merged.
    """
    return list(set(lst))

def contain_duplicates(lst):
    """(list) -> boolean
    return True if there is no duplicate in the list given.
    """
    return len(lst) == len(set(lst))

And this is very helpful in our CSC148 assignment.