Is natural selection a tautology, and therefore not truly falsifiable?
I think @Remi.b's answer is great and really the only way to answer your questions is with a comprehensive introduction to evolution. However, I wanted to address the tautology issue more directly.

First, the "survival of the fittest" seems like a tautology with "natural selection" because it is not a description of how natural selection works, rather, it is a phrase meant as a synonym for natural selection, to help describe the result to someone unfamiliar with the phrase.

Let me use an analogy: it would be like if you were a very new learner of English, and I told you "Joe's truck has more mass than an elephant!"

If you aren't really familiar with the term "mass" in English, this phrase could be confusing. So I explain instead that "Joe's truck is heavier than an elephant." If you know the word "heavy" this is easier to understand.

However, there is a tautology there! the car is actually heavier because it has more mass, but that does not make either phrase untrue or untestable: it's just another way of saying the same thing within a context (i.e., those statements are the same if they are exposed to the same gravity).

The testable hypothesis that natural selection makes is that, given 2 things: 1) a population where individuals have traits that give them different chances of survival, and 2) some way for offspring to inherit traits from their parent(s), then the population over time will consist of individuals who are more likely to possess the traits that gave a high chance of survival.

Following this, should the environment change in some way such that a different trait is now beneficial, that trait will increase in prevalence.

There are way too many experiments to summarize here that show 1), 2), and a combination of 1) and 2), as well as experiments that show that indeed, when you have 1) and 2) you get natural selection.