CMSC 27100 — Lecture 13

Fermat’s Little Theorem

One observation from the previous problem is that once we have the notion of equivalence, we can very quickly simplify some numbers by swapping them out with an equivalent but smaller number. How far can we take this idea?

One thing to consider is what else we might gain when every element in our structure has a unique multiplicative inverse. An interesting consequence is that such a structure can be said to be cyclic in some sense.

Consider $\mathbb Z_5$. The multiplication table for $\mathbb Z_5$ is

0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1

Observe that, when we multiply every element of $\mathbb Z_5$ with an arbitrary non-zero element, we end up getting each element exactly once.

This leads us to the following observation.

Let $p$ be prime and let $a$ be relatively prime with $p$. Then $$\{[a]_p, [2a]_p, \dots, [(p-1)a]_p\} = \{[1]_p,[2]_p,\dots,[p-1]_p\}.$$

This is really a claim about the cyclicity of the elements in $\mathbb Z_p$. That is, we can “cycle” through every element of $\mathbb Z_p$ by multiplying each element by some fixed integer $a$, as long as $a \not\equiv 0 \pmod p$.

The proof of this lemma makes for a nice exercise. If you want to prove this, there are two things to show:

  1. there is no $i$ with $1 \leq i \leq p-1$ such that $a \cdot i \equiv 0 \pmod p$ (i.e. nothing gets cancelled to 0), and
  2. for $1 \leq i \lt j \leq p-1$, $a \cdot i \neq a \cdot j$ (multiplying $a$ by each $i$ goes to a unique element).

This then leads us to the following result of Pierre de Fermat.

For all prime numbers $p$ and integers $a$ such that $\gcd(a,p) = 1$, $a^{p-1} \equiv 1 \pmod p$.

Before, we mentioned non-linear congruences. These are congruences $x^k \equiv a \pmod m$ with $k \geq 2$. For these congruences, there is often not much you can do except to try out numbers and look for a solution—which there may not be. Fermat’s Little Theorem gives us a scenario in which we don’t have to go searching and a way to simplify congruences with seeming large degree.

Consider $n \equiv (a \cdot 1) \cdot (a \cdot 2) \cdot \cdots \cdot (a \cdot (p-1)) \pmod p$. By Lemma 13.2, \[(a \cdot 1) \cdot (a \cdot 2) \cdot \cdots \cdot (a \cdot (p-1)) \equiv 1 \cdot 2 \cdot \cdots \cdot (p-1) \pmod p.\]

Now, since $1, \dots, p-1$ are relatively prime with $p$, they all have inverses. So we multiply both sides of the congruence with the product of all inverses. The right hand side gives us \[1 \cdot 2 \cdot \cdots \cdot p-1 \cdot 1^{-1} \cdot 2^{-1} \cdot \cdots \cdot (p-1)^{-1} \equiv 1 \pmod p.\] Then the left hand side gives us \begin{align*} &\ (a \cdot 1) \cdot (a \cdot 2) \cdot \cdots \cdot (a \cdot (p-1)) \cdot 1^{-1} \cdot 2^{-1} \cdot \cdots \cdot (p-1)^{-1} \\ \equiv_p&\ a^{p-1} \cdot 1 \cdot 2 \cdot \cdots \cdot p-1 \cdot 1^{-1} \cdot 2^{-1} \cdot \cdots \cdot (p-1)^{-1} \\ \equiv_p&\ a^{p-1} \cdot 1 \\ \equiv_p&\ a^{p-1} \end{align*}

This result is called Fermat’s Little Theorem to distinguish it from Fermat’s more famous theorem, called Fermat’s Last Theorem, which states that there are no integers $a,b,c$ such that $a^n + b^n = c^n$ for $n \gt 2$. Other than having very similar names, what the two theorems have in common are that Fermat stated them in the mid 1600s but in both cases declined to give proof because the proof was “too long”.

While it would be about 400 years before Fermat’s Last Theorem gets proven (by Andrew Wiles in 1995), Fermat’s Little Theorem was proved only about 100 years later, by Leonhard Euler. The proof that we presented, using modular arithmetic, is due to James Ivory in the early 1800s and a bit later by Dirichlet.

A practical consequence of this theorem is that it allows us to very rapidly simplify congruences on large powers.

