This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

1
vote
1answer
14 views

Cardinality of the Cartesian Product of Two Equinumerous Infinite Sets

Is the cardinality of the Cartesian product of two equinumerous infinite sets the same as the cardinality of any one of the sets? I couldn't find this explicitly stated in any handout or text. This ...
1
vote
4answers
31 views

Use class algebra to prove the following: If A∩B = ∅ and A∪B = C, then A = C-B

I'm having a bit of trouble proving the following. If A∩B = ∅ and A∪B = C, then A = C-B My initial attempt is to prove it directly, however, I believe I'm assuming the consequent, namely, A = C-B, ...
3
votes
1answer
54 views

On the definition of a filter: Isn't $\emptyset$ a subset of any set?

Beginning my study of nonstandard analysis, I have found this definition of a filter U on a set J, where A, B are subsets of J: Proper filter: $\emptyset \not\in U$, Finite intersection property: If ...
2
votes
1answer
18 views

Can it be proved without the axiom of choice that every cardinal is comparable with every finite cardinal?

Can it be proven in ZF, without using the axiom of choice, that every finite set is a universal size comparator, meaning, is comparable with every set in terms of size? And what is the proof?
1
vote
3answers
63 views

Does $A\cap B =\varnothing \Rightarrow B\subseteq \overline{A}$?

How to prove $A\cap B =\varnothing \Rightarrow B\subseteq \overline{A}$? If I going by definitions, there is no $x$ s.t $x\in A$ and $x\in B$. But, what do we can tell about $\overline{A}$? What i'm ...
3
votes
3answers
62 views

Prove that if $\mathcal{F} \subseteq \mathcal{G}$ then $\cup\mathcal{F} \subseteq \cup\mathcal{G}$

Suppose $\mathcal{F}$ and $\mathcal{G}$ are families of sets. Prove that if $\mathcal{F} \subseteq \mathcal{G}$ then $\cup\mathcal{F} \subseteq \cup\mathcal{G}$ My attempt: Given $\mathcal{F} ...
0
votes
1answer
30 views

Can someone present an example of linear ordering less trivial than $A = [1,2,3,4,5,6…]$

A linear ordering (loset) is a poset that also satisfies the trichotomy law. For any $x,y \in A$, we have $x \leq y$ or $y \leq x$ A common example is presented as $A = [1,2,3,4,5,6...]$ Can ...
1
vote
1answer
37 views

How to use Principle of Inclusion-Exclusion here?

A while ago I posted a question: Coloring a Grid. Online, I seem to have stumbled upon a usage of PIE AOPS Wiki Solution AIME II #9. (1) Now, I have experience with PIE, but I do not see how to ...
2
votes
2answers
43 views

Set theory: $A-(B-C)=(A-B)\cup C$.

I'm working through the set theory exercises in Apostol's Calculus Volume 1. I'm down to the last problem: Show that one of the following results is always correct and the other one is sometimes ...
5
votes
2answers
25 views

How many limits of limits are there in $\omega_1$?

We know there are $\omega_1$-many limit ordinals less than $\omega_1$. What about ordinals that are limits of limit ordinals? Are there also $\omega_1$-many of these?
1
vote
1answer
59 views

Can we prove that set of irrational numbers is a set using Zermelo-Fraenkel axioms?

To remove paradoxes of naive set theory, We started with the axioms of Zermelo-Fraenkel and developed a set theory. Where we are building sets starting from a empty set. How to construct set of ...
1
vote
1answer
21 views

Prove that if $\forall A \in \mathcal F (B\subseteq A)$ then $B \subseteq \bigcap \mathcal F $

This is Velleman's exercise 3.3.10. Suppose that $\mathcal F$ is a nonempty family of sets, B is a set, and $\forall A \in \mathcal F (B\subseteq A)$. Prove that $B \subseteq \bigcap \mathcal F $. My ...
0
votes
0answers
86 views

Prove $\{Y: Y \text{ is a subset of } X \}$ is a set. TAO Analysis 1 Ex 3.4.6

