cs241

Proofs Seem so Hard, How do I get Better at Writing Them? Before we get in to the practical application of logic and proofs to your (a CS student’s) career, we will first make a detour to answer a question that I often get when talking about proofs to students who are unfamiliar with them.

This page will use a small amount of information from the chapter on Set Theory. It is not required, but understanding sets might be helpful to get how induction works.

Integers Made up of Small Pieces Think back to elementary school, a time when things were simple and you had recess. Despite the most difficult math being times tables, we still said math classes were hard 💀 oh how times have changed.

Screw Writing Out Lists When you look at the NJIT campus, there are a bunch of dorm buildings. Specifically, there is Oak, Cyprus, Redwood, Maple, Laurel, Greek Village, and Honors; NJIT sure likes its trees huh.

Remainders and Division Before we get to a topic that is incredibly important in number theory, lets talk about division of integers and the different pieces that you can get when you divide numbers up into integer parts.

Making Sets Even More Brief Look at an example of a set Example: Let $\mathbb{D}$ be the set of all NJIT dorm buildings. This is way better than writing out every individual building, but its still pretty verbose.

Unlimited Power ⛈️ Now that we have the machinery1 of the $\gcd$ and general divisibility, we can touch on a theorem that will unlock us the ability to prove a ton of problems that otherwise would have been super freaking annoying to solve without it.

Sets Exist Therefore… The Venn Diagram Throughout this section, we will show operations in a visual form by showing Venn Diagrams of how the operations work. A Venn Diagram is a simple visualization for performing set operations that can assist in giving an intuition.

The Math of Time In the Chapter on Set Theory, we discussed the idea of relations1 and specifically provided the example of modular equivalence on this page. In there we stated that the relation $$ a\equiv b \mod n $$ was true if both $a,b$ had the same remainder when divided by $n$.

Singular Set Operations Cardinality Cardinality is super easy to understand (at least in the finite sense). Cardinality can be thought of a measure of how “big” a particular set is, and is just the count of how many items are inside the set.