Let’s solve the congruence $x^{312} + 6 \equiv 0 \pmod{11}$. First, we note that this is $x^{312} \equiv -6 \equiv 5 \pmod{11}$, so $x \not\equiv 0 \pmod{11}$, and therefore we can apply Fermat’s Little Theorem to reduce the power. Observing that $10 = 11-1$, we see that $312 = 10 \cdot 31 + 2$ by division. This gives us \begin{align*} x^{312} &\equiv 5 & \pmod{11} \\ x^{31 \cdot 10 + 2} &\equiv 5 &\pmod{11} \\ (x^{10})^{31} \cdot x^2 &\equiv 5 &\pmod{11} \\ 1^{31} \cdot x^2 &\equiv 5 &\pmod{11} \\ x^2 &\equiv 5 &\pmod{11} \end{align*} At this point, we cannot simplify any further, so we need to check all squares in $\mathbb Z_{11}$. Luckily, this is straightforward:

$x$ 1 2 3 4 5 6 7 8 9 10
$x^2$ 1 4 9 16 25 36 49 64 91 100
$x^2 \pmod{11}$ 1 4 9 5 3 3 5 9 4 1

This gives us $x \equiv 4, 7 \pmod{11}$.

A note on cryptography

Cryptography is the study of how to transform information and communication so that it’s concealed and secure. The most basic form of cryptography dates back to the classical era, via the use of substitution ciphers. These involve shifts of letters: if your cipher was shifted by 13, then you would map $a \rightarrow n, b \rightarrow o, c \rightarrow p, \dots$ and so forth. Such ciphers are still in use today, but not for secure communications. For example, if you wanted to talk about your favourite currently screening movies and tv shows on social media, one common way to do so is to conceal such spoilers by running it through a ROT13 encoding, which is just a substitution cipher with shift 13 that was just described.

The key to making cryptography work is by ensuring the encoding of the information remains secret. This doesn’t work very well for substitution ciphers because the encoding is very simple. In fact, if you read enough ROT13 spoilers, you can begin to see patterns of how words form. So one aspect of cryptography is ensuring that the key is complex and remains secret. However, this is only half the battle. The other problem that remains is how to communicate about the key.

In Canada, the banks collectively run a system called Interac, which, among other things, makes it very handy to transfer money via email and is why services like Venmo didn’t really catch on. Suppose Alice and Bob, the two famous recurring characters of cryptography, want to transfer some Canadian money. So Alice logs onto her bank’s website and initiates an email transfer that can be deposited by Bob into any bank account he wants once he gets the email. How does this stay secure? Alice will set a password that she communicates to Bob, who will then use the password to verify that he is allowed to accept the email transfer.

Hypothetically, what Alice needs to do is communicate the password to Bob in a secure way. What usually ends up happening is that Alice just emails Bob the password to the same account. This is bad, because if an eavesdropper, like Eve, gets access to Bob’s email, then Bob is, as they say in Canada, hosed, because both the password and the email containing the transfer are sitting in Bob’s email account. All Eve needs to do is use the password and then she can deposit the Canadian dollars into any bank account she wishes.

This highlights a common weakness: even though we may devise an unbreakable cryptographic scheme, if the key for that system is acquired, then we’re screwed. This shifts the problem of secure communication from the message that we originally wanted to send to the problem of how to securely distribute our key.

One way to do this is to make it not a cryptographic problem anymore and do something like send the keys physically. This is what actually happened prior to communication with electronic computers, but situations that demand security, like communications with government agencies or banks may still use mail to send such keys.

The use of a secret key for encryption and decryption is called private-key cryptography. This is also called symmetric-key cryptography. This name hints at the root of our problem and a possible solution: what if we separate the encryption and decryption key?

This leads us to the idea of public-key cryptography, or asymmetric-key cryptography. Here, only the decryption keys are secret, while encryption keys are made public. This way, if Alice wants to send Bob a message that only Bob can read (perhaps containing Alice’s credit card number or something), then Alice encrypts her message with Bob’s public key, sends the encrypted message, and Bob would then decrypt the message.

The key to making this work is that the public and private keys need to be related in such a way that decryption is easy when the private key is known, but difficult when only the public key is known.

RSA

The most famous public-key cryptosystem (and definitely the most popular to teach in elementary number theory classes) is RSA, named for Rivest, Shamir, and Adleman who designed it in 1977 at MIT. RSA is commercially implemented in many Internet communication protocols currently in use and won Rivest, Shamir, and Adleman the Turing Award in 2002.