The definition of a set I am given is as follows: $\text{ A set is defined as an unordered collection of objects. If x is an object then we say that } $ x $ \text{is an element of A, otherwise x is ...
-1
votes
1answer
48 views

Bijective correspondence between $X$ and $X \cup \{a\}$ for an infinite set $X$ [on hold]

Let $X$ be an infinite set, and $a\notin X$. I need to prove that $|X \cup \{a\}| = |X|$. Preferably using bijective correspondence or Schröder–Bernstein theorem. Thank you.
1
vote
3answers
78 views

How to show that a statement in sets is false?

How to show that a statement in sets is false and prove its negation is true? For example I have the exercise: Let's say that $E$ is a non-empty set and $A,B,C$ $\subseteq$$E$.For each $Α,Β,C$ how ...
2
votes
2answers
52 views

Does anyone know when I would use this symbol ($\supseteqq$) and meaning?

Does anyone know what this symbol means? Where would one use it? Someone recently asked me but I do not know what it means. I have seen it with just one line underneath to denote subset. With an ...
5
votes
2answers
63 views

Proving that $(A\setminus C)\cap(B\setminus C)\cap(A\setminus B)=\emptyset$

For each $A,B,C$ how would I prove that $(A\setminus C)\cap(B\setminus C)\cap(A\setminus B)=\emptyset$ ? My thoughts are if $x\in (A\setminus C)\cap(B\setminus C)\cap(A\setminus B)$, then $x\in ...
2
votes
1answer
21 views

Using addition and subtraction in algebraic proving in set theory

I am trying to prove (using algebraic way) the following statement: A∆B=A iff B=∅ So it goes like this in one direction: A∆B=A A∆B∆A=A∆A (I added ∆A to both sides) B∆A∆A=A∆A (commutativity) B∆∅=∅ ...
3
votes
2answers
65 views

A simple expression to map $\mathbb N^*$ bijectively to $\mathbb N$

Let $\mathbb N = \{ 1,2,3,\ldots \}$, then by the well-known "Cantor"-Scheme we have $\mathbb N \times \mathbb N \cong \mathbb N$. But even nicer is that we can write this scheme $\varphi : \mathbb N ...
1
vote
4answers
48 views

Discrete Maths Set Theory: Prove that $\left|(X^Y)^ Z\right|=\left|X ^{Y \times Z}\right|$.

I need to prove that $(X^Y)^ Z$ and $X ^{Y \times Z}$ are in bijective correspondence. Can anyone please help? EDIT: Chuks's version said: prove that $(X\times Y)\times Z\sim X\times(Y\times Z)$. ...
2
votes
1answer
61 views

There exists a bijection between $(0,1)$, $(0,1]$ and $[0,1]$? [duplicate]

There exists a bijection between $(0,1)$, $(0,1]$ and $[0,1]$? These 3 sets are not countable and since there are all in $\mathbb{R}$ they should have the same number of elements, so my question ...
2
votes
1answer
24 views

Can someone present a visualization of the partitioning of a $L^p$ space into equivalent classes?

I am a bit confused by what it means for a $L^p$ space to be partitioned into equivalent classes instead of functions. I understand that give two or more functions $f$, $g$, $h,\ldots$ of which are ...
3
votes
2answers
43 views

Notation for union / intersection (in the same way $\pm$ stands for plus / minus) - is this a good idea?

Note: $F$ is a class of sets. I was solving a problem in Apostol's Calculus Volume 1. It is to show that $$B-\bigcup_{A\in F} A=\bigcap_{A\in F}(B-A)\qquad\text{ and }\qquad B-\bigcap_{A\in F} ...
0
votes
3answers
42 views

Bogus set theory proof

I'm having trouble figuring out where I went wrong in this proof. I think it's to do with my understanding of things like $\cup$ and $\cap$ in that I don't really have a solid understanding of what ...
2
votes
2answers
49 views

What is $A-B\cup C$ in words?

I'm working through the set theory exercises in Apostol's Calculus Volume 1 and am having some trouble describing $A-(B\cup C)$ in words. What I'm thinking is: If $x\in A-(B\cup C)$ then $x$ is in $A$ ...
1
vote
2answers
71 views

Prove that the Cardinality of $| \Bbb R \times \Bbb Z |$ has the same cardinality of $\Bbb R$

Prove that $| \Bbb R \times \Bbb Z | = |\Bbb R|$ So I know I have to prove that there exists a bijective function between $\Bbb R \times \Bbb Z$ and $\Bbb R$. How I would do that, I don't know. I ...
4
votes
1answer
82 views

Set-theoretic equality

Let $A⊂U^{*},B⊂U.$ Find the set $X⊂U,$ that satisfies the equation. $$(\overline{X \cup A}) \cup (X \cup \overline{A}) =B.$$ My thoughts: $$\begin{align}B&=(\overline{X \cup A}) \cup (X ...
0
votes
3answers
45 views

Why ordered sequences can be reduced to sets?

I am trying to understand why ordered sequences can be reduced to basic sets. I understand most of the following proof: Sequences can be defined as functions Functions are a special case of ...
2
votes
2answers
169 views

Definition for the set of Real Numbers

Could the set of Real Numbers be defined as \begin{array}{l} \mathbb{R} \equiv \mathbb{Q} \cup \{ x\neq \frac{a}{b} :a\wedge b\in \mathbb{Q} \} \end{array} ? Why or why not?
4
votes
3answers
48 views

Discrete math - Set theory - Symmetric difference: Proof for a given number.

I can't find anything on this topic elsewhere. I'd like to know what keywords/sites I should be using to find what I'm looking for if this is to elementry of a question. (been using discrete math, set ...
1
vote
5answers
58 views

Proving that that ${(R \setminus S)\setminus T} \subseteq R \setminus (S \setminus T)$

How might I prove that ${(R \setminus S)\setminus T} \subseteq R \setminus (S \setminus T)$? I am not sure the best place to start other than assuming $x\in(R \setminus S)\setminus T$ and trying to ...
1
vote
1answer
33 views

why this is not transitive yet a reflexive relation?

The relation given is $ R = \{(a,b); 1ab>0; a,b ∈ R \} $ I clearly understand that this is symmetric since $a*b = b*a$ but I'm not able to understand that why is this reflexive also and not at all ...
0
votes
0answers
14 views

Indexed sum of cardinals [duplicate]

Let $\{ \kappa_i | i\in I \}$ be an indexed set of cardinals. We define the sum as: $\sum\limits_{i\in I}\kappa_i = \left\vert \bigcup\limits_{i\in I}X_i \right\vert$, where $\left\vert X_i ...
0
votes
1answer
15 views

Preference relations and the existence of extensions of functions representing them

In a book I found the following question: Let $\succsim$ be a complete preference relation on a nonempty set $X$, and let $\varnothing \neq B \subseteq A \subseteq X$. If $u \in [0,1]^A$ ...
2
votes
2answers
67 views

Prove that $E \cap E^{c} = \varnothing$.

This is a 'simple' question on elementary set theory. I said 'simple' because statement like this is presented all over introductory sections in advanced math books, but they are not really proved in ...
0
votes
1answer
15 views

Draw figures for the 5 different lattices with 5 elements.

I can only think of 4 lattices. Those are: a 1-1-1-1-1 (a chain), a 1-3-1, a 1-1-2-1 and a 1-2-1-1 (if this notation isn't clear, I'll provide images). I really can't figure out what the 5th lattice ...
3
votes
1answer
30 views

The set $T=\{l\in\mathbb{N}: ml=nl \ \text{implies} \ m=n \}$ is inductive.

I'm trying to prove the following statement: $ml=nl$ implies $m=n$ for every $m,n,l\in \mathbb{N}$. So I defined the set $T=\{l\in\mathbb{N}: ml=nl \ \text{implies} \ m=n \}$ and if I prove that ...
1
vote
2answers
35 views

Predicate logic inference in a simple proof of uniform continuity.

For a function $f$ from a metric space $X$ into a metric space $Y$, uniform continuity can defined in this way: $\forall ε>0:\existsδ > 0:\forall p,q\in X:d_{X}(p,q)<δ \rightarrow ...
-6
votes
0answers
24 views

Bijection of finite and infinite sets [closed]

Prove that a nonempty set T1 is finite if and only if there is a bijection from T1 onto a finite set T2.
1
vote
3answers
73 views

Suppose $A\subseteq \mathscr P (A)$. Prove that $ \mathscr P (A)\subseteq \mathscr P ( \mathscr P (A))$

This is Velleman's exercise 3.3.4. Suppose $A\subseteq \mathscr P (A)$. Prove that $ \mathscr P (A)\subseteq \mathscr P ( \mathscr P (A))$. I started reexpressing the terms in their equivalent forms ...
2
votes
1answer
47 views

How to Prove It Exercise 7.2.5

Prove that ${}^{\mathbb{Z}^+} \mathcal{P}(\mathbb{Z}^+) \sim \mathcal{P}(\mathbb{Z}^+)$ where ${}^A B$ means the set of all functions $f:A \rightarrow B$ and $\mathcal{P}(A)$ is the power set of $A$. ...
1
vote
2answers
44 views

counterexample in relations of sets

Suppose $R$ is a relation from $A$ to $B$ and $S$ and $T$ are relations from $B$ to $C$. Can anyone produce a counterexample to $(S \setminus T)◦R⊆(S◦R) \setminus (T◦R)$?
1
vote
3answers
54 views

Union of sets proof

Prove that $\{3t\}\cup\{3t+1\}\cup\{3t+2\}=\Bbb Z$, where $t$ is in the set of integers. It makes sense that you can get every integer from this Union of sets but how would you prove something like ...
3
votes
2answers
131 views

The set of all real functions of a real variable

How can I prove that the set of all real functions of a real variable, or even that the set of functions that take only the values 0 and 1, more than the continuum? I have one idea, but ...
-1
votes
1answer
30 views

Determining sets using basic operations

Let A={ O, {O}, 1, a, cat, {1, a, cat}} where O has been used to represent the null set. Determine the follwing: (a) A \ {a, b, c} = {O,{O}, 1, cat, {1, a, cat}} (b) AU{X}= {O,{O}, 1, a, cat, {1, a, ...
0
votes
2answers
40 views

Cardinality of a set containing sets

I've just started learning basic set theory and am puzzled by this question I came up with: What is the cardinality of {1, {2,3}}? Do I treat sets within sets as just one element and so the answer ...
3
votes
4answers
99 views

$S$ and $T$ are two sets. Prove that if $|S-T|=|T-S|$, then $|S|=|T|$.

Here is the problem that I am currently working on: $S$ and $T$ are two sets. Prove that if $|S-T|=|T-S|$, then $|S|=|T|$. I have access to the answer for this proof, and wanted help with the first ...
4
votes
1answer
49 views

Cardinality of a set of natural sequences

Let $a=(a_n)_{n\ge 1}$ a sequence such that for every $n\ge 1$ we have: a) $a_n \in\mathbb{N}$ b) $a_n\lt a_{n+1}$ c) Exists $\displaystyle\lim_{n\to \infty} \frac{\#\{j\mid a_j\le n\}}{n}$ Let ...
1
vote
1answer
45 views

Set-builder Notation

In set-builder notation we describe a set in the following way: $A=\left\{x:\phi (x)\right\}$ Is it correct to say the following? Fix any $x_{0}\in X$ Evaluate the predicate $\phi(x_{0})$ ...
0
votes
2answers
31 views

Totally ordered $\sigma$-algebras

I know that every $\sigma$-algebra is partially ordered with respect to the inclusion operator $\subset$. However, it seems as though every $\sigma$-algebra should be totally ordered with respect to ...