There are three parts to the system.

  1. Setup. Bob wants to be able to receive encrypted messages. He does the following.
    1. Choose two large, distinct primes $p$ and $q$, and let $n = pq$.
    2. Choose an arbitrary integer $e$ so that $\gcd(e,(p-1)(q-1)) = 1$ and $1 \lt e \lt (p-1)(q-1)$.
    3. Solve $ed \equiv 1 \pmod{(p-1)(q-1)}$.
    4. The public key is $(e,n)$.
    5. The private key is $(d,n)$, and the prime numbers $p$ and $q$.
  2. Encryption. Alice does the following to encrypt a message $M$.
    1. Get Bob’s public key $(e,n)$.
    2. Encrypt the plaintext message $M$ as the ciphertext $C$, $$C \equiv M^e \pmod n.$$
    Then Alice sends $C$ to Bob.
  3. Decryption. Bob receives $C$ from Alice. To decrypt it, he does the following.
    1. Use the private key $(d,n)$ to decrypt $C$ into $R$, $$R \equiv C^d \pmod n.$$
    We claim that $R = M$.

Let $p = 19, q = 37$. Bob chooses $e = 559$.

>>> p, q = 19, 37   # choose some enormous primes
>>> n = p * q
>>> e = 559         # choose an integer up to (p-1)(q-1)
>>> math.gcd(p-1, e), math.gcd(q-1, e)
(1, 1)              # make sure it’s relatively prime
>>> {d for d in range((p-1)*(q-1)) if e*d % ((p-1)*(q-1)) == 1}
{415}               # compute d for ed = 1 mod (p-1)(q-1)
>>> d = 415
>>> M = ord('i')    # message is ‘i’
>>> M
105
>>> C = (M**e) % n  # encrypt
>>> C
561
>>> R = (C**d) % n  # decrypt
>>> R
105

To see that this claim is true, we first recall that we have $$R \equiv C^d \equiv (M^e)^d \equiv M^{ed} \pmod n.$$ Since $ed \equiv 1 \pmod{(p-1)(q-1)}$, by the definitions of congruence and divisibility, we have $$ed = 1+k(p-1)(q-1)$$ for some integer $k$. This gives us $$R \equiv M^{1+k(p-1)(q-1)} \pmod n.$$

Now, we show that $R \equiv M \pmod p$. There are two cases: either $p \mid M$ or $p \nmid M$. In the first case, we have $M \equiv 0 \pmod p$, which gives $$R \equiv 0^{1+k(p-1)(q-1)} \equiv 0 \pmod p$$ and therefore $R \equiv 0 \equiv M \pmod p$. In the second case, $p \nmid M$ implies $\gcd(p,M) = 1$ and therefore, by Fermat’s Little Theorem, $M^{p-1} \equiv 1 \pmod p$. Then we get $$R \equiv M(M^{p-1})^{k(q-1)} \equiv M\cdot 1^{k(q-1)} \equiv M \pmod p.$$ Therefore, $R \equiv M \pmod p$. The same reasoning applies for $q$ to show that $R \equiv M \pmod q$. Since $p$ and $q$ are distinct primes, we must have $\gcd(p,q) = 1$ and so, by the Chinese Remainder Theorem, we can put together the two congruences to get $R \equiv M \pmod{n}$. This confirms that the encryption and decryption operations “work”: Bob gets the same message $M$ out as Alice had put in.

So why is this secure? The publicly available information is $(e,n)$, which means that all an attacker needs is $d$. So how hard is finding $d$ based on $e$ and $n$? Since $d$ is the inverse of $e$ modulo $(p-1)(q-1)$, this means that one needs to find $p$ and $q$ from $n$. This means that if we can factor numbers into prime factors efficiently, then it is possible to recover $d$ efficiently. Unfortunately (or fortunately?) we don’t know how to find prime factors of a number efficiently using classical computers (if we had a quantum computer, it is possible—something the NSA is quite worried about).

This problem of finding prime factors is the problem of finding divisors that we discussed earlier. Older RSA keys range from hundreds of bits to 1024 while modern key sizes are typically 2048 or 4096 bits. If the key size is 4096 bits, then the difference between an $O(n)$ algorithm like our naive divisor search and a $O(\log n)$ algorithm is proportional to the difference between $2^{4096}$ and $4096$. Note that \begin{align*} 2^{4096} = &\ 10443888814131525066917527107166243825799642490473 \\ & \ 83780384233483283953907971557456848826811934997558 \\ & \ 34089010671443926283798757343818579360726323608785 \\ & \ 13652779459569765437099983403615901343837183144280 \\ & \ 70011855946226376318839397712745672334684344586617 \\ & \ 49680790870580370407128404874011860911446797778359 \\ & \ 80290066869389768817877859469056301902609405995794 \\ & \ 53432823469303026696443059025015972399867714215541 \\ & \ 69383555988529148631823791443449673408781187263949 \\ & \ 64751001890413490084170616750936683338505510329720 \\ & \ 88269550769983616369411933015213796825837188091833 \\ & \ 65675122131849284636812555022599830041234478486259 \\ & \ 56744921946170238065059132456108257318353800876086 \\ & \ 22102834270197698202313169017678006675195485079921 \\ & \ 63641937028537512478401490715913545998279051339961 \\ & \ 15517942711068311340905842728842797915548497829543 \\ & \ 23534517065223269061394905987693002122963395687782 \\ & \ 87894844061600741294567491982305057164237715481632 \\ & \ 13806310459029161369267083428564407304478999719017 \\ & \ 81465763473223850267253059899795996090799469201774 \\ & \ 62481771844986745565925017832907047311943316555080 \\ & \ 75682218465717463732968849128195203174570024409266 \\ & \ 16910874148385078411929804522981857338977648103126 \\ & \ 08590300130241346718972667321649151113160292078173 \\ & \ 8033436090243804708340403154190336 \end{align*}

What if we tried a more direct approach, like recovering $M$ from $M^e \bmod n$? In essence, we are talking about finding the $e$th modular root of a number. This is also difficult to do if $n$ is not prime and would still depend on knowing $p$ and $q$. (There are deeper number theoretic reasons for this, having to do with Euler’s $\varphi$ function, which is discussed in Section 9.10 of the textbook)

Sets

We very briefly introduced the idea of sets earlier when discussing modular arithmetic. They were a nice way to describe “collections” of things. However, they are much more than that—modern mathematics happens to be built on the idea that everything is a set. Everything. Functions? Sets. Numbers? Sets. Problems? Sets.

Even before we had formally introduced them, the language of sets has already snuck into our discussions a few times. For instance, we refer to the natural numbers $\mathbb N$ as a set. And when discussing the domain of discourse in logic, we refer to the domain as a set of items.

Recall the following definition.

A set is an unordered collection of objects. If $S$ is a set and $a$ is a member of $S$, then we write $a \in S$, which is read “$a$ is an element of $S$”, or informally as “$a$ is in $S$”. Similarly, if $a$ is not a member of $S$, then we write $a \not \in S$.

Here, the term “objects” is used loosely. Often, we’ll just stick to numbers, but just like our discussion of the domain in logic, these can really be anything: books, trees, other sets, or anything else.

The definitions we’ve seen so far tell us what sets are used for and what we want to know about them. We want to be able to describe collections of things and the main thing we want to know is whether some thing belongs to a particular set or not. This is the membership problem: given an item $x$ and a set $S$, is $x \in S$?

At first, it seems kind of trivial to determine whether something is in a set or not, but we’ll see that because of how we can define sets, this turns out to be kind of an ur-problem—because set theory is so fundamental, you can formulate many mathematical problems as a question of set membership. We’ll see that this has consequences, particularly for computer science.

Note that since sets are unordered, this means that $\{1,2,3\}$ and $\{3,2,1\}$ are the same set. Furthermore, since an element is either a member or not a member of a set, each element occurs in a set at most once. This means that $\{2,1,3,2\}$ is really just $\{1,2,3\}$.

The set $\{\}$ containing no elements is the empty set and is denoted by $\emptyset = \{\}$.

In light of the above remark about objects in sets, note that $\{\emptyset\}$ is not the same as $\emptyset = \{\}$. The set $\{\emptyset\}$ is actually the set containing the empty set, which means it is not empty; it contains one element: the empty set.

The set type in Python is an implementation of mathematical sets. They are indicated using the curly braces, except for {}, which denotes an empty dictionary because both sets and dictionaries are denoted using curly braces. An empty set in Python is denoted by using the constructor explicitly, set().

>>> type({})
dict
>>> type(set())
set

One hitch with Python sets is that the objects that they contain must be hashable. As a consequence, a set cannot contain a set, since sets are mutable. To get around this, Python has the notion of a frozenset, which is an immutable set.

>>> {set()}
Traceback (most recent call last):
  File "", line 1, in 
    {set()}
TypeError: cannot use 'set' as a set element (unhashable type: 'set')
>>> {frozenset()}
{frozenset()}
>>> {frozenset()} == frozenset()
False

In mathematics, objects are immutable. This is one reason for why it can be difficult to reason about programs, particularly imperative programs, which can have notions of state (i.e. memory) that can be changed.

Since we want to be able to describe collections, we need to talk about how to define sets. There are two common ways. First, we can just list the elements of the set, like $\{1, 2, 3\}$. This is easy to do for finite sets. For infinite sets, we can do something like $\{1, 2, 3, \dots\}$ and usually, that’s enough for us to understand that this is the set containing all natural numbers.

Here are some more sets you may have seen before.

Name Symbol Contents
Natural numbers $\mathbb N$ $\{0,1,2,3, \dots\}$
Integers $\mathbb Z$ $\{\dots, -3, -2, -1, 0,1,2,3, \dots\}$
Rational numbers $\mathbb Q$ $\{\frac m n \mid m,n \in \mathbb Z\}$. That is, fractions, like $\frac 4 3, \frac{-16}1, \frac{2}{-23}$.
Real numbers $\mathbb R$ Includes things like $\sqrt 3, \pi, -e, 4, \frac 2 5$.
Complex numbers $\mathbb C$ $\{x + yi \mid x,y \in \mathbb R\}$. Includes things like the imaginary number $i= \sqrt{-1}, 3+27.43234i, -\frac{23}{9}, 45, 3\pi - \frac 7 9 i$.

Here, we introduce some notation for more complicated definitions. We can define sets using comprehensions, also called set-builder notation.

If we wanted to define the set of even natural numbers, we can write something like $\{2,4,6,\dots\}$. Using comprehensions, we can also write $$\{n \in \mathbb N \mid \exists m \in \mathbb N, n = 2 \cdot m \},$$ which says that we want the set of all natural numbers $n$ such that $n$ can be expressed as $2 \cdot m$ for some natural number $m$. That, of course, turns out to be the even natural numbers.

There are some notational issues here you may have noticed. I’ve said before that in logical sentences that we typically don’t write things like $\exists n \in \mathbb Z, a \cdot n = b$, but this seems to be exactly what we did above. This is because we’re not really working in logic anymore—we’re doing set theory. In this context, we do use this shorthand because it’s not as clear what the domain should be and we do have a notion of what sets actually are now.

By the way, this is where the idea of comprehensions in Python come from—notice the syntax is not so different.

{n for n in ℕ if n % 2 == 0}

Obviously, this code doesn’t work because ℕ isn’t anything that’s defined. Of course, you can define your favourite collection as ℕ since Python supports unicode names. There’s also an interesting question of how to represent sets that are infinitely large in Python, which is not straightforward. The answer here is that you’d need to represent such a set in a more complicated way, such as involving an iterator, which is necessarily computational rather than just descriptive.

For example, libraries like SymPy, which do symbolic computation, have implementations and representations of such sets.

>>> from sympy import S
>>> S.Naturals0
Naturals0
>>> type(S.Naturals0)

>>> 3 in S.Naturals0
True
>>> 0 in S.Naturals0
True
>>> -2 in S.Naturals0
False
>>> 21876361109 in S.Naturals0
True

We can do more complicated things with this, since there aren’t very many hard rules about what kinds of conditions we can or cannot place on our sets. For instance, we can define the set $$\{n \in \mathbb N \mid \exists m \in \mathbb N, (2 \cdot m = n) \wedge (\forall k \in \mathbb N, n \neq k^2) \}.$$ Sometimes, we don’t even bother with that level of formality and just write something like $$\{n \in \mathbb N \mid \text{$n$ is even and not a square}\}.$$ This means that we have a lot of power in how we want to define our sets. Something crucial to note here is that definition is not the same as construction—when we define a set, we’re not saying that we know how to construct them. In fact, there are many sets that we can define that we can’t compute (a truth that is at the root of computer science).

In other words, one can think of set theory, like logic, as being about expression. We use set theory to describe certain structures, but this doesn’t necessarily tell us how they’re constructed.

For example, here is a useful set for us to work with.

Let $a$ be an integer. We define the set $\operatorname{Div}(a)$ to be the set of divisors of $a$. That is, $\operatorname{Div}(a) = \{d \in \mathbb Z \mid (d \mid a)\}$.

This set happens to be constructible.

{d for d in range(1,a+1) if a % d == 0}

Consider the set $\operatorname{Div}(6)$. This set contains the divisors of 6, which we can work out easily enough. This means that an equivalent description of the set can be described as $\{1,2,3,6\}$.

>>> div = lambda a: {d for d in range(1,a+1) if a % d == 0}
>>> div(6)
{1, 2, 3, 6}

 

Again, definitions of sets are descriptions. We want the set of divisors of $a$. This description doesn’t tell us how to construct this set.

Consider the set $\{n \in \mathbb N \mid \exists a,b,c \in \mathbb N, a^n + b^n = c^n \wedge a,b,c \gt 0 \wedge n \geq 3 \}$. For hundreds of years, it was not known which elements were members of this set or even whether there was anything in here. This raises a few important points: just because you have a definiton doesn’t mean that it’s easy to tell whether there are any elements that satisfy that definition. Showing that an item is or isn’t a member of a set requires proof.

This means that we can get into trouble if we’re not careful about how we define sets. Bertrand Russell noticed this problem, leading to the following famous example: $$S = \{T \mid T \not \in T\}.$$ If we let something like this happen, then we get to conclude $S \in S \leftrightarrow S \not \in S$, which is very bad if we want mathematics to be consistent (when Russell communicated this to Gottlob Frege, who was trying to formalize mathematics based on set theory, he was quite spooked).

So we can define sets. Recall that the typical question to ask is whether an element is or is not in a set. We can extend this question to talk about how sets are related to one another.

Two sets $A$ and $B$ are equal if and only if they have the same elements. That is, $$A = B \leftrightarrow (\forall x, x \in A \leftrightarrow x \in B).$$

A set $S$ is a subset of $T$, written $S \subseteq T$, when every element of $S$ belongs to $T$. That is, \[S \subseteq T \leftrightarrow \forall x (x \in S \rightarrow x \in T).\] A set $S$ is a proper subset of a set $T$, written $S \subsetneq T$, when $S$ is a subset of $T$ and there exists an element of $T$ which does not belong to $S$.

Consider the sets $A = \{a,c\}$ and $B = \{a,\Box,3,c\}$. We have $A \subseteq A$ and $A \subseteq B$ but $B \not \subseteq A$. Since there is at least one element of $B$ not in $A$ ($\Box$ and $3$), we also have that $A \subsetneq B$ (i.e. $A$ is a proper subset of $B$).

>>> A = {'a', 'c'}
>>> B = {'a', '◻', 3, 'c'}
>>> A, B
({'a', 'c'}, {3, 'a', 'c', '◻'})
>>> A == A
True
>>> A <= B  # <= is for subset
True
>>> B <= A
False
>>> B <= B
True

Here’s a proposition about divisors. Let $a$ and $b$ be integers. Then $a \mid b$ if and only if every divisor of $a$ is a divisor of $b$. We can rephrase this using sets: $a \mid b$ if and only if $\operatorname{Div}(a) \subseteq \operatorname{Div}(b)$.

For instance, it is well known that $6 \mid 24$. Indeed:

>>> div(6) <= div(24)
True

You may notice that sometimes $\subset$ is used for proper subset. This works quite nicely with $\subseteq$ meaning subset. However, we’ll avoid this particular notation because there are many other mathematicians who use $\subset$ to mean (not necessarily a proper) subset.

In this class, we will use $\subseteq$ for subset. If you must, use $\subsetneq$ for proper subset. But I would recommend never relying only on notation for this—it is good practice to mention explicitly when you are considering a proper subset.

From the above, we note that by definition, we have $S \subseteq S$ and if $S = T$, we have $S \subseteq T$ and $T \subseteq S$. This second definition gives us an alternate characterization of two sets that are equal. And if we look at the definitions carefully, they point to a connection between set theory and logic that we’ll explore further.